leetcode 5.25-5.31

2020-05-27

974 和可被K整除的子数组
394 字符串解码

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是先求出整个数组相加得到的最大值（所有正数和）和最小值（所有负数和）是多少，限定倍数范围后调用子数组和为k的解法求和为$n \times K$的子数组个数。提交超时，需优化。

def subarraySum(nums, k):
    dic = {}
    s = 0
    count = 0
    for num in nums:
        s += num
        if s in dic:
            dic[s] += 1
        else:
            dic[s] = 1
        if (s-k) in dic:
            count += dic[s-k]
    if k in dic:
        count += dic[k]
    if k == 0:
        count -= len(nums)
    return count

class Solution(object):
    def subarraysDivByK(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        max_sum = 0
        min_sum = 0
        for num in A:
            if num >= 0:
                max_sum += num
            else:
                min_sum += num
        min_sum /= K
        max_sum /= K
        cnt = 0
        for n in range(min_sum, max_sum + 1):
            cnt += subarraySum(A, n * K)
        return cnt

尝试用滑动窗口，慢慢增大窗口宽度，时间复杂度$O(n^2)$，超时。

def subarraysDivByK(A, K):
    for i in range(1, len(A)):
        A[i] += A[i-1]

    A.insert(0, 0)
    ret = 0
    for width in range(1, len(A)):
        for end in range(width, len(A)):
            if (A[end] - A[end-width]) % K == 0:
                ret += 1
    return ret

最终求助题解。

同余定理：只要$P[j]$ mod $k == P[i]$ mod $k$，则$P[j] - P[i]$ mod $k = 0$

那么套用之前寻找两数之和的解法，维护的字典以模K的结果为键。个人认为比较trick的点是首先在数组头加一个0元素，那样遍历数组时就不需要考虑下标为0的边界情况；另外需注意，每次统计cnt需要减掉$j$到$j$这样的情况，所以需要-1.

python小知识：字典的get()方法，dict.get(key, default=None)，如果key不存在则返回默认值。

AC代码：

class Solution(object):
    def subarraysDivByK(self, A, K):
        dic = {}
        s = 0
        cnt = 0
        A.insert(0,0)
        for num in A:
            s += num
            remain = s % K
            # cnt += dic.get(remain, 0)
            if remain in dic:
                dic[remain] += 1
            else:
                dic[remain] = 1
            cnt += dic[remain] - 1
        return cnt

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”.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：涉及到括号匹配，用栈操作

AC代码：

class Solution(object):
    def decodeString(self, s):
        stack = []
        for ch in s:
            if ch == ']':
                pattern = []
                while stack[-1] != '[':
                    pattern.append(stack.pop())
                stack.pop()
                repeat = []
                while len(stack) > 0 and stack[-1].isdigit() :
                    repeat += stack.pop()
                repeat.reverse()
                num = int("".join(repeat), 10)
                pattern = num * pattern[::-1]
                stack.append("".join(pattern))
            else:
                stack.append(ch)   
        return ("".join(stack))

参考高速答案，可在进栈前对数字和字符串进行预处理。

python小知识：

list反转：list[::-1]会返回一个新的反转的list，list.reverse()是in-place update
list转字符串：str = “”.join(list)
字符串转整数：num = int(str, scale)，题中转换成十进制