【8】字符串转换函数

📖 题目要求

实现一个atoi函数，将字符串转换为整数，转换规则如下：

丢弃字符串开头的空格字符 ' ' 。，得到新的字符串，

• 第一个字符是+或-号，则取该字符与之后的连续数字

• 第一个字符是数字，也取其和之后的数字

• 有效整数部分后的字符，忽略

第一个非空字符不是一个有效整数字符（数字和正负号）、字符串为空或字符串仅包含空白字符时，则无法进行有效转换，返回0

• 边界条件：当数值超出边界[$−2^{31}$, $2^{31} − 1$]时,返回边界值。

💡 解题思路

（1）按条件一个一个来

class Solution:
    def myAtoi(self, str_: str) -> int:
        str_=str_.lstrip()   # 去掉左侧空格
        if len(str)==0:    # 字符串为空/仅包含空白字符
            return 0

        flag,num = None,[]
        for char in str_:
            if char in '+-' and not flag and not num: # 第一个非空字符为±号
                flag = (1 if char =='+' else -1 )
            elif char in '0123456789': 
                num.append(char)
            else:
                break

        if not num: # 非空首字符为字母等情况,中断了循环，返回0
            return 0

        # 第一个字符不是±号时,flag为None，此时全是数字
        ans = (flag if flag else 1)*int(''.join(num))
        
        # 边界条件
        if ans > 2**31 -1:
            ans = 2**31 -1
        if ans < -2**31:
            ans = -2**31
        return ans

（2）正则表达式

class Solution:
    def myAtoi(self, str_: str) -> int:
        return max(min(int(*re.findall('^[\+\-]?\d+', str_.lstrip())), 2**31 - 1), -2**31)

• max(min(数字, 2**31-1), -2**31)处理边界问题
• 用到的正则定义
  • ^：匹配字符串开头
  • [\+\-]：一个+或者-号
  • ?：前面的一个字符可有可无
  • \d：一个数字
  • +：前面一个字符的一个或多个
• re.findall得到的是一个列表，通过*可以解包，比如['40']→40

【11】盛最多水的容器

📖 题目要求

给你 n 个非负整数 $a_1，a_2，…，a_n$，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

💡 解题思路

开始的思路是，先找到最高的高度，然后遍历元素，计算最大宽度，得到最大面积。此时，会忽略[1,2,1]这种有相同高度持平的情况。

