算法工程师的日常
0%

数组与数学

发表于 更新于 分类于 ，

螺旋矩阵系列

螺旋矩阵

题号为54，位于https://leetcode.cn/problems/spiral-matrix/description/ 题解如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix)==1:
            return matrix[0]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        row, col, direction_index = 0, 0, 0
        res = []
        m = len(matrix)
        n = len(matrix[1])
        for i in range(m * n):
            res.append(matrix[row][col])
            matrix[row][col] = -999999999
            next_row = row + directions[direction_index % 4][0]
            next_col = col + directions[direction_index % 4][1]
            if next_row < 0 or next_row >= m or next_col < 0 or next_col >= n or matrix[next_row][next_col] == -999999999:
                direction_index = direction_index + 1
                next_row = row + directions[direction_index % 4][0]
                next_col = col + directions[direction_index % 4][1]
            row, col = next_row, next_col
        return res

上下两道题用的是同样的思路，这样比较好统一

螺旋矩阵II

题号为59，位于 https://leetcode.cn/problems/spiral-matrix-ii/description/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        directions = [(0,1),(1,0),(0,-1),(-1,0)]
        matrix = [[-1]*n for _ in range(n)]
        row, col, direc_index = 0,0,0
        for i in range(n*n):
            matrix[row][col] = i + 1
            next_row = row + directions[direc_index%4][0]
            next_col = row + directions[direc_index%4][1]
            if next_row < 0 or next_row >= n or next_col < 0 or next_row >= n or matrix[next_row][next_col] > -1:
                direc_index = direc_index + 1
                next_row = row + directions[direc_index%4][0]
                next_col = row + directions[direc_index%4][1]
            row, col = next_row, next_col
        return matrix

注意具体的思路是先便利，然后换方向

螺旋矩阵III

题号为885，位于 https://leetcode.cn/problems/spiral-matrix-iii/description/

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
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]: 
        visited_flag = [[False] * cols for _ in range(rows)]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        direction_index = -1
        cnt = 0
        init_lens = 0
        res = []
        res.append([rStart, cStart])
        while cnt + 1 < rows * cols:
            init_lens = init_lens + 1

            direction_index = direction_index + 1
            for j1 in range(init_lens):
                next_r = rStart + directions[direction_index % 4][0]
                next_c = cStart + directions[direction_index % 4][1]
                if next_r < 0 or next_r >= rows or next_c < 0 or next_c >= cols or visited_flag[next_r][next_c]:
                    rStart = next_r
                    cStart = next_c
                else:
                    res.append([next_r, next_c])
                    rStart = next_r
                    cStart = next_c
                    visited_flag[next_r][next_c] = True
                    cnt = cnt + 1

            direction_index = direction_index + 1
            for j2 in range(init_lens):
                next_r = rStart + directions[direction_index % 4][0]
                next_c = cStart + directions[direction_index % 4][1]
                if next_r < 0 or next_r >= rows or next_c < 0 or next_c >= cols or visited_flag[next_r][next_c]:
                    rStart = next_r
                    cStart = next_c
                else:
                    res.append([next_r, next_c])
                    rStart = next_r
                    cStart = next_c
                    visited_flag[next_r][next_c] = True
                    cnt = cnt + 1
        return res

主要思路就是分析题目，其实每个固定的长度比如走1格子，其实是分为两个角度来走的，那么整体上就是1步往右，1步往下，2步往左，2步往上。依次这样来再结合判断条件。

螺旋矩阵 IV

和,2一样，题目2326，位于 https://leetcode.cn/problems/spiral-matrix-iv/

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        res = []
        while head:
            res.append(head.val)
            head = head.next
        matrix = [[-1]*n for _ in range(m)]
        visited = [[False]*n for _ in range(m)]
        x, y, dirrection_index = 0,0,0
        directions = [(0,1),(1,0),(0,-1),(-1,0)]
        for i in range(m*n):
            if i < len(res):
                matrix[x][y] = res[i]
            visited[x][y] = True
            next_x = x + directions[dirrection_index%4][0]
            next_y = y + directions[dirrection_index%4][1]
            if next_x<0 or next_x>=m or next_y<0 or next_y>=n or visited[next_x][next_y]:
                dirrection_index = dirrection_index + 1
                next_x = x + directions[dirrection_index%4][0]
                next_y = y + directions[dirrection_index%4][1]
            x, y = next_x, next_y
        return matrix

数组类

摆动排序II[324]

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
28
29
30
31
32
33
34
35
36
37
38
39
40
# 自己解法
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        mid = (len(nums) + 1) // 2
        nums.sort()
        left = nums[0:mid][::-1]
        right = nums[mid:][::-1]
        all_combine = []
        n1 = mid
        n2 = len(nums) - n1
        index1 = 0
        index2 = 0
        while index1 < n1 and index2 < n2:
            all_combine.append(left[index1])
            all_combine.append(right[index2])
            index1 += 1
            index2 += 1
        all_combine.extend(left[index1:])
        for i in range(len(nums)):
            nums[i] = all_combine[i]
# 简单解法
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        temp = [0] * len(nums)
        j = len(nums) - 1
        for i in range(1, len(nums), 2):
            temp[i] = nums[j]
            j = j - 1
        for i in range(0, len(nums), 2):
            temp[i] = nums[j]
            j = j - 1
        for i in range(len(nums)):
            nums[i] = temp[i]

奇数索引上规律是从大到小，偶数索引上规律也是从大到小，再次发现先对奇数索引进行填充，再对偶数索引填充

数学类

幂类

获取2进制

如何获取一个数的2进制表示

1
2
3
4
5
6
7
8
n = 10
res = []
if n < 0:
    n = n + pow(2,32)
while n > 0:
    n, m = divmod(n, 2)
    res.append(m)
