21天算法挑战总结

写个冒泡排序就可以通过面试笔试的时代早已经过去，技术岗对于算法的掌握要求越来越高。最近三周参加了算法挑战，题目算是一边copy一边囫囵吞枣地给做完了。这就导致当再一次遇到类似的题目甚至是原题时，也难以在短时间内解决掉，只有总结归纳才能得到更好地提升。

Day 1 双指针技巧：原地修改数组

对于数组来说，在尾部插入、删除元素的时间复杂度为O(1)，但是在数组的前部进行操作（例如头部或者中间），就会涉及到操作位置后部的元素的搬迁问题，时间复杂度为O(N)。

如何将复杂度给降下来，对数组进行原地修改，是我们所要优化的问题。

下面直接给出题目，举实际例子进行分析：

leetcode 26题

这道题的输入示例如下：

题目的意思相当于把数组中重复的元素给过滤掉，并且不考虑数组中超出新长度后面的元素，那么直接对 nums[:newlength]进行操作就好了。
考虑双指针的方法，该方法的核心思路在于丢一个fast指针在前面探路，符合条件的就加入到slow的位置。对于这道题，fast指针，便是判断元素是否重复，至于具体如何操作，fast不管，只是一个劲往前冲。
代码如下：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 先进行特例的判断，如果nums本身没有，直接返回零
        if not nums: return 0
        # 对slow，fast指针初始化，size用来确定循环结束条件
        slow, fast, size = 0, 0, len(nums)
        # fast指针走到尾部，循环截至
        while fast < size:
            # 因为数组已经是排好序的，重复的元素一定是紧挨着
            # 所以能够这样判断
            if nums[slow] != nums[fast]:
                slow += 1
                # 在slow位置上赋值为nums[fast]
                nums[slow] = nums[fast]
            # fast一直往前冲
            fast += 1
        # 返回长度
        return slow + 1

该题还有相应的拓展

leetcode 80题

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 初始化slow，fast指针（从2开始）
        slow, fast = 2, 2
        size = len(nums)
        # 对特殊情况予以处理
        if size <= 2:
            return size
        # 循环的边界确定
        while fast < size:  
            # 当fast指针指向的元素，与当前slow位置的前两个元素不同时
            # 更新nums[slow]的元素          
            if  nums[slow - 2] != nums[fast]:
                nums[slow] = nums[fast]
                # 更新slow指针
                slow += 1
            # fast每一轮是必须要更新的
            fast += 1
        # 返回slow
        return slow

类似地，如下题应该很容易解答：

leetcode 27题

fast指针所指向的元素只需要!=val就ok，代码：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if not nums: return 0
        # 双指针
        slow, fast, size = 0, 0, len(nums)

        while fast < size:
            # 进行筛选
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        
        return slow

类似地，可以借用双指针，解如下题：

leetcode 283题

大概的思路：

• fast指针向前遍历，当nums[fast] != 0时，nums[slow] = nums[fast]
• 当fast指针越界，循环停止时，slow指向的正好是数组中最后一个不为零的元素位置，此时将nums[slow]之后的元素置为零。
  
  
  代码如下：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow, fast, size = 0, 0, len(nums)
        # 特殊情况，直接返回nums
        if size == 1:
            return nums
        # 循环的边界条件
        while fast < size:
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1

            fast += 1
        # 此时slow已经指向了应该为零的元素的位置
        while slow < size:
            nums[slow] = 0
            slow += 1

        return nums

第一天挑战的题目都是简单题，很容易就cover住了，但重新总结一下，仍然有新的收获~

Day 2 前缀和

前缀和的方法适用于快速计算某个索引区间内的元素之和，考虑这样的场景：

nums = [x_1, x_2, ..., x_n]，想要计算该数组区间[k_1, k_2]之间的元素和，那么应该怎样处理呢？当然，我们可以套上几个for循环来解决，不能用暴力方法解决的算法题，只能说明方法还不够暴力。但是，我们知道，一旦套上for循环的方法，基本上都会面临超时的问题。

这时候或许就应该考虑前缀和的技巧了，前缀和的技巧往往又与差分的思想结合起来使用。

举例：

基于上述思想，来解决如下实际算法题：

leetcode 560 题

大概的思路：

• 初始化一个计数变量cnt，当某个子数组的区间和等于k时，cnt += 1;
• 返回cnt.

代码如下：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cnt, n = 0, len(nums)
        # 初始化前缀和数组
        pre = [0] * (n + 1)
        # 对nums的前i项进行累加
        for i in range(1, n + 1):
            pre[i] = pre[i - 1] + nums[i - 1]
        # 寻找满足和为k的子区间
        for i in range(1, n + 1):
            for j in range(i, n + 1):
                # 找到后，cnt += 1
                # 这个条件说明，sum(nums[i:j]) == k
                if (pre[j] - pre[i - 1] == k):cnt += 1
        return cnt

这样做的问题在于，当构建好前缀和数组后，仍然需要用两个for循环去匹配条件。果不其然，点击提交按钮，发现超时了...

这时候，考虑维护一个hashmap对前缀和方法优化，看leetcode上的题解，一时半会儿也没理解，还是需要自己动手画个图，结合几个实际的例子：

代码首先需要构建这样的一个haspmap，键是前缀和，值是该前缀和的个数，构建的同时，去匹配条件，当满足条件时，计数变量cnt += 1，最后return cnt

