sprint

双周总结

吐槽

• 新增计划双周参加一次周赛（你问我为啥不参加单周每次的？ 白天学别的去了）

• 软工第四周作业，实战图形识别，虽然代码主体是老师给的，不过研究了研究做了小优化提升了一点准确率，还是有点成就感的。 https://www.cnblogs.com/chmod000/p/13909891.html

• mini os 学不懂了，缓缓

• 吐槽大三的专业课：软件工程——人工智能导论（不想吐槽了），操作系统——哲学+天书，今天讲装载链接听得我觉得白看了《程序员的自我修养》，完全听不懂在说啥，课本写的也很玄乎，感觉自己不像在学操作系统，像在学操作系统设计的哲学。就拿今天讲装载链接，听完之后还是讲不出来 cpp 咋变成 exe 的，我还不如翻翻之前的读书笔记…

• LeetCode 刷题记录，个人较菜，慢慢努力进步，做题时随手的记录，这里收录一些有意思的题目。

120. 三角形最小路径和

经典dp问题，倒着算可以省下来很多多余的判断

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if len(triangle) == 1:
            return min(triangle[0])
        for row in range(len(triangle)-2, -1, -1):
        # 每一行有 row+1 个数
            for col in range(row+1):
                triangle[row][col] += min(triangle[row+1][col], triangle[row+1][col+1])
        return triangle[0][0]

1638. 统计只差一个字符的子串数目

暴力，寻找两个字符串中的不相同的字母，然后从这个位置开始左右寻找最大的相同的左右位置，就可以得到由这组不相同的字符生成的不同子字符串个数为(l+1)*(r+1)

暴力天下第一！ 双百解答（可能是因为交的人太少了）

def countSubstrings(self, s: str, t: str) -> int:
    result = 0
    for index_s, alpha_s in enumerate(s):
        for index_t, alpha_t in enumerate(t):
            # 寻找每一个不相同的数左右扩展比较
            if alpha_s == alpha_t:
                pass
            else:
                l = 1
                r = 1
                while index_s-l >= 0 and index_t-l >= 0 and s[index_s - l] == t[index_t - l]:
                    l += 1
                while index_s + r < len(s) and index_t + r < len(t) and s[index_s + r] == t[index_t + r]:
                     r += 1
                result += l*r
    return result

1639. 通过给定词典构造目标字符串的方案数

动态规划，dp[i][j]表示使用前 i 个下标，组成 target 第 j 个字符

dp[i][j]由不使用第 i 个字符就组成这 target 中 j 个字符的个数 + 使用 i-1 个组成了 j-1 个字符，然后使用第i个匹配target第j个字符。

…后面的样例很大，算法优化的不好很容易超时。推荐预先记录一下第 i 位每个字母出现的次数，省略多次循环的不必要计算

可以预处理 words，将 words 各字符串的每一位合并，并计算该位置上每种字符数量，得f[][]数组

def numWays(self, words: List[str], target: str) -> int:
    alphas = [0 for k in range(26)]
    MOD = 10**9+7
    word_num = len(words[0])
    target_num = len(target)
    dp = [[0]*target_num for i in range(word_num)]
    num = 0
    for word in words:
        if word[0] == target[0]:
            num += 1
    dp[0][0] = num  # dp[0][j>0] = 0无法构成

    for i in range(1, word_num):
        for a in range(26):
            alphas[a] = 0    
        # alpha 数组为后面的循环做准备，降低时间复杂度
        ss = 0
        for word in words:
            alphas[ord(word[i])-ord('a')] += 1
            ss += word[:i+1].count(target[0])
        dp[i][0] = ss  # 使用前i个字符拼成 target 第 0 个字符的个数
        # 超过 word_num 的部分无法匹配出
        for j in range(1, min(target_num, word_num)):
            # words中第 i位中有多少个可以作为 target 第j位的选择
            num = alphas[ord(target[j])-ord('a')]
            dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] * num) % MOD
    return dp[word_num-1][target_num-1]

6328ms 37.7MB