print("".join([str(i) for i in res[::-1]))

小数的二进制结果如下：
题目在这里 https://leetcode-cn.com/problems/bianry-number-to-string-lcci/

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def printBin(self, num: float) -> str:
        res = []
        for i in range(1,50):
            if num - 1/(2**i) >= 0:
                num = num - 1/(2**i)
                res.append(1)
            else:
                res.append(0)
        index2 = len(res) - res[::-1].index(1)
        if index2>=32:
            return "ERROR"
        return '0.' + "".join([str(x) for x in res[:index2]])

获取16进制

题目见 https://leetcode-cn.com/problems/convert-a-number-to-hexadecimal/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def toHex(self, num: int) -> str:
        num_lst = list("0123456789abcdef")
        res = []
        if num < 0:
            num = num + 2**32
        while num > 0:
            num, n = divmod(num, 16)
            res.append(n)
        res2 = [num_lst[i] for i in res[::-1]]
        return "".join(res2)

计算pow

这道题有两个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# v1 使用递归
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            if N == 0:
                return 1.0
            y = quickMul(N // 2)
            return y * y if N % 2 == 0 else y * y * x
        
        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)


# v2 使用快读幂指数算法
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

数值的整数次方

题目见 https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/ 题解如下：

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

计算sqrt

题解如下：

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
28
29
30
31
32
33
34
35
# 通过log
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        ans = int(math.exp(0.5 * math.log(x)))
        return ans + 1 if (ans + 1) ** 2 <= x else ans
# 通过二分
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l <= r:
            mid = (l + r) // 2
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans
# 通过牛顿
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        
        C, x0 = float(x), float(x)
        while True:
            xi = 0.5 * (x0 + C / x0)
            if abs(x0 - xi) < 1e-7:
                break
            x0 = xi
        
        return int(x0)


计算是否是2的幂

题目见 https://leetcode-cn.com/problems/power-of-two/ 题解如下：

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 isPowerOfTwo(self, n: int) -> bool:
        if n==0:
            return False
        num = n
        while num!=1:
            ys = num%2
            if ys==1:
                return False
            num = num//2
        return True
# 技巧
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0
# 框架
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        while n and n % 2 == 0:
            n //= 2
        return n == 1

重新排序得到 2 的幂

题目见 https://leetcode-cn.com/problems/reordered-power-of-2/ 题解如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# TL了
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        if n==1:
            return True
        res = []
        def back(state, s):
            if len(s)==0:
                res.append(state[:])
            else:
                for i in range(len(s)):
                    state.append(s[i])
                    back(state, s[0:i]+s[i+1:])
                    state.pop()
        back([],str(n))

        res2 = []
        for i in res:
            if not int(i[-1])%2:
                res2.append(int("".join(i)))
    
        def isPow(n):
            return n > 0 and (n & (n - 1)) == 0

        for i in res2:
            if isPow(i):
                return True
        return False

# 首先算好每个结果，然后去查一下是不是在其中
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        def check(targ: int, num: int) -> bool:
            a = [0 for _ in range(10)]
            b = [0 for _ in range(10)]
            while targ:
                x = targ % 10 
                a[x] += 1
                targ //= 10
            while num:
                x = num % 10
                b[x] += 1
                num //= 10
            return a == b


        for i in range(31):
            targ = 2 ** i
            if check(targ, n) == True:
                return True
        return False

计算是否是3的幂

题目见 https://leetcode-cn.com/problems/power-of-three/ 题解如下：

1
2
3
4
5
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while n and n % 3 == 0:
            n //= 3
        return n == 1

计算是否是4的幂

题目见 https://leetcode-cn.com/problems/power-of-four/，题解如下：

1
2
3
4
5
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        while n and n % 4 == 0:
            n //= 4
        return n == 1

幂集

题目在 https://leetcode-cn.com/problems/power-set-lcci/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 错误
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        def back(state,s):
            res.append(state[:])
            for i in range(len(s)):
                state.append(s[i])
                back(state, s[i:])
                state.pop()
        back([],nums)
        return res
# 正确
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        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)
        return res

判断一个数字是否可以表示成三的幂的和

题目见 https://leetcode-cn.com/problems/check-if-number-is-a-sum-of-powers-of-three/ 题解如下：

1
2
3
4
5
6
7
8
class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        for i in range(31,-1,-1):
            if n - 3**i >= 0:
                n = n - 3**i
                if n==0:
                    return True
        return False

大餐计数

题目见 https://leetcode-cn.com/problems/count-good-meals/ 题解如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 时间不够
class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        nums = deliciousness

        def ispow(x):
            return x>0 and x & (x-1)==0
        
        cnt = 0
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                v = nums[i] + nums[j]
                if ispow(v):
                    cnt += 1
        return cnt
# 错误
class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        cnt = Counter(deliciousness)
        res = 0
        print(cnt.keys())
        for key in cnt.keys():
            for i in range(32):
                if key == 2 **i:
                    res = res + cnt[key] * (cnt[key] - 1)
                else:
                    res = res + cnt[key] * (cnt[2 ** i - key])
        return res//2
# 好
class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        cnt = Counter(deliciousness)
        res = 0
        print(cnt.keys())
        for key in cnt.keys():
            for i in range(32):
                if key == 2 ** (i-1): # 改动
                    res = res + cnt[key] * (cnt[key] - 1)
                else:
                    res = res + cnt[key] * (cnt[2 ** i - key])
        return res//2

注意这里需要考虑 pow(2,i) 和key的关系，避免1+1=2这种，或者你在else里面加上 pow(2,i)-key!=key的判断才可以的.

除法类

快速求余

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/

两数相除

题目见 https://leetcode-cn.com/problems/divide-two-integers/， 这里我做了很多次代码，每次都是在边界条件那里出了问题，看下详细的过程如下：

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
# 提交次数1
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        flag = 1 if dividend * divisor > 0 else -1
        dividend = abs(dividend)
        divisor = abs(divisor)

        if divisor == 0:
            return 0
        if divisor == 1:
            return dividend
        i = 1
        while divisor * i < dividend:
            i *= 2

        l = i // 2
        r = i

        while r - l > 1:
            mid = (r + l) / 2
            if mid * divisor > dividend:
                r = mid
            else:
                l = mid
        return int(l * flag)

错误原因，对于1 -1这样的输入是会有问题的，接下来第二版

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
# 提交次数2
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        flag = 1 if dividend * divisor > 0 else -1
        dividend = abs(dividend)
        divisor = abs(divisor)
        if divisor == 0:
            return 0
        if divisor == 1:
            return dividend*flag
        if divisor==dividend:
            return 1*flag

        i = 1
        while divisor * i < dividend:
            i *= 2

        l = i // 2
        r = i

        while r - l > 1:
            mid = (r + l) / 2
            if mid * divisor > dividend:
                r = mid
            else:
                l = mid
        return int(l * flag)

