前言

代码能力是计算机专业学生的基础能力，求职技术方向的同学，无论是测试、开发或算法，互联网公司在这一块的考察都是重中之重。一般而言，大厂在每一轮的技术面中，至少会出一道编程题，多的会直接上三道编程题，难度主要集中在easy和medium，少数丧心病狂（褒义词）的面试官会出hard题。而考察范围已是圈内公开的秘密，就在《剑指offer》和Leetcode上，因此刷题成为了大家求职路上必须要迈过的一道坎，这个坎没有人可以帮到你，只有靠你自己。

本笔记记录自己在刷题过程中的总结

剑指Offer

[206] 反转链表

反转一个单链表。

示例:

1 2	`输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL`

思路：
需要背诵级别的题目

代码：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None 
        p = head
        while p:
            p_next = p.next
            p.next = pre
            pre = p
            p = p_next
        return pre

[38]字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

1 2	`输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]`

https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

思路：
回溯法

代码：

class Solution:
    def permutation(self, s: str) -> List[str]:
        result = []
        visits = [False for i in range(len(s))]

        def backtrace(trace):
            if len(trace) == len(s):
                result.append("".join(trace))
            
            tmp_set = set()
            for i in range(len(s)):
                if not visits[i] and s[i] not in tmp_set:
                    trace.append(s[i])
                    visits[i] = True
                    tmp_set.add(s[i])
                    backtrace(trace)
                    trace.pop()
                    visits[i] = False
        backtrace([])
        return result

[42]连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

1
2
3

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思想：
动态规划的问题，以num为最后一个数字的子数组

代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return -1
        
        result = nums[0]
        temp_result = nums[0]

        for num in nums[1:]:
            # 以num为最后一个数字的子数组的最大值
            if temp_result < 0:
                temp_result = num
            else:
                temp_result += num
            if temp_result > result:
                result = temp_result
        
        return result

[42]重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

1 2	`前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]`

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

思路：
递归的进行调用，主要是细心

代码：

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder) == 0:
            return None

        if len(preorder) == 1:
            return TreeNode(preorder[0])
        
        root_val = preorder[0]

        index = inorder.index(root_val)

        left_tree = self.buildTree(
            preorder[1:1+index],
            inorder[:index]
        )

        right_tree = self.buildTree(
            preorder[1+index:],
            inorder[index+1:]
        )

        root = TreeNode(root_val)
        root.left = left_tree
        root.right = right_tree

        return root

[48]最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

1
2
3

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

1
2
3

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

思考：
滑动窗口的题目，直接用双端队列进行操作

代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        
        result = 1
        q = collections.deque()
        q.append(s[0])

        for c in s[1:]:
            while q and c in q:
                q.popleft()
            q.append(c)
            result = max(result,len(q))
        
        return result

[20]表述数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof

