Giter VIP home page Giter VIP logo

leetcode-python3-hot100's Introduction

【leetcode】刷题记录 python实现 🔥hot100+简单题顺序做

备注:
  • 每个题解包含含题目、解题思路、python3程序、问题思考与解答
  • 🟢表示”简单题“,🟡表示”中等题“,🔴表示”困难题“

🆕最新消息

  • 2023年8月16日:上传了前6题的题解

  • 2023年8月17日:

  • 2023年8月22日:

    • 复习0042接雨水的题解
    • 之后的题解主要参考算法小抄中的**进行重述,加深印象
    • 做了美团20数据岗笔试题寻找最高的山峰
    • 滑动窗口开篇,晚上看了算法小抄
  • 2023年8月23日:

    • 做了滑动窗口0003最长无重复字串
    • 更新了题解但是没怎看懂
    • 体会:以后每天先一个简单题+一个hot100,要不要没自信了QAQ
  • 2023年8月24日:

    • 早上研读了算法小抄中关于滑动窗口的解说
    • 更新了0009回文数的题解
    • 调整项目目录格式
    • 新增 收获
    • 更新了0438_找到字符串中所有字母异位词的题解
  • 2023年8月29日:

    • 更新了0013_罗马数字转整数的题解
    • 总结了滑动窗口解题模板,还需进一步理解
  • 2023年8月30日:

    • 更新了0014_最长公共前缀的题解
    • 更新了0560_和为K的子数组的题解
  • 2023年8月30日:

    • 更新了0020_有效的括号的题解
    • 滑动窗口最大值问题没有搞明白
    • 计划总结括号相关问题的题解

hot100刷题记录

hot100序 题解链接 解法 考察知识 难度 总序 收获
01 两数之和 1.暴力循环``2.哈希表 哈希 🟢 0001
02 字母异位词分组 1.排序``2.计数 哈希 🟡 0049
03 最长连续序列 1.哈希表 哈希 🟡 0128
04 移动零 1.冒泡排序(超时)``2.快慢指针 指针 🟢 0283
05 盛水最多的容器 1.对撞指针``2.暴力循环(超时) 指针 🟡 0011
06 三数之和 1.对撞指针 指针 🟡 0015
07 接雨水 1.单调栈``2.韦恩图 指针 🔴 0042
08 无重复最长字串 1.哈希表 <br>2.滑动窗口 <br>3.快慢指针 滑动窗口 🟡 0003
09 找到字符串中所有字母异位词 1.哈希表 <br>2.滑动窗口 <br>3.快慢指针 滑动窗口 🟡 0438 1.总结滑动窗口解题模板
10 和为K的子数组 1.哈希表 <br>2.前缀和 <br> 字串 🟡 0560 1.定义默认字典a=collections.defaultdict(int)<br>2.前缀和

每天一个简单题

刷题序 题解链接 解法 考察知识 总序 收获
01 回文数 1.数学运算进行整数反转``2.转回字符串进行切片反转 数学 0009 1.取余 %<br>2.字符串切片反转s [::-1]
02 罗马数字转整数 1.哈希表存值,指针遍历累加 字符串、指针、哈希表 0023 1.给定字符串s可以直接取 s[0]<br>2.字符串切片反转s [::-1]
03 最长公共前缀 1.纵向遍历 <br>2.巧用max/min(字符数组)按字典排序 字符数组 0014 1.max/min(字符数组)按字典排序
04 有效的括号 1.栈 <br> 哈希表、栈 0014 1.使用栈进行括号关系判断 <br>2.使用哈希表记录左右括号的关系 <br>3.总结括号相关的问题的解法

📒模板总结

ACM模式

import sys

# 这里写解决问题的代码,和LeetCode就完全一样了
def solve(arr):
	pass

if __name__ == '__main__':

	# 接收输入的逻辑,这里先把输入接收过来, 两种选择input()和sys.stdin.readline()
	group_nums = input()   #字符串形式,得转成int

	group_nums = int(group_nums)

	# 对于每一组
	for i in range(group_nums):
		# 接收每一组的输入, 这里不同的题目就不一样了,但一定记住我们接收的还是一行,这是一个字符串
		arr = sys.stdin.readline().strip().split(' ')
		# 元素转成int
		arr = list(map(int, arr))

		# 输入接收过来之后,这里最好打印下看看接收的是不是正确,这个很重要
		# print(arr)

		# 处理具体的问题了
		res = solve(arr)

		# 输出结果
		print(res)

