2020-05-25 至 2020-05-31 LeetCode 每日一题

[0525] 146. LRU缓存机制

LeetCode 146. LRU缓存机制（中）

[0526] 287. 寻找重复数

剑指Offer 面试题03. 数组中的重复数字（易）& LeetCode 287. 寻找重复数（中）

[0527] 974. 和可被 K 整除的子数组

Question

974. 和可被 K 整除的子数组

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。 示例：

输入：A = [4,5,0,-2,-3,1], K = 5
输出：7

解释：有 7 个子数组满足其元素之和可被 K = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

提示： 1 <= A.length <= 30000 -10000 <= A[i] <= 10000 2 <= K <= 10000

keyword： 字符串与哈希表

Intuition

通常，涉及连续子数组问题的时候，我们使用前缀和来解决。

我们令 \(P[i] = A[0] + A[1] + ... + A[i]\)。那么每个连续子数组的和 \(sum(i,j)\) 就可以写成 \(P[j] - P[i-1]\)（其中 \(0 < i < j\)）的形式。此时，判断子数组的和能否被 \(K\) 整除就等价于判断 \((P[j] - P[i-1]) \bmod K == 0\)，根据同余定理，只要 \(P[j] \bmod K == P[i-1] \bmod K\)，就可以保证上面的等式成立。

因此我们可以考虑对数组进行遍历，在遍历同时统计答案。当我们遍历到第 \(i\) 个元素时，我们统计以 \(i\) 结尾的符合条件的子数组个数。我们可以维护一个以 \(P[i-1] \bmod K\)（前缀和模 \(K\) 的值）为键，出现次数为值的哈希表 \(record\)，在遍历的同时进行更新。这样在计算以 \(i\) 结尾的符合条件的子数组个数时，根据上面的分析，答案即为 \([0..i-1]\) 中前缀和模 \(K\) 也为 \(P[i] \bmod K\) 的位置个数，即 \(record[P[i] \bmod K]\)。

最后的答案即为以每一个位置为数尾的符合条件的子数组个数之和。需要注意的一个边界条件是，我们需要对哈希表初始化，记录\(record[0]=1\)，这样就考虑了前缀和本身被 \(K\) 整除的情况。

注意：不同的语言负数取模的值不一定相同，有的语言为负数，对于这种情况需要特殊处理。

作者：LeetCode-Solution 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

import unittest
from typing import List

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        record = {0: 1}
        total, ans = 0, 0
        for elem in A:
            total += elem
            modulus = total % K
            same = record.get(modulus, 0)
            ans += same
            record[modulus] = same + 1
        return ans

class Test_Solution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()
    
    def test_exist(self):
        # 测试用例
        # 功能测试：[4, 5, 0, -2, -3, 1], k=5
        # 边界值测试：[5], k = 5
        # 特殊输入测试：[], k = 5
        inputs = [
            [5],
            [4, 5, 0, -2, -3, 1],
            [],
        ]
        k = [5, 5, 1]
        answers = [
            1,
            7,
            0
        ]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.subarraysDivByK(inputs[i], k[i]))
        self.assertEqual(res, answers)
    
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":

    # 代码编写模式
    unittest.main()

[0528] 394. 字符串解码

Question

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string正好重复 k 次。注意k保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

key words：栈、深度优先搜索

Intuition

• 构建辅助栈 stack， 遍历字符串 s 中每个字符 c；
  • 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
  • 当 c 为字母时，在 res 尾部添加 c；
  • 当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置：
    • 记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作；
    • 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × [...] 字符串。
    • 进入到新 [ 后，res 和 multi 重新记录。
  • 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中:
    • last_res是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a；
    • cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 "3[a2[c]]" 中的 2。
• 返回字符串 res。

复杂度分析： 时间复杂度 \(O(N)\)，一次遍历 s；
空间复杂度 \(O(N)\)，辅助栈在极端情况下需要线性空间，例如 2[2[2[a]]]。

作者：Krahets 链接 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

import unittest
from typing import List

# >>> ord('0') 48
# >>> ord('9') 57
# >>> ord('a') 97
# >>> ord('z') 122
# >>> ord('A') 65
# >>> ord('Z') 90
# >>> chr(91) '['
# >>> chr(93) ']'
class Solution:
    def decodeString(self, s: str) -> str:
        if s == "":  return ""
        stack = []
        multi = 0
        res = ""
        for char in s:
            _ascii = ord(char)
            if 48 <= _ascii <= 57:  # 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
                multi = multi * 10 + int(char)  # 可能是123这样的多个数字
            elif 65 <= _ascii <= 90 or 97 <= _ascii <= 122: # 当 c 为字母时，在 res 尾部添加 c；
                res += char
            elif _ascii == 91:  # 当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置：
                stack.append((multi, res))
                multi = 0
                res = ""
            elif _ascii == 93:  # 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中
                cur_multi, last_res = stack.pop()
                res = last_res + cur_multi * res
            else:
                return ""
        return res


class Test_Solution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()
    
    def test_exist(self):
        # 测试用例
        # 功能测试：多行多列矩阵中存在或不存在的路径
        # 边界值测试：矩阵只有一行或只有一列 矩阵和路径中的所有字母都相同
        # 特殊输入测试：[]
        inputs = [
            "3[a]2[bc]",
            "3[a2[c]]",
            "2[abc]3[cd]ef",
        ]
        answers = [
            "aaabcbc",
            "accaccacc",
            "abcabccdcdcdef"
        ]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.decodeString(inputs[i]))
        self.assertEqual(res, answers)
    
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    # 代码编写模式
    unittest.main()

[0529] 198. 打家劫舍

Question

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1:

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

解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

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



*keyword*：动态规划




##  Intuition

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k(k>2) 间房屋，有两个选项：
1. 偷窃第 k 间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2 间房屋的最高总金额与第 k 间房屋的金额之和。
2. 偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。

用 $dp[i]$ 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
$$
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
$$
边界条件为：
$$
\begin{cases}
dp[0] = nums[0], \\
dp[1] = max(nums[0]， nums[1])
\end{cases}
$$

最终的答案即为 $dp[n-1]$，其中 $n$ 是数组的长度。



## Code

```python
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        size = len(nums)
        if size == 1:
            return nums[0]
        
        dp = [0] * size
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, size):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        
        return dp[size-1]

上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        size = len(nums)
        if size == 1:
            return nums[0]
        
        first = nums[0]
        second = max(first, nums[1])
        for i in range(2, size):
            tmp = second
            second = max(first + nums[i], second)
            first = tmp
        
        return second

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

LeetCode 84. 柱状图中最大的矩形

[0531]101. 对称二叉树

剑指offer 面试题28. 对称的二叉树（易）& LeetCode 101. 对称二叉树（易）