错误的原因在于没有考虑到2^31这种，接下来第三版

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
28
29
30
31
32
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        flag = 1 if dividend * divisor > 0 else -1
        dividend = abs(dividend)
        divisor = abs(divisor)
        if divisor == 0:
            c = 0
        elif divisor == 1:
            c = dividend
        elif divisor == dividend:
            c = 1
        else:
            i = 1
            while divisor * i < dividend:
                i *= 2

            l = i // 2
            r = i

            while r - l > 1:
                mid = (r + l) / 2
                if mid * divisor > dividend:
                    r = mid
                else:
                    l = mid
            c = l
        c = c * flag
        if c >= 2147483647:
            c = 2147483647
        if c <= -1 * math.pow(2, 31):
            c = -1 * math.pow(2, 31)
        return int(c)

这里改变了之前的逻辑结构，把所有的if改变了。但是还是会标错，原因在于while那里。

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
28
29
30
31
32
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        flag = 1 if dividend * divisor > 0 else -1
        dividend = abs(dividend)
        divisor = abs(divisor)
        if divisor == 0:
            c = 0
        elif divisor == 1:
            c = dividend
        elif divisor == dividend:
            c = 1
        else:
            i = 1
            while divisor * i <= dividend:
                i *= 2

            l = i // 2
            r = i

            while r - l > 1:
                mid = (r + l) / 2
                if mid * divisor > dividend:
                    r = mid
                else:
                    l = mid
            c = l
        c = c * flag
        if c >= 2147483647:
            c = 2147483647
        if c <= -1 * math.pow(2, 31):
            c = -1 * math.pow(2, 31)
        return int(c)

这是可以通过的代码。

高级的结算结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def divide(a, b):
    INT_MIN, INT_MAX = -2 ** 31, 2 ** 31 - 1
    if a == INT_MIN and b == -1:
        return INT_MAX

    sign = -1 if (a > 0) ^ (b > 0) else 1

    a, b = abs(a), abs(b)
    ans = 0
    for i in range(31, -1, -1):
        if (a >> i) - b >= 0:
            a = a - (b << i)
            ans += 1 << i

    # bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
    return ans if sign == 1 else -ans

我模仿写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def divide(self, a: int, b: int) -> int:
        INT_MIN, INT_MAX = -2 ** 31, 2 ** 31 - 1
        if a == INT_MIN and b == -1:
            return INT_MAX
        if b == 0 or a == 0:
            return 0
        flag = 1 if a*b>0 else -1
        a,b = abs(a),abs(b)
        ans = 0
        for i in range(31,-1,-1):
            if (a>>i) - b >= 0:
                a = a - (b<<i)
                ans+= 1<<i
        return ans*flag

剑指 Offer II 001. 整数除法

题目见 https://leetcode-cn.com/problems/xoh6Oh/， 和上面是一样的，解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def divide(a, b):
    INT_MIN, INT_MAX = -2 ** 31, 2 ** 31 - 1
    if a == INT_MIN and b == -1:
        return INT_MAX

    sign = -1 if (a > 0) ^ (b > 0) else 1

    a, b = abs(a), abs(b)
    ans = 0
    for i in range(31, -1, -1):
        if (a >> i) - b >= 0:
            a = a - (b << i)
            ans += 1 << i

    # bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
    return ans if sign == 1 else -ans

Excel表列名称

题目见 https://leetcode-cn.com/problems/excel-sheet-column-title/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 错误
class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        res = []
        while columnNumber > 0:
            a0 = (columnNumber-1)%26 + 1
            res.append(chr(a0 - 1 + ord("A")))
            columnNumber = columnNumber - a0
        return "".join(res[::-1] )
# 通过
class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        res = []
        while columnNumber > 0:
            a0 = (columnNumber-1)%26 + 1
            res.append(chr(a0 - 1 + ord("A")))
            columnNumber = (columnNumber - a0)//26
        return "".join(res[::-1] )

这道题的做法有点饶的，还是需要结合题解进一步理解
image

Excel 表列序号

题目见 https://leetcode-cn.com/problems/excel-sheet-column-number/ 题解如下：

1
2
3
4
5
6
7
8
9
class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        num = 0
        multipy = 1
        for i in columnTitle[::-1]:
            v = ord(i) - ord('A') + 1
            num += v * multipy
            multipy *= 26
        return num

这道题中的最后的累乘和 数字序列中某一位的数字 这道题有点类似，可以看下

水壶问题（最大公约数）

题目见 https://leetcode-cn.com/problems/water-and-jug-problem/ 解法如下：

1
2
3
4
5
6
7
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if x + y < z:
            return False
        if x == 0 or y == 0:
            return z == 0 or x + y == z
        return z % math.gcd(x, y) == 0

其实就是求最大公约数的问题

完美数

