LeetCode算法题整理（数学篇）Math

Posted on   |   Updated on | In | | Visitors

7. Reverse Integer

倒置一个整数， 此答案忽略了原题中的范围判断。原题

1
2
Input: -123
Output: -321

方法一：str

1
2
3
4
5
def reverse_int(x):
    if x >= 0:
        return int(str(x)[::-1])
    else:
        return -int(str(x)[:0:-1])

方法二：math

1
2
3
4
5
6
7
def reverse(self, x: int) -> int:
    sign = 1 if x >= 0 else -1
    ans, tail = 0, abs(x)
    while tail:
        ans = ans*10 + tail%10
        tail //= 10
    return ans * sign if ans < 2**31 else 0

9. Palindrome Number

判断一个数是否是回文数，这里把负数认为是不符合条件的。原题

方法一：str

1
2
def is_palindrome(x):
    return str(x) == str(x)[::-1]

方法二：math

1
2
3
4
5
6
def is_palindrome(x):
    l, r = x, 0
    while l > 0:
        r = r*10 + l%10
        l //= 10
    return r == x

13. Roman to Integer

罗马数字转换整型。原题

1
2
3
4
5
6
7
8
9
10
def roman_to_int(s):
    roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 
             'C': 100, 'D': 500, 'M': 1000}
    total = 0
    for i in range(len(s)):
        if i == len(s)-1 or roman[s[i]] >= roman[s[i+1]]
            total += roman[s[i]]
        else:
            total -= roman[s[i]]
    return total

69. Sqrt(x)

实现开方，返回整数部分。原题

1
2
3
4
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

方法一：二分法。

1
2
3
4
5
6
7
8
9
10
11
def mySqrt(self, x: int) -> int:
    lo, hi = 1, x
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid**2 < x:
            lo = mid + 1
        elif mid**2 > x:
            hi = mid - 1
        else:
            return mid
    return hi

牛顿迭代法

