4.30

刷完题复习一下软件项目管理就去考试了，考完起飞！

题目

137. 只出现一次的数字 II

难度中等580

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

思路

不会位运算，直接哈希表计数，一次遍历数组，一次遍历哈希表。

代码

function singleNumber(nums: number[]): number {
    const map = new Map()
    const len = nums.length
    for(let num of nums) {
        if (!map.has(num)) {
            map.set(num, 1)
        } else {
            map.set(num, 3)
        }
    }
    for(let [key, value] of map) {
        if (value === 1) {
            return key
        }
    }
};

4.29

单杀困难题，芜湖🛫！

题目

403. 青蛙过河

难度困难

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。

开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

示例 1：

输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

示例 2：

输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。

思路

很朴素的深搜，虽然题目中的数据规模是 2000，没想到记忆化一下就过了。

深搜过程：

• 记录上一次的步长和位置，尝试找到可以跳到的所有位置
• 然后记录跳的步长，从下一个位置继续搜索

记忆化：

• 记录下从第 i 格出发且步长为 j 的可能
• 避免多次尝试无用解

代码

最近在试着用 TS 写项目，所以就用算法顺手练一下语法（不过似乎在这种函数里和 JS 区分不大）

function canCross(stones: number[]): boolean {
    const len = stones.length
    // reachables[i] = [3, 4] 表示到达第 i 格的前一步可能是 3 或 4 个单位
    const reachables: Array<Array<number>> = new Array(len).fill(0).map(() => new Array())
    let res = false

    const dfs = (idx: number, k: number) => {
        if (idx === len - 1) {
            res = true
            return
        }
        for (let i = idx + 1; i < len; i++) {
            const step = stones[i] - stones[idx]
            if (step >= k - 1 && step <= k + 1) {
                if (reachables[i].indexOf(step) !== -1) {
                    // 说明深搜过当前可能
                    continue
                }
                reachables[i].push(step)
                dfs(i, step)
            } else if (step > k + 1) {
                return
            }
        }
    }

    dfs(0, 0)
    return res
};

4.28

633. 平方数之和

难度中等

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

示例 3：

输入：c = 4
输出：true

示例 4：

输入：c = 2
输出：true

示例 5：

输入：c = 1
输出：true

思路

两年前做过的第一到老题目了。

双指针，左指针初始值为 0，右指针为 根号c。

偏大右指针左移，偏小左指针右移，直到两个指针重合求出来的和还不满足，说明不存在。

代码

var judgeSquareSum = function(c) {
  let left = 0, right = parseInt(Math.sqrt(c))
  while (left <= right) {
    let res = Math.pow(left, 2) + Math.pow(right, 2)
    if (res === c) return true
    else if (res > c) right--
    else if (res < c) left++
  } 
  return false
};

4.27

题目

938. 二叉搜索树的范围和

难度简单

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

示例 1：

输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32

示例 2：

输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23

思路

利用二叉搜索树的性质：左 < 根 < 右，在求和的时候进行剪枝。

• 如果根结点的值比题目给出的最小值 low 还要小，那么就只能往右子树里继续找。

• 如果根结点的值比题目给出的最大值 high 还要大，那么就只能往左子树里继续找。

• 否则，就需要向两边找。

简单是简单，但是自己写完才发现官方题解代码真优雅。

代码

var rangeSumBST = function(root, low, high) {
    if (!root) return 0
    if (root.val < low) {
        return rangeSumBST(root.right, low, high)
    }
    else if (root.val > high) {
        return rangeSumBST(root.left, low, high)
    }
    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)
};

4.26

题目

1011. 在 D 天内送达包裹的能力

难度中等236

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 

示例 2：

输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：

输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

思路

下意识看到 在 * 天内 ** 的能力 还以为是动态规划，看了一遍题目之后发现遍历就行。

遍历完发现超时了，超时完看题解发现要用二分 🤒

题目要返回的是最低运载能力，左边界设为最大包裹的重量，右边界设为所有包裹的总重量。

二分的依据是判断是按照当前的运载能力是否能在 D 天内完成：

• 如果不能，说明运力偏小，左边界右移
• 如果能，说明运力偏大，右边界左移

