30道经典算法面试题

1. 无重复字符的最长子串

给定一个字符串，找出不含有重复字符的最长子串的长度。

原题：3. 无重复字符的最长子串

难度：中等

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n < 2:
            return n

        left = right = max_len = 0
        while left <= right < n:
            if s[right] in s[left:right]:
                while left <= right and s[right] in s[left:right]:
                    left += 1
            right += 1
            max_len = max(max_len, right - left)

        return max_len

上述算法每次比较都会遍历为O(right-left)，优化一下成hash集合即可

注意如果是用set()来存储数据的话不能用pop()而是要明确的删除该值，那么就需要维护一个left指针，麻烦

from collections import OrderedDict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n < 2:
            return n

        max_len = cur_len = 0
        tmp = OrderedDict()
        for i in range(n):
            while s[i] in tmp:
                tmp.popitem(last=False)
                cur_len -= 1
            tmp[s[i]] = 1
            cur_len += 1
            max_len = max(max_len, cur_len)
        return max_len

2. 整数反转

给定一个 32 位有符号整数，将整数中的数字进行反转。

原题：7. 整数反转

难度：简单

没什么东西，注意python的int不能遍历，需要转成str再翻转

class Solution:
    def reverse(self, x: int) -> int:
        s = str(x)[::-1]
        res = -int(s[:-1]) if x < 0 else int(s)
        return res if -2**31 <= res <= 2**31 - 1 else 0

当然这是一种做法还有一种做法就是数学方法来解

注意这里去绝对值是因为python//取余数的话123//10=13

class Solution:
    def reverse(self, x: int) -> int:
        res, y = 0, abs(x)
        out = 1<<31 if x > 0 else (1<<31)-1
        while y != 0:
            pop = y % 10
            res = res * 10 + pop
            if res > out:
                return 0
            y //= 10
        return res if x > 0 else -res

3. 字符串转换整数 (atoi)

实现 atoi，将字符串转为整数。

原题：8. 字符串转换整数 (atoi)

难度：中等

这题肯定不是要你直接int()的了。。

题目很难度：简单但是要注意一些特例和边界问题

首先去空格然后分析第一位是+-值或者是数字还是其它字符串

然后对每一轮结果做一个判断边界

比较麻烦的就是边界的处理对应正负值的不同比较和返回

class Solution:
    def myAtoi(self, str: str) -> int:
        s = str.lstrip()
        if not s:
            return 0
        flag = True
        if s[0] == '-':
            flag = False
            s = s[1:]
        elif s[0] == '+':
            s = s[1:]
        res = i = 0
        bo = (1 << 31) - 1 if flag else 1 << 31
        while i < len(s) and s[i].isdigit():
            res = res * 10 + int(s[i])
            if res > bo:
                return (1 << 31) - 1 if flag else -1 << 31
            i += 1
        return res if flag else -res

4. 盛最多水的容器

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

原题：11. 盛最多水的容器

难度：中等

双指针双向往中间移动

至于某些没有涉及到的面积比如这题的2-7

面积的高度依赖于更小的那个，那么肯定是小于长度比它长的1-7

所以中间的都不用去计算

class Solution:
    def maxArea(self, height: List[int]) -> int:
        if not height:
            return 0
        n = len(height)
        max_len, left, right = 0, 0, n - 1
        while left < right:
            max_len = max(max_len, min(height[left], height[right]) * (right - left))
            if height[left] > height[right]:
                right -= 1
            else:
                left += 1
        return max_len

5. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。

原题：14. 最长公共前缀

难度：简单

res = compare(compare(compare(s1,s2),s3),s4)

自然想到了使用reduce来解

进阶版可以考虑到搜索引擎的思路，维护一个树，当出现不同时，新增一个分支，最后返回一个最长公共前缀

from functools import reduce
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''

        def helper(x, y):
            res = []
            i = 0
            while i < min(len(x), len(y)):
                if x[i] == y[i]:
                    res.append(x[i])
                    i += 1
                else:
                    break
            return ''.join(res)

        return reduce(helper, strs)

6. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

原题：35. 搜索插入位置

难度：简单

因为是排序数组，最难度：简单的就是直接遍历返回即可

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        for i in range(n):
            if nums[i] >= target:
                return i
        return n

上述时间复杂度是O(N)

为了减少时间复杂度可以用二分法减少到O(logN)

稍微复杂点因为要处理边界问题([1,3],2)和([1,3],3)和([1,3],4)的处理需要谨慎

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n - 1
        while left < right:
            mid = (right + left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid
            else:
                left = mid + 1
        return left if target <= nums[right] else n

7. 跳跃游戏

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

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

原题：55. 跳跃游戏

难度：中等

首先猜测这是一个动态规划

但是能做的还是先用暴力法

reversed是先从大到小跳跃，尽可能减少次数

当然了超时了

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        def helper(pos):
            if pos >= n - 1 or nums[pos] >= n - 1:
                return True

            for i in reversed(range(pos + 1, pos + nums[pos] + 1)):
                if helper(i):
                    return True
            return False

        return helper(0)

从底到上的动态规划

边界就是最后一个值肯定能到达自己从这里往前推注意去最小值防止越界

但是这里python还是超时了(-_-||)

看来python想ac就得用最优解了

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        # 0 未处理  1 好坐标
        status = [0 for _ in range(n)]
        status[n - 1] = 1
        for i in reversed(range(n - 1)):
            max_move = min(n - 1, i + nums[i])
            for j in range(i + 1, max_move + 1):
                if status[j] == 1:
                    status[i] = 1
                    break

        return status[0] == 1

最优解其实很难度：简单，需要稍微思考一下，从右开始只要能到达终点的就是好坐标，那么能到达好坐标的也就是好坐标，推导下来，能到达最左边的好坐标就可以标记为好坐标

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        left_index = n - 1
        for i in reversed(range(n - 1)):
            if i + nums[i] >= left_index:
                left_index = i
        return left_index == 0

还有种思路最远能到达的位置大于终点即可

max_i >= i保证能到达i位置防止[3,2,1,0,4]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        max_i = 0
        for i, jump in enumerate(nums):
            if max_i >= i and i + jump > max_i:
                max_i = i + jump
            if max_i >= n - 1:
                return True
        return False

8. 旋转图像

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

原题：48. 旋转图像

难度：中等

在纸上多画画先对中翻转再左下右上斜对角

然后用代码实现即可

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

9. 二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。 (即逐层地，从左到右访问所有节点)。

原题：102. 二叉树的层次遍历

难度：中等

深度优先搜索DFS depth first search

用层数来给各级别节点空列表append

先想到了递归写出来再尝试迭代减少栈的空间占用

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return res
        
        def helper(node, level):
            if len(res) == level:
                res.append([])
            res[level].append(node.val)
            if node.left:
                helper(node.left, level + 1)
            if node.right:
                helper(node.right, level + 1)

        helper(root, 0)
        return res

这道题更直观的是用广度优先搜索BFS breadth first search

使用一个双向队列(deque，这里我用的是列表，还可以from collections import deque)

把每一层的放到队列中再全部出队列进行append处理

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return res
        level = 0
        deque = [root]
        while deque:
            res.append([])
            n = len(deque)
            for i in range(n):
                node = deque.pop(0)
                res[level].append(node.val)
                if node.left:
                    deque.append(node.left)
                if node.right:
                    deque.append(node.right)
            level += 1
        return res

10. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?

原题：136. 只出现一次的数字

难度：简单

这道题属于难度：简单我是没想到的因为限定死了不使用额外空间

所以只能使用异或运算

还有道题类似，不过那个题限定整数有个范围，可以使用每个数乘以等于-1 这样两次循环，最后负数的坐标就是该值

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(1, n):
            nums[i] = nums[i - 1] ^ nums[i]
        return nums[-1]

或者这么写

from functools import reduce
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)

11. 只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

原题：137. 只出现一次的数字 II

难度：中等