思考：
如果出现的字符是.，那么需要还没有.和e，
如果出现的字符是e/E，那么需要已经出现了数字并且没有e
如果出现的字符是+/-，那么需要位于第一位，或者之前是`e/E

代码：

class Solution:
    def isNumber(self, s: str) -> bool:
        nums = set("0123456789")
        num_flag = False
        dot_flag = False
        e_flag = False
        s = s.strip()
        for index, c in enumerate(s):
            if c in nums:
                num_flag = True
            elif c == '.' and (not dot_flag) and (not e_flag):
                dot_flag = True
            elif c in 'eE' and (not e_flag) and num_flag:
                e_flag = True
                num_flag = False
            elif c in '+-' and (index==0 or s[index-1] in 'eE'):
                pass
            else:
                return False
        return num_flag

[29]顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

1 2	`输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]`

https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/

思路：
确定好边界和跳出条件，这段代码需要背诵.边界收缩，增加以后，超过了什么；减少以后，更小了什么

代码：

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
        left,right,top,bottom = 0, len(matrix[0])-1, 0, len(matrix)-1
        ret = []

        while True:
            # ->
            for i in range(left,right+1):
                ret.append(matrix[top][i])
            top += 1
            if top > bottom: break

            # |
            for i in range(top,bottom+1):
                ret.append(matrix[i][right])
            right -= 1
            if right < left: break

            # <-
            for i in range(right,left-1,-1):
                ret.append(matrix[bottom][i])
            bottom -= 1
            if bottom < top: break

            # |
            for i in range(bottom,top-1,-1):
                ret.append(matrix[i][left])
            left += 1
            if left > right: break

        return ret

[40]最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

1 2	`输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]`

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

思路：
排序是一个必要的操作，通过快排序可以更快的进行

代码：

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if not arr or k==0:
            return []
        return self.quicksort(arr,0,len(arr)-1,k)
    
    def quicksort(self,arr,l,r,k):
        j = self.partition(arr,l,r)

        if k == j or k == j+1:
            return arr[:k]
        
        if k < j:
            return self.quicksort(arr,l,j-1,k)
        
        if k > j:
            return self.quicksort(arr,j+1,r,k)
    
    def partition(self,arr,l,r):
        pivot = arr[l]
        index = l+1
        for i in range(l+1,r+1):
            if arr[i] < pivot:
                arr[i],arr[index] = arr[index],arr[i]
                index += 1
        arr[l],arr[index-1] = arr[index-1],arr[l]
        return index-1

[53]0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof

思想：
因为是0-n的有序序列，所以可以保证nums[i] = i, 从而可以通过二分查找快速定位。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        i,j = 0,len(nums)-1

        while i <= j:
            k = (i+j) // 2
            if nums[k] == k: 
                i+=1
            else:
                j-=1
        
        return i

[60]从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

思想：
因为是反转，所以可以通过栈来实现

代码：

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if not head:
            return []
        stack = []
        p = head
        while p:
            stack.append(p.val)
            p = p.next
        return stack[::-1]

[52]两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

思想：
a + c + b = b + c + a，即使没有公共节点也是满足的

代码：

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p = headA
        q = headB
        
        while p != q:
            if p:
                p = p.next
            else:
                p = headB
            if q:
                q = q.next
            else:
                q = headA
        
        return p

[56]数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

思路：
两个相同的数字的“异或”结果为0，所以一个数组中如果只有一个不重复的数字，那么对整个数组执行异或操作就能找到该数字。

现在有两个不同的数字，所以问题的关键是对数组进行分组操作，划分成两组，每组都只有一个不重复的数字，然后对两组分别执行整体“异或”操作。

如何划分？假设数组中不重复的两个数字为x,y，对整个数组进行异或操作的结果为ret, 即x^y=ret, 假设ret二进制表示中一定有至少1为为1，假设第i位的结果位1，那么说明x与y在第i位的结果不同。那么就可以根据第i位是否为1对整个数组进行划分: x与y一定分到不同的两个队列中，而剩余数字中相同的两个数字也一定划分到一个相同的队列中。

具体在操作上可以先找出ret最左侧的第一个为1的那一位，通过&操作和<<操作可以实现，再根据那一位对整个数组进行&操作进行划分。

代码：

from functools import reduce

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        ret = reduce(lambda x,y:x^y, nums)
        div = 1
        while div & ret == 0:
            div <<= 1
        # 0与任何数的异或结果为这个数本身
        a,b = 0,0
        for num in nums:
            if num & div == 0:
                a ^= num
            else:
                # 此时 num & div = div
                b ^= num
        return [a,b]

[26]树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构，即 A中有出现和B相同的结构和节点值。
例如: 给定的树 A:

给定的树 B：

1
2
3

   4 
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

思路：
B是A的子结构的三种情况:
(1)节点A为根节点的子树包含B
(2)B是A的左子树的子结构
(3)B是A的右子树的子结构

代码：

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not B:
            return False
        if not A:
            return False
        return self.recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)
    
    def recur(self, A: TreeNode, B: TreeNode) -> bool:
        # 注意一定是先判断B的情况
        if not B:
            return True
        if not A:
            return False
        if A.val != B.val:
            return False
        return self.recur(A.left,B.left) and self.recur(A.right,B.right)

[62]圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

思路：
这是典型的约瑟夫环问题，有几种做题的方法
(1) 模拟：构建一个list，模拟整个操作
(2) 递归：第一个去除的元素是m%n-1，那么剩下n-1个元素，假设最后剩下的元素为k，那么对于原始的n个元素最后剩下的就是(m%n + k) % k,也就是从m%n开始数k个。
(3) 迭代：对于递归进行优化，也就是正过来计算

代码：
模拟

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        circle = list(range(n))
        current_index = 0
        while True:
            remove_index = (current_index + m - 1) % len(circle)
            circle.pop(remove_index)
            current_index = remove_index
            if len(circle) == 1:
                return circle[0]

递归

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        if n == 1:
            return 0
        last_remain = self.lastRemaining(n-1,m)
        return (m%n + last_remain) % n

迭代

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        last_remain = 0
        for i in range(2,n+1):
            last_remain = (m%i + last_remain ) %i
        return last_remain

[59]滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

思路：
窗口对应的数据结构为双端队列，本题需要使用一个单调的队列：

队列中的元素均来自窗口，所以窗口滑动，需要将队列中对应的元素一起移除
队列保持单调，非严格递减，所以窗口滑动新增元素的时候，需要将比新增元素小的元素一并删除

代码：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or k == 0: return []
        q = collections.deque()
        for i in range(k):
            while q and q[-1] < nums[i]:
                q.pop()
            q.append(nums[i])
        ret = [q[0]]
        for i in range(k,len(nums)):
            if q[0] == nums[i-k]:
                q.popleft()
            while q and q[-1] < nums[i]:
                q.pop()
            q.append(nums[i])
            ret.append(q[0])
        return ret

[14]剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

1
2
3

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

1
2
3

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/submissions/

思路：
动态规划，dp[n]为长度为n绳子的最好结果，那么对于长度为m的绳子，先剪开一刀j，那么就是对比max( (m-j) * j ,dp[m-j] * j )的大小，也就是剩下的部分要不要继续再切分了

代码：

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[2] = 1
        for i in range(3,n+1):
            for j in range(1, (i+1)//2 + 1):
                dp[i] = max(dp[i], max(j * (i-j),dp[i-j] * j))
        return dp[n]

[32]从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],

1	`[3,9,20,15,7]`

https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof

思路：
本质是对树的BFS，所以基于队列实现

代码：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root: return []
        ret,q = [],collections.deque()
        q.append(root)
        while q:
            node = q.popleft()
            ret.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        return ret

[68] 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof

思路：
先通过DFS遍历整个树，记录一下每个节点的父节点

代码：

class Solution:
    def __init__(self) -> None:
        self.parent_map = {}

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        self.dfs(root)
        self.parent_map[root] = None
        self.p_path = set()
        while p:
            self.p_path.add(p)
            p = self.parent_map[p]
        while q:
            if q in self.p_path:
                return q
            q = self.parent_map[q]
        return None


    def dfs(self,root):
        if root.left:
            self.parent_map[root.left] = root
            self.dfs(root.left)
        if root.right:
            self.parent_map[root.right] = root
            self.dfs(root.right)

[49]丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:

1
2
3

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

链接：https://leetcode-cn.com/problems/chou-shu-lcof

思路：
动态规划，dp[n] = min(dp[a]*2,dp[b]*3,dp[c]*5)，

同时：
dp[a-1]*2 <= dp[n-1] < dp[a]*2;
dp[b-1]*3 <= dp[n-1] < dp[b]*3;
dp[c-1]*5 <= dp[n-1] < dp[c]*5;

代码：

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # dp[n] = min(dp[a]*2,dp[b]*3,dp[c]*5)
        dp,a,b,c = [1]*n,0,0,0
        for i in range(1,n):
            n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5
            print(n2,n3,n5)
            dp[i] =  min(n2,n3,n5)
            if dp[i] == n2: a += 1
            if dp[i] == n3: b += 1
            if dp[i] == n5: c += 1
        return dp[-1]

[54]二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

思路:
遍历二叉数：右子树 -> 根节点 -> 左子树
注意减枝

代码:

class Solution:
    def __init__(self) -> None:
        self.result = []

    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.k = k
        self.dfs(root)
        return self.result[k-1]


    def dfs(self,root):
        if not root:
            return 
        self.dfs(root.right)
        if len(self.result) >= self.k:
            return
        self.result.append(root.val)
        if len(self.result) >= self.k:
            return
        self.dfs(root.left)

[35]复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

思路：
通过一个字典来保存老节点与新节点的映射关系

代码：

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        d = {}

        def getClonedNode(node):
            if not node:
                return None
            if node not in d:
                d[node] = Node(node.val)
            return d[node]
        
        oldNode = head
        newNode = getClonedNode(head)
        ret = newNode

        while oldNode:
            newNode.next = getClonedNode(oldNode.next)
            newNode.random = getClonedNode(oldNode.random)
            oldNode = oldNode.next
            newNode = newNode.next
        
        return ret

[34]二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 target = 22，

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

[
   [5,4,11,2],
   [5,8,4,5]
]

https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof

思路：
典型的DFS的遍历，当然也可以BFS

代码：
DFS

class Solution:

    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        def recur(node,tar):
            if node.left == None and node.right == None and tar == 0:
                ret.append(path[:])
            if node.left:
                # 尝试向左走一步
                path.append(node.left.val)
                recur(node.left,tar-node.left.val)
                path.pop()
            if node.right:
                # 尝试向右走一步
                path.append(node.right.val)
                recur(node.right,tar-node.right.val)
                path.pop()

        if not root:
            return []
        
        ret = []
        path = [root.val]
        recur(root,target-root.val)

        return ret

BFS

class Solution:

    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        ret = []
        q = collections.deque()
        if not root:
            return ret
        q.append((root, [root.val]))
        while q:
            node, current_path = q.popleft()
            if node.left is None and node.right is None and sum(current_path) == target:
                ret.append(current_path[:])
            if node.left:
                path = current_path[:]
                path.append(node.left.val)
                q.append((node.left, path))
            if node.right:
                path = current_path[:]
                path.append(node.right.val)
                q.append((node.right, path))
        return ret

[47]礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof

思路：
通过动态规划求解，否则会超时

代码

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        m = len(grid)
        n = len(grid[0])
        dp = [[0] * n]*m
        for i in range(m):
            for j in range(n):
                if i-1<0:
                    upper = 0
                else:
                    upper = dp[i-1][j]
                if j-1<0:
                    left = 0
                else:
                    left = dp[i][j-1]
                dp[i][j] = grid[i][j] + max(left,upper)
        return dp[m-1][n-1]

[59] 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof

思路：
额外维护一个双端队列，保持单调不递增；类比第59题

代码：

import queue

class MaxQueue:


    def __init__(self):
        self.max_value_queue = collections.deque()
        self.normal_queue = queue.Queue()


    def max_value(self) -> int:
        if not self.max_value_queue:
            return -1
        return self.max_value_queue[0]

    def push_back(self, value: int) -> None:
        while self.max_value_queue and self.max_value_queue[-1] < value:
            self.max_value_queue.pop()
        
        self.normal_queue.put(value)
        self.max_value_queue.append(value)


    def pop_front(self) -> int:
        if not self.max_value_queue:
            return -1
        fron_value = self.normal_queue.get()
        if fron_value == self.max_value_queue[0]:
            self.max_value_queue.popleft()
        return fron_value

[66]构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

1 2	`输入: [1,2,3,4,5] 输出: [120,60,40,30,24]`

https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof

思路：
构建上下三角形的举证，通过两轮循环来实现

代码：

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        B = [1] * len(a)
        for i in range(1,len(a)):
            B[i] = B[i-1] * a[i-1]
        temp = 1
        for i in list(range(len(a)-1))[::-1]:
            temp = temp * a[i+1]
            B[i] = B[i] * temp
        return B

[30] 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

思路：
对比59题，这里将数据结构替换成栈，相比队列，栈的结构如果不符合条件，直接不入栈即可。

代码：

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = []


    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or self.min_stack[-1] >= x:
            self.min_stack.append(x)


    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()
        

    def top(self) -> int:
        return self.stack[-1]


    def min(self) -> int:
        return self.min_stack[-1]

[68]二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

思路：
因为是一个二叉搜索数，所以可以快速得到一个节点的路径；再进行路径的对比，找到分叉的节点即可。

代码：

class Solution:
    def __init__(self) -> None:
        self.parent_map = {}

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        def get_path(target):
            path = []
            node = root
            while node:
                path.append(node)
                if node.val > target.val:
                    node = node.left
                elif node.val < target.val:
                    node = node.right
                else:
                    break
            return path
        
        p_path = get_path(p)
        q_path = get_path(q)
        result = None
        for p_path_node,q_path_node in zip(p_path,q_path):
            if p_path_node == q_path_node:
                result = p_path_node
                break
        return result

[21]合并两个有序的链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思考：
先确定一个最终返回的链表，然后把后面的链表链接上去即可

代码：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1
        
        # 确保l1 < l2
        if l2.val < l1.val:
            l1,l2 = l2,l1
        
        head = l1
        
        # 将l2合并到l1上即可,也就是q合并到p上
        p,q = l1,l2
        while p.next and q:
            if p.val <= q.val <= p.next.val:
                p_next = p.next
                q_next = q.next
                p.next = q
                p.next.next = p_next
                p = p.next
                q = q_next
            else:
                p = p.next
        if q:
            p.next = q
        
        return head

[11]旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

1 2	`输入：[3,4,5,1,2] 输出：1`

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

思路：
二分查找，主要要跟右侧的数进行对比

代码：

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        start = 0
        end = len(numbers) - 1
        # 确保让最小的数字在[start,end]的区间
        while start < end:
            mid = (start+end) // 2
            if numbers[mid] > numbers[end]:
                start = mid + 1
            elif numbers[mid] < numbers[end]:
                end = mid
            else:
                end = end - 1
        return numbers[mid]

[12]矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

1
2
3

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof

思考：
典型的DFS问题

代码：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:

        def dfs(x,y,step):
            if x < 0 or x >= len(board):
                return False
            if y < 0 or y >= len(board[0]):
                return False
            if board[x][y] != word[step]:
                return False
            if step == len(word) - 1:
                return True
            
            board[x][y] = ''
            ret = dfs(x+1,y,step+1) or dfs(x-1,y,step+1) or dfs(x,y+1,step+1) or dfs(x,y-1,step+1)
            board[x][y] = word[step]

            return ret


        if not board:
            return False
        if not word:
            return False

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i,j,0): return True
        
        return False

[36]二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

思考：
确定最小的节点和最大的节点，通过递归来实现

代码：

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None
        
        left_min = root
        right_max = root

        if root.left:
            left_min = self.treeToDoublyList(root.left)
            left_max = left_min.left
            left_max.right = root
            root.left = left_max
        if root.right:
            right_min = self.treeToDoublyList(root.right)
            right_max = right_min.left
            right_min.left = root
            root.right = right_min
        
        left_min.left = right_max
        right_max.right = left_min

        return left_min

[46]把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

1
2
3

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof

思考：
两种场景，分开思考

代码：

class Solution:
    def translateNum(self, num: int) -> int:
        return self.helper(str(num))
    
    def helper(self,num_str):
        if len(num_str) <= 1:
            return 1
        
        ret = self.helper(num_str[1:])

        if 10 <= int(num_str[:2]) <= 25:
            ret += self.helper(num_str[2:])
        
        return ret

回溯算法

答题框架

result = []

def backtrack(路径，选择列表):
    if 满足条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其中：
路径：也就是已经做出的选择；选择列表：也就是你当前可以做的选择；结束条件：也就是到达决策树底层，无法再做选择的条件。

[78]子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

https://leetcode-cn.com/problems/subsets/
https://leetcode-cn.com/problems/subsets-ii/

思想：
回溯法,注意减枝的操作即可

代码：
无重复

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrace(trace,index):
            # 从index开始
            result.append(trace[:])

            if index >= len(nums):
                return 
            
            for i in range(index,len(nums)):
                trace.append(nums[i])
                backtrace(trace,i+1)
                trace.pop()
        
        backtrace([],0)
        return result

有重复

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrace(trace,index):
            result.append(trace[:])

            if index >= len(nums):
                return 
            
            s = set()
            for i in range(index,len(nums)):
                if nums[i] in s:
                    continue
                trace.append(nums[i])
                s.add(nums[i])
                backtrace(trace,i+1)
                trace.pop()
        
        nums.sort()
        backtrace([],0)
        return result

[93]复原 IP 地址

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的有效 IP 地址。你可以按任何顺序返回答案。

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

链接：https://leetcode-cn.com/problems/restore-ip-addresses

思想：
回溯法，同时进行减枝的操作

代码：

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []

        def is_valid(ip_str):
            if len(ip_str) == 1:
                return True
            if ip_str[0] == '0':
                return False
            if 0 < int(ip_str) <= 255:
                return True
            else:
                return False

        def backtrace(trace,index):
            # trace 当前已经添加的ip地址
            # index 从index开始遍历s
            if len(trace) == 4 or index == len(s):
                if len(trace) == 4 and index == len(s):
                    result.append(".".join(trace))
                return 
            
            # 继续剪枝
            if not ( 4-len(trace) <= len(s) - index <= 3*(4-len(trace)) ):
                return 
            
            # 选择
            for i in range(1,4):
                if index + i <= len(s):
                    sub_str = s[index:index+i]
                    if is_valid(sub_str):
                        trace.append(sub_str)
                        backtrace(trace,index+i)
                        trace.pop()
        
        backtrace([],0)
        return result

动态规划

[42]接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1
2
3

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

https://leetcode-cn.com/problems/trapping-rain-water

思考：
动态规划，当前位置能接到的雨水，等于两侧最大值中的较小的一个减去当前的数量

代码：

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        left_max = [0 for i in range(len(height))]
        left_max[0] = height[0]
        for i in range(1,len(height)):
            left_max[i] = max(left_max[i-1],height[i])
        right_max = [0 for i in range(len(height))]
        right_max[-1] = height[-1]
        for i in range(len(height)-2, -1, -1):
            right_max[i] = max(right_max[i+1],height[i])
        ans = 0
        for i in range(len(height)):
            ans = ans + (min(left_max[i],right_max[i]) - height[i])
        return ans

通过优先队列，缩小范围来实现

from queue import PriorityQueue

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        visited = set()
        q = PriorityQueue()
        q.put((height[0],0))
        q.put((height[-1],len(height)-1))
        visited.add(0)
        visited.add(len(height)-1)
        ret = 0
        while not q.empty():
            h,index = q.get()

            steps = [1,-1]
            for step in steps:
                new_index = index + step
                if 0 < new_index < len(height) and new_index not in visited:
                    if height[new_index] < h:
                        ret += (h - height[new_index])
                        height[new_index] = h
                    q.put((height[new_index],new_index))
                    visited.add(new_index)
        return ret

[407]接雨水 II

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

https://leetcode-cn.com/problems/trapping-rain-water-ii/

思考：
基于优先队列实现，逐步缩小范围

代码：

from queue import PriorityQueue

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        if not heightMap:
            return 0
        
        q = PriorityQueue()
        visited = set()

        m = len(heightMap)
        n = len(heightMap[0])

        # 把四周放进去
        for i in range(m):
            q.put((heightMap[i][0],i,0))
            visited.add((i,0))
            q.put((heightMap[i][n-1],i,n-1))
            visited.add((i,n-1))
        
        for j in range(1,n-1):
            q.put((heightMap[0][j], 0 ,j))
            visited.add((0,j))
            q.put((heightMap[m-1][j],m-1,j))
            visited.add((m-1,j))

        ret = 0
        while not q.empty():
            h,x,y = q.get()

            steps = [(0,-1),(0,1),(1,0),(-1,0)]

            for step in steps:
                new_x,new_y = x+step[0],y+step[1]
                if 0 <= new_x < m and 0 <= new_y < n and (new_x,new_y) not in visited:
                    if heightMap[new_x][new_y] < h:
                        ret += (h - heightMap[new_x][new_y])
                        heightMap[new_x][new_y] = h
                    q.put((heightMap[new_x][new_y],new_x,new_y))
                    visited.add((new_x,new_y))
        
        return ret

[72]编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

1
2
3

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

https://leetcode-cn.com/problems/edit-distance

思想：
动态规划的问题，假设已经知道如何 (1)将word1[:-1]转换成word2, 那么只要增加一步就可以将word1转换成word2；(2)将word1转换成word2[:-1]，那么只要增加一步就可以将word1转换成word2;（3）将word1[:-1]转换成word2[:-1]，如果word1[-1] == word2[-1]那么不用再增加步骤就已经转换完成了，如果不等，则需要再增加一步。

代码：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)

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

        for i in range(1,m+1):
            dp[i][0] = i
        
        for i in range(1,n+1):
            dp[0][i] = i
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                a = dp[i-1][j] + 1
                b = dp[i][j-1] + 1
                c = dp[i-1][j-1]
                if word1[i-1] != word2[j-1]:
                    c += 1
                dp[i][j] = min(a,b,c)
        
        return dp[m][n]

面试高频题

[146] LRU

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该

在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

链接：https://leetcode-cn.com/problems/lru-cache

思考：
通过一个双向链表和一个字典实现；提前构建一个虚拟的头节点和虚拟的尾节点

代码：

class Node:
    def __init__(self, key=0, val=0) -> None:
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.d = {}
        self.head,self.tail = Node(),Node()
        self.head.next,self.tail.prev = self.tail,self.head
    
    def get(self, key: int) -> int:
        if key in self.d:
            node = self.d[key]
            self.move_to_head(node)
            return node.val
        else:
            return -1
    
    def put(self, key: int, value: int) -> None:
        if key in self.d:
            node = self.d[key]
            node.val = value
            self.move_to_head(node)
        else:
            node = Node(key,value)
            self.d[key] = node
            self.add_to_head(node)
            if len(self.d) > self.capacity:
                node = self.pop_last_node()
                del self.d[node.key]
    
    def move_to_head(self,node):
        self.remove_node(node)
        self.add_to_head(node)
    
    def remove_node(self,node):
        node_prev,node_next = node.prev,node.next
        node_prev.next,node_next.prev = node_next,node_prev
    
    def add_to_head(self,node):
        head_next = self.head.next
        self.head.next,node.prev = node,self.head
        node.next,head_next.prev = head_next,node

    def pop_last_node(self):
        last_node = self.tail.prev
        self.remove_node(last_node)
        return last_node

[885]螺旋矩阵 III

在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始

这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。

每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有 R * C 个空间。

按照访问顺序返回表示网格位置的坐标列表。

https://leetcode-cn.com/problems/spiral-matrix-iii/

思路：
模拟整个行走的过程，忽略是否在网格中。整体行走的规则是: 向右 1，向下 1，向左 2，向上 2，向右 3 …

代码：

class Solution:
    def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:

        def valid(x,y):
            if 0 <= x < R and 0 <= y < C:
                return True
            return False

        if R*C == 0:
            return []
        
        ret = []
        ret.append([r0,c0])
        r,c = r0,c0
        step = 1
        while len(ret) < R*C:
            # 向右
            for i in range(1,step+1):
                r,c = r,c+1
                if valid(r,c): ret.append([r,c])
            # 向下
            for i in range(1,step+1):
                r,c = r+1,c
                if valid(r,c): ret.append([r,c])
            step += 1
            # 向左
            for i in range(1,step+1):
                r,c = r,c-1
                if valid(r,c): ret.append([r,c])
            # 向上
            for i in range(1,step+1):
                r,c = r-1,c
                if valid(r,c): ret.append([r,c])
            step += 1
        return ret

[470] 用 Rand7() 实现 Rand10()

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

思考：
生成两次产生的结果为 [1,49],需要保证这个结果是均匀随机的；再截取[1,40]的结果，然后映射到[1,10]

代码：

class Solution:
    def rand10(self):
        boundary = ((7 * 7) // 10) * 10
        while True:
            x = 7 * (rand7() - 1) + rand7()
            # 
            if x <= boundary:
                break
        return x % 10 + 1

证明1: 产生的[1,40]的概率是均等的:

$$P(1) = \frac{1}{49} + \frac{9}{49}*\frac{1}{49} + … + {\frac{9}{49}}^{n-1}*\frac{1}{49} = \frac{1}{49} * \sum\limits_{k=1}^{k= \infty }{\frac{9}{49}}^{k-1} = \frac{1}{49} * \frac{49}{40} = \frac{1}{40}$$

证明2: 调用rand7()的期望

$$E = 2 * \frac{40}{49} + 4 * \frac{9}{49} * \frac{40}{49} + … + 2n * \frac{9}{49}^{n-1} * \frac{40}{49} =
2*\frac{40}{49} \sum\limits_{k=1}^{k= \infty }k\frac{9}{49}^{k-1} = 2.45
$$

[69]x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

1 2	`输入: 4 输出: 2`

https://leetcode-cn.com/problems/sqrtx

思想：
通过二分查找

代码：

class Solution:
    def mySqrt(self, x: int) -> int:
        start = 1
        end = x
        while start <= end:
            mid = (start + end) // 2
            if mid * mid < x:
                start = mid + 1
            elif mid * mid > x:
                end = mid - 1
            else:
                return mid
        return end

[82]删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。

返回同样按升序排列的结果链表。

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

思想：
分解成子问题，递归的处理，或者线性遍历

代码：
线性遍历

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        pre = ListNode()
        ret = pre
        pre.next = head
        p = head
        while p and p.next:
            if p.val == p.next.val:
                q = p
                while q and q.val == p.val:
                    q = q.next
                pre.next = q
                p = q
            else:
                pre = p
                p = p.next
        return ret.next

[451] 根据字符出现频率排序

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

https://leetcode-cn.com/problems/sort-characters-by-frequency

思考：
用map存储个数，再排序之后输出

代码：

class Solution:
    def frequencySort(self, s: str) -> str:
        d = {}
        for c in s:
            d[c] = d.get(c,0) + 1
        buckets = [ [] for i in range(len(s)+1) ]
        for c in d:
            count = d[c]
            buckets[count].append(c)
        index = len(buckets) - 1
        ret = []
        while index >= 1:
            if buckets[index]:
                for c in buckets[index]:
                    for i in range(index):
                        ret.append(c)
            index -= 1
        return "".join(ret)

[912]排序数组

给你一个整数数组 nums，请你将该数组升序排列。

思路：
手写快排，分解问题实现，主要是切分的操作

代码：

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self.quicksort(nums,0,len(nums)-1)
        return nums
    
    def quicksort(self,nums,l,r):
        if r - l <= 0:
            return
        index = self.partition(nums,l,r)
        self.quicksort(nums,l,index-1)
        self.quicksort(nums,index+1,r)
    
    def partition(self,nums,l,r):
        pivot = nums[l]
        index = l + 1
        
        for i in range(index,r+1):
            if nums[i] < pivot:
                self.swap(nums,i,index)
                index += 1
        
        self.swap(nums,l,index-1)

        return index-1
    
    def swap(self,nums,l,r):
        nums[l],nums[r] = nums[r],nums[l]

[1014]最佳观光组合

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和减去它们两者之间的距离。

返回一对观光景点能取得的最高分。

https://leetcode-cn.com/problems/best-sightseeing-pair

思考：
遍历，同时维护max(value[i-1] + (i-1))

代码：

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        ret,mx = 0,values[0] + 0
        for j in range(1,len(values)):
            ret = max(ret,mx+values[j] - j)
            mx = max(mx,values[j] + j)
        return ret

[224]基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

https://leetcode-cn.com/problems/basic-calculator/

思考：
两个栈来分别存储数字和符号，细节处理，在数字栈先存一个0，对于(- / (+ 需要在数字栈额外压一个0
如果遇到符号，要一路计算到不能再计算为止

代码：

class Solution:
    def calculate(self, s: str) -> int:
        num_stack = [0]
        op_stack = []
        index = 0

        def calcu():
            if len(num_stack) < 2 or len(op_stack) < 1:
                return 
            b = num_stack.pop()
            a = num_stack.pop()
            op = op_stack.pop()
            if op == '+':
                num_stack.append(a+b)
            else:
                num_stack.append(a-b)

        while index < len(s):
            if s[index] == ' ':
                index += 1
            elif s[index].isdigit():
                num = 0
                while index < len(s) and s[index].isdigit():
                    num = num * 10 + int(s[index])
                    index += 1
                num_stack.append(num)
            elif s[index] == '(':
                op_stack.append(s[index])
                index += 1
                if index < len(s) and s[index] in "+-":
                    num_stack.append(0)
            elif s[index] == ')':
                while op_stack and op_stack[-1] != '(':
                    calcu()
                op_stack.pop()
                index += 1
            else:
                while op_stack and op_stack[-1] != '(':
                    calcu()
                op_stack.append(s[index])
                index += 1
    
        while op_stack:
            calcu()
    
        return num_stack[-1]

[10]正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

https://leetcode-cn.com/problems/regular-expression-matching

思想：
通过递归的思想来实现，从后向前看比较合理；值得注意的是，即使包含*号的跟之前的匹配上了也可以继续匹配。

代码：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not s and not p:
            return True
        
        if s and not p:
            return False
        
        # 还存在的情况是 s and not p; s and p

        # 根据p[-1]的情况进行划分
        if p[-1] != '*':
            if not s:
                return False
            if self.is_match_c(s[-1],p[-1]):
                return self.isMatch(s[:-1],p[:-1])
            else:
                return False
        
        # 说明p[-1] == '*'
        if len(p) == 1:
            return False
        
        # 说明p至少有两位, 假设*表明复制0次
        ret = self.isMatch(s,p[:-2])
        if ret:
            return True
        
        # 说明*至少复制了1次
        if not s:
            return False
        
        if self.is_match_c(s[-1],p[-2]):
            return self.isMatch(s[:-1],p)
        else:
            return False
    
    def is_match_c(self,s_c,p_c):
        if p_c == '.':
            return True
        if s_c == p_c:
            return True
        return False

[84]柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

思考：
通过单调栈可以求解，获取当前节点的左右边界

代码：

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights = [0] + heights + [0]
        stack = [0]
        ans = 0
        for i in range(1,len(heights)):
            while heights[stack[-1]] > heights[i]:
                cur = stack.pop()
                ans = max(ans, (i-1 - (stack[-1]+1) +1)*heights[cur])
            stack.append(i)
        return ans

[124]二叉树中的最大路径和

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

思考：
递归每个节点产生的增益，在递归的同时，记录最大值

代码：

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.ret = float('-inf)
        self.maxGain(root)
        return self.ret
    
    def maxGain(self,node):
        if not node:
            return 0
        left = max(0, self.maxGain(node.left))
        right = max(0,self.maxGain(node.right))
        # 如果node是路径的根节点
        self.ret = max(self.ret,node.val + left + right)
        # 返回结果，只能选择一条
        return node.val + max(left,right)

[43]字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

https://leetcode-cn.com/problems/multiply-strings/

思考：
分解问题成一个数字的乘法和加法

代码：

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        # len(num1) >= len(num2)
        if len(num2) > len(num1):
            num1,num2 = num2,num1
        
        if num2 == "0":
            return "0"

        if len(num2) == 1:
            ret = []
            tmp = 0
            num2 = int(num2)
            for i in range(len(num1)-1,-1,-1):
                tmp = num2 * int(num1[i]) + tmp
                ret.append(str(tmp%10))
                tmp = tmp // 10
            if tmp > 0:
                ret.append(str(tmp))
            return "".join(ret[::-1])
                
        
        ret = "0"
        for i in range(len(num2)-1,-1,-1):
            tmp = self.multiply(num1,num2[i])
            tmp = tmp + "0" * (len(num2)-1 - i)
            ret = self.plus(ret,tmp)
        return ret
    
    def plus(self,num1,num2):
        # len(num1) >= len(num2)
        if len(num2) > len(num1):
            num1,num2 = num2,num1
        num2 = "0"*(len(num1)-len(num2)) + num2
        # 当前num1与num2等长
        tmp = 0
        ret = []
        for i in range(len(num1)-1,-1,-1):
            tmp = int(num1[i]) + int(num2[i]) + tmp
            ret.append(str(tmp%10))
            tmp = tmp // 10
        if tmp > 0:
            ret.append(str(tmp%10))
        return "".join(ret[::-1])

[300]最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

https://leetcode-cn.com/problems/longest-increasing-subsequence

思想：
通过动态规划，dp[i] 表示以nums[i]结尾的最长递增子序列，那么只要向前看即可

代码：

[25]K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

https://leetcode-cn.com/problems/reverse-nodes-in-k-group

思想：
模拟整个过程，有一个虚拟的头节点

代码：

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if k == 1:
            return head
        ret = ListNode()
        ret.next = head
        pre_node = ret
        p = head
        while p:
            tmp_head = p 
            for i in range(1,k):
                if p.next:
                    p = p.next
                else:
                    return ret.next
            next_node = p.next
            p.next = None
            reversed_head,reversed_tail = self.reverse(tmp_head)
            pre_node.next = reversed_head
            reversed_tail.next = next_node
            pre_node = reversed_tail
            p = next_node
        return ret.next
    
    def reverse(self,root):
        pre = None
        p = root
        while p.next:
            p_next = p.next
            p.next = pre
            pre = p
            p = p_next
        p.next = pre
        return p,root

[328] 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

https://leetcode-cn.com/problems/odd-even-linked-list

思考：
模拟操作，最后需要标记q节点为空

代码：

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        # 说明至少有两个节点
        ret = head
        p = head 
        q = head.next
        send_head = q
        while p.next.next and q.next.next:
            p_next = p.next.next
            q_next = q.next.next
            p.next = p_next
            q.next = q_next
            p = p.next
            q = q.next
        if q.next:
            p.next = q.next
            p = p.next
            q.next = None
        p.next = send_head
        return ret

[207]课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，��回 false 。

https://leetcode-cn.com/problems/course-schedule

思考：
通过BFS可以求解，根据入度确定哪个结点可以先遍历

代码：

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        in_degree = [0 for i in range(numCourses)]
        traget_node_d = {i:[] for i in range(numCourses)}

        for edge in prerequisites:
            a,b = edge[0],edge[1]
            # a <- b
            in_degree[a] += 1
            traget_node_d[b].append(a)
        
        q = collections.deque()
        for node in range(numCourses):
            if in_degree[node] == 0:
                q.append(node)
        visited = 0
        while q:
            visited += 1
            node = q.popleft()
            # 更新剩下的结点
            for target_node in traget_node_d[node]:
                in_degree[target_node] -= 1
                if in_degree[target_node] == 0:
                    q.append(target_node)
        return visited == numCourses

[50] Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。

思考：
快速幂

代码：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickPow(N):
            if N == 0:
                return 1.0
            y = quickPow(N // 2)
            if N % 2 == 0:
                return y*y
            else:
                return y*y*x
        if n > 0:
            return quickPow(n)
        else:
            return 1.0 / quickPow(-n)

Joshi M, Chen D, Liu Y, et al. Spanbert: Improving pre-training by representing and predicting spans[J]. Transactions of the Association for Computational Linguistics, 2020, 8: 64-77.
Liu Y, Ott M, Goyal N, et al. Roberta: A robustly optimized bert pretraining approach[J]. arXiv preprint arXiv:1907.11692, 2019.
Lan Z, Chen M, Goodman S, et al. Albert: A lite bert for self-supervised learning of language representations[J]. arXiv preprint arXiv:1909.11942, 2019.

计算机基础

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Docker使用笔记上一篇

Leetcode刷题笔记

前言

剑指Offer

[206] 反转链表

[38]字符串的排列

[42]连续子数组的最大和

[42]重建二叉树

[48]最长不含重复字符的子字符串

[20]表述数值的字符串

[29]顺时针打印矩阵

[40]最小的k个数

[53]0～n-1中缺失的数字

[60]从尾到头打印链表

[52]两个链表的第一个公共节点

[56]数组中重复的数字

[26]树的子结构

[62]圆圈中最后剩下的数字

[59]滑动窗口的最大值

[14]剪绳子

[32]从上到下打印二叉树

[68] 二叉树的最近公共祖先

[49]丑数

[54]二叉搜索树的第k大节点

[35]复杂链表的复制

[34]二叉树中和为某一值的路径

[47]礼物的最大价值

[59] 队列的最大值

[66]构建乘积数组

[30] 包含min函数的栈

[68]二叉搜索树的最近公共祖先

[21]合并两个有序的链表

[11]旋转数组的最小数字

[12]矩阵中的路径

[36]二叉搜索树与双向链表

[46]把数字翻译成字符串

回溯算法

[78]子集

[93]复原 IP 地址

动态规划

[42]接雨水

[407]接雨水 II

[72]编辑距离

面试高频题

[146] LRU

[885]螺旋矩阵 III

[470] 用 Rand7() 实现 Rand10()

[69]x 的平方根

[82]删除排序链表中的重复元素 II

[451] 根据字符出现频率排序

[912]排序数组

[1014]最佳观光组合

[224]基本计算器

[10]正则表达式匹配

[84]柱状图中最大的矩形

[124]二叉树中的最大路径和

[43]字符串相乘

[300]最长递增子序列

[25]K 个一组翻转链表

[328] 奇偶链表

[207]课程表

[50] Pow(x, n)