代码能够清晰表达上述逻辑，文字有时候不够精炼， show the code：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 初始化hashmap
        d = {}
        # 初始化前缀和以及计数变量
        acc, cnt = 0, 0
        for num in nums:
            acc += num
            # 这个 if 的逻辑好理解
            if acc == k:
                cnt += 1
            # 这个 if 的逻辑，结合图，以及实际例子就好理解了
            if acc - k in d:
                cnt += d[acc - k]            
            # 构建 hashmap 
            if acc in d:
                d[acc] += 1
            else:
                d[acc] = 1

        return cnt

前缀和的技巧同样可以应用于二维数组中，解决如下题：

leetcode 304 题

初看这题，都没多想，直奔题解区ctrl c+v，趁着总结的机会，算是把这题给弄懂了。

做此类初始化一次，检索多次的题目，对数据要进行预处理

我们拿这题的示例来看：

暴力的for循环仍然能做，只不过复杂度太高了，结合前面一维的前缀和技巧，这道题不过是在前缀和在二维的拓展。

因为所求的，仍然是数组的某个子数组的和。

类比于一维的情况，拓展到二维，本题的思路：

• 得到二维的 preSum，preSum[i, j] 表示从坐标(0, 0)到(i, j)，这块区域的元素和；
• 利用 preSum，得到子矩阵 S[(row1, col1), (row2, col2)]范围内的元素和。
  具体地，S[(row1, col1), (row2, col2)] = S[(0, 0), (row2, col2)] - S[(0, 0), (row2, col1)] - S[(0, 0), (row1, col2)] + S[(0, 0), (row1, row1)]

结合代码：

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        # 初始化二维前缀和矩阵
        self.preSum = [[0] * (n + 1) for _ in range(m + 1)]
        # 二维前缀和矩阵的赋值，由于多加了一次self.preSum[i][j]，所以要减一次
        for i in range(m):
            for j in range(n):
                self.preSum[i + 1][j + 1] = self.preSum[i + 1][j] + self.preSum[i][j + 1] - self.preSum[i][j] + matrix[i][j]



    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # 由二维前缀和矩阵，直接得到某个子矩阵的元素和
        # 由于多减去了一次 self.preSum[row1][col1]，所以要加上
        return self.preSum[row2 + 1][col2 + 1] + self.preSum[row1][col1] - self.preSum[row1][col2 + 1] - self.preSum[row2 + 1][col1]

第二天挑战的前缀和，首次做的时候确实很懵，重新梳理一下，清晰多了。

Day 3 差分数组技巧

对于Day2挑战中学习到的前缀和，我们可以总结它的适用场景：数组本身不进行更改，多次查询某个区间内的元素和。

差分数组的主要适用场景则是：多次对原始数组的某个区间的元素进行增减，当题目中有表达出类似的意思时，要想到差分数组的技巧。

结合实际题目来说明问题：

leetcode 370 题

在数组的某个区间段nums[start, end]上进行操作，例如+k操作，等价于先在nums[start:]上+k，再在nums[end+1:]上-k，结合下图进行说明：

对于这种+k再-k的套路，我们应该如何在代码中实现呢？这就要引出差分数组了，设数组a[0,1,2..n]的差分数组为d[0,1,2..n]，差分数组的定义为：

• 当i = 0时，d[0] = a[0]
• 当i > 0时，d[i] = a[i] - a[i - 1]

求差分数组的过程，就是求前缀和数组的逆过程，对于原数组某个区间范围[L, R]内加减同一个数的更新操作，反映到差分数组上，只用更新区间两端(L和R+1)位置的值

这句话怎么理解呢？由差分数组的定义，易得：

a[i] = d[0] + d[1] + ... + d[i]

假设a[3], a[4], a[5]这三个数同时加上k，反映到差分数组上d[3] + k，d[6] - k，将数组a展开：
a[0] = d[0]
a[1] = d[0] + d[1]
a[2] = d[0] + d[1] + d[2]
a[3] = d[0] + d[1] + .. (d[3] + k)
a[4] = d[0] + .. + (d[3] + k) + d[4]
a[5] = d[0] + .. + (d[3] + k) + d[4] + d[5]
a[6] = d[0] + .. + (d[3] + k) + .. + (d[6] - k)

可以看到，我们只需要对差分数组边界上的两个元素进行处理，就可以达到对原数组所对应区间上的元素同时加上一个元素的效果，a[3]之前的元素不受影响，a[5]之后的元素也不受影响。

代码实现如下：

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        # 初始化差分数组
        d = [0 for _ in range(length)]
        
        # 在差分数组的边界元素上进行操作
        for start, end, inc in updates:
            d[start] += inc
            if end + 1 < length:
                d[end + 1] -= inc

        # 整理差分数组
        for i in range(1, length):
            d[i] += d[i - 1]

        return d

leetcode 1094 题

将题目的要求抽象出来，其实就是一个区间和的问题，当某个区间上的承载量超过capacity时，返回False，结合上一题的分析，不难写出该题的代码：

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # 原题中由写明 0 <= trips.length <= 1000，
        # 所以初始化一个长度为1001的差分数组
        diff = [0] * 1001
        # 对于原数组某个区间段的操作，
        # 对应到差分数组的边界上进行处理
        for num, start, end in trips:
            diff[start] += num
            diff[end] -= num
        # preSum其实就是统计各个时间段上的乘客数
        # 一旦preSum > capacity，return False
        preSum = 0
        for i in range(1001):
            preSum += diff[i]
            if preSum > capacity:
                return False

        return True

经典的航班预定问题，其实是同样的套路：