不懂需要好好学习位运算以及怎么运用

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen_once = seen_twice = 0
        
        for num in nums:
            # first appearance: 
            # add num to seen_once 
            # don't add to seen_twice because of presence in seen_once
            
            # second appearance: 
            # remove num from seen_once 
            # add num to seen_twice
            
            # third appearance: 
            # don't add to seen_once because of presence in seen_twice
            # remove num from seen_twice
            seen_once = ~seen_twice & (seen_once ^ num)
            seen_twice = ~seen_once & (seen_twice ^ num)

        return seen_once

12. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

原题：148. 排序链表

难度：中等

O(n log n)基本就意味着归并法

快慢指针找中心点递归合并

但是一看常数级空间复杂那就意味着不能用递归，因为会产生占空间

那就尝试从第一层两两排序，到第二层4 4排序直到最高层

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # 4, 3, 2, 6, 5, 7, 1
        level, h, size, res = 1, head, 0, ListNode(0)
        res.next = head
        while h:
            h = h.next
            size += 1

        level, node = 1, head
        while level < size:
            pre, h = res, res.next
            while h:
                h1, i = h, level
                while i and h:
                    h = h.next
                    i -= 1
                if i:
                    break  # 可能存在第一个都不满 不需要和后面进行排序了例如总长度为6：4, 3, 2, 6, 5, 7的5, 7
                h2, i = h, level
                while i and h:
                    h = h.next
                    i -= 1
                l1, l2 = level, level - i  # 右部分可能不足level长度 例如 5, 7和1
                while l1 and l2:
                    if h1.val < h2.val:
                        pre.next, h1 = h1, h1.next
                        l1 -= 1
                    else:
                        pre.next, h2 = h2, h2.next
                        l2 -= 1
                    pre = pre.next
                pre.next = h1 if l1 else h2
                while l1 > 0 or l2 > 0:
                    pre = pre.next
                    l1 -= 1
                    l2 -= 1
                pre.next = h

            level *= 2
        return res.next

13. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。

说明:

你的解法应该是 O(logN) 时间复杂度的。

原题：162. 寻找峰值

难度：中等

O(N)，一次遍历，需注意首尾两个值也可以是峰值，那么只需要判断当前值大于下一个值即可，如果走到这一步说明上一个值小于该值，直接返回

例外就是一个左下到右上的直线，此时峰值为最后一个

当然这种接法不符合说明

O(logN)明显是二分查找

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return i

        return len(nums) - 1

值得注意的是二分法不需要把密度和左右对比，然后左右再对比，只需要根据一个趋势来判断中间值位于下坡还是上坡

# 递归版
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        def helper(left=0, right=n - 1):
            if left == right:
                return left
            
            mid = (left + right) // 2
            if nums[mid] > nums[mid + 1]:
                return helper(left, mid)
            return helper(mid + 1, right)

        return helper()

# 迭代版
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, n - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return left

14. 最大间距

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

说明:

你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。

请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

原题：164. 最大间距

难度：困难

先来个暴力法，直接AC

但是线性复杂度明显不能直接使用自带的排序

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        
        nums.sort()
        max_len = 0
        for i in range(n - 1):
            max_len = max(max_len, nums[i + 1] - nums[i])
        return max_len

查阅资料得知，排序算法中有三种是线性时间复杂度的，基数排序，桶排序，计数排序

这里我选用的是基数排序，总的来说是O(d*N)，约等于O(N)

这个算法不难但是要能想得到

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        max_digit = 0
        max_num = max(nums)
        while max_num > 0:
            max_num = max_num // 10
            max_digit += 1

        for i in range(max_digit):
            tmp = [[] for _ in range(10)]
            tmp_digit = 10 ** i
            tmp_nums = []
            for j in range(n):

                radix = nums[j] // tmp_digit % 10
                tmp[radix].append(nums[j])

            for a in tmp:
                for b in a:
                    tmp_nums.append(b)

            nums = tmp_nums
        
        max_len = 0
        for i in range(n - 1):
            max_len = max(max_len, nums[i + 1] - nums[i])
        return max_len