在看过题解后，最终采取双指针法遍历数组，求得最大面积

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left,right = 0,len(height)-1
        ans = 0
        while left < right:
            area = min(height[left],height[right])*(right-left)
            ans = max(ans,area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return ans
    
    
###  错误范例
# class Solution:
#     def maxArea(self, height: List[int]) -> int:
#         max_h = max(height)
#         length1 = len(height)
#         m_index = []
#         ans = 0

#         for i in range(length1):
#             if height[i] == max_h:
#                 m_index.append(i)
#         #print(m_index)

#         length2 = len(m_index)
        
#         for i in range(length1):
#             if length2 == 1:
#                 width = abs(i -m_index[0])
#             else:
#                 v = list(map(lambda x: abs(x[0]-x[1]), zip([i]*length2, m_index)))
#                 width = max(v)
#             ans = max(ans,width*height[i])

#         return ans

【20】有效括号

（1）题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

（2）解题思路

使用栈来遍历字符串，

• 当遇到左半边括号时，压入栈中
• 当遇到右半边括号时：
  • 若栈不为空，则取出顶部元素，让和哈希表进行匹配，看成功与否
  • 当栈为空时，匹配失败

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []  
        mapping = {")": "(", "}": "{", "]": "["}

        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'   #如果堆栈非空，弹出最顶部的元素；否则，赋为“#”
                if mapping[char] != top_element:              #遇到了一个右括号，但此时栈顶不是对应左括号，直接返回false，宣告匹配失败
                    return False
            else:
                stack.append(char)  #开括号时
        return not stack

print(Solution().isValid(')[()])'))

【22】括号生成

📖 题目要求

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

💡 解题思路

（1）DFS

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        res = []
        cur_str = ''

        def dfs(cur_str, left, right, n):
            """
            :param   cur_str: 从根结点到叶子结点的路径字符串
            :param   left: 左括号已经使用的个数
            :param   right: 右括号已经使用的个数
            :return:
            """
            if left == n and right == n:
                res.append(cur_str)
                return
            if left < right:
                return

            if left < n:
                dfs(cur_str + '(', left + 1, right, n)

            if right < n:
                dfs(cur_str + ')', left, right + 1, n)

        dfs(cur_str, 0, 0, n)
        return res

【42】接雨水

📖 题目要求

给定n个非负整数表示每个宽度为1的柱子的高度图，求储水量

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

💡 解题思路

（1）按列求

对于当前列（高度为cur），分别求出其左侧和右侧最高列高度max_left、max_right，此时可能存在三种情况：

cur < min(max_left，max_right)	cur > min(max_left，max_right)	cur > min(max_left，max_right)
当前列储水量 = min(max_left，max_right) - cur	当前列无法储水	当前列无法储水

具体实现如下：

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        length = len(height)
        for i in range(1,length-1):  # 最两侧位置无法储水，可跳过
            # 找出左侧最大值
            max_left = 0
            for j in range(0,i): # 从0开始！ range(start,stop,step)
                if height[j] > max_left:
                    max_left = height[j]
            # 找出右侧最大值
            max_right = 0
            for j in range(i+1,length):
                if height[j] > max_right:
                    max_right = height[j]
            # 取较小值进行比较
            temp = min(max_left,max_right)
            if height[i] < temp:
                ans += temp - height[i]
        return ans

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

（2）动态规划

前一个解法，在数组很大时，两重循环直接导致时间复杂度爆炸。

因此，我们可以直接通过两个数组max_left[index]、max_right[index]来保存每个位置的左侧最大值和右侧最大值，然后再进行一次遍历，将当前值和min(max_left[index],max_right[index])进行比较即可。

• 当前列左边最大值 为 前一列的左边最大值和前一列数值 作比较
• 当前列右边最大值 为 右一列的右边最大值和右一列数值 作比较

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        length = len(height)
        max_left = [0]*length  # 创建初始列表
        max_right = [0]*length

        for i in range(1,length):
            max_left[i] = max(max_left[i-1],height[i-1])  # 当前列左边最大值 为 前一列的左边最大值和前一列高度 作比较
        
        for i in range(length-2,0,-1):            
            max_right[i] = max(max_right[i+1],height[i+1])  # 当前列右边最大值 为 右一列的右边最大值和右一列高度 作比较

        for i in range(length):
            temp = min(max_left[i],max_right[i])
            if temp > height[i]:
                ans += temp - height[i]

        return ans 

时间复杂度：$O(n)$

空间复杂度：$O(n)$，空间换时间效率

（3）双指针

设置left和right两个指针分别从左右两侧遍历数据。对于位置left而言，其左侧最大值一定是max_left，右侧最大值大于等于max_right；若max_left <= max_right，对位置left而言，经min(左侧最大值，右侧最大值)操作，其高度较小的一侧必然是左侧了，无论右边出现多大的max_right，其储水量已定。

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        left,right= 0,len(height) - 1 # 【从左到右】和【从右到左】处理数据的当前下标
        max_left,max_right = 0,0  # 左侧和右侧数据的最大值
        
        while left<=right:
            if max_left < max_right:  # 从左向右遍历
                ans += max(0,max_left-height[left])  # max是因为只有当前值 小于 较小的最大值时，才能储水
                max_left = max(max_left,height[left]) # 更新左侧最大值
                left += 1
            else: 
                ans += max(0,max_right-height[right])
                max_right = max(max_right,height[right])
                right -= 1    
        
        return ans 

时间复杂度：$O(n)$

空间复杂度：$O(1)$

【55】跳跃游戏

📖 题目要求

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

💡 解题思路

贪心算法，求解当前位置可以达到的最远位置，将最远位置和数组长度进行比较

class Solution:
    def canJump(self, nums: List[int]) -> bool
        length = len(nums)
        max_Reach = nums[0]
        for i in range(length):
            if i < max_Reach: # 当前位置可以到达
                max_Reach = max(max_reach,i+nums[i]) # 更新可达到的最远位置
        return max_Reach >= length -1

【56】合并区间

📖 题目要求

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

💡 解题思路

• 按照区间起始位置进行排序
• 比较当前区间的起始位置和结果区间中最后一个区间的终止位置

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 按照起始位置排序
        intervals.sort(key=lambda x:x[0])
        ans=[]
        for interval in intervals:
            # 结果区间为空，或者当前区间的起始位置大于结果区间中最后区间的终止位置
            if len(ans)==0 or interval[0] > ans[-1][1]:
                ans.append(interval)
            # 否则，当前区间和结果区间有重叠区域，更新结果区间中最后区间的终止位置
            else:
                ans[-1][1] = max(ans[-1][1],interval[-1])
        return ans

【72】编辑距离.md

📖 题目要求

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

💡 解题思路

定义dp[i][j]为word1的前i个元素转换为word2的前j个元素所使用的最少操作数

• 当两个字符串中一个为长度为0时，最少操作数等于另一个字符串的长度
• 当两个字符串都不为空时，
  • 若word1的第i个字符和word2的第j个字符恰好相等时，存在dp[i][j]=dp[i-1][j-1]
  • 不相等时，取三种情况的最小值，dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
    • abcde — abcd — fgh
    • abcde — fg — fgh
    • abcd — fg — fgh

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m,n = len(word1),len(word2)
        dp = [ ( [0] * (n+1) ) for i in range(m+1) ]  # 长度为n+1,m+1
        dp[0][0] = 0

        for i in range(1,m+1):
            dp[i][0] = i
        for j in range(1,n+1):
            dp[0][j] = j

        for i in range(1,m+1):
            for j in range(1,n+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else: 
                    dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
        return dp[m][n] # 此处索引，不能为i,j

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(mn)$

之前的二维数组中仅用到dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三个元素，即当前元素的左侧、下侧和左下角的元素。

可以采用一位数组来表示原先二维数组的一行，然后更新该数组的值，使其可表示二维数组。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m,n = len(word1),len(word2)
        dp = list(range(n+1))
        for i in range(m):
            lu = dp[0]
            dp[0] = i+1
            for j in range(n):
                dp[j+1],lu = min(dp[j]+1,dp[j+1]+1,lu+int(word1[i]!=word2[j])),dp[j+1] # 有点迷糊
                # dp[j],lu = min(dp[j-1]+1,dp[j]+1,lu+int(word1[i]!=word2[j])),dp[j]            
        return dp[-1]

【91】解码方法

题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码：‘A’ -> 1，B’ -> 2， … ，‘Z’ -> 26。给定一个只包含数字的非空字符串，请计算解码方法的总数。如:

输入: “121”
输出: 3
解释: 它可以解码为 “ABA”（1 2 1）或者 “LA”（12 1）或者“AU”（1 21）。

解题思路

输入是一个数字字符串，如果拆分之后其中的部分数字能代表了一个英文字母，那么算作一种拆分方式，求所有共多少拆分方式。据说类似于爬楼梯问题（并不知道是什么），可以直接使用DP。

• 令dp[i]表示解码s[:i]字符串所有可能的方式数目，则

  dp[i] = dp[i-1] if s[i-1] != '0'
  	  + dp[i-2] if '9' < s[i-2:i] < '27'

对于226：

令dp数组为[0,0,0,0]，初始化为[1,0,0,0]；

从第一个位置开始，输入为”2”，不为”0”，所以dp数组为[1,1,0,0]；

第2个位置，输入为”2”，不为”0”，所以dp数组为[1,1,1,0]；此时前两位数字是”22”，满足区间，所以变为[1,1,2,0]；

第3个位置，输入为”6”，不为”0”，所以dp数组为[1,1,2,2]；此时前两位数字是”26”，满足区间，所以变为[1,1,2,3]。

对于1211：

令dp数组为[0,0,0,0,0]，初始化为[1,0,0,0,0]；

从第一个位置开始，输入为”1”，不为”0”，所以dp数组为[1,1,0,0,0]；

第2个位置，输入为”2”，不为”0”，所以dp数组为[1,1,1,0,0]；此时前两位数字是”12”，满足区间，所以变为[1,1,2,0,0]；

第3个位置，输入为”1”，不为”0”，所以dp数组为[1,1,2,2,0]；此时前两位数字是”21”，满足区间，所以变为[1,1,2,3,0]。

第4个位置，输入为”1”，不为”0”，所以dp数组为[1,1,2,3,3]；此时前两位数字是”11”，满足区间，所以变为[1,1,2,3,5]。

对于270：

令dp数组为[0,0,0,0]，初始化为[1,0,0,0]；

从第一个位置开始，输入为”2”，不为”0”，所以dp数组为[1,1,0,0]；

第2个位置，输入为”7”，不为”0”，所以dp数组为[1,1,1,0]；此时前两位数字是”27”，不满足区间，所以dp数组仍然为[1,1,1,0]；

第3个位置，输入为”0”，为”0”，所以dp数组仍然为[1,1,1,0]；此时前两位数字是”70”，不满足区间，所以dp数组仍然为[1,1,1,0]。

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        for i in range(1, len(dp)):
            if s[i-1] != '0':  #当前字符是否为0
                dp[i] = dp[i-1]
                
            if i != 1 and '09' < s[i-2:i] < '27': #非第一个字符，当前字符与前面一位字符 在(9,27)之间
                dp[i] += dp[i-2]    #大于09是为了避免01这种情况
        return dp[-1]
        
print(Solution().numDecodings("1211"))

第一道完整的Leetcode，再接再厉，2019.08.20

【151】翻转字符串中的单词.md

📖 题目要求

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

💡 解题思路

class Solution:
    def reverseWords(self, s: str) -> str:
        #s=s.lstrip()   # 去掉两侧侧空格
        #s=s.rstrip()   
        list1 = s.split() # split会自动去除两侧空格
        ans=''
        for i in range(len(list1)-1,-1,-1):
            ans = ans + ' '+list1[i]
        return ans[1:]

【169】多数元素.md

📖 题目要求

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

💡 解题思路

• 首先，统计每个字符的个数
• 然后，然后个数大于 ⌊ n/2 ⌋ 的字符

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        
        # dict={}
        # for i in nums:    # 统计每个元素的数量
        #     #dict[i]=nums.count(i) 超时了
        #     if i in dict: # 如果该元素已经在字典中了
        #         dict[i]+=1
        #     else:         # 还没在字典中
        #         dict[i]=1
        dict = collections.Counter(nums) # 统计每个元素的数量

        for num in dict: # key索引
            if dict[num] > (len(nums) // 2): 
                return num

精简版，(并没有任何用处)

class Solution:
  def majorityElement(self, nums: List[int]) -> int:
    return [k for k, v in collections.Counter(nums).items() if v>len(nums)//2][0]

【198】打家劫舍.md

题目要求

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 

解题思路

输入长度为n的数组，表示n个房子的金额，求到第n个房子偷窃到的最高金额dp[n]。

一个典型的递归问题：

• 如果偷第n个房子的话，第n-1个房子不能偷，此时金额为$dp[n-2]+nums[n]$
• 如果不偷第n个房子的话，第n-1个房子可以偷，此时金额为$dp[n-1]$

因此，递归方程为$dp[n]=max(dp[n-1],dp[n-2]+nums[n])$

（1）空间复杂度$O(n)$

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0    
        if n == 1: return nums[0]
        
        dp = ['']*n
        dp[0] = nums[0] # 起始值，第一个状态：必偷第一个
        dp[1] = max(nums[0],nums[1]) # 第2个状态：前两个房子偷哪个
        
        for i in range(2,n):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i])
        return dp[n-1]

(2)空间复杂度O(1)

由于i只依赖于i-1和i-2两个状态，因此，只需要定义两个变量a,b存储i-1和i-2即可。

此时，递归方程变成：$dp[i]=max(a,b+nums[i])$

class Solution:
    def rob(self, nums: List[int]) -> int:
    	a,b = 0,0
        
        for i in range(len(nums)):
            cur = max(a,b+nums[i]) # 当前状态
            b = a # 更新第i-2个状态
            a = cur # 更新第i-1个状态
            
        return a

【242】有效的字母异位词

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:

输入: s = “rat”, t = “car”
输出: false

说明：可以假设字符串只包含小写字母。

解题思路

可以直接使用sorted暴力排序，也可以采用哈希表（将字符串的每个字符分别存入两个哈希表中，比较两个哈希表）。

• sorted排序 (52ms)

class Solution:
    def isAnagram(self, s, t) :
        return sorted(s) == sorted(t)  #sorted(iterable, cmp=None, key=None, reverse=False)

print(Solution().isAnagram('ast','asr'))

• 哈希映射 (52ms)

class Solution:
    def isAnagram(self, s, t) :  
        map1, map2 = {}, {}
        for i in s:
            map1[i] = map1.get(i, 0) + 1  #dict_name.get(key,default=None)
        for j in t:
            map2[j] = map2.get(j, 0) + 1  #如果输入的key在dict中，会返回对应key值，否则返回default
        return map1 == map2

print(Solution().isAnagram('asst','asr'))

• 用数组实现哈希表 (40ms)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        map1, map2 = [0]*26, [0]*26     #对应26个小写字母
        for c in s:
            map1[ord(c)-ord('a')] += 1  #ord()以一个字符作为参数，返回对应的 ASCII 数值
        for d in t:
            map2[ord(d)-ord('a')] += 1
        return map1 == map2
    
print(Solution().isAnagram('asst','asr'))

【289】生命游戏

📖 题目要求

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例：

输入： 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
输出：
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

进阶：

你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

💡 解题思路

（1）复制一个新的数组，仅用作检索

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        dx = [1,1,1,-1,-1,-1,0,0]  # 八个方向 
        dy = [0,1,-1,0,1,-1,1,-1]

        rows = len(board)
        cols = len(board[0])
		
        # 复制一个新的数组检索用
        copy_board = [[board[row][col] for col in range(cols)] for row in range(rows)]

        for i in range(rows):
            
            for j in range(cols):
                neighbor = 0
                # 搜索细胞周围的活细胞数目
                for c in range(8):
                    x = i + dx[c]
                    y = j + dy[c]
                    if x >= 0 and x < rows and y >=0 and y < cols and copy_board[x][y] == 1:
                        neighbor += 1
                # 当前细胞是活细胞，规则1 和 3
                if copy_board[i][j] == 1 and (neighbor<2  or neighbor>3):
                    board[i][j] = 0
                # 当前细胞是死细胞，规则4
                if copy_board[i][j] == 0 and neighbor == 3:
                    board[i][j] = 1                

• 检索的时候，可以就改原数组的状态，此时index正好有。
• 统计活细胞个数的话，也可以采用卷积的概念，但为了计算边缘细胞周围的活细胞，需要补0作zero padding，卷积核为[[1,1,1],[1,0,1],[1,1,1]]，参考链接。

（2）设计复合状态

首先，对规则进行简化：

• 原先是活细胞，周围有2-3个活细胞，存活
• 原先是死细胞，周围有3个活细胞，复活
• 其他都是死的

复合状态，通过每个格子对周围八个格子的影响来实现：如果当前细胞是活细胞，周围格子数字+1，这样十位保存活细胞个数信息，个位保存细胞存活与否信息。

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        dx = [1,1,1,-1,-1,-1,0,0]  # 八个方向 
        dy = [0,1,-1,0,1,-1,1,-1]

        rows = len(board)
        cols = len(board[0])
		
        # 活细胞，周围八个位置，加10
        for i in range(rows):          
            for j in range(cols):
                if board[i][j] % 10 == 1:   # 活细胞
                    for c in range(8): # 周围位置
                        x = i + dx[c]
                        y = j + dy[c]
                        if x >= 0 and x < rows and y >=0 and y < cols :
                            board[x][y] += 10
		
        # 更新状态
        for x in range(rows):
            for y in range(cols):
                value=board[x][y]
                if value//10==3:
                    board[x][y]=1
                elif value//10==2 and value%10==1:
                    board[x][y]=1
                else:
                    board[x][y]=0

【365】水壶问题

问题描述

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

• 装满任意一个水壶
• 清空任意一个水壶
• 从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1: (From the famous “Die Hard” example)

输入: x = 3, y = 5, z = 4
输出: True

示例 2:

输入: x = 2, y = 6, z = 5
输出: False

解题思路

贝祖原理：若a，b为整数，且他们的最大公约数为d，那么对于任意的整数x，y，ax+by都一定是d的倍数。

• 首先，两个水壶不可能同时有水且不满：因为，都有水则至少有一个水壶是满的；不满时，至少有一个水壶是空的或者满的。
• 其次，向一个不满的水壶直接加水是没有意义的（比如5L的水壶仅装了3L）：若另一只水壶是空的，相当于从初始状态直接给这只壶装满水；如果另一只水壶是满的，相当于从初始状态分别给两只壶装满水。
• 把一个不满的水壶里的水倒掉是没有意义的（比如5L的水壶仅装了3L）：若另一只水壶是空的，相当于把两只水壶回溯到初始状态；若另一只水壶是满的，相当于从初始状态直接给另外一只水壶加满水。

因此，每次操作只会让水壶里的水总量增加x，增加y，减少x，或者减少y。

因此，找到一对整数a,b使得$ax+by=z$且$z≤x+y$即可。而贝祖定理告诉我们，$ax+by=z$ 有解当且仅当 z 是 x, y 的最大公约数的倍数。

因此我们只需要找到 x, y的最大公约数并判断 z是否是它的倍数即可。

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if z == 0 or z == x or z == y  :  # 得到0升水、恰好有一个壶的容量跟目标一致
            return True 
        if z > x + y :   # 只有两个水壶，因此总量不能超出其和
            return False
        #这里用到了math库中的最大公约数方法gcd,如果z是最大公约的整数倍关系的时候，就可以取到
        return z % math.gcd(x,y) == 0

3 x - 1 y = z的具体过程解释：

• 倒满a（1）
• 将a倒到b
• 再次倒满a（2）
• 再次将a倒到b（a这个时候还剩下1升）
• 倒空b（-1）
• 将剩下的1升倒到b
• 将a倒满（3）
• 将a倒到b
• b此时正好是4升

【409】最长回文串

题目要求

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

解题思路

先统计每个字符的个数：

• 复数个的字符全都要
• 奇数个的字符仅取一个作为中心点，其他的舍弃

Class Solution:
	def longestpalindrome(self, s: str) -> int:
		con = collections.Counter(s) # 统计字符个数
		odd = 0 # 奇数
		for i in con.values():
			if i % 2 == 1:
				odd += 1
		return len(s) - max(odd-1,0)

【460】LFU缓存机制

📖 题目要求

设计实现最不经常用（Least Frequently Used）缓存机制，其支持get和put操作。

• get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
• put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

时间复杂度尽量保证为$O(1)$

💡 解题思路

LRU在容量满时，移除最后被访问时间最久远的元素。

• 访问完元素后，将其移到链表首部
• 容量满时，删除尾部元素，再将新元素插入到首部

而LFU在容量满时，移除最近使用次数最少的元素。

• 设计一个链表，其元素先按访问次数由大到小排序，同访问次数时，再按访问时间由近及远排序。
• 难点在于，更新元素位置。解决思路是，将其访问次数依次和之前的访问次数进行比较，找到合适的插入位置。
• 容量满时，删除尾部元素，再将新的元素插入到尾部

class DbListNode:
    def __init__(self, key, val, cnt=0):
        self.val = [key, val, cnt]#键、值、访问次数
        self.pre = None
        self.nxt = None

class LFUCache:
    def __init__(self, capacity: int):
        self.cache = {} #通过key保存链表节点，key:node
        self.cap = capacity#字典容量
        self.head = DbListNode(1, 1, float('inf'))#头节点，定义访问次数正无穷
        self.tail = DbListNode(-1, -1, float('-inf'))#尾节点，定义访问次数负无穷
        self.head.nxt = self.tail 
        self.tail.pre = self.head

    def _refresh(self, cur, cnt): # 辅助函数，对节点node，以访问次数cnt重新定义其位置
        pNode, nNode = cur.pre, cur.nxt # 当前节点的前后节点
        if cnt < pNode.val[2]: # 如果访问次数小于前节点的访问次数，无需更新位置
            return
        pNode.nxt, nNode.pre = nNode, pNode # 将node从原位置剔除
        while cnt >= pNode.val[2]: # 找到插入位置
            pNode = pNode.pre
        nNode = pNode.nxt
        pNode.nxt = nNode.pre = cur # 插入
        cur.pre, cur.nxt = pNode, nNode

    def get(self, key: int) -> int:
        if self.cap <= 0 or key not in self.cache:# 容量<=0或者key不在字典中
            return -1
        cur = self.cache[key]#通过字典找到节点
        _, value, cnt = cur.val#通过节点得到key，value和cnt
        cur.val[2] = cnt+1#访问次数+1
        self._refresh(cur, cnt+1)#刷新位置
        return value

    def put(self, key: int, value: int) -> None:
        if self.cap <= 0:  #缓存容量<=0
            return
        if key in self.cache: # 已在字典中，则要更新其value，同时访问次数+1刷新位置
            cur = self.cache[key]
            _, _, cnt = cur.val
            cur.val = [key, value, cnt+1]# 更新其值
            self._refresh(cur, cnt+1)
        else:
            if len(self.cache) >= self.cap: # 容量已满，先清除掉尾部元素
                self.cache.pop(self.tail.pre.val[0]) # 从字典剔除尾节点
                self.tail.pre.pre.nxt, self.tail.pre = self.tail, self.tail.pre.pre 
            # 新建节点，并先插入到队尾;LRU的话，是先插入到首部
            cur = DbListNode(key, value)
            self.cache[key] = cur
            cur.pre, cur.nxt = self.tail.pre, self.tail
            self.tail.pre.nxt, self.tail.pre = cur, cur
            # 更新位置
            self._refresh(cur, 0)

• 时间复杂度：$O(n)$
• 空间复杂度：$O(capacity)$

两个哈希表+双向链表

创建两个哈希表，分别为freq_table和key_table：

• freq_table 以频率 freq 为索引，每个索引存放一个双向链表，这个链表里存放所有使用频率为 freq 的缓存，缓存里存放三个信息，分别为键 key，值 value，以及使用频率 freq。
• key_table以键值 key 为索引，每个索引存放对应缓存在 freq_table 中链表里的内存地址。

采用临时变量minFreq记录最少使用到的频率，get和put操作实现逻辑如下：

• get操作时，通过key在key_tabel中寻找缓存链表地址：若能找到，返回key对应的值，之后freq加一，在Freq_tabel中更新缓存位置。将其插入到freq+1索引下链表的顶部（这样底部元素就是访问时间最久远的，便于删除）。

class Node:
    def __init__(self, key, val, pre=None, nex=None, freq=0):
        self.pre = pre
        self.nex = nex
        self.freq = freq 
        self.val = val
        self.key = key
        
    # 在self后面插入节点node
    def insert(self, node):
        node.pre = self
        node.nex = self.nex
        self.nex.pre = node
        self.nex = node # 要在node.nex = self.nex之后
    

def create_linked_list():
    head = Node(0, 0)
    tail = Node(0, 0)
    head.nex = tail
    tail.pre = head
    return (head, tail)

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.minFreq = 0  # 最小访问次数
        self.freqMap = collections.defaultdict(create_linked_list) # 记录次数
        self.keyMap = {} # 记录缓存在上面哈希表的索引地址

    ## 删除节点
    def delete(self, node):
        if node.pre:
            node.pre.nex = node.nex 
            node.nex.pre = node.pre  # 已删除
            if node.pre is self.freqMap[node.freq][0] and node.nex is self.freqMap[node.freq][-1]: # node的前节点是freqMap[node.freq]的底部节点，node的后节点是freqMap[node.freq]的顶部节点
                self.freqMap.pop(node.freq)
        return node.key

    ## 访问次数加一，并更新节点node位置        
    def increase(self, node):
        node.freq += 1  # 访问频率加一
        self.delete(node)  # 删除原freq位置的节点
        self.freqMap[node.freq][-1].pre.insert(node) # freqMap[node.freq][-1].pre是head, 首部插入节点
        if node.freq == 1: # 刚加入
            self.minFreq = 1
        elif self.minFreq == node.freq - 1:
            head, tail = self.freqMap[node.freq - 1]
            if head.nex is tail: # 空的链表？
                self.minFreq = node.freq

    def get(self, key: int) -> int:
        if key in self.keyMap: 
            self.increase(self.keyMap[key]) # 访问次数加一，并更新节点位置
            return self.keyMap[key].val  # 返回value
        return -1

    def put(self, key: int, value: int) -> None:
        if self.capacity != 0:
            if key in self.keyMap:
                node = self.keyMap[key] # 得到key对应的缓存地址
                node.val = value # 更新value值
            else:
                node = Node(key, value) # key不在keyMap时，新建节点
                self.keyMap[key] = node
                self.size += 1
            if self.size > self.capacity:  # 缓存满了
                self.size -= 1
                deleted = self.delete(self.freqMap[self.minFreq][0].nex) # 删除freqMap中min_freq 处对应的双向链表中的尾部节点，返回key值
                self.keyMap.pop(deleted)  # 
            self.increase(node)

【543】二叉树直径

题目要求

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :
给定二叉树

    1
   / \
  2   3
 / \     
4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

解法

二叉树的直径（即最长路径），不一定经过根结点。

二叉树问题判断能否转换为子问题：

二叉树的最长路径=max{左子树的最长路径，右子树的最长路径，经过根节点的最长路径}

其中，经过根节点的最长直径等于左子树的深度加上右子树的深度，因此

二叉树的最长路径=max{左子树的最长路径，右子树的最长路径，左子树深度+右子树深度}

二叉树直径问题，转换为子问题：子树的最长路径、子树的最大深度。

class Solution:
        def diameterOfBinaryTree(self,root: TreeNode) -> int:
            depth, diam = self.traverse(root)
            return diam 

        # 返回二元 tuple (depth, diameter)
        # depth 表示子树的最大深度，diameter 表示子树的最长路径（直径）
        def traverse(self,root):
            if root is None:  return (0, 0)

            left_depth, left_diam = self.traverse(root.left)
            right_depth, right_diam = self.traverse(root.right)
            
            depth = 1 + max(left_depth, right_depth) # 求二叉树深度
            diam = max(left_diam, right_diam, left_depth + right_depth) # 直径
            return depth, diam

【695】岛屿的最大面积

题目描述

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

解题思路

我们想知道岛屿的最大面积，可以先找出所有的连通区域的面积，然后取最大值

如果我们在一个土地上，以 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积。

为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 0

class Solution:
    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i == len(grid) or j == len(grid[0]) or grid[i][j] != 1:
            return 0
        grid[i][j] = 0 # 访问过的岛屿置0，防止再次访问
        ans = 1

        top= self.dfs(grid,i+1,j) # 四个方向
        bottom=self.dfs(grid,i-1,j)
        left=self.dfs(grid,i,j+1)
        right=self.dfs(grid,i,j-1)
        return 1+sum([top,bottom,left,right])

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                ans = max(self.dfs(grid, i, j), ans)
        return ans

【820】单词的压缩编码

题目描述

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是["time", "me", "bell"]，我们就可以将其表示为S = "time#bell#" 和 indexes = [0, 2, 5]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到"#"结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

示例：

输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5] 。

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
每个单词都是小写字母 。

解题思路

（1）先翻转再排序

本题的基本思路是：如果有一对单词 s 和 t，使得 t 是 s 的后缀，例如 me 是 time 的后缀，我们就删掉单词 t。最后剩下来的单词，就是构成索引字符串的单词。

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        length = len(words)
        #reversed_words = [word[::-1] for word in words]
        reversed_words = []
        for word in words:
            reversed_words.append(word[::-1])    # 反转每个word
        reversed_words.sort()  # 排序
        
        cnt = 0
        for i in range(length):
            if i+1 < length and reversed_words[i+1].startswith(reversed_words[i]):
                pass
            else:
                cnt += len(reversed_words[i]) + 1
        
        return cnt            

（2）构建字典树/Trie树

Tire树，也称字典树，是一种专门处理字符串匹配的树形数据结构，常用来解决在一组字符串集合中中快速查找某个字符串的问题。Tire树的本质是利用字符串之间的公共前缀，将重复的前缀合并在一起。

本题字典树解法的基本思路为：

• 先去list按照字符串长度由长到短进行排序，避免em和emit都可以插入到Trie树这种情况
• 将每个字符串倒序，并插入到Trie树中
• 统计可以插入到Trie树中的字符串的长度

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        length = 0
        tire = Tire()
        words.sort(key = lambda s: len(s),reverse = True)  # 根据字符串长短排序
        #print(words)
        for word in words: 
            length += tire.insert(word[::-1])
        return length

class Tire:
     ### 初始化，存储无意义字符（根节点root）
    def __init__(self):
        self._root = TrieNode("")  
        
	### 插入字符串
    def insert(self, text: str) -> None:  
        node = self._root
        is_new = False
        # 字符串text中的每个字符都调用lamda表达式，其中ord求ASCII值 
        for index, char in map(lambda x: (ord(x) - ord("a"), x), text):   
            if not node._children[index]:  # node._children[index] 为空，Trie树还没有该字符
                is_new = True
                node._children[index] = TrieNode(char) # 插入字符
            node = node._children[index] # ???
        if is_new:  
            return len(text) + 1  
        else: 
            return 0

class TrieNode:
    def __init__(self, data: str):
        self._data = data
        self._children = [None] * 26 

（3）排序后直接搜索

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        words.sort(key= lambda s: len(s),reverse=True)  # 由长到短排序
        wide_str= words[0]+'#'
        for i in words:
            if wide_str.find(i+'#') == -1:    # 该单词不在里面（#不可省，避免跨单词）
                wide_str = wide_str + i + '#'  # 添加到里面
            else:
                continue
        return len(wide_str)

【836】矩阵重叠

题目要求

矩形以列表[x1, y1, x2, y2]的形式表示，其中(x1, y1)为左下角的坐标，(x2, y2)是右上角的坐标。

如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形，判断它们是否重叠并返回结果。

示例 1：

输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

示例 2：

输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false

说明：

两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。
矩形中的所有坐标都处于 -10^9 和 10^9 之间。

解题思路

重叠的情况比较多，可以转换为考虑非重叠的问题。

• x轴，矩阵终点的坐标 小于等于 另一个矩阵起点的坐标；
• y轴，同理

x轴、y轴都重叠时，两个矩阵重叠

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        x=not(rec1[2] <= rec2[0] or rec2[2] <= rec1[0])
        y=not(rec1[3] <= rec2[1] or rec2[3] <= rec1[1])
        return x and y

【876】链表中心节点

题目要求

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

解题思路

快慢指针法

设置快、慢两个指针，快指针每次走两格，慢指针每次走一格；当快指针走到链表尾端时，慢指针恰好在链表中心点。

需注意偶数个节点时，判断条件的确定。

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = head 
        fast = head 
        while fast and fast.next: # 此处需要的是第二个节点。若为第一个节点，应改为while fast.next and fast.next.next
            slow = slow.next
            fast = fast.next.next
        return slow        

相关

【1】Leetcode链表整理

【887】鸡蛋掉落

📖 题目要求

求最少扔多少次鸡蛋，可以得到边界楼层F所在的层数。

边界楼层是指：当不高于该层的楼层扔鸡蛋时，鸡蛋不会碎，可以再次扔；从高于该层的楼层扔鸡蛋时，鸡蛋会碎，无法再次使用

💡 解题思路

动态规划+二分法

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # 动态规划 + 二分搜索
        memo = {}   # 记忆化递归
        # dp(K,N) 为在状态 (K, N) 下最少需要的步数
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    # 二分查找t1和t2的交点
                    # 离函数交点左右两侧最近的整数
                    # 找到最大满足t1 < t2的left
                    # 以及最小满足t1 > t2的right
                    l, r = 1, n
                    # r = l + 1(夹住交点)
                    while l + 1 < r:
                        x = (l + r) >> 1 # 二分
                        # 鸡蛋碎了之后接下来需要的步数,随 X 的增加而单调递增的函数
                        t1 = dp(k-1, x-1)
                        # 鸡蛋没碎之后接下来需要的步数,随 X 的增加而单调递减的函数                        
                        t2 = dp(k, n-x)
                        # 在x右侧，刷新左侧边界值
                        if t1 < t2:
                            l = x
                        # 在x左侧，刷新右侧边界值
                        elif t1 > t2:
                            r = x
                        # 找到交点
                        else:
                            l = r = x
                    # 比较l和r的函数最大值取最小值
                    ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x)) for x in (l, r))  # x=l和x=r两种情况
                memo[k, n] = ans
            return memo[k, n]
        return dp(K, N)