直到左边界超过右边界时，左边界就是所需的最小运力。

代码

var shipWithinDays = function(weights, D) {
    let left = Math.max(...weights), right = weights.reduce((pre, cur) => pre + cur)
    while (left <= right) {
        const mid = Math.floor((left + right)/ 2)
        if (canFinish(weights, mid, D)) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
};

function canFinish(weights, ability, D){
    let d = 1, cur = 0
    for(let weight of weights) {
        if (ability < cur + weight) {
            cur = 0
            d++
            if (d > D) return false
        }
        cur += weight
    }
    return true
}

4.25

题目

897. 递增顺序搜索树

难度简单166

给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：

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

示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

思路

整体思路就是中序遍历，不过有两种建树方式。

1. 先中序遍历一遍原树，然后把遍历到的结点值逐个存入数组，最终遍历完一棵树的数组就是一个递增数列。根据该数组，逐个新建结点，生成新树。
2. 在中序遍历的同时改变原树上结点的指向，原地修改。

代码

两种思路都比较简单，这里就贴个第二种。

var increasingBST = function(root) {
    const inOrder = (node) => {
        if (!node) {
            return
        }
        inOrder(node.left)

        // 遍历的同时直接修改结点指向
        pre.right = node
        node.left = null
        pre = node

        inOrder(node.right)
    }

    let dummy = new TreeNode(-1)
    let pre = dummy    
    inOrder(root)

    return dummy.right
};

4.24

题目

377. 组合总和 Ⅳ

难度中等

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

思路1

第一想法 DFS，写出来就超时了。

因为像是 nums = [2, 1, 3], target = 35 的情况，递归实在太久了。

代码1

var combinationSum4 = function(nums, target) {
    let res = 0
    const dfs = (arr, sum) => {
        let diff = target - sum
        if (diff === 0) {
            res += 1
            return
        }
        nums.map((num) => {
            if (num <= diff) {
                arr.push(num)
                dfs(arr, sum + num)
                arr.pop()
            }
        })
    }
    dfs([], 0)
    return res
};

思路2

又又又是动态规划，本质上是一个完全背包问题。

这篇题解针不戳。

• DP table：开辟一个长度是 target + 1 的数组，dp[i] 表示的是和为 i 的组合数。
• Base case：dp[0] = 1，表示和为 0 的组合只有一种，就是空数组。
• 动态转移方程
  • 从 dp[1] 求到 dp[target]
  • 每次算 dp[i] 的时候，遍历一遍我们手头的数组 nums
  • 若 nums[j] <= i，说明当前的这个数可以与之前某个的组合相结合，因此令 dp[i] += dp[nums[j] - i]

代码2

var combinationSum4 = function(nums, target) {
    const dp = new Array(target + 1).fill(0)
    dp[0] = 1 // 和为 1 的组合是 []
    for (let i = 1; i <= target; i++) {
        nums.map((num) => {
            if (num <= i) {
                dp[i] += dp[i-num]
            }
        })
    }
    return dp[target]
};

4.23

题目

368. 最大整除子集

难度中等

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

• answer[i] % answer[j] == 0 ，或
• answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

示例 1：

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：

输入：nums = [1,2,4,8]
输出：[1,2,4,8]

思路

初看题目要求子集，下意识是想去用 DFS 的，但是发现数组规模是 1000，而且 DFS 似乎也不太好写，求助于官方题解后得知是用 DP。

之所以是 DP，是因为整除的性质：

• 对于一个给定的整除子集而言，如果另外有一个数是该子集中最大数的整数倍，那么把这个数加入子集也是合法的。

由于有这条性质，所以数字的大小和我们的遍历应该是关系的，先对数组排序可以简化后续步骤。

同时基于这条性质，也可以联想到 DP table 的定义和状态转移方程。

• 假设 dp[i] 表示在 nums[0:i] 子数组中包含 nums[i] 在内的最大整除子集数。

• 我们需要遍历比当前数字小的所有数字，根据上面的整除性质，可以很容易得到 dp[i]

Base case：由于数字自身整除于自身，所以 dp[i] 应该初始化为 1。

在进行动规后，我们就获得了一个 dp 数组，例如题目中的 nums = [1, 2, 3], dp = [1, 2, 2]。

但是题目要求的并不是最大整除子集的规模，而是子集本身，所以我们现在可以根据子集数求子集。

首先确定最大子集的规模 maxSize，通过倒序遍历 dp[i] ，找到 dp[i] = maxSize 的 nums[i]，加入到结果自己。令 maxSize--，继续往前找，找到能整除上一个数且 dp[i] = maxSize 的数。

代码

var largestDivisibleSubset = function(nums) {
    const n = nums.length
    nums.sort((x,y) => x-y)
    // dp[i] 表示在 nums[0:i] 子数组中包含 nums[i] 在内的最大整除子集数
    const dp = new Array(n).fill(1) 
    // 动态规划求解整除子集数
    for(let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] % nums[j] === 0) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }

    // 倒序遍历求有效解子集
    res = []
    maxSize = Math.max(...dp)
    let pre = null
    for (let i = n - 1; i >= 0; i--) {
        if (dp[i] === maxSize) {
            if (pre == null || nums[pre] % nums[i] === 0) {
                pre = i
                res.push(nums[i])
                maxSize--
            }
        }
    }
    return res
};