题目见 https://leetcode-cn.com/problems/perfect-number/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 超时
直接循环来做的话，会超时，因此需要熊2到sqrt进行遍历，这样会少了一部分的计算量
# 通过
class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num==1:
            return False
        res = [1]
        for i in range(2,int(num**0.5)+1):
            if num % i == 0:
                res.append(i)
                res.append(num//i)
        if sum(res)==num:
            return True
        else:
            return False

分数到小数

题目见 https://leetcode-cn.com/problems/fraction-to-recurring-decimal/ 题解如下：

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
28
29
30
class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0: return "0"
        res = []
        # 首先判断结果正负, 异或作用就是 两个数不同 为 True 即 1 ^ 0 = 1 或者 0 ^ 1 = 1
        if (numerator > 0) ^ (denominator > 0):
            res.append("-")
        numerator, denominator = abs(numerator), abs(denominator)
        # 判读到底有没有小数
        a, b = divmod(numerator, denominator)
        res.append(str(a))
        # 无小数
        if b == 0:
            return "".join(res)
        res.append(".")
        # 处理余数
        # 把所有出现过的余数记录下来
        loc = {b: len(res)}
        while b:
            b *= 10
            a, b = divmod(b, denominator)
            res.append(str(a))
            # 余数前面出现过,说明开始循环了,加括号
            if b in loc:
                res.insert(loc[b], "(")
                res.append(")")
                break
            # 在把该位置的记录下来
            loc[b] = len(res)
        return "".join(res)

参考如下：https://leetcode-cn.com/problems/fraction-to-recurring-decimal/solution/ji-lu-yu-shu-by-powcai/

其实主要玩的思路是这样的，比如2/3这个数，逻辑如下所示：

1
2
3
4
5
6
x = 2
y = 3
a, b = divmod(x, y)
while b:
    b *= 10
    a, b = divmod(b, y)

计算器

实现计算器的代码如下

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
28
29
30
代码如下
pri = {"(": 1, "+": 2, "-": 2, "*": 3, "/": 3}
ops_stack = []
post_stack = []
s = "(1+2)/3-4*2-(3-4)"
for i in s:
    if i == ' ':
        continue
    if i.isdigit():
        post_stack.append(i)
    elif i == "(":
        ops_stack.append(i)
    elif i == ")":
        while ops_stack[-1] != "(":
            post_stack.append(ops_stack.pop())
    else:
        while ops_stack and pri[ops_stack[-1]] >= pri[i]:
            post_stack.append(ops_stack.pop())
        ops_stack.append(i)
post_stack.extend([i for i in ops_stack[::-1] if i != "("])

s1 = []
for i in post_stack:
    if not i.isdigit():
        a = int(s1.pop())
        b = int(s1.pop())
        s1.append(do_math(i, a, b))
    else:
        s1.append(i)
sum(s1)

基本计算器

题目见 https://leetcode-cn.com/problems/basic-calculator/， 题解如下：

更一般的代码如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
a = "1+(2+6/1+2)"
# a = "2+9/3-5"
# 可能出现的符号
symbol_1 = ['+', '-', '*', '/']
symbol_2 = ['(']
symbol_3 = [')']
# 符号的优先级
priority = {'#': -1, '(': 1, '+': 2, '-': 2, '*': 3, '/': 3}
match_2 = {')': '('}
# 存储符号的栈
stack = []
stack.append("#")
# 结果
result = []


# 下面通过将中缀表达式转换为后缀表达式，并进行运算
def my_operation(symbol, a, b):
    a, b = int(a), int(b)
    if symbol == '+':
        return a + b
    elif symbol == '-':
        return a - b
    elif symbol == '*':
        return a * b
    elif symbol == '/':
        return a / b


def to_operation(result, stack):
    two = result.pop()
    one = result.pop()
    symbol = stack.pop()
    ret = my_operation(symbol, one, two)
    print(f"{one}{symbol}{two} = {ret}")
    result.append(ret)


### 在表达式转换的时候就一边进行了运算
for i in a:
    # 如果是数字直接添加到结果
    if i.isdigit():
        result.append(i)
    # 如果是 + - * / 运算，则先出栈更低优先级的，然后入栈
    elif i in symbol_1:
        # 如果优先级低，则出栈所有优先级>=的符号
        while priority[i] <= priority[stack[-1]]:
            to_operation(result, stack)
        # 压入符号
        stack.append(i)
    # 如果是左括号，直接压入
    elif i in symbol_2:
        stack.append(i)
    # 如果是右括号，则出栈，直到遇到了匹配的左括号，然后吧左括号也出栈
    elif i in symbol_3:
        while stack[-1] != match_2[i]:
            to_operation(result, stack)
        stack.pop()

to_operation(result, stack)
print(result)

基本计算器 II

题目见 https://leetcode-cn.com/problems/basic-calculator-ii/，题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        nums = 0
        pre_flag = "+" # 注意
        s = s + "$" # 注意

        for i in s:
            if i.isdigit():
                nums = nums*10 + int(i)
            elif i==' ':
                continue
            else:
                if pre_flag == '+':
                    stack.append(nums)
                if pre_flag == '-':
                    stack.append(-nums)
                if pre_flag == '*':
                    stack.append(stack.pop()*nums)
                if pre_flag == '/':
                    stack.append(int(stack.pop()/nums))
                pre_flag = i #注意
                nums = 0
        return sum(stack)

字典序类

数字序列中某一位的数字

题目见 https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/ 和之前的字典序的题目不太一样，和数学是有关系的，主要是要自减。
解法如下：

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
28
29
30
31
# 简洁做法
def findNthDigit(n):
    digit, start, count = 1, 1, 9
    while n > count:  # 1.
        n -= count
        start *= 10
        digit += 1
        count = 9 * start * digit
    num = start + (n - 1) // digit  # 2.获取数字
    return int(str(num)[(n - 1) % digit])  # 3. 获取对应的位数
# 我的解法
def findNthDigit(n):
    """
    :type n: int
    :rtype: int
    """
    digit = 1
    while n > 0:
        start = digit * 9 * (10**(digit-1))
        n -= start
        digit += 1
    
    last_nums = n + start
    digit -= 1
    begin = 10 **(digit-1)
    word = begin + last_nums//digit - 1
    index = last_nums % digit
    if index==0:
        return int(str(word)[-1])
    else:
        return int(str(word+1)[index-1])

加法类

二进制求和

题解见 https://leetcode-cn.com/problems/add-binary/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        n1 = len(a)
        n2 = len(b)
        if n1 < n2:
            a = '0'*(n2-n1)+a
        if n2 < n1:
            b = '0'*(n1-n2)+b
    
        res = ''
        div = 0
        for i in range(len(a)-1,-1,-1):
            h = int(a[i]) + int(b[i]) + div
            div, remain = divmod(h + div, 2)
            res+=str(remain)
        if div:
            res+=str(div) # 注意
        return res[::-1]

字符串相加

题目见 https://leetcode-cn.com/problems/add-strings/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        n1 = len(num1)
        n2 = len(num2)
        if n1 < n2:
            num1 = '0'*(n2-n1)+num1
        if n2 < n1:
            num2 = '0'*(n1-n2)+num2
    
        res = ''
        div = 0
        for i in range(len(num1)-1,-1,-1):
            h = int(num1[i])+int(num2[i])+div
            div, remind = divmod(h, 10)
            res+=str(zhi)
        if div:
            res+=str(div) # 注意
        return res[::-1]

加一

题目见 https://leetcode-cn.com/problems/plus-one/ 题解如下：

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
28
29
30
31
32
33
34
35
# 错误
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        res = []
        y = 0
        y = 0
        digits2 = digits[::-1]
        for i in range(len(digits2)):
            if i == 0:
                v = (digits2[i] + y + 1) % 10
            else:
                v = (digits2[i] + y) % 10
            y = (digits2[i] + 1) // 10
            res.append(v)
        if y > 0:
            res.append(y)
        return res[::-1]
#正确
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        res = []
        y = 0
        y = 0
        digits2 = digits[::-1]
        for i in range(len(digits2)):
            if i == 0:
                v = (digits2[i] + y + 1) % 10
                y = (digits2[i] + y + 1) // 10
            else:
                v = (digits2[i] + y) % 10
                y = (digits2[i] + y) // 10
            res.append(v)
        if y > 0:
            res.append(y)
        return res[::-1]

乘法类

递归乘法

题目见 https://leetcode-cn.com/problems/recursive-mulitply-lcci/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# v1
class Solution:
    def multiply(self, A: int, B: int) -> int:
        return A*B
# v2
class Solution:
    def multiply(self, A: int, B: int) -> int:
        res = 0
        while B:
            if B&1: res = res + A
            A = A + A
            B>>=1
        return res
# v3 
class Solution:
    def multiply(self, A: int, B: int) -> int:
        def dfs(A,B):
            if B==1:
                return A
            s = dfs(A,B//2)
            return s+s if B%2==0 else s+s+A
        return dfs(A,B)

位运算

不用加减乘除做加法

题目见 https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/ 题解如下：

1
2
3
4
5
6
7
class Solution:
    def add(self, a: int, b: int) -> int:
        x = 0xffffffff
        a,b = a&x,b&x
        while b!=0:
            a,b = a^b, (a&b)<<1&x
        return a if a <= 0x7fffffff else ~(a ^ x)

消失的数字

题目见 https://leetcode-cn.com/problems/missing-number-lcci/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        for i in range(n):
            res = res ^ i ^ nums[i]
        res ^= n
        return res
# 
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        r = 0
        for i in nums:
            r ^= i
        for i in range(len(nums)+1):
            r ^= i
        return r

数组中数字出现的次数

题目见 https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        res = 0
        for i in nums:
            res ^= i
        m = 1
        while res & m==0:
            m <<=1
        x = 0
        y = 0
        for i in nums:
            if i & m:
                x^=i
            else:
                y^=i
        return [x,y]

单数字操作

最大交换

题目见 https://leetcode-cn.com/problems/maximum-swap/， 题解如下

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
28
29
30
31
32
33
34
35
36
37
38
39
from collections import Counter


class Solution:
    def maximumSwap(self, num: int) -> int:
        if not num:
            return 0

        # 倒序之后的数字列表
        sorted_num = sorted(list(str(num)), reverse=True)
        # 原数字列表
        num_list = list(str(num))
        if sorted_num == num_list:
            # 本来就是降序的，直接返回
            return num

        index = 0
        change_num = -1
        # 一一对比原列表和排序列表
        while index < len(num_list):
            if num_list[index] == sorted_num[index]:
                # 如果相同位置的数字相同，继续
                index += 1
                continue
            # 找到不同的数字了，此时index就是需要交换的左边索引
            # change_num就是需要交换的数字
            change_num = sorted_num[index]
            break
            
        # 需要将最右边的大数跟最左边的小数交换
        num_list.reverse()
        # 找到最右边的大数索引
        change_index = len(num_list) - 1 - num_list.index(change_num)
        num_list.reverse()
        
        # 交换
        num_list[index], num_list[change_index] = num_list[change_index], \
                                                  num_list[index]
        return int(''.join(num_list))

下一个排列

下一个更大元素 I

下一个更大元素 II

下一个更大元素 III

其他

剪绳子

题目见 https://leetcode-cn.com/problems/jian-sheng-zi-lcof/ 题解如下：

1
2
3
4
5
6
7
8
9
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n < 4:
            return n - 1
        res = 1
        while n > 4:
            res *=3
            n -= 3
        return res * n

分糖果 II

题目见 https://leetcode-cn.com/problems/distribute-candies-to-people/ 题解如下：

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
28
29
30
31
32
33
34
35
36
37
38
# 复杂点的做法
class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        res = [0] * num_people
        start = 1
        index = 0
        while candies - start> 0:
            candies -= start
            res[index] = res[index] + start
            start += 1
            index = (index + 1)%num_people
        if candies > 0:
            res[index] = res[index] + candies
        return res
# 或者
class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        res = [0] * num_people
        start = 1
        index = 0
        while candies - start> 0:
            candies -= start
            res[index%num_people] = res[index%num_people] + start
            start += 1
            index = index + 1
        if candies > 0:
            res[index%num_people] = res[index%num_people] + candies
        return res
# 简洁做法
class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        res = [0]*num_people
        i = 0
        while candies!=0:
            res[i%num_people] += min(i+1, candies)
            candies = candies - min(i+1, candies) # 保证不为负数
            i+=1
        return res

排列序列

题目见 https://leetcode-cn.com/problems/permutation-sequence/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        import math
        toeken = [str(i) for i in range(1,n+1)]
        k -= 1
        res = ""
        while n > 0:
            n -= 1
            a, k = divmod(k,math.factorial(n))
            res += toeken.pop(a)
        return res

三个数的最大乘积

题目见 https://leetcode-cn.com/problems/maximum-product-of-three-numbers/ 题解如下：

1
2
3
4
5
6
class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        a = nums[-1]*nums[-2]*nums[-3]
        b = nums[-1]*nums[0]*nums[1]
        return max(a,b)

其实很简单的，只是我们在写的时候弄的复杂了，主要判断最后一个数字和倒数两个以及前两个的大小。

最小操作次数使数组元素相等

题目见 https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements/ 题解如下：

1
2
3
4
5
6
7
class Solution:
    def minMoves(self, nums: List[int]) -> int:
        min_num = min(nums)
        res = 0
        for num in nums:
            res += num - min_num
        return res

换酒问题

题目见 https://leetcode-cn.com/problems/water-bottles/ 题解如下：

1
2
3
4
5
6
7
8
class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        res = numBottles
        while numBottles >= numExchange:
            bear, numBottles = divmod(numBottles, numExchange)
            res += bear
            numBottles = numBottles + bear
        return res

注意上面的while的条件哈

矩形重叠

题目见 https://leetcode-cn.com/problems/rectangle-overlap/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 错误
class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        x1, y1 = rec2[0], rec2[1]
        x3, y3 = rec2[2], rec2[3]
        x2, y2 = x1, y3
        x4, y4 = x3, y1

        x, y = rec1[0], rec1[1]
        x5, y5 = rec1[2], rec1[3]

        for k,f in [(x1,y1),(x2,y2),(x3,y3),(x4,y4)]:
            if k>x and k<x5 and f>y and f<y5:
                return True
        return False
# 可以
class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        x_overlap = not(rec1[2]<=rec2[0] or rec2[2]<=rec1[0])
        y_overlap = not(rec1[3]<=rec2[1] or rec2[3]<=rec1[1])
        return x_overlap and y_overlap

矩阵面积

题目见

单调递增的数字

题目见 https://leetcode-cn.com/problems/monotone-increasing-digits/ 题解如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# 自己写的
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:      
        def get_p_n(n):
            res = []
            while n > 0:
                n, m = divmod(n, 10)
                res.append(m)
            return res[::-1]
        
        def get_index(res):
            for i in range(len(res)-1):
                if res[i+1] < res[i]:
                    return i
            else:
                return -1

        def dfs(res):
            idx = get_index(res)
            if idx==-1:
                return res
            else:
                font = res[0:idx+1]
                font[-1] = font[-1]-1 if font[-1]-1>=0 else 9
                return dfs(font) + [9]*(len(res)-idx-1)

        res = get_p_n(n)
        res2 = dfs(res)
        res3 = 0
        for i in res2:
            res3 = res3*10 + i
        return res3
# 贪心做法
lass Solution:
    def monotoneIncreasingDigits(self, N):
        n = str(N)
        num = []
        for i in n:
            num.append(i)

        nine = len(num)
        for i in range(len(num) - 1, 0, -1): # 注意之类的操作
            if num[i - 1] > num[i]:
                num[i - 1] = str(int(num[i - 1]) - 1)
                nine = i

        num = ''.join(num)
        num = int(num[:nine] + '9' * (len(num) - nine))
        return num

注意上面的操作，如果换成下面的代码会出错的，因此塔一边从后往前，一边会修改值。

1
2
3
4
for i in range(len(num) - 1):
	if num[i + 1] > num[i]:
		num[i] = str(int(num[i]) - 1)
		nine = i

1～n 整数中 1 出现的次数

题目见 https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def countDigitOne(self, n: int) ->  int:
        a, b, one_count = 1, 10, 0
        while n >= a:
            x, y = divmod(n, b)
            
            if y >= a * 2:
                one_count += (x + 1) * a
            elif y >= a:
                one_count += y + 1 + (x - 1) * a
            else:
                one_count += x * a 

            a, b = b, b*10 
        
        return one_count

三角形的最大周长

题目见 https://leetcode-cn.com/problems/largest-perimeter-triangle/， 题解如下：

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
# 超时
class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        max_triangle_length = 0
        nums.sort(reverse=True)
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                p = j + 1
                while p < len(nums):
                    if abs(nums[i] - nums[j]) < nums[p]:
                        return nums[i]+nums[j]+nums[p]
        return 0
# 通过
class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums)-1,1,-1):
            for j in range(i-1,0,-1):
                diff = abs(nums[i] - nums[j])
                index = bisect.bisect_left(nums, diff)
                if index < j and nums[j-1]>diff: # 注意条件哈
                    return nums[i]+nums[j]+nums[j-1]
                else:
                    break
        return 0