leetcode 1109 题

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        # 构建差分数组
        diff = [0] * n

        for first, last, seat in bookings:
            # first -= 1为了和数组的索引对应
            first -= 1
            diff[first] += seat
            # last不需要再进行 += 1的操作
            if last < n:
                diff[last] -= seat
        # 整理差分数组
        for i in range(1, n):
            diff[i] += diff[i - 1]

        return diff

差分数组的技巧，算是比较抽象。这种情况往往看别人的题解是难以完全看懂的，应该试着自己举几个实际例子，结合起来，为什么原数组某个区间段上的操作，对应到差分数组上就是在边界上进行操作就行。以及为什么对差分数组进行累加，就可以得到想要的数组，将原数组以差分数组的形式展开，便容易理解了。

Day 4 回文串的判断

回文串的判断据说是面试的高频题，尽管还不知道有啥具体实际意义。首先，明确回文串的定义，正着读和反着读都是一样的字符串。

例如aaaa，abcba，abccba都是字符串，而abab就不是，那么如何判断某个字符串是否为回文串，其实是一个很简单的问题，核心思路便是，从字符串的中间，借助双指针，向两边扩散，对指针指向元素是否相等进行判断。

回文串的判断本身并不值得出题（很简单），往往会结合着其他条件，如下题：

leetcode 5 题

对字符串s中的元素进行遍历，分别作为回文子串的中心，维护一个最大长度的变量：

这样的处理乍看之下没有问题，但忽视了回文子串长度为偶数的情况，例如字符串aabbccbbaa，其最大回文子串明显就是它本身，但如果我们按照上述逻辑去处理的话，只能找到长度为1的回文子串。

对于偶数长度的字符串，我们应该取相邻的两个元素作为中心点，向外扩散，实际的处理中，我们可以定义一个find函数，该函数的作用便是，找出当前中心点的最长回文子串，由于题目中要求输出子串，所以find函数，需要返回子串的左右索引。

那么这个find函数应该传入些什么参数呢？稍加分析，不难确定，要传入字符串s，因为要对s的左右侧元素进行比较；还需要传入中心点，方便主函数中的遍历。那么如何同时满足奇数长度子串和偶数长度子串需求呢？其实，这时候传入两个参数left和right就好了，对于奇数情况，left == right，一个中心点；对于偶数情况right = left + 1，两个相邻的中心点。

结合代码：

class Solution:
    def find(self, s, left, right):
        # find函数用来找以某元素为中心的最长回文子串
        # 返回位置索引
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1

        # 这里要将left和right退一个状态
        return left + 1, right - 1
    
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        # 特殊情况判断
        if size == 1:
            return s

        start, end = 0, 0

        for i in range(size):
            # 分别考虑子串长度为奇数以及偶数的情况

            # 奇数情况
            left1, right1 = self.find(s, i, i)

            # 偶数情况
            left2, right2 = self.find(s, i, i + 1)

            if right1 - left1 > end - start:
                end = right1
                start = left1

            if right2 - left2 > end - start:
                end = right2
                start = left2

        return s[start: end + 1]

Day 4 挑战的算法题就这一道，明白回文串的定义，懂得“从中间往两边扩散”的套路，结合题目的条件，耐心分析。

Day 5 二分搜索技巧（基础）

二分查找最基本的场景：寻找一个数，寻找左侧边界、寻找右侧边界。二分查找一般适用于有序数组，看到算法时间复杂度要求里面有log，就应该想到二分。

二分查找的思路很简单：

• 对于有序数组nums，先取索引为中间位置的元素nums[mid]，与目标target进行比较，无非就三种情况：
  1. 当nums[mid] == target时，返回mid;
  2. 当nums[mid] > target时，此时说明target只可能存在于数组的左侧；
  3. 当nums[mid] < target时，此时说明target只可能存在于数组的右侧。
• mid = (right - left) // 2 + left，当left > right时，说明数组中并没有目标元素target

二分查找的思路虽然很简单，但对于边界的细节问题，需要格外注意，结合一道实际题目说明：

leetcode 704 题

这道题可谓是经典的不能再经典

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        # 在上图的分析中，left应该允许等于right
        while left <= right:
            mid = (right - left) // 2 + left
            if nums[mid] > target:
                # 之所以right是用mid-1进行更新，而不是mid
                # 考虑一个极端情况当left == right == mid但
                # nums[mid] != target，此时循环出不去
                right = mid - 1
            elif nums[mid] < target:
                # left 也是用mid + 1进行更新
                left = mid + 1
            else:
                return mid
        return -1

对于边界的探讨，为什么right和left都要在mid的上进行+1或者-1的操作进行更新，难道不可以right = mid而left = mid + 1或者right = mid - 1而left = mid？

举个实际例子说明，假设我们是按照right, left = mid, mid + 1这种形式对索引进行更新，那么当nums[mid] > target，此时left = right - 1，此时的mid已经是等于left了，那么right = left，仍然是会陷入nums[left] == nums[right] == nums[mid] != target的死循环中。

借助二分查找的技巧，解决下题：

leetcode 34

看到进阶要求，实现时间复杂度的算法为O(log n)，加上数组本身是有序排列的，应该立马想到二分。

然而基本的二分查找方法，当nums[mid] == target时便返回了，应该如何去寻找目标值的开始位置和结束位置呢？

或许定义两个二分查找的函数，一个往左边去扩展，当扩展到数组中的元素不等于target时停下，记录下索引left；一个往右边去扩展，同样记录边界索引right，最终主函数只需要返回[left, right]就ok了。