4.22

今日没追求，暴力解困难

题目

363. 矩形区域不超过 K 的最大数值和

难度困难

给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

示例 1：

输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

示例 2：

输入：matrix = [[2,2,-1]], k = 3
输出：3

思路

首先需要将一维前缀和数组扩展到二维，然后遍历整个二维数组的所有子数组，找出小于 k 的最大和。

代码

var maxSumSubmatrix = function(matrix, k) {
    let m = matrix.length, n = matrix[0].length
    const sums = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0))
    // 先计算二维矩阵前缀和
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j]
        }
    }
    let res = -Infinity
    // 枚举所有子矩阵之和
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            for (let p = i; p < m; p++) {
                for (let q = j; q < n; q++) {
                    // (i,j) 是左上角，(p,q) 是右下角
                    let cur = sums[p+1][q+1] - sums[i][q+1] - sums[p+1][j] + sums[i][j]
                    if (cur <= k) {
                        res = Math.max(res, cur)
                    }
                }
            }
        }
    }
    return res
};

4.21

题目

91. 解码方法

难度中等

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

思路1

利用 BFS，尝试遍历进行所有可能性的。

每个位置可以有两种向下延申的情况：

• 往后扩展一位
• 往后扩展两位

会进行大量的重复计算，导致这个解法超时

代码1

var numDecodings = function(s) {
    let res = 0
    const n = s.length
    const bfs = (index) => {
        if (index >= n) {
            res += 1
        }
        if (parseInt(s[index]) >= 1) {
            bfs(index + 1)
        }
        if (index < n - 1) {
            let num = parseInt(s.slice(index, index+2))
            if (num >= 10 && num <= 26) {
                bfs(index + 2)
            }
        }
    }
    bfs(0)
    return res
};

思路2

动态规划，利用当前数和前一个数的大小，迭代计算。

• DP table：dp = new Array(n+1).fill(0)，数组长度为 字符串长度+1，dp[i] 表示 s[0:i] 的解码方法数。
• Base case：dp[0] = 1，表示我们假设空字符串有一种解码方式。
• 动态转移方程：从 i = 1 to n，当前的字符为 s[i-1]，前一个字符为 s[i-2]
  • 如果当前的字符本身不为0，说明他自己就可以进行解码，因此 s[0:i] 的解码方式和 s[0:i-1] 的解码方式数相同。
  • 如果当前的字符可以和前一个字符组成一个 10-26 的数，那么此时 s[0:i] 的解码方式和 s[0:i-2] 的解码方式数相同。

代码2

var numDecodings = function(s) {
    const n = s.length
    let res = 0
    let dp = new Array(n + 1).fill(0) // dp[i] 表示 s[0:i] 的解码方法
    dp[0] = 1 // 默认空字符串有一种编码方式
    for (let i = 1; i <= n; i++) {
        let cur = parseInt(s[i-1])
        let pre = parseInt(s[i-2])
        if (cur > 0) {
            dp[i] += dp[i-1]
        }
        if (i > 1 && pre !== 0 && cur + 10 * pre <= 26) {
            dp[i] += dp[i-2]
        }
    }
    return dp[n]
};