【892】三维物体的表面积

题目描述

在 N N 的网格上，我们放置一些 1 1 * 1 的立方体。

每个值 $v = grid[i][j] $表示 v 个正方体叠放在对应单元格 (i, j) 上。

请你返回最终形体的表面积。

示例 1：

输入：[[2]]
输出：10

示例 2：

输入：[[1,2],[3,4]]
输出：34

示例 3：

输入：[[1,0],[0,2]]
输出：16

示例 4：

输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：32

示例 5：

输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：46

提示：

1 <= N <= 50
0 <= grid[i][j] <= 50

解题思路

示例5所描述的立方体长这样：

对于该题，可以先不管立体图形形状如何，我们可以先求出所有立方体的总表面积，然后再减去重叠部分即可

假设一共有n个立方体，则总表面积为6n；若这些有e个接触面，则减去2e，最终的表面积为6n-2e

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        cubes = 0
        faces = 0
        for i in range(len(grid)):
            for j in range(len(grid)):
                
                cur = grid[i][j]
                left = grid[i-1][j]  
                down = grid[i][j-1]  
                
                if cur > 0:
                    cubes += cur # 求所有立方体的个数
                    faces += cur -1 # 叠起来的v个立方体，有v-1个接触面               
                if i > 0:       # 当前立方体和左边立方体的解除面
                    faces += min(cur,left)
                if j > 0 :      # 当前立方体下面立方体的接触面
                    faces += min(cur,down)
                    
        return 6*cubes - 2*faces