将思路梳理一下：

• 分别定义向左，向右的两个探寻函数，函数的主题实现方式仍然是二分；
• 对于探寻函数来讲，当nums[mid] == target时，并不直接返回，而是分别再往左或右进行扩展；

在上述十分不严谨的分析下，对于向左探寻的函数返回的条件应该是，nums[low] == target；类似地，对于向右探寻的函数返回的条件应该是，nums[high] == target

我们结合代码进行分析：

    def findleft(self, nums, target):
        low, high = 0, len(nums)-1
        # 整体框架仍然是二分查找的套路
        while low <= high:
            mid = (high - low) // 2 + low
            # 由于此时还需要往左侧探寻，对于目标在左侧的情况
            # high = mid - 1
            if nums[mid] == target:
                high = mid - 1

            elif nums[mid] > target:
                high = mid - 1

            else:
                low = mid + 1
        
        # 当循环结束，此时low = high + 1
        if nums[low] == target:
            return low

        # 说明数组本身连一个target都没有
        else:
            return -1

负责探寻右侧的函数和左侧类似，需要改变的是if nums[mid] == target: low = mid + 1，返回的是high

总代码如下：

class Solution:
    def findleft(self, nums, target):
        low, high = 0, len(nums)-1

        while low <= high:
            mid = (high - low) // 2 + low
            if nums[mid] == target:
                high = mid - 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1

        if nums[low] == target:
            return low
        else:
            return -1

    def findright(self, nums, target):
        low, high = 0, len(nums)-1

        while low <= high:
            mid = (high - low) // 2 + low
            if nums[mid] == target:
                low = mid + 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1

        if nums[high] == target:
            return high
        else:
            return -1


    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 先对特殊情况进行判断
        if not nums or target > nums[-1] or target < nums[0]:
            return [-1, -1]

        self.left = self.findleft(nums, target)
        self.right = self.findright(nums, target)

        return [self.left, self.right]

二分查找的技巧并不难，关键在于边界的细节上，需要结合实际例子，具体问题具体分析。

Day 6 二分搜索的应用

实际的算法题目中很少直接说明在有序数组中搜索指定元素，往往会给出一些情景，这时候就需要我们可以将问题给抽象出来，不要被表面的描述所迷惑了，私以为，要具备这种抽象能力，需要多刷题和总结。

直接拿实际题目说明：

leetcode 875 题

说实话，一开始看到这题，连题目想让我求什么都不太清楚。结合示例才把题目意思给搞明白，但看懂题目意思后也没有想到可以用二分的技巧求解。

对于有N堆的香蕉，由于珂珂不管她再能吃，都要最起码分N次给她吃完。那么，这个最起码的值是多少呢？稍加思索，不难得出当k == max(piles)时，珂珂可以N次吃完这N堆香蕉，k继续大下去，没意义，也需要N次；由于题目求的是最小值，自然只需要在[1, max(piles)]这个区间内进行搜索就好了。

一个朴素的想法就是从1一直遍历到max(piles)，当首次满足某个条件时，结束遍历，得到的就是最小速度K。

我们可以定义一个函数帮助判断，当前K的值，珂珂是否能吃完所有的香蕉。仔细审题，对于这种多了的不算，少了的需要补齐的操作，要想到整除操作。例如，某堆香蕉有8根，当速度为5时，需要两次吃完（ 8 // 5 + 1），可以写出如下代码：

    def possible(piles, k, h):
        tmp = 0
        for p in piles:
            # 因为在整除后 +1，所以p要先-1
            # 举例，当p = 5， k = 5， tmp应该等于1
            tmp += (p - 1) // k + 1
        if tmp <= h:
            return True
        else:
            return False

有了possible()函数后，可以直接在主函数中从小到大遍历，当满足条件时候返回。这时候题目就转换为了在有序数组中进行搜素的问题，应该想到二分查找，而且target也已经定义好了。
当思路转变到这，不难写出如下代码：

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        lo, hi = 1, max(piles)

        while lo <= hi: 
            # 仍然是拿中间的量先去比
            mid = (hi - lo) // 2 + lo
            # 当满足possible函数时，说明mid有点大了，或许可以更小，更新变量hi
            if self.possible(piles, mid, h):
                hi = mid - 1
            # 当不满足possible函数时，说明mid大了，更新lo
            else:
                lo = mid + 1
        return lo


    def possible(self, piles, k, h):
        tmp = 0
        for p in piles:
            tmp += (p - 1) // k + 1

        if tmp <= h:
            return True
        else:
            return False

从这一道题中，我们可以对二分查找的方法给抽象一下，总结二分搜索在以下场景适用：

• 可以得到一个单调函数f(x)，对于这个单调函数，能够得到自定域的左右边界（该题便是1和max(piles))
• 有约束target（本题中的约束便是根据题意定义出来的possible函数），题目的要求是让我们找到满足约束条件f(x) == target时的x

再来看下面一道题：

leetcode 1011 题

这种场景题，必须要结合示例的输入输出才能够搞清楚它到底想问啥。

对于weights这个数组而言，每个元素是不能拆开的。例如，当船舶的运载量为15，已经载上了13的货物，这时候再来一个重量为3的货物，已经装不下了，不能把货物拆成重量为2和1的两件。此外，需要按照weights的顺序来装，不能说看到后面有重量为2的，就先把它给装进去。这时候，只能隔天装了，day += 1。

很显然，这道题的约束条件便是day <= days，承载量的上限是sum(weights)（一次性全部装完），承载量的下限是max(weights)（单件货物不能分开装）