计算各个位数不同的数字个数

题目见 https://leetcode-cn.com/problems/count-numbers-with-unique-digits/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        def pending_sum(x):
            res = 1
            j = 10
            for i in range(x):
                res = res * min(9, j)
                j = j - 1
            return res
        if n==0:
            return 1 
        if n==1:
            return 10

        dp = [0] * (n+1)
        dp[0] = 1
        dp[1] = 10
        for i in range(2,n+1):
            dp[i] = dp[i-1] + pending_sum(i)
        return dp[n]

圆圈中最后剩下的数字

题目见 https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/ 题解如下：

1
2
3
4
5
6
7
class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        x = 1
        for i in range(2, n+1): # 注意起始不是1
            x = (x+m)%i
        return x
# https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/

image

类似的题目还有 找出游戏的获胜者，题目在https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/， 但是注意这个不是从0开始了，是从1开始的，因此解法会有些不一样

1
2
3
4
5
6
class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        x = 0
        for i in range(2, n + 1):
            x = (x + k) % i
        return x + 1  # 不一样

消除游戏

题目见 https://leetcode-cn.com/problems/elimination-game/ 题解如下：

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
28
29
30
31
32
# 方法一：迭代做法
class Solution:
    def lastRemaining(self, n: int) -> int:
        head = 1
        step = 1
        left = True
        
        while n > 1:
            # 从左边开始移除 or（从右边开始移除，数列总数为奇数）
            if left or n % 2 != 0:
                head += step
            
            step <<= 1 # 步长 * 2
            n >>= 1 # 总数 / 2
            left = not left #取反移除方向

        return head
