算法工程师的日常
0%

小抄

发表于 更新于 分类于 ，

快速初始化方法

zip用于旋转

1
list(zip(*a))[::-1]

二维数组这么旋转最快

高级乘法

a>>1 表示a//2
a<<1 表示a*2

判断是否为数字等

i.isalnnum()是否是数字或字符串
i.isalpha()判断是否字母
isdigit函数判断是否数字
isdecimal() 方法检查字符串是否只包含十进制字符这种方法只存在于unicode对象。

https://www.runoob.com/python/att-string-isdecimal.html

负数求补码

1
x & 0xffffffff

补码如何变成一个数

1
~(a ^ x)

https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/pythonjie-fa-xiang-xi-jie-du-wei-yun-sua-jrk8/

不能返回数字用于后续对的判断

1
2
3
4
5
def f(x):
    if contiions1:
        return 3
    else:
        return 5

不能用该函数的结果给后面的代码做判断，万一输出的是0，但是这个0是有意义的，那你这么判断是有问题的。

获取数字的二进制

1
bin(5)

获取ascill码的转换

1
2
print(chr(104))
print(ord('a'))

list和str赋值

1
2
3
4
5
6
7
a = ["123","456"]
for i in range(len(a)):
    a[i] = a[i] + '_'
可以得到["123_","456_"]
for i in a:
    i = i + "_"
得到["123","456"]

只能对list中的值修改，不能对str进行修改

快速间隔取数

1
2
nums = [1,2,3,43,4,5,6,7]
nums[1::2]

快速求余

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def remainder(x, a, p):
    rem = 1
    for _ in range(a):
        rem = (rem * x) % p
    return rem

# 求 (x^a) % p —— 快速幂求余
def remainder(x, a, p):
    rem = 1
    while a > 0:
        if a % 2: rem = (rem * x) % p
        x = x ** 2 % p
        a //= 2
    return rem

参考 https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f/

快速求进位数

1
2
(x>>10)&1
看x的第10位是啥

快速轮询

1
2
3
4
5
6
7
8
9
10
i%4表示以4作为循环
for i in range(100):
    res[i%4] += i

# 循环访问数组
res = 0
week = [1,2,3,4,5,6,7]
for i in range(n):
    res = res + week[i%7] + i//7
return res

快速判断奇偶

1
2
x&1
为1表示奇数

快速获取间隔的数组

1
2
a = [1,2,3,4,5,6,7,8]
a[1:10:3] 每间隔3

快速计算斐波那契数列

1
2
import math
math.factorial(3)

快速求中位数