我们定义这道题的约束函数：

def helper(weights, days, cap):
    # 注意这里day变量的初始化应该为1
    day = 1
    tmp = 0

    for weight in weights:
        tmp += weight
        # 此时装载的重量已经超过船舶的承载极限了
        if tmp > cap:
            # 天数 + 1
            day += 1
            # tmp初始化为当下的weight
            tmp = weight

    return True if day <= days else False

结合二分查找的技巧，不难写出此题的答案

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        lo, hi = max(weights), sum(weights)

        while lo <= hi:
            mid = (hi - lo) // 2 + lo

            if self.helper(weights, days, mid):
                hi = mid - 1

            else:
                lo = mid + 1

        return lo
    

    def helper(self, weights, days, cap):
        day = 1
        tmp = 0
        for weight in weights:
            tmp += weight
            if tmp > cap:
                day += 1
                tmp = weight

        return True if day <= days else False

单纯的二分查找，只需要注意边界问题就行；对于各种各样的场景题，要对题目进行抽象，这需要刷题的同时多进行总结。

Day 7 滑动窗口技巧

滑动窗口的概念不难理解，就是对一个窗口依照某种规则进行维护，不断滑动，更新答案。然而，到实际要写代码的时候，经常就是摸瞎，憋半天敲不出一行代码。

困难主要出现在以下几点：

• 怎么向窗口中添加元素；
• 怎么缩小窗口；
• 何时更新结果。

带着上述问题，我们来解决几道算法题，结合题目来理解，总结出套路。

leetcode 3 题

既然这道题出现在滑动窗口的专题下，也不藏着掖着了，直接用滑动窗口进行分析：

在这道题中，滑动窗口的删减，一定是从左侧进行的，因为子串要保持连续性；在分析中，我们可以看到会有一个元素是否在窗口中的判断；此外，窗口滑动的过程，明显有一个头部删除，尾部添加的操作。所以，当我们能够画出一趟滑动窗口的变化过程，写出代码并不是很难的事情。

代码如下：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 特殊情况，当s本身不存在的时候返回0
        if not s:
            return 0

        # 初始化window为一个栈结构
        window = []
        maxlength = 0
        for i in range(len(s)):

            #当s[i]在窗口中，要删除干净，所以这里用while
            while s[i] in window:
                # 删除头部
                window.pop(0)
            # 尾部追加
            window.append(s[i])
            # 维护一个最大长度
            maxlength = max(maxlength, len(window))

        return maxlength

leetcode 567题

由于题目要求判断的是否包含排列，这意味着，并不需要管s1本身字母的顺序如何，只要s1的子串中有即可，窗口的长度显然需要依据s1的长度来确定。

对于每个窗口，只需要对相应的字母计数，若与s1中字母计数的情况相同，便返回True，窗口滑动完了还没找到，返回False。

那么，具体应该如何实现上述操作呢？

可以先定义两个字母表，dictA和dicB，前者用以统计s1中各字母的个数，后者，针对于每个滑动窗口，统计窗口下子串中各字母的个数。

经上述分析，可以写出如下代码：

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        # 初始化字母表
        dicA = [0] * 26
        dicB = [0] * 26
        
        m, n = len(s1), len(s2)

        for i in range(m):
            dicA[ord(s1[i]) - ord('a')] += 1
            dicB[ord(s2[i]) - ord('a')] += 1
            
        if dicA == dicB:
            return True

        for i in range(m, n):
            # 出窗口操作
            dicB[ord(s2[i-m]) - ord('a')] -= 1
            # 进窗口操作
            dicB[ord(s2[i]) - ord('a')] += 1

            if dicA == dicB:
                return True

        return False

懂得了这道题的套路，应该可以丝滑地解决下面这道题

leetcode 438 题

这道题无非是改一下leetcode 567题的输出，写出如下代码：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        
        if len(s) < len(p):
            return []
        dicA = [0] * 26
        dicB = [0] * 26

        n, m = len(s), len(p)
        ans = []
        for i in range(m):
            dicA[ord(s[i]) - ord('a')] += 1
            dicB[ord(p[i]) - ord('a')] += 1

        if dicA == dicB:
            ans.append(0)

        for i in range(m, n):
            # 出操作
            dicA[ord(s[i - m]) - ord('a')] -= 1
            # 进操作
            dicA[ord(s[i]) - ord('a')] += 1
            if dicA == dicB:
                ans.append(i - m + 1)
        return ans

借助滑动窗口的技巧，来正儿八经地解决一道hard题

leetcode 76 题

解此题的思路不难想到：

• 初始化left, right = 0, 0，移动right指针，扩大窗口。当窗口包含所有需要的元素，记录下此时的长度，以及指针，维护变量minlength；
• 向右移动left，如果窗口中不再包含所有需要的元素，移动right，记录此时长度，判断是否比minlength小，如果是，更新minlength，并记录left, right。
• 继续移动left，对数组中的元素进行遍历，相当于对所有包含所有需要的元素的窗口进行了比较，最终记录下来的一定是满足要求的最小子串。

从上面的分析，最重要的一点是判定窗口已经包含所需要元素。

可以利用一个need字典，用来记录当下窗口中的元素，初始化need = {A:1, B:1, C:1}，表示本来需要的是1个A，1个B和1个C；

窗口滑动时，我们需要维护need这个字典，当滑动窗口包含某个元素时，就让need中这个元素对应的数值减少1；当滑动窗口移除某个元素时，就让need中这个元素对应的数值增加1。