【941】卡牌分组

题目要求

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

每组都有 X 张牌。
组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。

示例 1：

输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

示例 2：

输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。

示例 3：

输入：[1]
输出：false
解释：没有满足要求的分组。

示例 4：

输入：[1,1]
输出：true
解释：可行的分组是 [1,1]

示例 5：

输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]

提示：

1 <= deck.length <= 10000
0 <= deck[i] < 10000

解题思路

开始的思路是先统计每个元素的数量，如果每个元素的个数相等，则返回True。经测试发现忽略了[1,1,2,2,2,2]等情况。

因此，最终考虑采用最大公约数来解决：每组都有X张牌，则X必然为 每个元素的个数 的公约数；若最大公约数大于2，则返回True

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        if len(deck) < 2:
            return False
        cnt=list(collections.Counter(deck).values())  # 不要忘了list
        return reduce(gcd,cnt) >= 2  # reduce函数会将列表cnt中的元素均进行gcd操作

【945】使数组唯一的最小增量

题目描述

给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。

返回使 A 中的每个值都是唯一的最少操作次数。

示例 1:

输入：[1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

示例 2:

输入：[3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

提示：

0 <= A.length <= 40000
0 <= A[i] < 40000

解题思路

（1）先排序再遍历计数

首先对数组元素进行排序，然后遍历数组：

• 如果当前元素大于前一个元素，保存不变；
• 如果当前元素小于等于前一个元素，将该元素增大为 前一个元素+1

比如，输入为[3,2,1,2,1,7]，排序后为[1,1,2,2,3,7]，遍历过程如下所示：

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort() # 排序
        res = 0
        # 遍历数组
        for i in range(len(A)):
            if(i>0 and A[i] <= A[i-1]): # 注意i=0,不然A[-1]倒着数了。
                ai = A[i-1] + 1
                res += ai -A[i]
                A[i] = ai
        return res    

【999】车的可用捕获数量

题目描述

在一个 8 x 8 的棋盘上，有一个白色车（rook）。也可能有空方块，白色的象（bishop）和黑色的卒（pawn）。它们分别以字符 “R”，“.”，“B” 和 “p” 给出。大写字符表示白棋，小写字符表示黑棋。

车按国际象棋中的规则移动：它选择四个基本方向中的一个（北，东，西和南），然后朝那个方向移动，直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外，车不能与其他友方（白色）象进入同一个方格。

返回车能够在一次移动中捕获到的卒的数量。

解题思路

先暴力枚举发现白车的位置，然后从此位置出发，上下左右四个方向开始搜索

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        # 定义上下左右四个方向
        dx = [-1,1,0,0]
        dy = [0,0,-1,1] 

        for i in range(8):
            for j in range(8):
                if board[i][j] == 'R':  # 发现了白车的位置
                    cnt = 0
                    for k in range(4):
                        x,y = i,j
                        while(1): # 从白车所在位置出发， 延一个方向（上/下/左/右）一直搜索直到退出
                            x += dx[k]
                            y += dy[k]
                            if (x<0 or x>7 or y<0 or y>7 or board[x][y]=='B'): # 到达边界或者遇到白象
                                break
                            if (board[x][y]=='p'):
                                cnt += 1
                                break
                    return cnt
        return 0

【1013】数组三等分

题目要求

给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + A[j-1] + … + A[A.length - 1]) 就可以将数组三等分。

示例 1：

输出：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2：

输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false

示例 3：

输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

解决方法

class Solution:
    def canThreePartsEqualSum(self, A: List[int]) -> bool:
        s=sum(A)
        if s%3 !=0:  # 是否是3的倍数，即总和是否能被分成三部分
            return False

        i,z=0,0
        length=len(A)
        target=s/3

        while i<length: # 找到第一个切割点
            z=z+A[i]
            if z==target:
                break
            i+=1
        
        j=i+1
        while j+1<length:
            z=z+A[j]
            if z==target*2: # 存在第二个切割点，则必然存在第三段
                return True 
            j=j+1
        return False

• 时间复杂度：$O(n)$ ，其中n为数组A的长度
• 空间复杂度：$O(1)$，只需要存储i，z，length，target等的信息即可

贪心算法？

【1071】字符串中的最大公因子

题目要求

对于字符串 S 和 T，只有在 S = T + … + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

示例 1：

输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"

示例 2：

输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"

示例 3：

输入：str1 = "LEET", str2 = "CODE"
输出：""

提示：

1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母

解题方法

1.枚举

输出的最长字符串X，可以同时除尽str1和str2，则其长度必然是str1长度和str2长度的公因子，即：

$$(len_1 \quad mod \quad len_x=0 )and (len_2 \quad mod \quad len_x=0)$$

因此，我们可以逐个测试X的长度，长度从大到小枚举字符串，碰到第一个匹配的立即返回

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        for i in range(min(len(str1), len(str2)), 0, -1): # 从大到小开始枚举
            if (len(str1) % i) == 0 and (len(str2) % i) == 0:
                if str1[: i] * (len(str1) // i) == str1 and str1[: i] * (len(str2) // i) == str2:
                    return str1[: i]
        return ''

2.递归

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ''
        
        difference = len(str1) - len(str2)
        
        if difference == 0:
            return str1
        elif difference > 0: # str1长度更长，缩短str1
            str1 = str1[ len(str2) : len(str1)]
        else: # str2长度更长，缩短str2
            str2 = str2[ len(str1) : len(str2)]
        
        return self.gcdOfStrings(str1,str2) # 不要忘了self

复杂度？？

【1111】有效括号的嵌套深度

📖题目要求

给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，并使这两个字符串的深度最小。

划分方案用一个长度为 seq.length 的答案数组 answer 表示，编码规则如下：

• answer[i] = 0，seq[i] 分给 A 。
• answer[i] = 1，seq[i] 分给 B 。

如果存在多个满足要求的答案，只需返回其中任意 一个即可。

示例 1：

输入：seq = "(()())"
输出：[0,1,1,1,1,0]

示例 2：

输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]

💡解题思路

类似于力扣20题求有效括号，此题，也借助于栈来解题。

该题要求分出的两个字符串深度$depth(A+B)=max(depth(A),depth(B))$最小，使 深度较大的字符串 深度最小即可。

括号序列   ( ( ) ( ( ) ) ( ) )
嵌套深度   1 2 2 2 3 3 2 2 2 1 
一种答案   0 1 1 1 0 0 1 1 1 0

而要使得 max(depth(A), depth(B)) 的可能取值最小，可参考二叉树，二叉树平衡时深度最小，一个可行的做法是：把栈中连续出现的左括号 ( 根据奇偶性分到不同的组，右括号随与之匹配左括号的组号.

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        ans = []
        depth = 0
        
        for i in seq:
            if i == '(' :
                depth += 1
                ans.append((depth+1) & 1)  # 奇数层赋值0，偶数层赋值1
            else:
                ans.append((depth+1) & 1)   # 奇数层赋值0，偶数层赋值1
                # 当前还是depth层，执行完上述操作后，层数再减1，实现一层完整的括号。重新k开始计算层数
                depth -=1     
                
        return ans

【1160】字符串拼写

题目要求

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

示例 1：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例 2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

解题思路

• 首先，统计char中每个字符的数量m，
• 然后，统计words中每个单词的每个字符的数量n
  • 对于某个单词来说，只要所有的m都大于等于n，则可以组成该单词。

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        ans=0
        m=collections.counter(chars) # 统计每个字符的个数，返回的是一个字典
        for word in words:
            n=collections.counter(word) # 统计每个字符个数
            if all(m[i] >= n[i] for i in n) # 对于每个字符
            	ans=ans+len(word)
        return ans

all() 函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 TRUE，如果是返回 True，否则返回 False。

元素除了是 0、空、None、False 外都算 True。

【1162】地图分析

题目描述

你现在手里有一份大小为N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。

我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。

如果我们的地图上只有陆地或者海洋，请返回 -1。

示例 1：

输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。

示例 2：

输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释： 
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。

提示：

1 <= grid.length == grid[0].length <= 100
grid[i][j] 不是 0 就是 1

解题思路

要求海洋格子到陆地格子的最长路径，可以：

先发现所有的陆地，然后一层一层的遍历，知道最后占满整张地图，结束。

@sweetiee：你可以想象成你从每个陆地上派了很多支船去踏上伟大航道，踏遍所有的海洋。每当船到了新的海洋，就会分裂成4条新的船，向新的未知海洋前进（访问过的海洋就不去了）。如果船到达了某个未访问过的海洋，那他们是第一个到这片海洋的。很明显，这么多船最后访问到的海洋，肯定是离陆地最远的海洋。

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        queue = []
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]  # 方向向量
        distance = -1
        N = len(grid)

        # 将所有的陆地格子加入队列
        for i in range(N):
            for j in range(N):
                if grid[i][j] == 1:
                    queue.append([i, j])
                    
        # 地图上只有陆地或者海洋时，返回 -1。
        if len(queue) == 0 or len(queue) == N * N:
            return -1
		
		# BFS搜索        
        while queue:
            distance += 1
            n = len(queue)
            for _ in range(n): # 一层一层的来
                x_old, y_old = queue.pop(0)
                for i in range(4):
                    x = x_old + dx[i]
                    y = y_old + dy[i]
                    if x>=0 and x<N and y>=0 and y<N and grid[x][y] == 0: # 发现海洋
                            grid[x][y] = 1  # 已访问过；运行到最后，全为1了，不再上述判断条件了，退出
                            queue.append((x, y))  # 下一层的数据
        return distance

因此，BFS的基本思路可提取为：

depth = 0 # 记录遍历到第几层
while queue 非空:
    depth++ 
    n = queue 中的元素个数
    for _ in range(n): # 循环n次，遍历完本层数据
        node = queue.pop() 
        for node 的所有相邻结点 m:
            if m 未访问过:
                queue.push(m) # 获取下一层的数据

获取邻居区域，也可以用四个if语句，速度比循环快，但看成有点繁琐。。

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        queue = [] # 存储陆地
        distance = -1

        # 将所有的陆地格子加入队列
        for i in range(N):
            for j in range(N):
                if grid[i][j] == 1:
                    queue.append([i, j])
        # 地图上只有陆地或者海洋，返回 -1。
        if len(queue) == 0 or len(queue) == N * N:
            return -1

        while queue:
            distance += 1
            n = len(queue)
            for _ in range(n):
                x, y = queue.pop(0)
                
                if x-1 >= 0 and grid[x-1][y] == 0:  # 遍历左边单元格，寻找海洋
                    grid[x-1][y] = 2
                    queue.append((x-1, y))
                if x+1 < N and grid[x+1][y] == 0:   # 遍历右边单元格，寻找海洋
                    grid[x+1][y] = 2
                    queue.append((x+1, y))
                if y-1 >= 0 and grid[x][y-1] == 0:  # 遍历下边单元格，寻找海洋
                    grid[x][y-1] = 2
                    queue.append((x, y-1))
                if y+1 < N and grid[x][y+1] == 0:   # 遍历上边单元格，寻找海洋
                    grid[x][y+1] = 2
                    queue.append((x, y+1))

        return distance

【面试题01.07】旋转矩阵

📖 题目要求

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。设计一种算法，将图像旋转 90 度。尽量不占用额外内存空间

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

💡 解题思路

矩阵旋转就是，先上下翻转，再对角线翻转

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix[:]=matrix[::-1]
        for i in range(len(matrix)):
            for j in range(i):
                matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]

