LeetCode刷题笔记（七）

算法
Word count: 5.3k   |   Reading time≈ 20 min

206. 反转链表

这个题其实已经做过多次了，这次总结一下：

题目要求：给出一个链表的头节点，请反转整个链表，并且返回反转后的链表的头节点。

这个题用递归的方法简直是非常之妙，而且十分经典。

1
2
3
4
5
6
7
8
9
10
11
12
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverse(self, head: ListNode) -> ListNone:
        if not head or not head.next: return head
        last = self.reverse(head.next)
        head.next.next = head
        head.next = None
        return last

这个做法简直非常精妙，充分体现了递归方法中的关键：

1）找一个最简问题，解决它

2）充分理解并相信函数能解决你的问题

92. 反转链表 II

这道题要求的是 反转链表中的某一部分

比如给出 head，left，right，请反转从 left 到 right 的部分

img

根据前面做过的反转链表，这里的思路大概有两种：

  1. 先反转 left 到 末尾，再反转 right 到末尾；但是这种方法仔细一想就是不可能的，因为第一次反转之后，末尾的元素到前面来了，要想再把它们翻转回去是不可能的。
  2. 只翻转 left 到 right 的部分，然后再拼接起来。

第2种方法是可行的，但是需要考虑的问题有：

  1. 要记录 left 的前一个节点 pre
  2. 要记录 right 的后一个节点 succ（successor）
  3. pre 的 next 指向反转后的头节点
  4. 反转后的尾节点的 next 指向 succ

可见是一个比较复杂的问题，应该怎么处理呢

官方题解

分为7个步骤：

1）在头节点前添加哑节点防止头节点变化，哑节点不能动

2）创建一个移动节点寻找左节点的上一个节点，其实也就找到了左节点

3）再创建一个移动节点到右节点，其实也就找到了右节点的下一个节点

4）截断中间部分

5）反转中间部分（用一个无返回值的函数进行操作）

6）重接中间部分

7）返回哑节点的下一个节点

我的题解：官方解法-python复现

84. 柱状图中的最大的矩形

问题描述：

给出一个柱形图（数组），数组中的元素表示柱的高度，现在需要在柱形图中找出一个能画出的最大的矩形，比如：

img

先从暴力解法——枚举开始。

（1）枚举宽度【左右边界】

  1. 左边界从0开始遍历
  2. 右边界从左边界开始遍历
  3. 高度取从左边界到右边界区间最矮高度
  4. 计算面积，记录最大面积

这样一看，这个题的暴力方法其实也是很规矩的。

缺点是：时间复杂度在 O(N^2)，因为有循环套循环，而且占用内存也不小。

（2）枚举高度

这种方法的思想是先找定一个高度点，然后左右扩展确定边界【边界的特征是两边的高度将小于边界的高度】，最后计算出面积。

也就是扩展左右的柱子，高度均不能小于 h。

这个方法其实就是在找能够覆盖第 i 个柱子的最大矩形，可以参考：84. 柱状图中最大的矩形/C++

题目有一些特点：

  1. 借鉴枚举高度的方法，我们应该找到左右两侧 最近的 高度小于 h 的柱子。

  2. 一个结论和思想：

    1. 如果两根柱子：j0 < j1，height[j0]>height[j1]
    2. 那么对于 j1 之后的柱子，j0一定不是 最近的 小于 柱子高度的柱子。【至于高度大于它的，其实不重要】

第一个特点说明，我们要找的就是比当前柱子小的最近的柱子，包括左边和右边；

第二个特点说明，当我们找到这个最近的之后，远处的其实不重要了，比这个高的也不重要了【就可以删除了】

所以使用了 单调栈这样一个思路去求解这个问题

使用单调栈：

我个人觉得这篇题解讲的很好：暴力解法、栈（单调栈、哨兵技巧）

它讲明白了一件事情，就是栈顶元素删除之前做了什么：

  • 其实直到我们找到一个比较短的柱子时，我们才知道以上一个值为高度的矩形到这里结束了，一个面积就求出来了
  • 然后后面的高度就会以现在这个短的为基准了