例如，当滑动窗口中元素为ADOBEC时，need = {A:0, B:0, C:0, D:-1, E:-1, O:-1}，元素D、E、O其实是多余的，但是没关系，此时need中所有的元素都小于等于0，所以此时这个滑动窗口一定包含了所需要的元素。

此时，当left指针向左移动一个单位，滑动窗口中的元素变为DOBEC时，need = {A:1, B:0, C:0, D:-1, E:-1, O:-1}，这表示，还缺少一个元素A，所以right指针应该滑动，使得need中所有元素都小于等于0时，停止滑动，此时的滑动窗口再一次包含所有所需要的元素。

每一次对字典need的遍历，判断其中的值是否均小于等于零，会带来O(k)的时间复杂度，我们可以再定义一个needcnt变量，专门表示需要元素的数量是否满足需要，need[c]>0，便表示c是需要的元素。

可以写出如下代码：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t): return ""

        need = collections.defaultdict(int)

        for c in t:
            need[c] += 1
        needcnt = len(t)
        left = 0
        res = (0, float('inf'))

        for right, c in enumerate(s):

            if need[c] > 0:
                needcnt -= 1

            need[c] -= 1

            # 滑动窗口中已经包含了所有的元素
            if needcnt == 0: 
                while True:
                    c = s[left]
                    if need[c] == 0:
                        break

                    need[c] += 1
                    left += 1
                if right - left < res[1] - res[0]:
                    res = (left, right)

                need[s[left]] += 1

                needcnt += 1
                left += 1

        return '' if res[1] > len(s) else s[res[0]: res[1] + 1]

滑动窗口的思路不难理解，关键在于如何对窗口进行更新，如最小覆盖子串问题，第一次做很难想到会定义一个needcnt变量，用以判断当下窗口是否满足条件。熟能生巧，需要多加练习。

Day 8 链表技巧汇总

Day 7的挑战确实感到难度提升上来了，尽管自己梳理了一遍但感觉还是有些地方没有理解好。但不管怎么样，要迈向下一天的挑战了，我的更新进度还是被拖慢了一些。

Day 8的题目比较简单，直接结合相关的算法题来总结一下链表题的相关套路。

leetcode 141 题

判断链表是否有环，实属链表的经典题了，链表题常采用双指针的操作。

那么对于这道题，如果用双指针的技巧应该怎么去解呢？其实很简单，就是定义一个fast一个slow指针，fast指针移动的速度要快于slow。

这样，一旦fast和slow在除Null外的位置相遇，那么链表中就一定存在环，想到于在跑步比赛里面被人给套圈了。

可以写出如下的代码：

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head: return False

        fast = head.next
        slow = head

        while fast and fast.next:
            # fast要比slow快一步
            fast = fast.next.next
            slow = slow.next
            # 此时代表相遇
            if fast == slow:
                return True

        # 当跳出了while，说明fast == None或者fast.next == None
        # 此时已经到了终点，只有直线才有终点，说明无环，返回False
        return False

再接再厉，我们再来解决下题

leetcode 142 题

在141题中，我们学会了如何判断链表中是否有环，142题更进一步，要求返回一个pos参数。

• 先初始化slow和fast指针，起点位置相同，fast指针的速度是slow指针速度的两倍；
• 设链表的长度为m（对于示例1，m = 4)，设环的长度为k（对于示例1，k = 3)，那么，fast指针一定比slow指针多走nk步（n为正整数1，2，...）；
• fast指针走了2nk步，slow指针走了nk步；
• 可以确定slow指针的位置：
  [nk - (m - k)] % k + (m - k)，此时只要slow指针多走(m - k)步，就返回了环的初始位置(m - k)；
• 再定义一个新的指针newslow，从头开始，newslow速度为1。那么，当slow指针与fast指针相遇时，一定是在环的初始位置（都走了（m - k）步）。

可以写出如下代码：

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head

        while True:
            if not (fast and fast.next):
                return
            fast, slow = fast.next.next, slow.next

            if fast == slow: break

        newslow = head

        while newslow != slow:
            newslow, slow = newslow.next, slow.next

        return newslow

leetcode 876 题

对于这道题，一开始的想法是先让指针走一趟，统计出链表的长度k，然后再让指针从头再走k // 2步（要根据题目要求调整），返回链表的中间节点。

根据上述思想，不难写出如下代码：

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = head
        k = 0
        while fast:
            fast = fast.next
            k += 1

        step = k // 2 

        fast = head
        while step:
            fast = fast.next
            step -= 1

        return fast

但是这道题如是要求，扫描一趟链表就可以返回中间节点，那么我们应该如何做呢？

还是采用双指针的方法，快指针的速度是慢指针速度的两倍，当快指针到达链表终点，慢指针正好到达链表的中间位置。

根据上述思想，不难写出如下的代码：

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow, fast = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        return slow

leetcode 160 题

一开始看到这道题的难度为简单，正准备重拳出击，结果发现一时半会儿也想不到什么好思路。

这道题其实有点类似于leetcode 142题，开始尝试想着用双指针的技巧，最好也是能当两个指针碰到的时候，正好是两个单链表的起始节点。

• 定义两个指针A = headA和B = headB，指针移动的速度相同；
• 当指针A走完了headA，开始从headB往下走；当指针B走完了headB，开始从headA往下走，两者相遇的位置，便是相交链表的初始位置。

leetcode 19 题

