sprint

sprint

双周总结

吐槽

  • 新增计划双周参加一次周赛(你问我为啥不参加单周每次的? 白天学别的去了)
  • 软工第四周作业,实战图形识别,虽然代码主体是老师给的,不过研究了研究做了小优化提升了一点准确率,还是有点成就感的。 https://www.cnblogs.com/chmod000/p/13909891.html
  • mini os 学不懂了,缓缓
  • 吐槽大三的专业课:软件工程——人工智能导论(不想吐槽了),操作系统——哲学+天书,今天讲装载链接听得我觉得白看了《程序员的自我修养》,完全听不懂在说啥,课本写的也很玄乎,感觉自己不像在学操作系统,像在学操作系统设计的哲学。就拿今天讲装载链接,听完之后还是讲不出来 cpp 咋变成 exe 的,我还不如翻翻之前的读书笔记……

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

    120. 三角形最小路径和

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

1
2
3
4
5
6
7
8
9
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)

暴力天下第一! 双百解答(可能是因为交的人太少了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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[][]数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 空字符只有一个构成方法(这样刚好对,不知道为什么这么设置) 优化代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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. 数组中重复的数字

个人代码:

1
2
3
4
5
6
7
8
9
10
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),代码如下

1
2
3
4
5
6
7
8
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() 到列表索引的位置,由于使用原列表,空间复杂度就很小。

1
2
3
4
5
6
7
8
9
10
11
12
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++的样例写法

1
2
3
4
5
6
7
8
9
10
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;

矩阵快速幂

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
Author

Ctwo

Posted on

2020-11-03

Updated on

2020-11-03

Licensed under

Comments