4.20

KMP？？？告辞

题目

28. 实现 strStr()

难度简单

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例 3：

输入：haystack = "", needle = ""
输出：0

思路

不搞竞赛，暴力就完事儿了。

代码

var strStr = function(haystack, needle) {
    // 滑动窗口
    let i = 0
    let j = 0
    let m = haystack.length
    let n = needle.length
    if (n == 0) return 0
    while (j < m && i <= j) {
        // 根据两个指针的位置确定要对比的目标字符的位置
        let idx = j - i
        if (needle[idx] === haystack[j]) {
            j++
            if (needle[0] !== haystack[i]) {
                i++
            }
        } else {
            i++
            j = i
        }
        if (j - i === n) {
            return i
        }
    }
    return -1
};

4.19

题目

27. 移除元素

难度简单

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

思路

和昨天类似，也是双指针，直接上代码。

代码

var removeElement = function(nums, val) {
    let idx = 0
    nums.forEach((num) => {
        if (num != val) {
            nums[idx++] = num
        }
    })
    return idx
};

4.18

蓝桥杯考完了，10 道做出来 7 道 🤒 也不知道对不对。

题目

26. 删除有序数组中的重复项

难度简单

给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

思路

经典老题了，双指针，把非重复的数字直接放到数组前部即可。

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        cnt = 1
        n = len(nums)
        if n <= 1:
            return n
        for i in range(1,n):
            if nums[i] != nums[i-1]:
                nums[cnt] = nums[i]
                cnt += 1
        return cnt

4.17

题目

220. 存在重复元素 III

难度中等

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

思路

因为题目中对两个数字的距离有规定，很容易想到的是双指针（滑动窗口）的思路。

• 开辟一个长度为 k + 1 的滑动窗口，从数组左边滑到右边
• 滑动的过程中，维护一个有序集合来存储当前窗口内的数
• 边滑动，边判断这个有序集合中是否存在满足条件要求的差值 <= t 的两个数

然而 Python 原生库不提供有序集合，于是放弃了这个方法

另一种思路是参考的官方题解，利用桶排序的思想。

• 设我们当前遍历的数为 x，题目中允许的最大差值 t

• 所以我们的思想是每隔 t+1 的范围划分一个桶，把每个数放到对应的桶中

• 公式：x = (t + 1) * a + b，其中 a 就是 x 的桶序号

• 边遍历数组，边判断当前数字的前一个桶和后一个桶以及自己桶里有没有满足的数字

• 同时，保证桶的个数小于等于 k

代码

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        # 要求两个数的差的绝对值<=t，位置差<=k
        n = len(nums)
        # 把每个数 x 存到对应的桶里
        # x = (t + 1) * a + b，这里的 a 表示的就是 x 应该放入的桶序号
        dic = dict()

        def getId(x):
            if x >= 0:
                return x // (t + 1)
            else:
                return (x + 1) // (t + 1) - 1

        for i, num in enumerate(nums):
            numId = getId(num)
            if (numId - 1) in dic and abs(num - dic[numId - 1]) <= t:
                return True
            if (numId + 1) in dic and abs(num - dic[numId + 1]) <= t:
                return True
            if numId in dic:
                return True
            dic[numId] = num
            if i >= k:
                del dic[getId(nums[i-k])]
        
        return False

4.16

动规周他来了！

因为周日要参加蓝桥杯，所以又换回 python 写代码了。

题目

87. 扰乱字符串

难度困难

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

1. 如果字符串的长度为 1 ，算法停止
2. 如果字符串的长度 > 1 ，执行下述步骤：
   • 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
   • 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
   • 在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：s1 = "great", s2 = "rgeat"
输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true

示例 2：

输入：s1 = "abcde", s2 = "caebd"
输出：false

示例 3：

输入：s1 = "a", s2 = "a"
输出：true

提示：

• s1.length == s2.length
• 1 <= s1.length <= 30
• s1 和 s2 由小写英文字母组成

思路

动规困难题，最终还是参考了题解。

先确定动规的几个关键要素：