经过了前面几题的联系，这道题的思路应该不难想到，定义fast和slow两个指针，
fast指针先走n步，slow指针再出发，当fast指针走到末尾时，slow指针正好走到倒数第n个节点的位置。

此时删除操作也很简单，slow.next = slow.next.next（具体细节可能需要调整）；然而，为了方便对涉及到head节点时操作更方便，需要定义dummy变量，dummy.next=head.

对于示例1的情形，可以直接返回head，也可以返回dummy.next，此时设不设置dummy并没有多大的差别；对于示例2的情形，head都被删除了，真是拿头返回，此时就需要dummy节点的帮助了。

不难写出如下代码，注意fast指针和slow指针的起始位置，理想情况，fast指针走到末尾，slow指针走到要被删除元素的前一位。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

        dummy = ListNode()
        dummy.next = head

        fast, slow = head, dummy

        for _ in range(n):
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return dummy.next

链表的操作多涉及到双指针的技巧，一个跑一个追，期待能与你相遇，做个算法题还有几分感动。此前对dummy节点的用法也是不清楚，经过一番梳理，有种恍然大悟的感觉。

Day 9 队列和栈互转

作为最基础的数据结构，想必都能扯两句，队列是先进先出，栈是先进后出。

对于这两种数据结构如何相互转换，我们结合相关算法题进行分析：

leetcode 232 用栈实现队列

借助两个栈来实现队列的“先进先出”：

只有执行pop()以及peek()时，对栈B是否为空进行判断。此时，如果栈B为空，将栈A中的元素全部倒入栈B中，经过栈B再将需要的元素弹出或者返回。

代码如下：

class MyQueue:

    def __init__(self):
        self.A = []
        self.B = []

    def push(self, x: int) -> None:
        self.A.append(x)

    def pop(self) -> int:
        if not self.B:
            while self.A:
                self.B.append(self.A.pop())

        return self.B.pop()

    def peek(self) -> int:
        if not self.B:
            while self.A:
                self.B.append(self.A.pop())

        return self.B[-1]

    def empty(self) -> bool:

        return not self.A and not self.B

Day 10 单调栈

当题目的题意表达出类似于“寻找最近一个比某元素大”时，要想到单调栈的技巧解答。

leetcode 496 下一个更大元素 I

对于这道简单题，是可以采用暴力解法的，只需要在nums2中找到对应nums1的元素，再向右搜寻即可，不难写出如下代码：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        res = [-1] * n

        for i in range(n):
            # 找到nums2中对应元素的索引
            j = nums2.index(nums1[i])
            for k in range(j+1, len(nums2)):
                if nums2[k] > nums1[i]:
                    res[i] = nums2[k]
                    break
            
        return res

对于简单题我们可以这样处理，但稍微对时空复杂度做出一点限制，暴力解法就会超时。

那么，如果采用单调栈的技巧，这道题应该如何解决呢？

这道题目里面虽然有个nums1，但实际上找的仍然是nums2中每个元素的下一个更大元素。对于示例1，我们可以定义一个字典，键就是nums2中的每个元素，值就是所对应的下个更大元素，得到dic = {1:3, 3:4, 4:-1, 2:-1}。然后对于nums1中的每个元素，映射到dic中，找到每个值，返回结果就是我们需要的。

单调栈就是帮助我们建立起这样一个字典的手段，不难画出单调栈的形成过程：

由于是寻找下一个最大的元素，所以逆序遍历会高效很多。对遍历到的每一个元素，先和栈顶的元素进行比较，如果栈顶元素较小，删去栈顶元素，继续比较。

当栈顶出现比遍历元素大的元素时，说明该遍历元素右侧的第一个最大值，为此时的栈顶元素，若栈删空了，说明遍历元素右侧没有比它大的了

如上图，逆序遍历，遍历到的首个元素是1，此时栈空，1右侧没有比1大的元素了；遍历到第二个元素是7，此时栈内的元素只有1，1比7小，删去1，此时栈空，说明7的右侧也没有比7大的元素了。

基于上述分析，我们可以写出如下代码：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res, stack = {}, []

        for num in reversed(nums2):
            # 和栈顶元素比较
            while stack and num > stack[-1]:
                stack.pop()
            # 若栈内存在元素，res[num]赋值为栈顶元素；若栈空，赋值为-1
            res[num] = stack[-1] if stack else -1

            stack.append(num)

        # 根据所构造的字典进行映射
        return [res[num] for num in nums1]

接下来解决503题

leetcode 503. 下一个更大元素 Ⅱ

题目中所谓的循环查找，其实最多也就是扫描数组两遍，当第二遍还没有满足条件的元素时，说明是真没有了。此时，我们可以通过取余映射来完成扫描数组两次的操作。

相较于上一题，该题的单调栈并不直接存储元素了，而是存储对应的索引，我们可以画出示意图：

当索引值被弹出时，说明此时找到了比索引值对应元素大的元素，初始化一个输入res = [-1] * n，其中n = len(nums)，那么只需要将数组res弹出索引的位置上的元素赋值为所找到的，比索引值对应元素大的元素，最终的res就是答案。

文字属实有点绕，结合代码就能够明白什么意思了

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # 单调栈初始化
        stack = []
        # 初始化res
        res = [-1] * n
        # 最多遍历两趟
        for i in range(2 * n - 1):
            # stack 中存储的索引，所以比较的对象还要映射到数组中
            while stack and nums[i % n] > nums[stack[-1]]:
                # 此时找到了更大的元素，根据弹出索引位置赋值
                res[stack.pop()] = nums[i % n]
            # stack 中存储索引
            stack.append(i % n)

        return res