15. 分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字

符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

原题：166. 分数到小数

难度：中等

碰到这种数学问题，可以在纸上多写一个用例

这道题就是记录除数即可，当除数重复出现意味着余数都是一样的

定义一个hash表记录除数和它出现的位置在这个位置插入一个(就可以了

需要注意的是边界问题比如正负值 python的divmod或者//都是取整的所以先判断正负值然后拿绝对值去计算去除可能出现的四舍五入情况

然后就是0的情况

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if denominator == 0:
            return ''
        if numerator == 0:
            return str(0)

        res = []
        if (numerator > 0) ^ (denominator > 0):
            res.append('-')
        numerator, denominator = abs(numerator), abs(denominator)
        iv, fv = divmod(numerator, denominator)
        res.append(str(iv))
        if fv == 0:
            return ''.join(res)
        res.append('.')
        hashmap = {fv: len(res)}
        while fv:
            fv *= 10
            iv, fv = divmod(fv, denominator)
            res.append(str(iv))
            if fv in hashmap:
                res.insert(hashmap[fv], '(')
                res.append(')')
                break
            else:
                hashmap[fv] = len(res)
        return ''.join(res)

16. 实现 Trie (前缀树)

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

原题：208. 实现 Trie (前缀树)

难度：中等

前缀树就是类似搜索引擎的东西, 主要思路就是用hash字典来快速检索每个单词是否存在，需注意的是search和startsWith的区别，需要用一个*终止符号来判断是否是一个完整的单词

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.trie
        for w in word:
            if w not in node:
                node[w] = {}
            node = node[w]
        node['#'] = '#'

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.trie
        for w in word:
            if w not in node:
                return False
            node = node[w]
        if '#' in node:
            return True
        else:
            return False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.trie
        for w in prefix:
            if w not in node:
                return False
            node = node[w]
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

修改版，一个空根节点，将是否结束从一个占位字符串改为属性

class TrieNode:
    def __init__(self):
        self.child = {}
        self.is_end = False


class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for w in word:
            if w not in node.child:
                node.child[w] = TrieNode()
            node = node.child[w]
        node.is_end = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for w in word:
            if w not in node.child:
                return False
            node = node.child[w]
        if node.is_end:
            return True
        else:
            return False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for w in prefix:
            if w not in node.child:
                return False
            node = node.child[w]
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

17. 连接词

给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。

连接词的定义为:一个字符串完全是由至少两个给定数组中的单词组成的。

原题：472. 连接词

难度：困难

使用上一题写的前缀树，用深度搜索找到一个单词，然后再从根节点开始搜索

“catsdogcats”这个单词截至到cat是可以的，但是s开头并没有，所以再往下搜索到cats再继续裁切，此题需要记忆这个判定方式

另外，这里的前缀树与上一题不太一样，这里应该更好，因为是一棵树，根节点为空，上一题是多棵树，如果以上一题数据结构来解，会出现无线递归的问题，原因在if '#' in node:, 因为只要有一个空字符串，这里就会一直进来。。。

还有就是加一个参数，代表这个单词是否由多个单词组成而不是自身字符串

class TrieNode:
    def __init__(self):
        self.child = {}
        self.is_end = False


class Trie:
    def __init__(self, word_list):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        for word in word_list:
            if word:
                self.insert(word)

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for w in word:
            if w not in node.child:
                node.child[w] = TrieNode()
            node = node.child[w]
        node.is_end = True


class Solution:
    def findAllConcatenatedWordsInADict(self, words):
        t = Trie(words)
        res = []

        def dfs(node, i, w, has_cut):
            if i == len(w):
                return node.is_end and has_cut
            if node.is_end:
                if dfs(t.root, i, w, True):
                    return True

            if w[i] not in node.child:
                return False
            else:
                return dfs(node.child[w[i]], i + 1, w, has_cut)

        for w in words:
            if dfs(t.root, 0, w, False):
                res.append(w)
        return res

18. 滑动窗口中位数

中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数;此时中位数是最中间的两个数的平均数。

原题：480. 滑动窗口中位数

难度：困难

暴力法，竟然AC了。。。

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        n = len(nums)
        l, r = 0, k
        res = []
        
        while r <= n:
            tmp = nums[l:r]
            tmp.sort()
            tmp_r = k - 1
            if k % 2 == 1:
                res.append(tmp[tmp_r // 2])
            else:
                mid_num = (tmp[tmp_r // 2] + tmp[tmp_r // 2 + 1]) / 2
                res.append(mid_num)
            l += 1
            r += 1
        return res

稍微修改了一下，减少空间复杂度和代码复杂度

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        if k == 0: return []
        ans = []
        window = sorted(nums[0:k])
        for i in range(k, len(nums) + 1):
            ans.append((window[k // 2] + window[(k - 1) // 2]) / 2.0)
            if i == len(nums): break
            index = bisect.bisect_left(window, nums[i - k])
            window.pop(index)      
            bisect.insort_left(window, nums[i])
        return ans

官方实例是用两个堆来实现，类似295. 数据流的中位数

19. 祖玛游戏

回忆一下祖玛游戏。现在桌上有一串球，颜色有红色(R)，黄色(Y)，蓝色 (B)，绿色(G)，还有白色(W)。现在你手里也有几个球。
每一次，你可以从手里的球选一个，然后把这个球插入到一串球中的某个位置上(包括最左端，最右端)。接着，如果有出现三个或者三个以上颜色相同的球相连的话，就把它们移除掉。重复这一步骤直到桌上所有的球都被移除。
找到插入并可以移除掉桌上所有球所需的最少的球数。如果不能移除桌上所有的球，输出 -1 。

原题：488. 祖玛游戏

难度：困难

标签：dfs

首先是这么写的，使用剪枝法，在每一个重复球最后加上球，然后用clear方法来剪枝，但是这个测试用例过不了：

1 2	"RRWWRRBBRR" "WB"

以下方式会返回-1，最后剩一个RR

但是是可以解出来的

1	RRWWRRBBRR->RRWWRRBBR(W)R->RRWWRRBB(B)R(W)R->RRWWRRR(W)R->RRWW(W)R->RRR->""

所以不能剪枝了，必须要每一个方法都要兼顾到

from collections import Counter

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        # 'RBYYBBBRRB'  =>  'RBYYRRB'
        def clear(b):
            i = 0
            while i < len(b):
                j = i
                while j < len(b) and b[j] == b[i]:
                    j += 1
                if j - i >= 3:
                    b = b[:i] + b[j:]
                    i = 0
                else:
                    i += 1
            return b

        def dfs(b, h):
            n = len(b)
            if n == 0:
                return 0
            max_ball, i, j = float('inf'), 0, 0
            while i < n:
                while j < n and b[j] == b[i]:
                    j += 1
                balls = 3 - (j - i)
                color = b[i]
                if h[color] >= balls:
                    nb = clear(b[:j] + color * balls + b[j:])
                    h[color] -= balls
                    r = dfs(nb, h)
                    # 深度搜索结果不是-1
                    if r != -1:
                        max_ball = min(max_ball, r + balls)
                    h[color] += balls
                i = j

            return max_ball if max_ball != float('inf') else -1

        return dfs(board, Counter(hand))

正确方法如下：

from collections import Counter

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        def dfs(b, h):
            if not b:
                return 0

            n, max_ball, i, j = len(b), float('inf'), 0, 0
            while i < n:
                while j < n and b[i] == b[j]:
                    j += 1

                balls = 3 - (j - i)
                color = b[i]
                if h[color] >= balls:
                    balls = max(0, balls)
                    h[color] -= balls
                    r = dfs(b[:i] + b[j:], h)
                    if r >= 0:
                        max_ball = min(max_ball, r + balls)
                    h[color] += balls
                i = j
            return max_ball if max_ball != float('inf') else -1

        return dfs(board, Counter(hand))

20. 摘樱桃

一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：

0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。
你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：

从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）；
当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）；
如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。

原题：741. 摘樱桃

难度：困难

标签：dp

一筹莫展，去花花酱找题解

三维的动态规划

时间复杂度和空间复杂度都是O(N^3)

抽象成两个人从右下角终点同时往左上起点走，坐标是(x1,y1)和(x2,y2)，由于是同时走，所以可以降维，y2=x1+y1-x2

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[[float('-inf')] * n for _ in range(n)] for _ in range(n)]
        def helper(x1, y1, x2):
            y2 = x1 + y1 - x2
            if x1 < 0 or x2 < 0 or y1 < 0 or y2 < 0:
                return -1
            if grid[x1][y1] < 0 or grid[x2][y2] < 0:
                return -1
            if x1 == 0 and y1 == 0:
                return grid[x1][y1]
            if dp[x1][y1][x2] != float('-inf'):
                return dp[x1][y1][x2]
            
            res = max(
                        max(helper(x1 - 1, y1, x2 - 1), helper(x1, y1 - 1, x2)),
                        max(helper(x1, y1 - 1, x2 - 1), helper(x1 - 1, y1, x2))   
                )
            if res < 0:
                dp[x1][y1][x2] = -1
            else:
                res += grid[x1][y1]
                if x1 != x2:
                    res += grid[x2][y2]
                dp[x1][y1][x2] = res
            return dp[x1][y1][x2]

        return max(0, helper(n - 1, n - 1, n - 1))

21. 自除数

自除数是指可以被它包含的每一位数除尽的数。

例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。

还有，自除数不允许包含 0 。

给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。

原题：728. 自除数

难度：简单

标签：数学

暴力法开搞，一个是改成字符串进行匹配，一个用数学除数和余数进行匹配

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        # 改成字符串
        def helper1(num):
            for n in list(str(num)):
                if n == '0' or num % int(n) != 0:
                    return False
            return True
        
        # 数学运算
        def helper2(num):
            tmp = num
            while tmp > 0:
                n = tmp % 10
                if n == 0 or num % n != 0:
                    return False
                tmp = tmp // 10
            return True

        res = []
        for num in range(left, right + 1):
            if helper2(num):
                res.append(num)
        return res

22. 回文系列

原来的22题是 730. 统计不同回文子字符串难度困难，由于只有几道题解，且需要三维dp，所以暂时放在一边，记录下回文系列

原题：5. 最长回文子串 9. 回文数 647. 回文子串

难度：中等简单中等

5. 最长回文子串

中心扩展方法，需要分别奇数和偶数不同的下标

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 两个情况 偶数和奇数
        n = len(s)
        if n <= 1:
            return s

        def helper(index, is_odd=False):
            l = index - 1 if is_odd else index
            r = index + 1
            while l >= 0 and r < n:
                if s[l] == s[r]:
                    l -= 1
                    r += 1
                else:
                    break
            return s[l+1:r]

        res = ''
        for i in range(n - 1):
            odd, even = helper(i, True), helper(i)
            tmp = odd if len(odd) > len(even) else even
            if len(res) < len(tmp):
                res = tmp
        return res

动态规划必须掌握

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return s

        max_len, res = 1, s[0]
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True

        for j in range(1, n):
            for i in range(j):
                if s[i] == s[j]:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                if dp[i][j]:
                    if j - i + 1 > max_len:
                        max_len = j - i
                        res = s[i:j + 1]
        return res

9. 回文数

数学方法来解即可可以缩短时间复杂度从N到logN，在于翻转的数字大于等于去掉尾部的源数字即可对比了

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if 0 <= x < 10:
            return True
        if x < 0 or x % 10 == 0:
            return False

        new_x = 0
        while x > new_x:
            new_x = x % 10 + 10 * new_x
            x //= 10
        return new_x // 10 == x or new_x == x

674. 回文子串

跟第5题一模一样，就是换个返回值

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        if n <= 1:
            return n
        res = 0
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
            res += 1

        for j in range(1, n):
            for i in range(j):
                if s[i] == s[j]:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                    if dp[i][j] is True:
                        res += 1
        return res