• DP table

  • 动规的核心思想就是 大化小，小化了，本题的最终目标是要知道 s1 能否被扰乱成 s2，在什么子条件下我们会知道最终答案呢？
  • 如果我们把 s1 划分成 s11 + s12，s2 划分成 s21 + s22 ，若满足以下条件之一，我们可以确定 s1 能被扰乱成 s2
    • s11 可以被扰乱成 s21，s12 可以被扰乱成 s22
    • s11 可以被扰乱成 s22，s12 可以被扰乱成 s21
  • 由于被扰乱的字符串必定是等长的，我们只需要确定起始位置和字符串长度来表示状态。
  • dp[i][j][l] 的含义：s1[i:i+l] 能否扰乱获得 s2[j:j+l]

• Base case

  • 每个相同的字符必定是可扰乱的

• 状态转移方程

  • 在之前定义 DP table 的时候，其实就已经写出了状态转移的思想
  • 枚举 k in range(1, l)，表示切割的位置，下面两者之一为真则 dp[i][j][l] 为真
    • dp[i][j][k] and dp[i + k][j + k][l - k]
    • dp[i][j + l - k][k] and dp[i + k][j][l - k]

代码

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        # dp[i][j][l]的含义：s1[i:i+l] 能否扰乱获得 s2[j:j+l]
        n = len(s1)
        dp = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)] 
        
        for i in range(n):
            for j in range(n):
                if s1[i] == s2[j]:
                    dp[i][j][1] = True
        
        for l in range(2, n+1):
            # 枚举划分长度
            for i in range(n - l + 1):
                # 枚举s1起始位置
                for j in range(n - l + 1):
                    # 枚举s2起始位置
                    for k in range(1, l):
                        # 枚举分割位置
                        if dp[i][j][k] and dp[i + k][j + k][l - k]:
                            # 不交换 
                            dp[i][j][l] = True
                            break
                        if dp[i][j + l - k][k] and dp[i + k][j][l - k]:
                            dp[i][j][l] = True
                            break
        return dp[0][0][n]

4.15

题目

213. 打家劫舍 II

难度中等

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

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

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [0]
输出：0

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

思路

经典动规，和传统的打家劫舍的差别在于不能同时偷头尾两家，所以将头尾拆开考虑。

第一次遍历[0, n-2]，第二次遍历 [1, n-1]，找出最大值。

先定义 dp table : dp[i] 表示从第 0 家开始，打劫到第 i 家时，所获得的最大金额。

动态转移方程：dp[i] = max(dp[i-2] + nums[i], dp[i-1]) ，偷 i-2 和 i 或者 偷 i-1，两者选最大值。

代码

var rob = function(nums) {
    const n = nums.length
    if (n == 1) return nums[0]
    let pre = 0, cur = 0
    // 拆环
    for(let i = 0; i < n - 1; i++) {
        let tmp = Math.max(pre+nums[i], cur)
        pre = cur
        cur = tmp
    }
    let res = cur
    pre = 0
    cur = 0
    for(let i = 1; i < n; i++){
        let tmp = Math.max(pre+nums[i], cur)
        pre = cur
        cur = tmp
    }
    res = Math.max(cur, res)
    return res
};

4.14

题目

208. 实现 Trie (前缀树)

难度中等

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。

• void insert(String word) 向前缀树中插入字符串 word 。

• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。

• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

思路

数据结构题，能理解这棵树长什么样子就很容易画出来。

一般无非两种思路，一种是定义 TrieNode(字典树节点)，另一种是直接用哈希表（数组）。

JS 的语法就有点微妙，所以参考官方题解写的这个代码一开始有些费解。

代码

var Trie = function() {
    this.root = {}
};

Trie.prototype.insert = function(word) {
    let node = this.root
    for (ch of word) {
        if (!node[ch]) {
            node[ch] = {}
        }
        node = node[ch]
    }
    node.isEnd = true
};

Trie.prototype.searchPrefix = function(preix) {
    let node = this.root
    for(let ch of preix) {
        if (!node[ch]){
            return false
        }
        node = node[ch]
    }
    return node
};

Trie.prototype.search = function(word) {
    let node = this.searchPrefix(word)
    return node !== undefined && node.isEnd !== undefined
};