# 方法二：递归做法
class Solution:
    def lastRemaining(self, n: int) -> int:
        def dfs(n,direction):
            if n==1:
                return 1
            else:
                if direction:
                    return 2*dfs(n//2,  not direction)
                else:
                    if n&1:
                        return 2*dfs(n//2, not direction)
                    else:
                        return 2*dfs(n//2,not direction) - 1
        return dfs(n, True)

用递归来做的话，是比较快的

最大数值

题目见 https://leetcode-cn.com/problems/maximum-lcci/ 题解如下：

1
2
3
class Solution:
    def maximum(self, a: int, b: int) -> int:
        return (a+b+abs(a-b))//2

求解方程

题目见 https://leetcode-cn.com/problems/solve-the-equation/ 题解如下：

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
28
29
30
31
32
class Solution:
    def solveEquation(self, equation: str) -> str:
        low, high = equation.replace("-", "+-").split("=")
        a, b = 0, 0
        # 处理左边
        for i in low.split("+"):
            if i=='':continue
            if i.endswith('x'):
                if i[:-1] == '':
                    a = a + 1
                elif i[:-1] == '-':
                    a = a - 1
                else:
                    a = a + int(i[:-1])
            else:
                b = b + int(i)
        # 处理右边
        for i in high.split("+"):
            if i=='':continue
            if i.endswith('x'):
                if i[:-1] == '':
                    a = a - 1
                elif i[:-1] == '-':
                    a = a + 1
                else:
                    a = a - int(i[:-1])
            else:
                b = b - int(i)
        if a == 0:
            return 'Infinite solutions' if b == 0 else 'No solution'
        else:
            return 'x=%d' % (-b / a)

质数和因数

计算质数

题目见 https://leetcode-cn.com/problems/count-primes/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def count_primes_py(n):
    """
    求n以内的所有质数个数（纯python代码）
    """
    # 最小的质数是 2
    if n < 2:
        return 0

    isPrime = [1] * n
    isPrime[0] = isPrime[1] = 0   # 0和1不是质数，先排除掉

    # 埃式筛，把不大于根号 n 的所有质数的倍数剔除
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            isPrime[i * i:n:i] = [0] * ((n - 1 - i * i) // i + 1)

    return sum(isPrime)

注意上面的快速间隔的选中数值，也就是[1:100:3]每隔3个数

丑数

就是查看是否是2 3 5的乘积

1
2
3
4
5
6
7
8
class Solution:
    def isUgly(self, n: int) -> bool:
        if n==0:
            return False
        for i in [2,3,5]:
            while n %i == 0:
                n = n // i
        return n==1

丑数 II

题目见 https://leetcode-cn.com/problems/ugly-number-ii/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        import heapq
        seen = set()
        res = [1]
        for i in range(n-1):
            v = heapq.heappop(res)
            for j in [2,3,5]:
                if v*j not in seen:
                    seen.add(v*j)
                    heapq.heappush(res,v*j)
        return res[0]

超级丑数

题目见 https://leetcode-cn.com/problems/super-ugly-number/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        dp = [0] * (n + 1)
        m = len(primes)
        pointers = [0] * m
        nums = [1] * m

        for i in range(1, n + 1):
            min_num = min(nums)
            dp[i] = min_num
            for j in range(m):
                if nums[j] == min_num:
                    pointers[j] += 1 # 把之前最小的dp的位置的存下来，后面* 然后得到新的数值
                    nums[j] = dp[pointers[j]] * primes[j]
        return dp[n]

好子集的数目

题目见 https://leetcode-cn.com/problems/the-number-of-good-subsets/ 题解如下：

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
class Solution:
    def numberOfGoodSubsets(self, nums):
        num_map = collections.Counter(nums)
        res = collections.defaultdict(int)
        primes = set(map(lambda x: x*x,[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]))
        # 初始化 res[1] 的个数，但是后续结果需要减去
        res[1] = 2**num_map[1]

        for num in num_map:
            # 去除1
            if num == 1:
                continue
            
            for key in res.copy():
                # 暴力循环 构建数字
                good_num = key * num
                
                #  判断是否为好子集
                if not all( good_num % p for p in primes):
                    continue

                # 计算good_num的好子集的个数，初始 res[good_num] = 0 
                res[good_num] += res[key] * num_map[num]
        
        return (sum(res.values()) - res[1]) % (10 ** 9 + 7)

只有两个键的键盘

题目见 https://leetcode-cn.com/problems/2-keys-keyboard/ 这道题就是分解质因素的思路，一毛一样

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 递归
class Solution:
    def __init__(self):
        self.cnt = float("inf")
    def minSteps(self, n: int) -> int:
        def dfs(n,c,s,t):
            if s>=n:
                if s==n:
                    self.cnt = min(self.cnt, t)
                return
            dfs(n, c, c+s, t+1)
            dfs(n, s, s+s, t+2)
        if n==1:
            return 0
        dfs(n,1,1,1)
        return self.cnt
# 分解
class Solution:
    def minSteps(self, n: int) -> int:
        if n==1: # 注意
            return 0
        res = 0
        for i in range(2,n):
            while n%i ==0:
                res+=i
                n//=i
        return res if res else n # 如果为0说明为质数，直接返回n即可
# 动态
class Solution:
    def minSteps(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0] = 0
        for i in range(2,n+1):
            j = 1
            dp[i] = float("inf")
            while j * j <= n:
                if i%j==0:
                    dp[i] = min(dp[i], dp[i//j]+j)
                    dp[i] = min(dp[i], dp[j]+i//j)
                j = j + 1
        return dp[n]

数组类

翻转类

轮转数组

题目见 https://leetcode-cn.com/problems/rotate-array/ ，题解如下：

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
28
29
30
# 方法1
使用了额外的空间
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n  =  len(nums)
        yushu = k % n
        start = n - yushu
        print(nums[start:])
        print(nums[:start])
        v = nums[start:] + nums[:start]
        nums[:] = v[:]
# 方法2
直接进行翻转即可
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(nums,start,end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start+=1
                end-=1
        yushu = k % len(nums)
        reverse(nums, 0, len(nums)-1)
        reverse(nums, 0, yushu-1)
        reverse(nums,yushu,len(nums)-1)

原地哈希

缺失的第一个正数

考点：交换
因为需要找到值，而不是索引，所以需要交换，不然会丢失值。

建议先看下面的题目，从 数组中重复的数据开始看起，这样会加速理解，这道题其实按照我们在 找到所有数组中消失的数字 中的结论来看，不太好做的，主要是没有对数组中的值有范围，比如对于[7,8,-1,10]这种，数组的长度是4，但是里面的值都大于的，因此没法直接做value作为index的这样映射，这么一想其实很难做的。
不过，如果找不到索引的话，我们就不去动不就可以了吗，对于7这个值，对应的索引的地址是6，找不到6的地址的话，我们就不交换了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from typing import List
class Solution:
    # 3 应该放在索引为 2 的地方
    # 4 应该放在索引为 3 的地方
    def firstMissingPositive(self, nums: List[int]) -> int:
        size = len(nums)
        for i in range(size):
            # 先判断这个数字是不是索引，然后判断这个数字是不是放在了正确的地方
            while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
                self.__swap(nums, i, nums[i] - 1)
        for i in range(size):
            if i + 1 != nums[i]:
                return i + 1
        return size + 1

    def __swap(self, nums, index1, index2):
        nums[index1], nums[index2] = nums[index2], nums[index1]

这里需要注意的是，程序的中的while不能换成if，不然会报错的。上面的代码可以换成如下所示：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        size = len(nums)
        for i in range(size):
            # 先判断这个数字是不是索引，然后判断这个数字是不是放在了正确的地方
            while 1 <= nums[i] <= size and i != nums[i] - 1:
                nums[nums[i]-1],nums[i] = nums[i], nums[nums[i]-1]
        for i in range(size):
            if i + 1 != nums[i]:
                return i + 1
        return size + 1

会报错的，不可以写成i!=nums[i]-1。还有一点
nums[nums[i]-1],nums[i] = nums[i], nums[nums[i]-1]不能写成nums[i], nums[nums[i]-1]=nums[nums[i]-1],nums[i]这种格式。
如果不这么写的话，就得像上面的答案一样，定义一个swap函数，这样就可以了。

最后真确的如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        size = len(nums)
        for i in range(size):
            # 先判断这个数字是不是索引，然后判断这个数字是不是放在了正确的地方
            while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
                nums[nums[i]-1],nums[i] = nums[i], nums[nums[i]-1]
        for i in range(size):
            if i + 1 != nums[i]:
                return i + 1
        return size + 1

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

考点：交换
因为需要找到旧数组值，而不是索引，所以需要交换，不然会丢失值。

题目见 https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/， 题解如下

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == i:
                i = i + 1
                continue
            if nums[nums[i]] == nums[i]:
                return nums[i]
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]

这个解法不是很好理解，且不是很好的能够和上面的进行对应起来，下面的代码就可以和上面对应起来，建议用下面的代码，这样统一下，会好点便于后面进行快速写出来

1
2
3
4
5
6
7
8
9
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        size = len(nums)
        for i in range(size):
            while 0<=nums[i]<=size-1 and nums[i]!=nums[nums[i]]:
                nums[nums[i]],nums[i] = nums[i],nums[nums[i]]
        for i in range(size):
            if i!=nums[i]:
                return nums[i]

还是要注意的是代码中的

1
2
3
4
5
6
7
for i in range(size):
    while 0<=nums[i]<=size-1 and nums[i]!=nums[nums[i]]:
        nums[nums[i]],nums[i] = nums[i],nums[nums[i]]
#不能写成如下的形式
for i in range(size):
    while 0<=nums[i]<=size-1 and nums[i]!=nums[nums[i]]:
        nums[i],nums[nums[i]] = nums[nums[i]],nums[i]

如果要写的话也是可以的，只要在外面定义一个swap函数，就可以了。

丢失的数字

这道题可以使用^来做，解法如下：

1
2
3
4
5
6
7
8
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        r = 0
        for i in nums:
            r ^= i
        for i in range(len(nums)+1):
            r ^= i
        return r

使用交换来做得话，结果如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        size = len(nums)
        for i in range(size):
            while nums[i] <= size - 1 and nums[i]!=nums[nums[i]]:
                nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        
        for i in range(size):
            if i != nums[i]:
                return i
        return size

数组中重复的数据

考点：不是交换，而是直接赋值
因为需要找到数组中的值，其实也就是新数组的索引，直接在新数组上得到的索引就是原来的值。

题目见 https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/， 题解如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        n = len(nums)
        for i in nums:
            index = (i - 1)%n
            nums[index] += n
        for i in range(len(nums)):
            if nums[i] > 2*n:
                res.append(i+1)
        return res

其实就是将这个数组中的值，作为新的list的index， 这个数组的值是从1开始的，但是index的值是从0开始的，因此需要-1才可以。
如果题目改成至少出现3次，那就要将2改成3。

找到所有数组中消失的数字

考点：不是交换，而是直接赋值
理由和上面类似。

题目见 https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/， 这道题和上面的 数组中重复的元素基本上算是一样的，思路还是那个思路，就是把当前数组的值作为新数组的index，这里的做法和上面的类似，首先得到每个数组中的值，然后作为index，然后+n,那么那些缺失的值，如果以他们作为索引的话，对应的地方的值肯定是 < n的。这样就算出来的。

1
2
3
4
5
6
7
8
9
10
11
12
# 第一版-错的
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            index = nums[i] - 1
            nums[index] += n
        res = []
        for i in range(n):
            if nums[i] < n:
               res.append(i)
        return res

错误原因在于

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            index = (nums[i] - 1)%n # 改动1
            nums[index] += n
        res = []
        for i in range(n):
            if nums[i] <= n: # 改动2
               res.append(i+1) # 改动3
        return res 
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            index = (nums[i] - 1)%n
            nums[index] += n
        res = []
        for i in range(n):
            if nums[i] <= n:
               res.append(i+1)
        return res

为什么要用%这个，主要是为了防止index超出了数组的大小，这类题目中数字额值都会在数组的长度的范围，[4,3,2,7,8,2,3,1]这个数组，其中的值都是小于数组长度8的，不这么做的话，没法算啊，不然index也会超的。

重复数

寻找重复数

数组中重复的数字

下一个排列

题目见 https://leetcode-cn.com/problems/next-permutation/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums) -2 
        while i>=0 and nums[i]>=nums[i+1]:
            i = i - 1
        if i >= 0:
            j = len(nums) - 1
            while j>=0 and nums[i] >= nums[j]:
                j = j -1 
            nums[i], nums[j] = nums[j], nums[i]
        left = i + 1
        right = len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left = left + 1
            right = right - 1