1
2
3
4
5
6
7
# 奇数
n = len(nums1)
if n & 1:
    return nums1[(n-1)//2]
# 偶数
else:
    return (nums1[(n-1)//2] + nums1[(n-1)//2 + 1])/2

快速循环一个序列

1
2
3
4
5
6
7
nums = [1, 2, 3, 4]
for i in range(len(nums)):
    print(nums[i])
    index = (i + 1) % len(nums)
    while index != i:
        print(nums[index])
        index = (index + 1) % len(nums)

加油站[134]那道题

快速判断是否为素数

1
2
def is_prime(n):
		return n >= 2 and all(n%i for i in range(2, int(n**0.5) + 1))

for也可以这么搞

1
2
3
4
5
6
7
for i in range(100):
    if i%2==0:
        xxx
    else:
        xxx
else:
    xxxx

排序和字典排序

1
2
3
nums.sort()
t = list(zip(numn1,nu8m2))
t.sort(key=lambda x:x[0])

字典排序

1
2
3
4
5
nums = [1, 1, 2, 2, 2, 2, 3]
from collections import Counter

cnt = list(Counter(nums).items())
cnt.sort(key=lambda x: x[1], reverse=True)

或者使用defaultdict来排序

1
2
3
4
5
6
7
from collections import defaultdict
d = defaultdict(int)
for i in s:
    d[i] = d[i] + 1
d_list = list(d.items())
d_list.sort(key=lambda x: -x[1])
print(d_list)

快速计算除数和余数

1
2
3
a,b=divmod(10,3)
a=3
b=1

快速复制

a = [1,2,3]
b=a 这样的话a变了的话，b也会变
b=a[:] 这样就不会了

b=a=0
这样不会有问题的

连续求和快速初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def continueSum(nums):
    target = 9
    c = list(range(1, target))
    sums = [c[0]]
    for i in range(1, len(c)):
        sums.append(c[i] + sums[-1])
    print(sums)
    result = []
    for i in range(len(sums)):
        for j in range(i + 1, len(sums)):
            if i == 0:
                val = 0
            else:
                val = sums[i - 1]
            print(i, j, sums[j] - val)
continueSum([9, 4, 2, 3, 8, 0, 6])

如果要求i-j的和，则必须sums[j] - sum[i-1]

数组双循环

1
2
3
for i in range(n):
    for j in range(i+1,n+1):
        print()

快速前缀和初始化

1
2
3
4
5
6
nums = [1, 4, 8, 13]
prefix = [0]
for i in nums:
    prefix.append(prefix[-1] + i)
# 求解 i-j的值
print(prefix[j+1]-prefix[i])

如下：

1
2
3
4
5
for i in range(len(nums)):
    for j in range(i, len(nums)):
        if (prefix[j + 1] - prefix[i]) >= lower and (prefix[j + 1] - prefix[i]) <= upper:
            print(i, j)
            cnt += 1

计算两个索引之间的差值

1
2
3
4
5
6
7
8
arr = [1, 2]
predix = [0]
for i in arr:
    predix.append(predix[-1] + i)
res = 0
for i in range(len(arr)):
    for j in range(i, len(arr)):
        print(i, j)

https://leetcode-cn.com/problems/count-of-range-sum/submissions/

快速累积和

1
2
3
4
5
6
from itertools import accumulate

nums = [1, 2, 3, 5]
res = list(accumulate(nums))
print(res)

动态规划初始化

初始化动态规划数组

1
dp = [[0]* 5 for i in range(5)]

注意，有的时候，行数和列数是不一样的，需要这样初始化

1
2
3
4
m = 2
n = 3
dp = [[0] * m for _ in range(n)]
print(dp)

输出为

1
[[0, 0], [0, 0], [0, 0]]

其中m为列数，n为行的数目

初始化3维的如下，这点在股票交易中常用到的

1
2
# 生成一个3个2 x 2的矩阵
dp = [[[0] * 2 for _ in range(2)] for i in range(3)]

多种遍历方法

右上矩阵遍历

1
2
3
4
5
n = 5
for l in range(n):
    for i in range(n - l):
        j = l + i
        print(i, j)

其它的遍历方方法的话，可以看连接
https://blog.csdn.net/miyagiSimple/article/details/110561865
大部分的情况下，使用横向的遍历就可以了

二分查找Bisect

1
2
3
4
5
6
7
# 使用bisect模块，使用如下
import bisect
arr = [1,3,3,6,8,12,15]
value = 3
idx_left=bisect.bisect_left(arr,value) # 结果1
idx_right=bisect.bisect_right(arr,value) # 结果3
bisect.insort(arr,13)

注意哈，可能会有搜索到的值的索引在最后一个，这就需要判断index是不是>=len(Nums)如果是大于的话，那就要报错了

二分查找的边界条件

1
2
3
4
5
6
7
8
nums = [1,2,3,4,5]
print(bisect.bisect_left(nums,12))
# 得到的值为5，但是没有5的索引的，因此会报错
index = bisect.bisect_left(array2, i + diff // 2)
index = min(len(array2)-1, index)
if array2[index] == i + diff // 2:
    return [i, i + diff // 2]
# 通过将值插入后，判断位置，如果是=len()的话，那直接为len()-1。

二分查找中边界的设置

1
2
3
4
5
6
7
8
9
10
11
res = float("inf")
for i in a:
    index = bisect.bisect_left(b, i)
    if index==len(b):
        diff = abs(i-b[index-1])
    elif index == 0:
        diff = abs(i - b[0])
    elif index>0:
        diff = min(abs(i-b[index-1]), abs(i-b[index]))
    res = min(diff, res)
return res

堆模块heapq

堆的队列，称为优先队列，通常是一个小顶锥，每次维护的头部是最小值。因此可以用来解决topK最大值问题。注意想一下，为啥是一个小顶锥，可以用来解决最大值问题。

注意：heapq.pop是弹出第一个元素，也就是最小的那个

最大topk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 最大topk问题
import heapq
def bigestK(arr, k):
    if k == 0:
        return []
    else:
        l = []
        for i in arr:
            if len(l) < k:
                heapq.heappush(l, i)
            else:
                if i > l[0]:# 注意点
                    heapq.heappop(l)
                    heapq.heappush(l, i)
    return l
a = bigestK([1, 3, 5, 7, 2, 4, 6, 8], 4)
print(a)

可以看到，heapq就是对一个list做操作而已，因此。最后动的还是列表。
可以简化写成如下：

1
2
3
4
5
6
for i in nums:
    if len(res) >= k:
        if i > res[0]:
            heapq.heappop(res)
    else:
        heapq.heappush(res, i)

最小topk

题目见https://leetcode-cn.com/problems/smallest-k-lcci/
对于最小的topk问题解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 最小tooK问题
def smallestK(arr, k):
    if k == 0:
        return []
    else:
        l = []
        for i in arr:
            if len(l) < k:
                heapq.heappush(l, -i)
            else:
                if -i > l[0]: # 注意点
                    heapq.heappop(l)
                    heapq.heappush(l, -i)
    return [-i for i in l]


a = smallestK([1, 3, 5, 7, 2, 4, 6, 8], 4)
print(a)

滑动窗口最大值

解决滑动窗口最大值，题目见 https://leetcode-cn.com/problems/sliding-window-maximum/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxSlidingWindow2(nums, k):
    if k == 1:
        return nums
    else:
        ans = []
        l = []
        for i, j in enumerate(nums):
            if i < k: # 别写错
                heapq.heappush(l, (-j, i))
            else:
                while l and l[0][1] <= i - k:# 别写错
                    heapq.heappop(l)
                heapq.heappush(l, (-j, i))
            if i >= k - 1:# 别写错
                ans.append(-l[0][0])
    return ans

这里注意为啥要取-的呢，因为我们只取一个数值，不会取前K个。
简单写法如下：

1
2
3
4
5
6
7
8
9
def maxSlidingWindow3(nums, k):
    hp, ret = [], []
    for i, j in enumerate(nums):
        while hp and hp[0][1] <= i - k:
            heapq.heappop(hp)
        heapq.heappush(hp, [-j, i])
        if i >= k - 1:
            ret.append(-hp[0][0])
    return ret

单调栈

1
2
3
4
5
6
7
8
9
10
heights = [2, 1, 5, 6, 2, 3]
stack = []
n = len(heights)
right_min = [n] * n
for i in range(n):
    while stack and stack[-1][0] > heights[i]:
        val = stack.pop()
        right_min[val[1]] = i
    stack.append((heights[i], i))
# 求出右边最大的也是可以的

队列queue

解决滑动窗口最大值，题目见 https://leetcode-cn.com/problems/sliding-window-maximum/
解法如下所示：

1
2
3
4
5
6
7
8
9
10
11
def maxSlidingWindow(nums, k):
    q, ret = deque(), []
    for i, j in enumerate(nums):
        while q and nums[q[-1]] < j:
            q.pop()
        if q and q[0] <= i - k:
            q.popleft()
        q.append(i)
        if i >= k - 1:
            ret.append(nums[q[0]])
    return ret

队列在使用中需要注意，需要判断队列是否为空，如在56 合并区间这道题中，如果你需要用队列的话，需要变成这样。

1
2
3
4
5
for index, value in enumerate(nums):
    if not q or value[0]>a[-1][0] and value[0]<q[-1][1]:
        q.append(value)
    else:
        results.append(list(q)

collection常用函数

defaultdict

1
2
3
4
from collections import defaultdict
d = defaultdict(int)
for i in a:
    d[i] = d[i] + 1

Counter

1
2
3
4
a = [2,2,2,2,3]
from  collections import Counter
ct = Counter(a)
print(ct)

如果一个数字不在其中，则输出结果为0，如ct[6]

deque

1
2
3
4
5
6
from collections import deque
d = deque()
d.append(1)
d.append(2)
d.popleft()
d.pop()

回溯结构

分割字符串

将"abc"分割为[a,b,c],[ab,c],[abc],[a,bc]…
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def seg_str(s):
    res = []

    def back(state, s):
        if len(s) == 0:
            res.append(state[:])
        else:
            for i in range(len(s)):
                state.append(s[:i + 1])
                back(state, s[i + 1:])
                state.pop()

    back([], s)
    print(res)

随机组合元素

将[1,2,3,4]变为[1],[1,2,3],[1,2,4],[3,4],[3],[3,4,5],[3,5],…
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
def com_seq(nums):
    res = []

    def back(state, s):
        res.append(state[:])
        for i in range(len(s)):
            state.append(s[i])
            back(state, s[i + 1:])
            state.pop()

    back([], nums)
    print(res)

这里注意在back中没使用到if条件，因为不需要使用到if条件，如果来了一句

1

这点在单词拆分 II中用到了，可以看下。

快速访问二维的list

下面介绍下访问二维的list的方法

1
2
3
4
5
6
7
8
9
matrix = [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]
m = len(matrix)
n = len(matrix[0])
max_k = 0
for i in range(m):
    for j in range(n):
        for k in range(1, max(m - i, n - i)):
            c = [i[j:j + k] for i in matrix[i:i + k]]
            print(c)

初始化结果表

我们在很多情况下，都会要保持结果，如果我们定义了res=[]和res=[0]*n
这两张方式，哪种会更好呢，答案是res=[0]*n。具体可以看特殊数据结构这里的每日温度这道题。如果我们用[]的话，每次都要往里面添加数据，可能有的时候回漏掉数据，但是第二种方式就不会。

1
2
3
4
5
6
res1 = []
res1 = [0] * 5
for i in range(5):
    if i%2==0:
        res1.append(i)
        res1[i] = 4

上述得到的res1和res2结果是不一样的。

常见必备基础算法

快速幂

1
2
3
4
5
6
7
8
9
10
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0: return 0.0
        res = 1
        if n < 0: x, n = 1 / x, -n
        while n:
            if n & 1: res *= x
            x *= x
            n >>= 1
        return res

字典序

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        ans = []
        num = 1
        while len(ans) < n:
            while num <= n:  # 不断进入下一层
                ans.append(num)
                num *= 10
            while num % 10 == 9 or num > n:  # 不断返回上一层
                num //= 10
            num += 1  # 遍历该层下一个数
        return ans

bisect快速赋值

1
2
3
a=[1,2,3]
a[0:0] = [0] 得到结果[0,1,2,3]
a[0:1] = [] 得到[2,3]

这样的效率会高很多

快速定位数据的位数

我们自做1011121314这种题目是，问道你n个数字对应的数值是多少时，可以通过如下简单的方式进行访问。

1
2
3
4
digit = 2
n = 5
nums = 10 + (n-1)//digit
v = str(nums)[(n-1)%digit]

这里你也可以通过如下的方式来访问，不过很慢的

1
2
3
4
5
6
nums = 10 + n//digit - 1
index = last_nums % digit
if index==0:
	return int(str(nums)[-1])
else:
	return int(str(nums+1)[index-1])

这样也可以不过很蛮烦的。

获取最长递增子序列

1
2
3
4
5
6
7
stk = []
for x in posAr:
    if stk and x <= stk[-1]:
        idx = bisect_left(stk, x)
        stk[idx] = x
    else:
        stk.append(x)

更简答的方法如下：

1
2
3
4
stk = []
for x in posAr:
    pos = bisect.bisect_left(stk, x)
    stk[pos: pos + 1] = [x]

注意这里不是stk[pos:pos]

列表快速插入和替换

1
2
3
4
5
6
7
8
9
10
11
a = [1, 2, 3, 6, 7, 8, 9]
a[1:1] = [4]
print(a)
a[3:4] = []
print(a)
a[1:2] = [8]
print(a)
# 结果
[1, 4, 2, 3, 6, 7, 8, 9]
[1, 4, 2, 6, 7, 8, 9]
[1, 8, 2, 6, 7, 8, 9]

埃及筛

1
2
3
4
sign = [1] * 100
for i in range(2,100):
    for j in range(2*i, 101, i):
        sign[j] = 0