总结一下，我们是怎么确定一个柱形的面积的：

  • 我们记录了下标，下标对应的高度
  • 当我们发现这个下标比上一个下标矮的时候，好了，说明上一个下标对应的高度的矩形到头了，可以计算了
  • 而上一个下标对应的高度的矩形，其实还要找一下左边界，什么时候左边界也比它小了，这个区间找到了，这个高度的矩形面积可以算了，这个高度就完全结束了

上面说的这个过程可能需要 进行多次，直到左边没有高度 小于 当前的高度了

这个过程中，缓存数据是从左往右的，计算结果是从右往左的，所以就是后进的先出，这样的数据结构就是栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 先求一下总长度
        n = len(heights)
        # 这是结果，记录面积
        area = 0
        # 这个栈用来做单调栈，栈是用来记位置的，而不是记高度的
        stack = []
        
        # 对数组一次遍历
        for i in range(n):
            # 遇到了下降的情况，开始出栈和计算了
            while len(stack) > 0 and heights[i] < heights[stack[-1]]:
                # 出栈，要计算面积了
                cur_height = heights[stack.pop()]
                
                # 这个是？保证绝对单调吗？
                while len(stack) > 0 and cur_height == heights[stack[-1]]:
                    stack.pop()
            
                if len(stack) > 0:
                    # 栈没有空，那么左右边界求一下
                    cur_width = i - stack[-1] - 1
                else:
                    # 栈空了，那就是全长
                    cur_width = i
                # 计算面积
                area = max(area, cur_height * cur_width)
            # 这是新的高度（可能是更高的，也可能是栈操作了一遍之后新加的高度）
            stack.append(i)
            
        # 数组遍历结束了，但是栈可能还没有清空
        while len(stack) > 0 is not None:
            cur_height = heights[stack.pop()]
            while len(stack) > 0 and cur_height == heights[stack[-1]]:
                stack.pop()
            
            if len(stack) > 0:
                # 因为数组已经遍历结束了，这里留下来的高度就是从记录位置到尾部的了
                cur_width = n - stack[-1] - 1
            else:
                cur_width = n
            area = max(area, cur_height * cur_width)
            
       	return area

上面这种方法做了分类讨论：

  • 弹栈的时候，栈有可能是空的
  • 遍历完成后，栈里还有元素

解决方法：【哨兵方法】Sentinel

  • 数组两端加上两个 0：只要比 1 严格小就可以了
    • 左边的哨兵一定比数组中所有元素都小，绝对不会出栈
    • 右边的哨兵一定比数组中所有元素都小，会让所有元素都出栈（除了左边的哨兵）
  • 这样就可以不用分类讨论了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        area = 0
        heights = [0] + heights + [0]
        # 先向栈中放入哨兵
        stack = [0]
        n += 2
        
        for i in range(1, n):
            while heights[i] < heights[stack[-1]]:
                cur_height = heights[stack.pop()]
                cur_width = i - stack[-1] -1
                area = max(area, cur_height * cur_width)
            # 下面这一句为什么是在 while循环外的？
            # 这个地方不要担心 i 不满足要求，因为如果不满足要求，过不了上面的while循环
            stack.append(i)
        return area

居然一下子简洁了这么多，哨兵的作用真的很厉害

python 实现栈的方法其实就是 list，栈顶就是 list 尾部

我想起有一个收集雨水的问题，其实有一定的联系，都是单调栈的问题

单调栈问题：739、469、42

1603. 设计停车系统

题目描述：

  1. 告诉了三种车位的数量：大、中、小车位各有几个
  2. 然后告诉车的类型：大、中、小车辆

最后，问每辆车是不是有位置停，返回布尔值

而且这个问题就是先到先得，车位满了后面的就是 false

最简单的想法，直接3个 if 进行判断

稍微好一点的方法，可以使用一个哈希表进行3种车位的存储，这样搜索起来也比较快：内存消耗少了一点点，用时居然还是很高