滑动窗口

参考:我写了首诗,把滑动窗口算法算法变成了默写题 | labuladong 的算法小抄

相关题目

LeetCode 力扣 难度
3. Longest Substring Without Repeating Characters 3. 无重复字符的最长子串 🟡
438. Find All Anagrams in a String 438. 找到字符串中所有字母异位词 🟡
567. Permutation in String 567. 字符串的排列 🟡
76. Minimum Window Substring 76. 最小覆盖子串 🔴
- 剑指 Offer 48. 最长不含重复字符的子字符串 🟡
- 剑指 Offer II 014. 字符串中的变位词 🟠
- 剑指 Offer II 015. 字符串中的所有变位词 🟡
- 剑指 Offer II 016. 不含重复字符的最长子字符串 🟡
- 剑指 Offer II 017. 含有所有字符的最短字符串 🔴

答题模板

这个算法技巧的思路非常简单,就是维护一个窗口,不断滑动,然后更新答案么。LeetCode 上有起码 10 道运用滑动窗口算法的题目,难度都是中等和困难。该算法的大致逻辑如下:

left = 0, right = 0
while left < right && right < len(s):
    # 增大窗口
  
    while window need shrink:
        # 缩小窗口

以找到字符串中的所有字母异位词为例,详细的答题模板如下:

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # 用合适的数据结构记录窗口中的数据,一般是哈希表,此处以哈希表为例
        # 初始化目标字符串与滑动窗口的哈希表,字符做键,字符个数做值
        need, window = defaultdict(int), defaultdict(int)
        # 将给定字符串的属性赋值到已经初始化好的哈希表中
        for c in p:
            need[c] += 1
        # 初始化快慢指针与返回值
        left, right = 0, 0 
        res = []
        '''初始化覆盖程度【本题用】
        valid = 0
        '''

        # 判断是否还需要进行窗口滑动
        while right < len(s):
            c = s[right] # c是要加进窗口的字符
            right += 1 # 扩大窗口
            '''进行窗口内一系列数据的更新
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            '''
            # 判断左侧窗口是否需要收缩(left < right and window needs shrink(这里是窗口的长度大于给定p的长度))
            while right - left >= len(p):
                '''当串口符合条件时,将起始索引加入res【本题用】
                if valid == len(need):
                    res.append(left)
                '''
                d = s[left] # d是将移出窗口的字符
                left += 1 # 增大左指针进行窗口收缩
                '''进行窗口内一系列数据的更新
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                window[d] -= 1
                '''
        return res

应用示例

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # 初始化目标字符串与滑动窗口的哈希表,字符做键,字符个数做值
        need, window = defaultdict(int), defaultdict(int)
        # 将给定字符串的属性赋值到已经初始化好的哈希表中
        for c in p:
            need[c] += 1
        # 初始化快慢指针,覆盖程度与返回值
        left, right = 0, 0 
        valid = 0
        res = []

        # 判断是否还需要进行窗口滑动
        while right < len(s):
            c = s[right] # c是要加进窗口的字符
            right += 1 # 扩大窗口
            # 进行窗口内一系列数据的更新
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            # 判断左侧窗口是否需要收缩(窗口的长度大于给定p的长度)
            while right - left >= len(p):
                #  当串口符合条件时,将起始索引加入res
                if valid == len(need):
                    res.append(left)
                d = s[left] # d是将移出窗口的字符
                left += 1 # 增大左指针进行窗口收缩
                # 进行窗口内一系列数据的更新
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                window[d] -= 1

        return res

思考:为什么这里不能交换位置?

image-20230829175714763

单调队列结构解决滑动窗口问题

参考:单调队列结构解决滑动窗口问题 | labuladong 的算法小抄

应用示例

leetcode-python3-hot100's People

Contributors

lgy0404 avatar

Stargazers

 avatar  avatar 努力学习者 avatar momopusheen avatar  avatar Licca avatar  avatar LiGaOg avatar  avatar  avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.