Trie.prototype.startsWith = function(prefix) {
    return this.searchPrefix(prefix)
};

4.13

题目

783. 二叉搜索树节点最小距离

难度简单1

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

• 树中节点数目在范围 [2, 100] 内
• 0 <= Node.val <= 105

思路

利用二叉搜索树的特性，node.left.val < node.val < node.right.val，通过中序遍历一棵二叉搜索树就可以得到一个递增的序列。

有了这个递增序列之后，就很容易寻找任意两个结点的最小差值了。

代码

var minDiffInBST = function(root) {
    const nodes = []
    const inorder = (node) => {
        if(!node) return
        inorder(node.left)
        nodes.push(node.val)
        inorder(node.right)
    }
    inorder(root)
    let res = Infinity
    for(let i = 1; i < nodes.length; i++) {
        res = Math.min(res, nodes[i]-nodes[i-1])
    }
    return res
};

4.12

题目

179. 最大数

难度中等

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

**注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

示例 3：

输入：nums = [1]
输出："1"

示例 4：

输入：nums = [10]
输出："10"

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

思路

有脑筋急转弯内味了，参考了题解。

首先要知道肯定需要对 nums 排序，那么要确定 x 和 y 哪个应该放到更前面，我们可以直接通过以下两个字符串的值来确定

• x + y
• y + x

注意，这边做的都是字符串的拼接，不是单纯加减

如果前者大，那么 x 就放前面，否则放后面。

对排完序之后的数组进行拼接即可得到最终答案。

当然，也有可能出现数组全为 0 的情况，需要额外判断。

代码

var largestNumber = function(nums) {
    nums.sort((x, y) => {
        let s1 = `${x}${y}`
        let s2 = `${y}${x}`
        return s2 - s1
    })
    return nums[0] === 0 ? '0' : nums.join("")
};

4.11

题目

264. 丑数 II

难度中等

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

• 1 <= n <= 1690

思路

1. 最小堆：先存后排序

   一开始最小堆里存放的是 1，然后迭代 n-1 次，每次从最小堆中取出最小数，放回最小数的 2，3，5 倍。

   迭代完之后，堆顶的数，就是第 n 小的数（因为前 n-1 个数已经被用掉了）

2. 三指针：先排序后存

   初始化一个 0 数组，长度为 n，第一个元素初始化为 0

   用三个指针 idx1, idx2, idx3 分别表示当前应该被乘 2,3,5 的基数的位置，一开始都初始为0

   迭代 n-1 次，每次迭代中找到当前能添加的最小数，然后放到对应位置。

代码

# 最小堆
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        nums = [1]
        nums_set = set()
        nums_set.add(1)
        factors = [2, 3, 5]
        for i in range(n-1):
            cur = heapq.heappop(nums)
            for factor in factors:
                if (nxt := cur * factor) not in nums_set:
                    nums_set.add(nxt)
                    heapq.heappush(nums, nxt)
        return heapq.heappop(nums)

// 三指针
var nthUglyNumber = function(n) {
    const nums = new Array(n).fill(0)
    let idx1 = 0, idx2 = 0, idx3 = 0
    nums[0] = 1
    for(let i = 1; i < n; i++){
        let cur = Math.min(nums[idx1] * 2, nums[idx2] * 3, nums[idx3] * 5)
        if (nums[idx1] * 2 === cur) {
            idx1++
        }
        if (nums[idx2] * 3 === cur) {
            idx2++
        }
        if (nums[idx3] * 5 === cur) {
            idx3++
        }
        nums[i] = cur
    }
    return nums[n-1]
};

4.10

语法题

题目

263. 丑数

难度简单

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3

代码

var isUgly = function(n) {
    if (n <= 0) return false 
    while (n > 1){
        if (n % 2 == 0) {
            n /= 2
        } else if (n % 3 == 0) {
            n /= 3
        } else if (n % 5 == 0) {
            n /= 5
        } else {
            return false
        }
    }
    return true
};

4.8

继续二分

题目

153. 寻找旋转排序数组中的最小值

难度中等

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 4 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

思路

通过二分来不断约束，找到最小数的位置。

之所以只需要判断 nums[mid] 和 nums[right] 的原因是：