20. 有效的括号

描述：

数学中，括号是成对出现的，而且括号应该是 由内向外完整嵌套的，比如：

{[()]} 就是有效的

{[}]) 方括号位置不对，圆括号少了一半就是无效的

现在就是给一个全是括号的字符串，检测是不是有效的

这个题曾经看过了题解，记下了一个重要的方法：哈希表

用 左括号 做 key，右括号 做value

我自己想出以下步骤：

  1. 遍历字符串
    1. 如果是左括号
      1. 新建一个 need 列表存储 需要的右括号
    2. 如果是右括号，看是不是 need 中最后一个（最新需要的）右括号
      1. 如果是，need 中最新的右括号扔掉【其实就是栈啊】
      2. 如果不是，直接 False
  2. 最后看 need 是不是空的
    1. 如果是，返回 True
    2. 如果不是，返回 False

其中几个细节点：

  1. 怎么样检查是不是左括号？
    1. 方法一，需要一个左括号的列表
    2. 方法二，检查 括号是不是字典的一个 key：if xxx in dict.keys():

5. 最长回文子串问题

问题描述：

给一个字符串，请返回该字符串中最长的回文子串（串，应该是连续的）

首先想到暴力解法：

枚举所有可能的字符串（的左右两边）

然后判断这个子串是不是回文的，并记录最长的回文子串

我的写法超时了，最大问题在于怎么判断是不是回文的，如果对于每一个可疑的子串都采用双指针的方法进行判断，那么肯定会超时，所以才需要用算法

方法一：动态规划

从大的角度讲，枚举所有可能的子串是必要的，这个复杂度可能少不了

但是

  1. 判断回文串的方法可以采用动态规划方法，如果 [i+1, j-1] 的子串是回文串，那么[i, j] 且 s[i]==s[j]的子串就是一个回文串，这样的判断方法比每一次都用双指针要好得多；
  2. 怎么样知道 [i+1, j-1] 的子串是不是回文串呢，这里就需要记录一定的信息了，怎么样既能记录开头，也能记录结尾，还能记录是不是回文串呢？二维数组

注意两种情况：

  1. [i, i] 一定是回文的
  2. [i, i+1] 是不是回文的，要看 s[i] 和 s[i+1] 是不是相等

官方解答中使用的遍历方法是按照 子串长度 和 起始位置 进行枚举，这种方法确实可以实现枚举，而且优点是对同一个长度的子串，可以使用一个简单的判断条件进行排除

方法二：中心扩展

这个方法很有意思

回文串有两种：奇数形和偶数形

奇数形的中心应该是 s[i] == s[i]

偶数形的中心应该是 s[i] == s[i+1]

然后所有的回文串都是有这样的中心的，并且应该根据这个中心向两边进行扩展，所以我们的步骤就是：

  1. 枚举中心，并检查奇数形和偶数形两种可能
  2. 向两边进行扩展，直到出现不对称的情况
  3. 返回最长长度

这个方法其实时间复杂度还是 O(n^2)，因为少不了要向两边进行扩展

但是这个思路可能比较清晰

细节一：原字符串长度为1

按照第二个思路进行尝试，部分错误，案例为：a ，结果输出为空

问题还是没有对一个字母，或者一个数字的情况做很好的处理

我的错误方法是：

1
2
3
4
5
n = len(s)
for i in range(n):
    ...
    ans = s[elft, right]
return ans

这样导致一个问题就是，如果 n = 1，那么会直接跳过循环遍历，直接把空的 ans 导出了

官方的方法是：

1
2
3
4
start, end = 0, 0
for i in range(len(s)):
    修改 start, end 的值
return s[start: end+1]

其实主要还是最后一句的功劳，就是把0，0的情况也考虑在内了

可以对我的方法进行一点点修改，保证不是空的就可以了

return s[0] if not ans else ans

细节二：索引相减 和 字符串长度不一定相等

right - left 和 len() 不是相等的，差了1

