leetcode 马拉松 6.27

剑指 Offer 67. 把字符串转换成整数](https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/)

用正则表达式真的很简单，不必自己造轮子

import re
class Solution:
    def strToInt(self, str: str) -> int:
        s=str.strip(" ")
        if re.match(r"[+-]?\d+",s):
            t=int(re.match(r"[+-]?\d+",s).group(0))
            if t<=-pow(2,31):
                return -pow(2,31)
            elif t>=pow(2,31):
                return pow(2,31)-1
            return t

        return 0
1
2
3
4
5
6
7
8
9
10
11
12
13

剑指 Offer 64. 求1+2+…+n

将乘法变成pow，将除以2换成>>

def sumNums(n: int) -> int:
    """
    (1+n2)*n2/2  -> pow(n2,2)+n2 >>1
    """
    return pow(n,2)+n >>1
if __name__ == '__main__':
    print(sumNums(100))
1
2
3
4
5
6
7

剑指 Offer 66. 构建乘积数组

用left数组记录index左边的数乘积（不包括index）

用right数组记录index右边的数乘积（不包括index）

则B每个数等于left[index]*right[index]

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        if len(a)==0:
            return []
        left=a[:] #记录除了i之外，左边的成绩
        right=a[:] #记录除了i之外 右边的乘积
        s1 = a[0]
        left[0]=1
        for index1 in range(1,len(a)):
            left[index1]=s1
            s1=s1*a[index1]
        s2 = a[-1]
        right[-1]=1
        for index2 in range(len(a)-2,-1,-1):
            right[index2]=s2
            s2=s2*a[index2]
        l=[left[index]*right[index] for index in range(len(a))]
        return l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剑指 Offer 65. 不用加减乘除做加法

用位运算

比如：0100 + 0111

用异或得到加和（不带进位） 0011

用交集得到进位 0100 再往左移一位 1000

此时0011+1000即为结果

但因为不允许用+，所以直接递归，直到其中一者为0即可

def add(a, b):
    if (b == 0):return a
    if (a == 0):return b
    plus1 = (a ^ b) # 求和（不计进位）.相同位置0，相反位置1
    plus2 = ((a & b) << 1)#计算进位.先保留同为1的位，都为1的位要向左进位，因此左移1位
    return add(plus1, plus2)
1
2
3
4
5
6