了解了这种在栈中存入索引的操作，不难解决下题

leetcode 739 每日温度

不难画出如下构造单调栈的过程：

栈中每弹出一个索引，就说明找到了比该弹出索引对应元素大的元素，例如当i=1时，栈中存放的索引是0，temperatures[1] > temperatures[0]，由于题目求的是当天后的第几天，所以对于temperatures[0]来讲，返回的应该是1 - 0 = 1；

同理，当i = 5时，弹出栈的索引为4和3，那么对于temperatures[4]来讲，返回的应该时5 - 4 = 1；对于temperatures[3]来讲，返回的应该时5 - 3 = 2.

基于上述分析，不难写出如下代码：

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        size = len(temperatures)
        stack = []
        ans = [0] * size

        for i in range(size):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                out = stack.pop()
                ans[out] = i - out

            stack.append(i)

        return ans

Day 11 二叉树训练

许多经典算法，实质上都是树的问题，例如回溯算法、动态规划算法等。此外，二叉树相关的题目也是最练习递归基本功，有助于我们理解递归思想。

递归算法的关键：明确函数的定义，并且相信这个定义，但不要跳入细节中。

leetcode 226 翻转二叉树

明确题意，要求我们做到对二叉树上的每个节点的左右子节点进行交换。
1.对根节点的左右子节点进行交换；
2.对根节点的左节点的左右子节点进行交换，对根节点的右节点的左右子节点进行交换；

3. ....

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        tmp = root.left
        root.left = root.right
        root.right = tmp

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

leetcode 116 填充每个节点的下一个右侧节点指针

子树内的左节点和右节点连接并没有什么问题，问题的关键在于如何将在子树之间的节点连接。由于连接是从左至右的，最右侧子树的右节点没有连接的对象，只能指向[Null]，依此来进行判断。

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None
        if root.left:
        # 如果树还没有到底
            root.left.next = root.right
            if root.next:
            # 如果还没到最右侧
                root.right.next = root.next.left
      
        self.connect(root.left)
        self.connect(root.right)

        return root

leetcode 114 二叉树展开为链表

题目要求展开后的单链表要与二叉树的先序遍历相同，所以展开后的左子树要接在展开后的右子树之前。

对于递归问题，具体考虑最后一步怎么处理，前面的步骤相信我们所定义的函数能够完成。

不难写出如下代码：

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return 

        # 相信所定义的flatten函数，可以将左子树与右子树展开
        self.flatten(root.left)
        self.flatten(root.right)

        left = root.left
        right = root.right

        root.left = None

        root.right = left

        p = root
        while p.right:
            p = p.right

        p.right = right

Day 12 二叉搜索树基础

二叉搜索树（Binary Search Tree, BST)，特点：左小右大

BST的定义：

1. BST中任意一个节点的左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值；
2. BST中任意一个节点的左右子树都是BST.

基于BST的这种特性，在其中采用类似于二分搜索的操作，搜索一个元素的效率很高。

Leetcode 700 二叉搜索树中的搜索

题目较为简单，分情况讨论：
1、如果val < root.val，说明需要在当前根节点的左子树寻找；
2、如果val > root.val，说明需要在当前根节点的右子树寻找；
3、如果val == root.val，说已经找到；
4、如果root.val == None，直接返回None.

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root

        if val < root.val:
            return self.searchBST(root.left, val)

        if val > root.val:
            return self.searchBST(root.right, val)

Leetcode 701 二叉搜索树中的插入操作

仍然是分情况讨论：
1、当val < root.val，说明要插入该根节点的左子树，插入后对根节点的左子树进行更新root.left = self.insertIntoBST(root.left, val);
2、当val > root.val，说明要插入该根节点的右子树，插入后对根节点的右子树进行更新root.right= self.insertIntoBST(root.right, val)
3、当根节点不存在，插入新节点，并返回，return TreeNode(val)

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        if val < root.val:
            # 说明要插入左子树中
            root.left = self.insertIntoBST(root.left, val)

        else:
            # 说明要插入右子树中
            root.right = self.insertIntoBST(root.right, val)

        return root

Leetcode 98 验证二叉搜索树

二叉搜索树的中序遍历一定是升序的：左 --> 根 --> 右，据此验证二叉搜索树

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 判断中序遍历  左 --> 根 --> 右  为升序遍历
        stack, inorder = [], float('-inf')

        while stack or root:
            while root:
                stack.append(root)
                root = root.left

            root = stack.pop()

            if root.val <= inorder:
                return False

            inorder = root.val
            root = root.right

        return True

Day 13

leetcode 102. 二叉树的层序遍历

采用广度优先算法，逐层向下扫描，借助队列依次让每层节点出队

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        queue = [root]
        res = []

        while queue:
            length = len(queue)
            level = []
            for _ in range(length):

                node = queue.pop(0)

                level.append(node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            res.append(level)

        return res

leetcode 111.二叉树的最小深度

递归实现深度优先算法，递归需要写出：

1. 终止条件；
2. 不要陷入递归，将一棵树简化为根节点，左子节点，右子节点三个节点；
3. 只考虑当前做什么，不用考虑下次应该做什么；（人做事应该也是如此）
4. 每次调用应该返回什么。

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 特殊情况
        if not root: return 0

        # 特殊情况
        if root.left is None and root.right is None:
            return 1

        if root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

        if root.left:
            return self.minDepth(root.left) + 1

        if root.right:
            return self.minDepth(root.right) + 1