• 如果中间比右边大，说明最小数必定在右边数组中

  	中
  左
      	右
  

• 如果中间比右边小，那么最小数必定在左边数组中

  左
  		右
  	中
  

参考：leetcode 题解

代码

var findMin = function(nums) {
    let left = 0, right = nums.length - 1
    while (left < right) {
        const mid = (left + right) >> 1
        if (nums[mid] > nums[right]) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
};

4.7

题目

81. 搜索旋转排序数组 II

难度中等

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

思路

菜鸡写不出二分，只能官方题解了。

先说基础的思路：

• 普通的二分可以直接搜索有序数组，但是题目中给的是翻转后的数组，所以只能保证数组部分有序
• 但是我们确实只需要部分有序就能够对二分的范围进行约束
• 假设当前的左指针为 left，右指针为 right，中指针 mid = (left + right) // 2，且此时的 nums[mid] != target
• 此时 nums[left:mid] 和 nums[mid:right] 其中之一必定是有序的
  • 如果 nums[left] <= nums[mid] ，就是左边有序
  • 如果 nums[mid] <= nums[right]，就是右边有序
• 如果此时左边有序
  • 若 nums[left] <= target < nums[mid]，则区间向左约束 right = mid - 1
  • 否则区间向右约束 left = mid + 1
• 如果此时右边有序
  • 若 nums[mid] < target <= nums[right]，则区间向右约束
  • 否则向左约束

在这个基础上，由于题目中给出的数组会重现重复数组，可能出现 [1, 0, 1, 1, 1]，无法正确约束区间

参考官方题解给出的思路是，在 nums[left] == nums[mid] == nums[right] 时，直接将左指针右移一格，右指针左移一格，向中心约束。

代码

var search = function(nums, target) {
    // [mid-1, ...., right, left, ..., mid]
    let left = 0, right = nums.length - 1, mid = 0
    while (left <= right) {
        mid = Math.floor((right + left) / 2)
        const cur = nums[mid]
        if (cur == target) return true
        if (nums[left] == cur && cur == nums[right]) {
            left++
            right--
        }
        else if (nums[left] <= cur) {
            // 前半段有序
            if (nums[left] <= target && target < cur) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // 后半段有序
            if (cur < target && target <= nums[right]) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return false
};

4.6

收到 offer 啦 🤗

题目

80. 删除有序数组中的重复项 II

难度中等

给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按升序排列

思路

快慢指针，这个思路真的🐂。

用慢指针指向合法的数组尾部，用快指针指向已经遍历过的数组尾部。

代码

var removeDuplicates = function(nums) {
    let slow = 2, fast = 2
    while (fast < nums.length) {
        if (nums[fast] != nums[slow-2]) {
            nums[slow++] = nums[fast]
        }
        fast++
    }
    return slow
};

4.5

简单题 😴

题目

88. 合并两个有序数组

难度简单

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中*，*使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[i] <= 109

思路

从 nums1 的尾部开始放数字，反向遍历数组，无需额外开辟数组。

代码

var merge = function(nums1, m, nums2, n) {
    let cur = m + n - 1
    let i = m - 1, j = n - 1
    while (i >= 0 && j >= 0) {
        if(nums1[i] >= nums2[j]) {
            nums1[cur--] = nums1[i--]
        } else {
            nums1[cur--] = nums2[j--]
        }
    }
    while (i >= 0) {
        nums1[cur--] = nums1[i--]
    }
    while (j >= 0) {
        nums1[cur--] = nums2[j--]
    }
};

4.4

题目

781. 森林中的兔子

难度中等

森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

输入: answers = [10, 10, 10]
输出: 11

输入: answers = []
输出: 0

说明:

1. answers 的长度最大为1000。
2. answers[i] 是在 [0, 999] 范围内的整数。

思路

哈希表 + 贪心，先按兔子回答的数字对兔子进行分组，再尽可能地把回答相同的数字分成一个颜色。

代码

var numRabbits = function(answers) {
    const m = new Map()
    answers.forEach((val) => {
        const key = val + 1
        if (!m.has(key)) {
            m.set(key, 1)
        } else {
            m.set(key, m.get(key) + 1)
        }
    })
    let res = 0
    for(let [key, val] of m) {
        const k = Math.ceil(val / key)
        res += k * key
    }
    return res 
};

4.3

字节不出所料，秒挂。

腾讯似乎有点希望？

题目

1143. 最长公共子序列

难度中等472

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

思路

动态规划：由于有两个变量，考虑使用二维的动态规划。

开辟一个二维数组 dp 记录 dp[i][j] 代表 text1[0:i] 和 text[0:j] 的最大公共子序列长度。

Base case：第一行和第一列全部初始化为 0

状态转移方程：如果 text1[i] == text2[j]，则 dp[i][j] = dp[i-1][j-1] + 1，否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

代码

var longestCommonSubsequence = function(text1, text2) {
    const m = text1.length, n = text2.length
    const dp = new Array(m+1).fill(0).map(() => new Array(n+1).fill(0))
    for (let i = 1; i <= m; i++) {
        const c = text1[i-1]
        for (let j = 1; j <= n; j++) {
            if (c === text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
};

4.2

题目

面试题 17.21. 直方图的水量

难度困难

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。

示例:

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

思路

每个位置能储存的水的量，由它左侧的最高柱和右侧最高柱以及它本身的高度的决定。

例如，左侧最高 2，右侧最高 3，本身高度为 1，那么它能存的水就是 min(2, 3) - 1 = 1

有两种方式来统计每根柱子的左右最高情况

• 开辟一个数组进行统计，时间复杂度 O(N)，空间复杂度 O(N)
• 双指针，一边遍历统计，时间复杂度 O(N)，空间复杂度 O(1)

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        # 每个位置能接到的水收到左侧最大高度和右侧最大高度的限制
        if len(height) < 3: return 0
        height = [0] + height + [0]
        left = []
        cur = 0
        for i in height:
            cur = max(cur, i)
            left.append(cur)
        n = len(height)
        res = 0
        cur = 0
        for i in range(n-1, -1, -1):
            if height[i] < min(cur, left[i]):
                res += (min(cur, left[i]) - height[i])
            cur = max(cur, height[i])
        return res
        

var trap = function(height) {
    // 双指针
    let left = 0, right = height.length - 1
    let res = 0
    let leftMax = 0, rightMax = 0
    while (left < right) {
        leftMax = Math.max(leftMax, height[left])
        rightMax = Math.max(rightMax, height[right])
        if (height[left] < height[right]) {
            res += leftMax - height[left]
            left += 1
        } else {
            res += rightMax - height[right]
            right -= 1
        }
        
    }
    return res
};

4.1

🐟人节快乐嗷

题目

1006. 笨阶乘

难度中等50

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。

例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

示例 1：

输入：4
输出：7
解释：7 = 4 * 3 / 2 + 1

示例 2：

输入：10
输出：12
解释：12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

提示：

1. 1 <= N <= 10000
2. -2^31 <= answer <= 2^31 - 1 （答案保证符合 32 位整数。）

代码

标准栈解法

/**
 * @param {number} N
 * @return {number}
 */
var clumsy = function(N) {
    const stk = [N--]
    let idx = 0
    while(N){
        if (idx % 4 == 0) {
            stk.push(stk.pop() * N)
        } else if (idx % 4 == 1) {
            const cur = stk.pop();
            stk.push(cur > 0 ? Math.floor(cur / N) : Math.ceil(cur / N));
        } else if (idx % 4 == 2) {
            stk.push(N)
        } else {
            stk.push(-N)
        }
        N--
        idx++
    }
    
    let res = stk.reduce((pre, cur)=> {
        return pre + cur
    })
    return res
};

if else 大法

class Solution:
    def clumsy(self, N: int) -> int:
        res = 0
        flag = 0
        if N == 3: return 6
        elif N == 2: return 2
        elif N == 1: return 1
        while N > 0:
            if N >= 4:
                if not flag:
                    res += N*(N-1)//(N-2)
                    flag = 1
                else:
                    res -= N*(N-1)//(N-2)
                res += (N-3)
                N -= 4
            elif N == 3:
                res -= 6
                break
            elif N == 2:
                res -= 2
                break
            elif N == 1:
                res -= 1
                break
        return res