所以应该要 right-left == len(ans)-1

但是如果要更新 ans 结果子串的时候，又应该是 ans = s[left:right+1]以免 right 字符没有加入到子串当中

10. 正则表达式匹配

输入：

两个字符串，s - 要匹配的字符串，p-正则表达式

正则表达式中会有三种值：

  • 字母，直接匹配，必须相等
  • . 匹配任意一个单个字符
  • * 匹配任意个前面的一个元素

需要返回的是，是否能够进行匹配

这个题的关键难点在 .* 表示可以匹配任意多个任意字符

如果正则表达式中这两个后面还有字符呢，那就会非常棘手

这类问题之前其实也有，就是有多种可能性的问题 —— 动态规划

这道题做动态规划，最难的一点是怎么样把问题思考全面，还有就是初始化非常容易出错

动态规划思路：

  1. p[j] == s[i] ，最方便，dp[i][j] = dp[i-1][j-1]
  2. p[j] == '.'，也还可以，dp[i][j] = dp[i-1][j-1]
  3. p[j] == '*'，比较麻烦，需要分两种情况
    1. p[j-1] != s[i]，那么就是说 * 前面的字母也不匹配，那么直接dp[i][j] = dp[i][j-2]
    2. p[j-1] == '.'或p[j-1] == s[i]，那么就要考虑匹配多少的问题呢，有两种情况，匹配了很多，或者一个都没有匹配==【这里给出了一个很好的例子，比如 “###b”和“###b*”】==
      1. 匹配了很多 dp[i][j] = dp[i-1][j]
      2. 一个都没有匹配 dp[i][j] = dp[i][j-2]
      3. 以上两种情况，只要出现一种就可以了，所以是 or 的关系

初始化问题：

  1. 如果全部初始化为 False，那么不管怎么变，最后都是 False，所以一定要有Ture，但是又不能直接判断出某一个是True，所以方法有在 s 和 p 前面都加一个空格，然后定义第一个 dp[0][0]=True
  2. dp矩阵是个二维矩阵，到底需要多大？而且它的索引又会和s和p的索引相关
  3. 如果 p 字符串并不能覆盖 s字符串呢？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m = len(s)
        n = len(p)
        dp = [[False] * (n+1) for _ in range(m+1)]
        dp[0][0] = True
        
        for j in range(1, n+1):
            if p[j-1] =='*': dp[0][j] = dp[0][j-2]

        # i 指针，在 s 上滑动
        for i in range(1, m+1):
            r = i - 1
            for j in range(1, n+1):
                c = j - 1
                if p[c] == s[r] or p[c] == '.':
                    dp[i][j] = dp[i-1][j-1]
                elif p[c] == '*':
                    if p[c-1] == s[r] or p[c-1] == '.':
                        dp[i][j] = dp[i-1][j] or dp[i][j-2]
                    else:
                        dp[i][j] = dp[i][j-2]
        return dp[m][n]

最后参考内容：

https://leetcode-cn.com/problems/regular-expression-matching/solution/shou-hui-tu-jie-wo-tai-nan-liao-by-hyj8/

11. 盛水最多的容器

是接雨水问题、柱状图中最大矩形问题的前序问题

这个相对比较简单一点

两个柱子之间有阻挡也没有关系

用双指针-左右指针进行收缩

如果左边高度比较低，就移动左边指针

如果右边高度比较低，就移动右边指针

但是这道题的耗时有点离谱，大家都是怎么刷时间的

34. 在排序数组中查找元素的第一个和最后一个位置 - 二分法

数组是有序的，给定一个target

查找 target 在数组中的位置

这个题其实是看过算法的，但是二分法就是 细节魔鬼！

有一个非常好的题解：34.【朴实无华的二分查找】咱们一步一步来！

这篇文章中的思路非常好，在不会跑的时候，就先用走的。

二分法在本问题中的应用是：

  1. 找到target的左边界
  2. 找到target的右边界