【面试题13】机器人的运动范围

📖 题目要求

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

💡 解题思路

（1）DFS

• 递归参数： 当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 si, sj 。
• 终止条件： 当 ① 行列索引越界 或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过 时，返回 00 ，代表不计入可达解。
• 递推工作：
  • 标记当前单元格 ：将索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
  • 搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。
• 回溯返回值： 返回 1 + 下方搜索的可达解总数 + 右方搜索的可达解总数，代表从本单元格递归搜索的可达解总数

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def dfs(i, j, si, sj):
            if i >= m or j >= n or si + sj > k or (i, j) in visited: return 0
            visited.add((i,j))
            return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8)

        visited = set()
        return dfs(0, 0, 0, 0)

数位和增量计算公式：$x$的数位和为$Sx$，$x+1$的数位和为$S{x+1}$

• 当(x+1)%10= =0时，$S_{x+1}=S_x-8$，如$x=19$，则19、20的数位和为10，2
• 当(x+1)%10!= 0时，$S_{x+1}=S_x+1$，如$x=17$，则17、18的数位和为8，9

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def dfs(i, j, m,n,k):
            if i >= m or j >= n or (i%10+i//10+j%10+j//10)>k or (i, j) in visited: 
                return 0
            visited.add((i,j))
            return 1 + dfs(i + 1, j, m,n,k) + dfs(i, j + 1, m,n,k)

        visited = set()
        return dfs(0, 0, m, n,k)

a=Solution()
print(a.movingCount(3,1,0))

【面试题】完全背包