1
2
3
4
5
def my_sqrt(x):
    r = x
    while r**2 > x:
        r = (r+x//r) // 2
    return r

367. Valid Perfect Square

判断一个数是不是某个数的平方。原题

1
2
Input: 16
Output: true
方法一：牛顿迭代法。同69。 
1
2
3
4
5
def isPerfectSquare(self, num):
    r = num
    while r**2 > num:
        r = (r + num // r) // 2
    return r**2 == num

171. Excel Sheet Column Number

excel表格列表数字转换，二十六进制。原题

1
2
3
4
5
6
7
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28     A -> 1
1
2
3
def titleToNumber(self, s: str) -> int:
    OFFSET = ord('A')-1
    return sum((ord(x)-OFFSET)*26**i for i, x in enumerate(s[::-1]))

168. Excel Sheet Column Title

excel转换，数字转字母。十进制->26进制。原题

1
2
3
4
5
6
7
def convertToTitle(self, n):
    res = ''
    while n:
        res = chr((n-1)%26+65) + res
        # n //= 26
        n = (n-1) // 26
    return res

172. Factorial Trailing Zeroes

求n的阶乘末尾有几个0。原题

1
2
3
Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

思路：每一对2和5可以产生一个0，在n的阶乘中，5比2多，所以问题变成求5的个数，而25这种数有两个5，所以递归求解

1
2
def trailing_zeroes(n):
    return 0 if n == 0 else n//5 + trailing_zeroes(n//5)

204. Count Primes

求小于n的整数中，有多少个质数。原题

1
2
3
4
5
6
def countPrimes(self, n):
    is_prime = [False]*2 + [True]*(n-2)
    for i in range(2, int(n ** 0.5)+1):
        if is_prime[i]:
            is_prime[i*i:n:i] = [False] * len(is_prime[i*i:n:i])
    return sum(is_prime)

50. Pow(x, n)

实现pow函数。原题

1
2
3
4
5
Input: 2.00000, 10
Output: 1024.00000

Input: 2.00000, -2
Output: 0.25000 .

说明：常规方法在Leetcode 上内存会爆掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):

    def myPow(self, x, n):
        if n < 0:
            return 1 / self.pow_with_unsigned(x, -n)
        else:
            return self.pow_with_unsigned(x, n)
              
    def pow_with_unsigned(self, x, n):
        if n == 1:
            return x
        if n == 0:
            return 1
        
        res = self.pow_with_unsigned(x, n >> 1)
        res *= res
        
        if n & 1 == 1:
            res *= x
            
        return res

233. Number of Digit One

1~n数字中1的个数。原题

1
2
3
4
5
6
7
def countDigitOne(self, n):    
    countr, i = 0, 1
    while i <= n:
        divider = i * 10
        countr += (n // divider) * i + min(max(n % divider - i + 1, 0), i)
        i *= 10
    return countr

263. Ugly Number

判断一个数是否是丑数。原题

方法一：根据定义实现。< num是为了判断num=0的情况。

1
2
3
4
5
def isUgly(self, num):
    for f in 2, 3, 5:
        while num % f == 0 < num:
            num //= f
    return num == 1

264. Ugly Number II

输出第n个丑数。原题

书中的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def nthUglyNumber(self, n):
    q = [1]
    t2, t3, t5 = 0, 0, 0
    for i in range(n-1):
        a2, a3, a5 = q[t2]*2, q[t3]*3, q[t5]*5
        to_add = min(a2, a3, a5)
        q.append(to_add)
        if a2 == to_add:
            t2 += 1
        if a3 == to_add:
            t3 += 1
        if a5 == to_add:
            t5 += 1
    return q[-1]

67.Add Binary

实现二进制加法。原题

1
2
Input: a = "11", b = "1"
Output: "100"

方法一：按照加法的二进制思想来计算，不过Runtime大约100ms。后来试着将list comprehension拆成一个for循环，也并没有提高速度。居然beats只有4%，难道大部分人都用的bin。讨论区简单翻了了一下，没有找到一个高效的pythonic的方法。

1
2
3
4
5
6
7
8
9
10
11
def addBinary(self, a, b):
    if len(a) > len(b):
        b = b.zfill(len(a))
    else:
        a = a.zfill(len(b))
    
    while int(b):
        sum_not_carry = ''.join([str(int(a[i]) ^ int(b[i])) for i in range(len(a))])
        carry = ''.join([str(int(a[i]) & int(b[i])) for i in range(len(a))])
        a, b = "0"+sum_not_carry, carry+'0'
    return a.lstrip('0') if a != '0' else '0'

202. Happy Number

判断是否是欢乐数。进行所有位的平方和运算，最后为1的是欢乐数。原题

1
2
3
4
5
6
7
Input: 19
Output: true
Explanation: 
1**2 + 9**2 = 82
8**2 + 2**2 = 68
6**2 + 8**2 = 100
1**2 + 0**2 + 0**2 = 1

方法一：思路，使用一个字典映射0~9的平方值，然后如果死循环的话，各位数的和一定存在着一种循环，所以用一个set来判断是否重复。

1
2
3
4
5
6
7
8
9
10
def isHappy(self, n):
    squares = {str(k): k**2 for k in range(0, 10)}
    sum_digit = set()
    while n != 1:
        n = sum(squares[digit] for digit in str(n))
        if n in sum_digit:
            return False
        else:
            sum_digit.add(n)
    return True

231. Power of Two

判断一个数是否是2的n次方。思路也就是判断这个数的二进制形式是否只有一个’1’。原题

方法一：可以用作通用方法。

1
2
3
4
5
def isPowerOfTwo(self, n, power=2):
    if n == 0: return False
    while n % power == 0:
        n //= power
    return n == 1

方法二：二进制统计1。

1
2
def isPowerOfTwo(self, n):
    return n > 0 and bin(n).count('1') == 1

方法三：如果一个数n的二进制只有一个1，那么n&(n-1)一定为0。

1
2
def isPowerOfTwo(self, n):
    return n > 0 and (n&n-1) == 0

342. Power of Four

判断一个数是否是4的n次方。原题

方法一：从简单入手通过231题，了解到了2的n次方特点是，二进制形式只有一个’1’，那么4的n次方就是不但只有一个’1’，后面还跟了偶数个’0’。

1
2
3
4
5
6
7
8
9
10
11
def isPowerOfFour(self, num):
    single_1 = num > 0 and not (num & num-1)
    if single_1:
        while num > 0:
            if num == 1:
                return True
            else:
                num >>= 2
        return False
    else:
        return False
方法二：上述代码看起来更像是java代码，我们使用count来判断0的个数是否为偶数个。 
1
2
3
def isPowerOfFour(self, num):
    # return num > 0 and (num & num-1)==0 and bin(num)[2:].count('0')&1==0
    return num > 0 and (num & num-1)==0 and len(bin(num))&1==1

方法三：也可以使用正则。

1
2
3
def isPowerOfFour(self, num):
    import re
    return bool(re.match(r'^0b1(00)*$',bin(num)))

292. Nim Game

说，有这么一堆石头，一次只能拿1~3个，拿到最后一个石头的人获胜。求n堆石头，你先拿是否可以获胜。原题

思路：找规律，发现只有最后剩4个石头的时候，此时轮到谁，谁输。

1
2
def canWinNim(self, n):
    return n % 4 != 0

400. Nth Digit

找出无限整数序列中的第n个数字。原题

1
2
3
4
5
6
Input:
11
Output:
0
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

思路，根据n的位数，将无限序列分为几个范围。

size of n step start ~ stop
1 9 1 ~ 9
2 90 10 ~ 99
3 900 100 ~ 999
  1. 寻找范围。寻找n处于哪个范围，是1~9，还是10~99，例如n=15。则需要跳过1~9的范围，而这个范围有size*step个数字，所以问题变成在10~99范围上寻找第15-1*9=6个数。
  2. 定位数字。10~99范围中是从10开始的，每一个数都有两位数字，所以最终数字为10+(6-1)//2，因为索引从0开始，所以需要-1。
  3. 定位数字的位。上一步找到了数字为12，对size求余就可以知道，'12'[(6-1)%2]='2'。
1
2
3
4
5
def findNthDigit(self, n):
    start, step, size = 1, 9, 1
    while n > size * step:
        n, start, step, size = n-size*step, start*10, step*10, size+1
    return int(str(start + (n-1)//size)[(n-1) % size])

415. Add Stings

给定两个字符串表示的数字，把它们相加，这两个数的长度小于5100，不能使用任何BitIntegr库或是直接将其转换为整数。ps: 题中要求不将输入直接转换成int，所以我个人认为int还是可以使用的，有一些答案中是使用了ord来做运算。原题

方法一：不使用标准库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def addStrings(self, num1, num2):
    
    if len(num1) > len(num2):
        num2 = num2.zfill(len(num1))
    else:
        num1 = num1.zfill(len(num2))

    res, carry = '', 0
    n1, n2 = len(num1)-1, len(num2)-1
    while (n1 >= 0 and n2 >= 0) or carry:
        v1 = int(num1[n1]) if n1 >= 0 else 0
        v2 = int(num2[n2]) if n2 >= 0 else 0
        carry, val = divmod(v1+v2+carry, 10)
        res = str(val) + res
        n1 -= 1
        n2 -= 1
    return res
方法二：使用zip_longest。 
1
2
3
4
5
6
7
8
9
10
def addStrings(self, num1, num2):
    from itertools import zip_longest
    nums = list(zip_longest(num1[::-1], num2[::-1], fillvalue='0'))
    carry, res = 0, ''
    for digits in nums:
        d1, d2 = map(int, digits)
        carry, val = divmod(d1+d2+carry, 10)
        res = res + str(val)
    res = res if carry==0 else res+str(carry)        
    return res[::-1]

492. Construct the Rectangle

给定一个面积，求组成这个面积的长高差最小。原题

1
2
3
4
Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1]. 
But according to requirement 2, [1,4] is illegal; according to requirement 3,  [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.
方法一：一开始我居然这样写。结果超时了，后来发现L+=1，循环次数要比L-=1要多。 
1
2
3
4
5
6
7
8
9
10
def constructRectangle(self, area):
    import math
    squre = math.sqrt(area)
    if int(squre) == squre:
        return [int(squre), int(squre)]
    else:
        L = int(squre) + 1
        while area % L != 0:
            L += 1
        return [L, area//L]

方法二：整理一下思路其实很简单，之前想多了还以为有二分的方法。递减肯定是会优先退出循环的，但是我还不知道怎么证明这个结论。

1
2
3
4
5
6
def constructRectangle(self, area):
    import math
    w = int(math.sqrt(area))
    while area % w != 0:
        w -= 1
    return [area//w, w]

504. Base 7

10进制转7进制。原题

1
2
3
4
Input: 100
Output: "202"
Input: -7
Output: "-10"

方法一：需要注意负数。

1
2
3
4
5
6
7
def convertToBase7(self, num: int) -> str:
    if num == 0: return '0'
    n, ans = abs(num), ''
    while n:
        n, val = divmod(n, 7)
        ans = str(val) + ans
    return ans if num > 0 else '-'+ans

970. Powerful Integers

求满足x^i+y^j <= bound的所有和。原题

1
2
3
4
5
6
7
8
9
10
Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

方法一：这题难得地方在于两个循环的临界值，貌似我这样写也不是最优解，原题的Solution中给定了2**18>bound的最大值。所以两个范围都是18。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def powerfulIntegers(self, x, y, bound):
    res = set()
    imax = self.get_max(x, bound) + 1
    jmax = self.get_max(y, bound) + 1
    for i in range(imax):
        for j in range(jmax):
            if x**i + y**j <= bound:
                res.add(x**i+y**j)
    return list(res)

    def get_max(self, n, bound):
        for i in range(bound//n + 1):
            if n ** i >= bound:
                return i
        return bound//n + 1

973. K Closest Points to Origin

求离原点最近的K个坐标点。原题

1
2
3
4
5
6
7
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

方法一：很简单。

1
2
3
def kClosest(self, points, K):
    res = sorted(points, key=lambda x: x[0]**2 + x[1]**2)
    return res[:K]

976. Largest Perimeter Triangle

给定一个边长数组，求能组成的三角形的最长周长。原题

方法一：这个也不难，就是长度为3的滑动窗口。

1
2
3
4
5
6
def largestPerimeter(self, A):
    res = sorted(A, reverse=True)
    for i in range(len(res)-2):
        if sum(res[i+1:i+3]) > res[i]:
            return sum(res[i:i+3])
    return 0

628. Maximum Product of Three Numbers

数组中三个数的最大乘积。元素范围[-1000, 1000]。原题

1
2
Input: [1,2,3,4]
Output: 24

方法一：排序。在正数个数大于等于3的时候，显然最大的三个数就可以产生最大的乘积。而当正数个数不够的时候，那么必须需要两个最小的负数（即绝对值最大），和一个最大的正数。

1
2
3
def maximumProduct(self, nums):
    ary = sorted(nums)
    return max((ary[0]*ary[1]*ary[-1], ary[-3]*ary[-2]*ary[-1]))
方法二：使用heapq. 
1
2
3
4
5
6
7
def maximumProduct(self, nums):
    import heapq
    from operator import mul
    from functools import reduce
    three_max = heapq.nlargest(3, nums)
    two_min = heapq.nsmallest(2, nums)
    return max(reduce(mul, three_max), reduce(mul, two_min + three_max[:1]))

728. Self Dividing Numbers

自整除数字，一个数字能够被本身的每个数字整除，并且不能有0，求某个范围内所有的数。原题

1
2
3
Input: 
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

方法一：Brute Force. 此题强行使用列表生成式没有意义。

1
2
3
4
5
6
7
8
9
def selfDividingNumbers(self, left, right):
    res = []
    for i in range(left, right+1):
        for char in str(i):
            if int(char)==0 or i % int(char)!=0:
                break
        else:
            res.append(i)
    return res

836. Rectangle Overlap

矩形是否重叠，矩形的边平行于坐标轴。原题

1
2
Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

方法一：通过画图找出的规律。

1
2
3
4
def isRectangleOverlap(self, rec1: 'List[int]', rec2: 'List[int]') -> 'bool':
    x_overlap = (rec2[0]-rec1[2]) * (rec2[2]-rec1[0]) < 0
    y_overlap = (rec2[1]-rec1[3]) * (rec2[3]-rec1[1]) < 0
    return x_overlap and y_overlap
方法二：方法一还是想复杂了。

Given 2 segment (left1, right1), (left2, right2), how can we check whether they overlap?
If these two intervals overlap, it should exist an number x,

1
2
3
left1 < x < right1 && left2 < x < right2
left1 < x < right2 && left2 < x < right1
left1 < right2 && left2 < right1
1
2
3
def isRectangleOverlap(self, rec1: 'List[int]', rec2: 'List[int]') -> 'bool':
    return rec2[0] < rec1[2] and rec1[0] < rec2[2] and \
           rec2[1] < rec1[3] and rec1[1] < rec2[3]

991. Broken Calculator

坏掉的计算器，只能*2或者-1，使X变为Y。原题

1
2
3
Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

解析：如果从X到Y问题会变得复杂，不确定什么时候该*2或者是-1。所以逆向思维从Y变成X。

If Y <= X, we won’t do Y / 2 anymore.
We will increase Y until it equals to X

So before that, while Y > X, we’ll keep reducing Y, until it’s smaller than X.
If Y is odd, we can do only Y = Y + 1
If Y is even, if we plus 1 to Y, then Y is odd, we need to plus another 1.
And because (Y + 1 + 1) / 2 = (Y / 2) + 1, 3 operations are more than 2.
We always choose Y / 2 if Y is even.

方法一：iteratively.

1
2
3
4
5
6
7
8
9
def brokenCalc(self, X: 'int', Y: 'int') -> 'int':
    ans = 0
    while X < Y:
        ans += 1
        if Y & 1 == 1:
            Y += 1
        else:
            Y //= 2
    return ans + X - Y

方法二：方法一变形。因为如果Y是奇数，那么必定在+1操作后要/2，这里将其合并

1
2
3
4
5
6
7
8
9
def brokenCalc(self, X: 'int', Y: 'int') -> 'int':
    ans = 0
    while X < Y:
        ans += 1
        if Y & 1 == 1:
            Y += 1
            ans += 1
        Y = Y // 2
    return ans + X - Y
方法三：方法二再变形，看到Y是奇数时，ans + 2，所以可以用ans += (Y&1) + 1表示，而Y在是奇数时先+1再//2即Y = (Y + 1) // 2，偶数时Y = Y // 2，其实，对于偶数来说Y=(Y+1)//2和Y=Y//2结果一样。所以可以写成。 
1
2
3
4
5
6
def brokenCalc(self, X: 'int', Y: 'int') -> 'int':
    ans = 0
    while X < Y:
        ans += (Y & 1) + 1
        Y = (Y + 1) // 2
    return ans + X - Y
方法四：递归写法。Y&1必须括号 
1
2
def brokenCalc(self, X: 'int', Y: 'int') -> 'int':
    return X - Y if X >= Y else 1+(Y&1)+self.brokenCalc(X, (Y+1)//2)

908. Smallest Range I

给定一个数组，和一个K，数组里的数加上-k<=x<=k的任意一个数字后，求数组最大数和最小数的，最小差。原题

1
2
3
Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]
1
2
def smallestRangeI(self, A: 'List[int]', K: 'int') -> 'int':
    return max(max(A) - min(A) - 2*K, 0)

949. Largest Time for Given Digits

给定四个数字，返回能生成的最大时间。24小时制。原题

1
2
Input: [1,2,3,4]
Output: "23:41"

方法一：排序。

1
2
3
4
5
6
def largestTimeFromDigits(self, A: 'List[int]') -> 'str':
    p = itertools.permutations(A)
    for a, b, c, d in sorted(p, reverse=True):
        if 0 <= a*10+b <= 23 and 0 <= 10*c+d <= 59:
            return '{}{}:{}{}'.format(a, b, c, d)
    return ''
1
2
3
4
def largestTimeFromDigits(self, A: 'List[int]') -> 'str':
    p = itertools.permutations(A)
    return max(['{}{}:{}{}'.format(*d) for d in p 
                if d[:2] < (2, 4) and d[2] < 6] or [''])

914. X of a Kind in a Deck of Cards

有这样一堆数字卡牌，问是否存在一个X>=2，使得将同样数字的卡牌分为每X个一组，并且刚好所有的卡牌分完。原题

思路：使用Counter来统计每个数字的个数，然后求这些数字的最大公约数是否大于等于2，这里思路卡了一下，因为没想到最大公约数可以通过reduce来计算，没考虑到是可以累积的。

1
2
3
4
5
def hasGroupsSizeX(self, deck):
    from collections import Counter
    from math import gcd
    from functools import reduce
    return reduce(gcd, Counter(deck).values()) >= 2

470. Implement Rand10() Using Rand7()

使用rand7实现rand10原题

1
2
Input: 3
Output: [8,1,10]

方法一：先将rand7-1变为[0, 6]然后乘7，[0,7,14,21,28,35,42]然后+[0,6]这样能将这6个数均匀地分配到每段中，得到了[0, 48]然后舍弃[40,48]剩下[0,39]然后取余得[0,9]最后加一。

1
2
3
4
5
def rand10(self):
    while True:
        x = (rand7()-1)*7 + rand7()-1
        if x < 40: 
            return x%10 + 1

1006. Clumsy Factorial

将一个阶乘的式子用*/+-替代，给出结果。原题

1
2
3
Input: 10
Output: 12
Explanation: 12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

方法一：python此题有作弊的方法，我看排行榜中大神有的特意切到python做这道题，不过没我写得好。

1
2
3
4
def clumsy(self, N: int) -> int:
    op = itertools.cycle(['*', '//', '+', '-'])
    return eval(''.join(str(n)+next(op) if n!=1 else str(n) 
                        for n in range(N, 0, -1)))

1022. Smallest Integer Divisible by K

最小的由1组成的能被K整除。原题

1
2
3
Input: 2
Output: -1
Explanation: There is no such positive integer N divisible by 2.

如果有2或5的质因数，那么不能整除。

1
2
3
4
5
6
def smallestRepunitDivByK(self, K: int) -> int:
    if K % 2 == 0 or K % 5 == 0: return -1
    r = 0
    for N in range(1, K + 1):
        r = (r * 10 + 1) % K
        if not r: return N

1028. Convert to Base -2

10进制转成-2进制。原题

方法一：负数进制时，如果余数为负数，那么商+1。

1
2
3
4
5
6
7
8
9
10
def baseNeg2(self, N: int) -> str:
    if not N:
        return '0'
    ans = ''
    while N:
        remainder = N % (-2)
        ans += str(abs(remainder))
        N //= -2
        N += (remainder < 0)
    return ans[::-1]

方法二：在二进制上加一个负号。

1
2
3
4
5
6
def baseNeg2(self, N: int) -> str:
    ans = []
    while N:
        ans.append(N & 1)
        N = -(N >> 1)
    return ''.join(map(str, ans[::-1] or [0]))

313. Super Ugly Number

根据指定的质数序列，找出第n个超级丑数。原题

和剑指offer中，丑数一题很像，只不过那题是固定的2,3,5三个质数。

方法一：根据之前的方法进行微调。时间要1s左右，因为遍历了两次primes。

1
2
3
4
5
6
7
8
9
10
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
    ans = [1]
    last_index = [0] * len(primes)
    for _ in range(n-1):
        ugly = min(ans[last_index[i]]*p for i, p in enumerate(primes))
        ans.append(ugly)
        for i, p in enumerate(primes):
            if ans[last_index[i]] * p == ugly:
                last_index[i] += 1
    return ans[-1]
方法二：304ms。开始想到了生成器和堆，其他结构差不多，但是生成器内部实现想错了。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
    import heapq as hq
    uglies = [1]
    
    def gen_ugly(prime):
        for ugly in uglies:
            yield ugly * prime
            
    merged = hq.merge(*map(gen_ugly, primes))
    while len(uglies) < n:
        ugly = next(merged)
        if ugly != uglies[-1]:
            uglies.append(ugly)
    return uglies[-1]

869. Reordered Power of 2

重新排列一个数字的各位数，判断是否能组成2的幂。原题

这题我看到是，显示拆成两个子问题，全排列和判断是否是2的幂，结果超时了，不知道为什么，我看Solution中也有这种解法，我还提交了好几次。

所以此题需要换一种思路，2的幂是指数上升的，所以，在范围内的数一共也没有几个。那么使用Counter来判断是否能组成这个数。

1
2
3
def reorderedPowerOf2(self, N: int) -> bool:
    c = Counter(str(N))
    return any(c==Counter(str(1<<i)) for i in range(0, 30))

1025. Divisor Game

两个人做游戏，黑板上有个数N，每次找到一个0 <x<N的数，并且N能被x整除，然后替换这个N，直到找不出这样x，就输了。问给出这样一个数N，第一个人是否能赢。原题

方法一：写了一个动态规划，最后一分析实际上只要N为偶数就能赢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ans = []
def divisorGame(self, N: int) -> bool:
    # for i in range(1, N+1):
    #     for j in range(1, i):
    #         if i % (i-j)==0 and not ans[j]:
    #             print('{} % {}'.format(i, j))
    #             ans.append(True)
    #             break
    #     # for j in range(1, len(ans)):
    #     #     if i % (i-j)== 0 and not ans[j]:
    #     #         ans.append(True)
    #     #         break
    #     else:
    #         ans.append(False)
    #     print('count {} {}'.format(i, ans[-1]))
    # print(ans)
    return N & 1 == 0

1037. Valid Boomerang

验证三个坐标点是否共线。原题

方法一：需要注意的是，除数为0 的情况，所以这里改成了乘法。

1
2
3
def isBoomerang(self, points: List[List[int]]) -> bool:
    return (points[1][1]-points[0][1])*(points[2][0]-points[1][0]) != \
           (points[2][1]-points[1][1])*(points[1][0]-points[0][0])

1041. Robot Bounded In Circle

一个面向北的机器人进行三种操作，一种是前进，或者向左向右转。问一系列的操作中，无限循环时，机器人是否在绕圈。原题

方法一：将操作反复4次，判断是否回到原点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isRobotBounded(self, instructions: str) -> bool:
    instruction = instructions * 4
    operations = [('+0', '+1'), ('-1', '+0'), ('+0', '-1'), ('+1', '+0')]
    cur_op = 0
    x, y = 0, 0
    for inst in instruction:
        if inst == 'G':
            x_op, y_op = operations[cur_op]
            x, y = eval(str(x)+x_op), eval(str(y)+y_op)
        elif inst == 'L':
            cur_op = (cur_op+1) % 4
        else:
            cur_op = (cur_op-1) % 4
    return x == y == 0

方法二：不需要循环四次，在一次之后，如果面向的不再是北，那么最后将会绕圈。

1
2
3
4
5
6
7
def isRobotBounded(self, instructions: str) -> bool:
    x, y, dx, dy = 0, 0, 0, 1
    for inst in instructions:
        if inst == 'G': x, y = x+dx, y+dy
        elif inst == 'L': dx, dy = -dy, dx
        elif inst == 'R': dx, dy = dy, -dx
    return (x == y == 0) or (dx, dy) != (0, 1)

1137. N-th Tribonacci Number

三个数的斐波那契数列。原题

1
2
3
4
5
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
1
2
3
4
5
def tribonacci(self, n: int) -> int:
    a, b, c = 1, 0, 0
    for _ in range(n):
        a, b, c = b, c, a+b+c
    return c

1073. Adding Two Negabinary Numbers

两个-2进制的数相加。原题

方法一：转成十进制相加，再转回-2进制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
    
    def to_ten(arr):
        return sum(d*(-2)**i for i, d in enumerate(arr[::-1]))
    
    def to_neg_binary(n):
        if not n:
            return '0'
        ans = ''
        while n:
            remainder = n % (-2)
            ans += str(abs(remainder))
            n //= -2
            n += (remainder < 0)
        return ans[::-1]
    
    return to_neg_binary(to_ten(arr1) + to_ten(arr2))

1154. Day of the Year

根据输入的日期，返回它是一年中的第几天。原题

方法一：使用了datetime库，开始还自己手动减，后来看评论发现有这样的方法。

1
2
3
4
def dayOfYear(self, date: str) -> int:
    import datetime
    date = datetime.datetime.strptime(date, '%Y-%m-%d')
    return date.timetuple().tm_yday

1155. Number of Dice Rolls With Target Sum

扔一个f面的 骰子d次，结果为target的次数。原题

1
2
3
4
5
Input: d = 2, f = 6, target = 7
Output: 6
Explanation: 
You throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:
1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

方法一：竞赛时用的数组，后来发现字典效率更高。此题和剑指offer中骰子题类似。

1
2
3
4
5
6
7
8
9
def numRollsToTarget(self, d: int, f: int, target: int) -> int:
    last_p = collections.defaultdict(int)
    last_p.update({d: 1 for d in range(1, f+1)})
    for i in range(2, d+1):
        new_p = collections.defaultdict(int)
        for j in range(i, i*f+1):
            new_p[j] = sum(last_p[j-k] for k in range(1, f+1))
        last_p = new_p
    return last_p[target] % (10**9+7)

1093. Statistics from a Large Sample

统计大量的样本数据，求最小值，最大值，平均值，众数。原题

1
2
Input: count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,3.00000,2.37500,2.50000,3.00000]

方法一：中位数的求法这里没想到，使用二分可以完美的解决奇偶问题。

1
2
3
4
5
6
7
8
9
10
11
def sampleStats(self, count: List[int]) -> List[float]:
    n = sum(count)
    mi = next(i for i in range(255) if count[i]) * 1.0
    ma = next(i for i in range(255, -1, -1) if count[i]) * 1.0
    mean = sum(i * val for i, val in enumerate(count)) * 1.0 / n
    mode = count.index(max(count)) * 1.0
    cc = list(itertools.accumulate(count))
    left = bisect.bisect(cc, (n-1)//2)
    right = bisect.bisect(cc, n//2)
    median = (left + right) / 2.0
    return mi, ma, mean, median, mode

1103. Distribute Candies to People

发糖果，按照顺序每个人比上一人多一颗，发到最后再循环。原题

1
2
3
4
5
6
7
Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

方法一：此题做法和Lee神不谋而合。

1
2
3
4
5
6
7
8
def distributeCandies(self, candies: int, n: int) -> List[int]:
    ans = [0] * n
    cur = 1
    while candies > 0:
        ans[cur%n-1] += min(candies, cur)
        candies -= cur
        cur += 1
    return ans

1109. Corporate Flight Bookings

通过给定的一些区间，确定每天的座位数。原题

1
2
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]

方法一：此题暴力法会超时。核心在于记录变化的状态，然后累加求结果。

1
2
3
4
5
6
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
    ans = [0] * (n+1)
    for s, e, v in bookings:
        ans[s-1] += v
        ans[e] -= v
    return list(itertools.accumulate(ans))[:-1]

1175. Prime Arrangements

质数排列。原题

1
2
3
Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.
1
2
3
4
5
6
7
8
9
10
11
12
def numPrimeArrangements(self, n: int) -> int:
    
    def countPrimes(n):
        is_prime = [False]*2 + [True]*(n-2)
        for i in range(2, int(n ** 0.5)+1):
            if is_prime[i]:
                is_prime[i*i:n:i] = [False] * len(is_prime[i*i:n:i])
        return sum(is_prime)
    c = countPrimes(n+1)
    ans = math.factorial(c) * math.factorial(n-c)
    
    return ans % (10**9+7)

1360. Number of Days Between Two Dates

计算两个日期之间的天数。原题

1
2
Input: date1 = "2020-01-15", date2 = "2019-12-31"
Output: 15

方法一：简单的datetime模块方式。

1
2
3
4
5
def daysBetweenDates(self, date1: str, date2: str) -> int:
    from datetime import datetime
    d1 = datetime.strptime(date1, '%Y-%m-%d')
    d2 = datetime.strptime(date2, '%Y-%m-%d')
    return abs((d2-d1).days)

方法二：有个公式，如果将1月二月看成是13月和14月，那么月份转化天数有个公式(153 * m + 8) // 5

1
2
3
4
5
6
7
8
9
def daysBetweenDates(self, date1: str, date2: str) -> int:
    def f(date):
        y, m, d = map(int, date.split('-'))
        if m < 3:
            m += 12
            y -= 1
        return 365 * y + y // 4 + y // 400 - y // 100 + d + (153 * m + 8) // 5

    return abs(f(date1) - f(date2))

1363. Largest Multiple of Three

组成的最大的3的倍数。原题

1
2
Input: digits = [8,1,9]
Output: "981

方法一：数学。

  1. Calculate the sum of digits total = sum(A)
  2. If total % 3 == 0, we got it directly
  3. If total % 3 == 1 and we have one of 1,4,7 in A:
    we try to remove one digit of 1,4,7
  4. If total % 3 == 2 and we have one of 2,5,8 in A:
    we try to remove one digit of 2,5,8
  5. If total % 3 == 2:
    we try to remove two digits of 1,4,7
  6. If total % 3 == 1:
    we try to remove two digits of 2,5,8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def largestMultipleOfThree(self, A):
    total = sum(A)
    count = collections.Counter(A)
    A.sort(reverse=1)

    def f(i):
        if count[i]:
            A.remove(i)
            count[i] -= 1
        if not A: return ''
        if not any(A): return '0'
        if sum(A) % 3 == 0: return ''.join(map(str, A))

    if total % 3 == 0:
        return f(-1)
    if total % 3 == 1 and count[1] + count[4] + count[7]:
        return f(1) or f(4) or f(7)
    if total % 3 == 2 and count[2] + count[5] + count[8]:
        return f(2) or f(5) or f(8)
    if total % 3 == 2:
        return f(1) or f(1) or f(4) or f(4) or f(7) or f(7)
    return f(2) or f(2) or f(5) or f(5) or f(8) or f(8)

1493. Longest Subarray of 1’s After Deleting One Element

删除一个元素，子数组有最长的1、子数组长度。原题

1
2
3
Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

方法一：双端队列，其实是求最多包含1个0的滑动窗口长度。

1
2
3
4
5
6
7
8
9
10
11
12
def longestSubarray(self, nums: List[int]) -> int:
    ans = k = 0
    q = collections.deque()
    for num in nums:
        q.append(num)
        k += num==0
        if k == 2:
            while q.popleft()!=0:
                pass
            k -= 1
        ans = max(ans, len(q)-1)
    return ans

方法二：Lee215的解法，还是选择维持了一个最大的长度，所以没用while 而是if，这样也不用每次max来求值。

1
2
3
4
5
6
7
8
def longestSubarray(self, nums: List[int]) -> int:
    k, i = 1, 0
    for j in range(len(nums)):
        k -= nums[j]==0
        if k < 0:
            k += nums[i]==0
            i += 1
    return j - i

537. Complex Number Multiplication

两个负数相乘。求结果，需要注意的是这里会多一个+。原题

1
2
3
Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

方法一：内置库。这里format时不能用d，因为都是float。但是%却可以做到。

1
2
3
4
5
6
def complexNumberMultiply(self, a: str, b: str) -> str:
    a = complex(a.replace('+-', '-').replace('i', 'j'))
    b = complex(b.replace('+-', '-').replace('i', 'j'))
    c = a * b
    return '{:.0f}+{:.0f}i'.format(c.real, c.imag)
	# return '%d+%di' % (c.real, c.imag)

方法二：不用内置库。

1
2
3
4
5
6
def complexNumberMultiply(self, a: str, b: str) -> str:
    a_real, a_imag = map(int, re.match(r'(\-?\d+)\+(\-?\d+)i', a).groups())
    b_real, b_imag = map(int, re.match(r'(\-?\d+)\+(\-?\d+)i', b).groups())
    real = a_real*b_real - a_imag*b_imag
    imag = a_real*b_imag + b_real*a_imag
    return '{}+{}i'.format(real, imag)
方法三：我还搁这groups呢，人家stefan一行就搞定了。 
1
2
3
def complexNumberMultiply(self, a, b):
    a, ai, b, bi = map(int, re.findall('-?\d+', a+b))
    return '%d+%di' % (a*b - ai*bi, a*bi + ai*b)

794. Valid Tic-Tac-Toe State

在一个九宫格里下棋，谁连上3个就算赢，问给出一个棋子局面，判断是否可能下出来。原题

方法一：case挺多的，需要想明白判断条件，基本就是请求x,o的分别连3的个数，然后和分别的棋子数，最后判断。

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
def validTicTacToe(self, b: List[str]) -> bool:
    
    fb = ''.join(b)
    x_cnt, o_cnt = fb.count('X'), fb.count('O')
    cnt = {'X': 0, 'O': 0}
    
    for row in b:
        if len(set(row))==1 and row[0]!=' ':
            cnt[row[0]] += 1
    for col in zip(*b):
        if len(set(col))==1 and col[0]!=' ':
            cnt[col[0]] += 1
    if b[1][1] != ' ':
        if len(set(b[i][i] for i in range(3))) == 1:
            cnt[b[1][1]] += 1
        if len(set(b[i][2-i] for i in range(3))) == 1:
            cnt[b[1][1]] += 1
    # print(x_cnt, o_cnt, cnt)  
    if not o_cnt<=x_cnt<=o_cnt+1:
        return False
    if cnt['X'] and x_cnt!=o_cnt+1: 
        return False
    if cnt['O'] and (cnt['X'] or x_cnt!=o_cnt):
        return False
    return True
方法二：stefan的答案，判断精简了，求连子过程也精简了。当X>O时，那么O必然没有连3。相等时，X必然没有连3。用了一个切片求出是否出现了连3。 
1
2
3
4
b = '|'.join(board)
    x, o = (any(p*3 in b[s::d] for s in range(9) for d in (1, 3, 4, 5)) for p in 'XO')
    m = b.count('X') - b.count('O')
    return m == (not o) if m else not x

227. Basic Calculator II

计算式子，没有括号，包含加减乘除和小数点。原题

1
2
Input: " 3+5 / 2 "
Output: 5

方法一：eval算是作弊了，这个stefan的方法不错。用了生成器。

1
2
3
4
5
6
7
8
9
10
11
12
13
def calculate(self, s: str) -> int:
    tokens = iter(re.findall('\d+|\S', s))
    total, sign = 0, 1
    for token in tokens:
        if token in '+-':
            total += sign * term
            sign = ' +'.find(token)
        elif token in '*/':
            n = int(next(tokens))
            term = term*n if token == '*' else term//n
        else:
            term = int(token)
    return total + sign * term

640. Solve the Equation

解方程，方程中只有x一个变量，只有加减操作。原题

1
2
3
4
5
6
Input: "x+5-3+x=6+x-2"
Output: "x=2"
Input: "x=x"
Output: "Infinite solutions"
Input: "2x+3x-6x=x+2"
Output: "x=-1"

方法一：首次AC的方法。正则调了半天，因为不止一为数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solveEquation(self, equation: str) -> str:
    left, right = equation.split('=')
    
    def short(s):
        coe, d = 0, 0
        vs = re.findall(r'[+|-]?\d+x|[+|-]?\d+|[+|-]?x', s)
        for v in vs:
            if 'x' in v:
                c = v[:-1]
                if not c or not c[-1].isdigit():
                    c += '1'
                coe += int(c)
            else:
                d += int(v)
        return coe, d
    
    l_c, l_d = short(left)
    r_c, r_d = short(right)
    f_c, f_d = l_c-r_c, r_d-l_d
    if f_c == 0:
        return ('No solution', 'Infinite solutions')[f_d==0]
    else:
        return 'x={}'.format(f_d//f_c)
方法二：看了stefan的答案。replace呀，这种题可以替换一些字符串产生简单的操作。复数的操作我在想的时候思路一闪而过，然后不知道怎么实现就没往下想。 
1
2
3
4
def solveEquation(self, equation: str) -> str:
    z = eval(equation.replace('x', 'j').replace('=', '-(') + ')', {'j': 1j})
    a, x = z.real, -z.imag
    return 'x=%d' % (a / x) if x else 'No solution' if a else 'Infinite solutions'
方法三：左右可以一起算，通过=来改变一个符号。+的变成-，-变成+，正则分成4个组没有想到。头铁就想把它们塞到一起，那样反而判断得更多了。 
1
2
3
4
5
6
7
8
9
10
11
def solveEquation(self, equation: str) -> str:
    x = a = 0
    side = 1
    for eq, sign, num, isx in re.findall('(=)|([-+]?)(\d*)(x?)', equation):
        if eq:
            side = -1
        elif isx:
            x += side * int(sign + '1') * int(num or 1)
        elif num:
            a -= side * int(sign + num)
    return 'x=%d' % (a / x) if x else 'No solution' if a else 'Infinite solutions'

319. Bulb Switcher

有n个开关控制n个初始化为关的灯泡。从1开始，每次隔1,2,3,4..n开这些开关，问最后有多少个开着的灯。原题

方法一：这题有点像脑筋急转弯，我分析出了只有1~n的数有奇数个约数，那么最后就是开着的。然后什么样的数有奇数个约数，看了stefan后恍然大悟，原来是开方。

1
2
def bulbSwitch(self, n: int) -> int:
    return int(math.sqrt(n))

592. Fraction Addition and Subtraction

分数运算，有负数，只有+-操作，最后要返回一个分数，如果是整数的话，需要分母1。

1
2
3
4
5
6
Input:"-1/2+1/2"
Output: "0/1"
Input:"-1/2+1/2+1/3"
Output: "1/3"
Input:"1/3-1/2"
Output: "-1/6"

方法一：cheat 写法。

1
2
3
4
5
6
7
8
9
10
11
def fractionAddition(self, expression: str) -> str:
    import fractions
    tokens = iter(re.findall(r'-?\d+\/-?\d+|[+-]', expression))
    ans, sign = fractions.Fraction(0), 1
    for token in tokens:
        if token in '+-':
            sign = ' +'.find(token)
        else:
            ans += sign * fractions.Fraction(token)
    ans = str(ans) + ('/' not in str(ans)) * '/1'
    return ans

方法二：自己实现了一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def fractionAddition(self, expression: str) -> str:
    tokens = iter(re.findall(r'-?\d+\/-?\d+|[+-]', expression))
    
    def cal(a, b, sign=1):
        na, da = map(int, a.split('/'))
        nb, db = map(int, b.split('/'))
        dc = da*db // math.gcd(da, db)
        nc = dc//da*na + sign*dc//db*nb
        r = math.gcd(nc, dc)
        return '{}/{}'.format(nc//r, dc//r)
        
    ans, sign = '0/1', 1
    for token in tokens:
        if token in '+-':
            sign = ' +'.find(token)
        else:
            ans = cal(ans, token, sign)
    return ans
方法三：受到评论区大佬启发，优化一下，首先对正则优化，可以将分子分母都拆分出来，然后一次取两个。Stefan的答案，我居然把分数累加的公式都给忘了。 
1
2
3
4
5
6
7
8
9
10
11
def fractionAddition(self, expression: str) -> str:
    nums = iter(map(int, re.findall(r'[+-]?\d+', expression)))
    na, da = 0, 1
    for nb in nums:
        db = next(nums)
        na = na*db + da*nb
        da *= db
        r = math.gcd(na, da)
        na //= r
        da //= r
    return '{}/{}'.format(na, da)
方法四：Lee的写法，是我愚钝了。 
1
2
3
4
def fractionAddition(self, expression: str) -> str:
    from fractions import Fraction as f
    ans = sum(map(f, re.findall(r'[+-]?\d+/\d+', expression)))
    return '{}/{}'.format(ans.numerator, ans.denominator)

397. Integer Replacement

给定一个数，偶数可以/2，奇数可以+1，-1，问最少多少步能到1。

1
2
3
4
5
6
7
8
Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1

方法一：递归。

1
2
3
4
5
6
7
8
9
10
11
def integerReplacement(self, n: int) -> int:
    
    @lru_cache(None)
    def dp(i):
        if i == 1: return 0
        if i & 1 == 0:
            return dp(i//2) + 1
        else:
            return min(dp(i+1), dp(i-1)) + 1
    
    return dp(n)

方法二：这是一个贪心的方法。首先需要推导证明。//2的方式一定是最快的，因为2/1也只用了1步。

1
2
3
4
5
f(1) = 0
f(2n) = 1 + f(n)
f(2n+1) = min(f(2n)+1, f(2n+2)+1)
f(2n+2) = f(n+1) + 1
f(2n+1) = min(f(2n)+1, f(n+1)+2)
1
2
3
4
5
6
7
8
9
10
11
def integerReplacement(self, n):
    rtn = 0
    while n > 1:
        rtn += 1
        if n % 2 == 0:
            n //= 2
        elif n % 4 == 1 or n == 3:
            n -= 1
        else:
            n += 1
    return rtn

372. Super Pow

求大数的幂。幂也可以很大。对1337的余数。

1
2
Input: a = 2, b = [1,0]
Output: 1024

方法一：我用math.pow()， 超过了range error了。而stefan的pow就可以，难道因为取余运算放到方法里就很快？即使是这种方式，将1337用%取余也会超时。

1
2
def superPow(self, a: int, b: List[int]) -> int:
    return pow(a, int(''.join(map(str, b))), 1337)

方法二：Stefan的方法。

1
2
3
4
5
def superPow(self, a: int, b: List[int]) -> int:
    ans = 1
    for digit in b:
        ans = (pow(ans, 10, 1337) * pow(a, digit, 1337)) % 1337
    return ans

面试题 16.14. 最佳直线

平面上有一些点，画一条直线，问穿过做多点的线，最开始的两个点的索引是什么。

1
2
3
输入： [[0,0],[1,1],[1,0],[2,0]]
输出： [0,2]
解释： 所求直线穿过的3个点的编号为[0,2,3]

方法一：暴力,O(n^3)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bestLine(self, points: List[List[int]]) -> List[int]:
    N = len(points)
    ans, cnt = [], 0
    for i, p1 in enumerate(points):
        for j, p2 in enumerate(itertools.islice(points, i+1, N), i+1):
            x1, y1 = p2[0]-p1[0], p2[1]-p1[1]
            c = 2
            for p3 in itertools.islice(points, j+1, N):
                x2, y2 = p3[0]-p1[0], p3[1]-p1[1]
                if x1*y2 == x2*y1:
                    c += 1
            if c > cnt:
                cnt = c
                ans = [i, j]
    return ans

方法二：评论区学到的方法，改了一下。哈希表记录，一条直线有斜率和截距来确定。以此为hash。截距怎么求都忘了，推导了半天。这里索引比较乱，所以用了namedtuple。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def bestLine(self, points: List[List[int]]) -> List[int]:

    def f(p1, p2) -> tuple:
        # 返回两个点的斜率和纵截距
        if p1.x == p2.x:
            return float('inf'), p1.x
        else:
            return ((p2.y-p1.y) / (p2.x-p1.x),
                    (p1.y*p2.x-p2.y*p1.x) / (p2.x-p1.x))

    d, N = {}, len(points)
    x = y = max_cnt = 0
    Point = namedtuple('Point', 'x y')
    for i, coor1 in enumerate(points):
        p1 = Point(*coor1)
        for j, coor2 in enumerate(islice(points, i+1, N), i+1):
            p2 = Point(*coor2)
            k, b = f(p1, p2)
            d.setdefault((k, b), [0, (i, j)])
            d[k, b][0] += 1
            if d[k, b][0]>max_cnt or (d[k, b][0]==max_cnt and (x, y) > d[k, b][1]):
                max_cnt = d[k, b][0]
                x, y = d[k, b][1]
    return x, y
方法三：这个方法很效率，时间空间是前两种的一半。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def bestLine(self, points: List[List[int]]) -> List[int]:
    ans = []
    N, max_cnt = len(points), 0
    for i, p1 in enumerate(points):
        slope = {}
        for j, p2 in enumerate(islice(points, i+1, N), i+1):
            if p1[0] == p2[0]:
                k = None   # 这里赋值什么都行，只要别和斜率重复
            else:
                k = (p2[1]-p1[1]) / (p2[0]-p1[0])
            slope.setdefault(k, [i])
            slope[k].append(j)
        for idx in slope.values():
            if len(idx) > max_cnt:
                max_cnt = len(idx)
                ans = idx[:2]
    return ans

60. Permutation Sequence

全排列中的第k个。原题

1
2
Input: n = 3, k = 3
Output: "213"

方法一：这道题写法进行了一些改进，严格意义上来说不算回溯，不知道为什么官方标签贴了一个回溯，只是做了剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def getPermutation(self, n: int, k: int) -> str:
    self.k = k - 1

    def dfs(s, rest):
        if not rest:
            return ''.join(s)

        for i in range(len(rest)):
            if self.k >= math.factorial(len(rest)-1):
                self.k -= math.factorial(len(rest)-1)
                continue
            s += rest[i]
            return dfs(s, rest[:i]+rest[i+1:])

    nums = list(map(str, range(1, n+1)))
    return dfs([], nums)

方法二：改变一下思路，根据k的大小来确定每个位置的数。这道题想了不到个小时，最终原创出自己的写法。耗时36ms，beats 99%。果然数据规律才是致命的降维打击。

1
2
3
4
5
6
7
8
9
10
11
def getPermutation(self, n: int, k: int) -> str:
    ans = ''
    nums = list(map(str, range(1, n+1)))
    fact = math.factorial(len(nums)-1)
    while k != 1:
        i = (k - 1) // fact
        k -= i * fact
        ans += nums.pop(i)
        fact //= len(nums)            
    ans += ''.join(nums)
    return ans
方法三：根据solution中调整了一些点。关于k索引的问题可以在一开始就-1，然后循环中便可以使用divmod内置函数来求值。 
1
2
3
4
5
6
7
8
9
10
11
def getPermutation(self, n: int, k: int) -> str:
    ans = ''
    nums = list(map(str, range(1, n+1)))
    fact = math.factorial(len(nums)-1)
    k -= 1
    while k:
        i, k = divmod(k, fact)
        ans += nums.pop(i)
        fact //= len(nums)            
    ans += ''.join(nums)
    return ans

1643. Kth Smallest Instructions

第k个最小的指令，其实是求R*'V'+C*'H'的第k个最小的非重复的全排列。

1
2
3
4
Input: destination = [2,3], k = 1
Output: "HHHVV"
Explanation: All the instructions that reach (2, 3) in lexicographic order are as follows:
["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].

方法一：可惜，比赛时没有足够时间来做，是想到了数学法，也想起来和60题很像，区别在于60题没有重复，这里需要去重。评论区的一个解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def kthSmallestPath(self, destination: List[int], k: int) -> str:
    ans = ''
    R, C = destination
    left_v = R
    for i in range(R+C):
        left_p = R+C - i - 1
        com = comb(left_p, left_v)		# H开头的有多少种
        if com < k:
            ans += 'V'
            left_v -= 1
            k -= com
        else:
            ans += 'H'
    return ans

1621. Number of Sets of K Non-Overlapping Line Segments

给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。返回方案数。

方法一：比赛时没做出来，卡在第二题，想到了组合。看到了Lee的答案。给你n个点，k个线段可以共享端点。这个问题可以转化成：

给你n+k-1个点，每个线段不可以共享端点。在k个线段之间各补一个点。所以只需要求出从这些点出选出2k个点的组合。因为每两个相邻的点连成一段，所以是2k。

1
2
def numberOfSets(self, n: int, k: int) -> int:
    return math.comb(n+k-1, 2*k) % (10**9+7)

458. Poor Pigs

说有这么1000桶里面装了水，其中有一桶里面是毒药。你可以让无数头猪来这些水，但是每头猪15分钟只能喝一次，不过可以同时喝若干桶水。你要在1个小时之内知道哪个桶是有毒药的。最少需要多少头猪。

方法一：数学方法。这题比较难想。从一只猪开始思考。60分钟一共可以喝4次，不过可以检测5个桶，因为喝完最后的没有死，所有毒药在没有喝的桶。然后是两只猪，可以检测5**2个桶，将25个桶想象成一个平面。一只猪每次按照行来喝，另一只猪按照列来喝。最后通过行列可以确定毒药的位置。3只猪的时候要想象成三维的平面，每次每只猪要喝25桶的水，分别按照x, y, z轴的顺序。最后三个维度的坐标可以确定。本质上此题是一道信息论的题。知乎有个大佬通过信息熵来解此题，不明觉厉。

1
2
3
4
5
def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
    pigs = 0
    while (minutesToTest // minutesToDie + 1) ** pigs < buckets:
        pigs += 1
    return pigs

1744. Can You Eat Your Favorite Candy on Your Favorite Day?

能否在某一天吃到某种特定的糖果。三个规则：每天至少吃一个；从类型小的吃，吃完才能吃下个类型；查询条件中限制每天最多吃多少糖果。

1
2
3
4
5
6
7
8
Input: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
Output: [true,false,true]
Explanation:
1- If you eat 2 candies (type 0) on day 0 and 2 candies (type 0) on day 1, you will eat a candy of type 0 on day 2.
2- You can eat at most 4 candies each day.
   If you eat 4 candies every day, you will eat 4 candies (type 0) on day 0 and 4 candies (type 0 and type 1) on day 1.
   On day 2, you can only eat 4 candies (type 1 and type 2), so you cannot eat a candy of type 4 on day 2.
3- If you eat 1 candy each day, you will eat a candy of type 2 on day 13.

方法一：比赛时没有做出来，结束后18分钟做出来了。一个条件想错了应该是pre_sum[can+1]>=day+1，而不是pre_sum[can]>=day。

其实能否吃到，只有两个条件。一个是那一天能不能够到指定的糖果，每天按照最多的吃。另一个是每天只吃一个，到了那天该种糖果还有没有剩余。

1
2
3
4
def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
    pre_sum = list(accumulate([0]+candiesCount))
    return [pre_sum[can] < (day+1)*limit and (pre_sum[can+1]>=day+1)
            for can, day, limit in queries]

1780. Check if Number is a Sum of Powers of Three

判断一个数是否由不一样3的幂，组成。

1
2
3
Input: n = 91
Output: true
Explanation: 91 = 30 + 32 + 34

方法一：比赛时，暴力求出了所有的可能的结果，然后判断。1500ms。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def __init__(self):
        p3 = [1]
        while p3[-1] < 10**7:
            p3.append(p3[-1]*3)
        cand = []
        for i in range(1, len(p3)+1):
            cand.extend(map(sum, combinations(p3, i)))
        self.cand = set(cand)
        
    def checkPowersOfThree(self, n: int) -> bool:
        return n in self.cand
方法二：10 = 1 * 3^0 + 0 * 3^1 + 1 * 3^2 -> True
11 = 2 * 3^0 + 0 * 3^1 + 1 * 3^2 -> False, because there is a 2 as coeficient。如果余数出现2，就不能组成这个数。 
1
2
3
4
5
def checkPowersOfThree(self, n: int) -> bool:
    while n > 1:
        n, r = divmod(n, 3)
        if r == 2: return False
    return True

1819. Number of Different Subsequences GCDs

求一个数组的任意子序列所有的数的最大公约数，有多少种。

1
2
3
4
Input: nums = [6,10,3]
Output: 5
Explanation: The figure shows all the non-empty subsequences and their GCDs.
The different GCDs are 6, 10, 3, 2, and 1.

方法一：竞赛没有参加，比较是比赛写不出来的题。看别人的答案看了很久。首先，枚举子序列一定会超时，这里要用逆向思维，枚举公约数。当指定了公约数之后，找会不会有这样一个子序列能满足这个公约数。这些子序列中的数一定是这个公约数的倍数。y表示公约数，x为组成子序列的数，g值会逐渐减小，直到等于y表示，找到了这样一个子序列的最大公约数为g。这里迷惑了很久为什么要break，因为题中要求的是种类的个数。所以不需要再往下进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
    nums = set(nums)
    c = max(nums)
    ans = 0
    for y in range(1, c + 1):
        g = None
        for x in range(y, c + 1, y):
            if x in nums:
                if not g:
                    g = x
                else:
                    g = math.gcd(g, x)
                if g == y:
                    ans += 1
                    break
    return ans

523. Continuous Subarray Sum

是否存在连续的子数组和为k的倍数。

1
2
3
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

方法一：前缀和+哈希。没有想出来。很关键的一点，是当pre_sum[j]-pre_sum[i]=n*k即pre_sum[j]和pre_sum[i]对k取余有相同的结果。想明白这点，此题就很简单。

1
2
3
4
5
6
7
8
9
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
    pre_sum = list(accumulate(nums))
    remider = {0: -1}
    for i, s in enumerate(pre_sum):
        mod = s % k
        remider.setdefault(mod, i)
        if i - remider[mod] > 1:
            return True
    return False