整个流程是：

  1. 找到target在区间中的左右边界：用二分法
  2. 对左右边界进行判断，决定最后输出情况

核心：怎样找到 target 的左右边界，注意细节

找左边界：

  1. left 取开头，right 取结尾，先把左边界的原始值设置为-2，如果根本就不需要进行下面的判断，左边界将为-2
  2. 循环，条件是 left <= right
    1. 二分法，找中间位置 mid
    2. 如果 mid 位置数值 小于 target【说明左边界在 mid 的右边】，那就
      1. left 换到 mid+1 的位置
    3. 如果 mid 位置数值 大于等于 target【说明左边界在 mid 的左边，但是具体在哪还不确定】
      1. right 换到 mid-1 的位置
      2. 把 左边界 也移到 right 的位置

找右边界：【虽说左边和右边可以类比，但是细节真的还是不太一样】

  1. left 取开头，right 取结尾，先把右边界的原始值设置为-2，如果根本就不需要进行下面的判断，右边界将为-2【这一步基本相同】
  2. 循环，条件是 left <= right
    1. 二分法，找中间位置 mid
    2. 如果 mid 位置数值 大于 target【说明右边界在 mid 的左边】
      1. right = mid - 1
    3. 如果 mid 位置数值 小于等于 target【说明左边界在 mid 的右边，但是具体在哪还不确定】
      1. 先把left移过去，缩小区间，left = mid + 1
      2. 把右边界也移过去，rightBorder = left

上面两个过程就把寻找左右边界的工作走完了，这样也比较清晰，但是里面到底是什么时候修改 left 或者 right，什么时候记录左右边界值，其实还是需要一点讲究的，需要注意一下！

接下来是判断，会有几种情况：

  1. 最简单的肯定是有target，那么左右边界之间应该是不太一样的，返回 [leftBorder+1, rightBorder-1]
  2. 如果全部比 target 大，或者全部比 target 小呢？这个时候肯定会有一侧的边界为-2，就是没有变化过，所以也可以进行得出了【-1， -1】
  3. 其他情况，【-1， -1】

可能最不容易判断的情况是 [1], target=1的情况，其实这个时候，leftBorder为-1，rightBorder为2，所以是可以得出结论的【0，0】

804. 唯一摩尔斯密码词

这个问题是说，给了一个写有多个词的 list

根据摩尔斯密码分别进行转化，然后判断这些词的摩尔斯密码中有没有相同的

返回的是不相同的摩尔斯密码的数量

补充知识：

python 与 ASCII码

这道题给的是小写字母

密码本也是一个list，怎么样进行检索

小写字母的 ASCII 码是 97-122

大写字母的 ASCII 码是 65-90

数字的 ASCII 码是 48-57

可以使用 ord(str) 函数将字符转换为相应的 ASCII 码

还可以使用 chr(int) 将 ASCII 码转换为相应的字符

还可以直接使用 ord(x) - ord('a') ，这样即使不知道 a 的ASCII 码是多少也可以进行使用

第一步，获得所有单词的摩尔斯密码串：

本题使用就这样使用

ord(str)-97 就是这个小写字母在密码本中的索引值了

获得摩尔斯密码串是比较容易的

第二步，分析这些密码穿是不是又重复的：

  • 我用了 set() 集合，主要是存储和查询
  • 官方用了哈希表进行存储，其实差不多

再补充知识：

python中的集合

创建一个集合，可以用

B = {a, b, 'c'} 这样的形式

但是如果创建 空集合，必须是 A = set()， 如果是 {} 就成了创建空的字典了

增加元素：add

将元素拆分成一个一个字符再添加进集合：update

删除某个元素：

  • remove，不存在会报错
  • discard， 不存在也不报错
  • pop，删除并返回【注意是任意元素】
  • clear，清空集合

集合与集合之间可以进行数学运算：交并包含等关系

本期十题就到这里，接下来将会主攻 LeetCode Hot 100 问题！

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 Sun Yue

请我喝杯咖啡吧~

支付宝
微信