尝试用评论里的思路优化一下 修改dp[i][j]的含义，改为使用前 i-1 位构成 target 前 j-1 位的方案数 dp[i][0]=1表示target 空字符只有一个构成方法（这样刚好对，不知道为什么这么设置） 优化代码如下：

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        alphas = [0 for k in range(26)]
        MOD = 10**9+7
        word_num = len(words[0])
        target_num = len(target)
        dp = [[0]*(target_num+1) for i in range(word_num+1)]
        dp[0][0] = 1

        for i in range(1, word_num+1):
            for a in range(26):
                alphas[a] = 0
            # alpha 数组为后面的循环做准备，降低时间复杂度
            for word in words:
                alphas[ord(word[i-1])-ord('a')] += 1
            dp[i][0] = 1
            # 超过 word_num 的部分无法匹配出
            for j in range(1, min(target_num+1, word_num+1)):
                # words中第 i位中有多少个可以作为 target 第j位的选择
                num = alphas[ord(target[j-1])-ord('a')]
                dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] * num) % MOD
        return dp[word_num][target_num]

时间2348ms，提升很大（确实这样避开了原方案中dp[i][0]的循环计算）

剑指 Offer 03. 数组中重复的数字

个人代码:

def find_repeat_number(nums: list) -> int:
    nums.sort()
    last = nums[0]
    for i in range(1, len(nums)):
        # 统计出现次数大于 2的数字
        if nums[i] == last:
            return nums[i]
        else:
            last = nums[i]
    return -1

思路挺容易想到，先对列表排序，然后找到第一个重复出现的数字就好了，记录一下前一个数字，遍历和列表的元素对比，顺便直接使用 nums[i] == num[i+1] 由于多次取数组元素会导致速度慢。时间复杂度 O(nlogn)，空间复杂度 O(1)

评论提供了更好的思路:

使用字典自带的哈希表来处理，优点是速度快,对于每个元素 hash() 完成后只需要遍历一遍搜索有无重复即可，时间复杂度 O(n)，但需要另外建立n大小的表，空间复杂度 O(n),代码如下

def findRepeatNumber(self, nums: List[int]) -> int:
    repeat_dict = {}
    for i in nums:
        if i in repeat_dict:
            return i
        else:
            repeat_dict[i] = 1
    return -1

原地哈希方法，时间复杂度 O(n)，空间复杂度 O(1)，很巧妙。具体做法就是因为题目中给的元素是小于 n-1 的，所以我们可以让位置i的地方放元素i。如果位置 i 的元素不是 i 的话，那么我们就把 i 元素的位置放到它应该在的位置，即 nums[i] 和 nums[nums[i]] 的元素交换，这样就把原来在nums[i]的元素正确归位了。如果发现要正确归位的时候，位置上已经有和自己一样的元素了，说明就重复了。相当于将原列表中每个元素 hash() 到列表索引的位置，由于使用原列表，空间复杂度就很小。

def findRepeatNumber(self, nums: List[int]) -> int:
    for i, v in enumerate(nums):
        while i != v:
            # 交换
            v_pos = nums[v]
            if nums[v_pos] == v:
                return v
            else:
                # 将 v 放到属于自己的位置
                nums[i] = nums[v_pos]
                nums[v_pos] = v
    return -1

剑指 Offer 16. 数值的整数次方

比较重要的一个地方 int 的范围是 -2147483648 到 2147483647，如果对 -2147483648 取绝对值会导致 int 型溢出，而2147483647(01111…1) 溢出后还是 -2147483648(100…0) 需要扩大数据类型。（python表示从不关心这个）

本题涉及到快速幂 快速幂一般处理那种指数爆炸的题目，往往要取余 (a * b) % p = (a % p * b % p) % p

快读幂原理 base^exponent = (base*base)^exponent/2 当指数为 1 时就减去 1 base^exponent = base*(base^exponent-1) 然后还可以重复上面的操作

python 自带的 pow 就是快速幂，用不着自己写（比你写的快） 原理就是降指数，变换为底数的平方 给个 c++的样例写法

long long fastPower(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power & 1) {//此处等价于if(power%2==1)
            result = result * base % 1000;
        }
        power >>= 1;//此处等价于power=power/2
        base = (base * base) % 1000;
    }
    return result;

矩阵快速幂

先贴个代码，太晚了先睡了，原理有空再整出来

def matrix_multiply(a, b):
    res = []

    for i in range(len(a)):
        rows = []
        for j in range(len(a[i])):
            temp = 0
            for k in range(len(a[i])):
                temp = (temp + a[i][k] * b[k][j])
            rows.append(temp)
        res.append(rows)

    return res


def matrix_quick_pow(a, n: int):
    # 单位矩阵
    res = [[1 if i == j else 0 for j in range(len(a))] for i in range(len(a))]

    while n:
        if n & 1:
            res = matrix_multiply(res, a)

        a = matrix_multiply(a, a)
        n = n >> 1

    return res