刷题记录帖子

2108. Find First Palindromic String in the Array
2109. Adding Spaces to a String
2110. Number of Smooth Descent Periods of a Stock

300. Longest Increasing Subsequence

经典题，NlgN 值得背诵

1. class Solution:
   
2.     def lengthOfLIS(self, nums: List[int]) -> int:
   
3.         sub = []
   
4.         for num in nums:
   
5.             i = bisect_left(sub, num)
   
6. 
   
7.             # If num is greater than any element in sub
   
8.             if i == len(sub):
   
9.                 sub.append(num)
   
10.             
    
11.             # Otherwise, replace the first element in sub greater than or equal to num
    
12.             else:
    
13.                 sub[i] = num
    
14.         
    
15.         return len(sub)

复制代码

231 Power of two 熟题，主要是记忆 Bit 操作的和 Binary Number of Power of Two 的特征进行求解。

1. """
   
2. 
   
3. n & (n - 1) == 0
   
4. 
   
5. """
   
6. class Solution(object):
   
7.     def isPowerOfTwo(self, n):
   
8.         if n == 0:
   
9.             return False
   
10.         return n & (n - 1) == 0
    
11. 
    
12. """
    
13. 
    
14. n&(-n) == n
    
15. 
    
16. """
    
17. class Solution(object):
    
18.     def isPowerOfTwo(self, n):
    
19.         if n == 0:
    
20.             return False
    
21.         return n & (-n) == n
    
22. 
    
23. """
    
24. 
    
25. log N
    
26. 
    
27. """
    
28. class Solution(object):
    
29.     def isPowerOfTwo(self, n):
    
30.         if n == 0:
    
31.             return False
    
32.         while n % 2 == 0:
    
33.             n /= 2
    
34.         return n == 1

复制代码

973. K Closest Points to Origin

2119. A Number After a Double Reversal

其实很简单，就是最后这个数不能是 10 的倍数。。。

1. class Solution:
   
2.     def isSameAfterReversals(self, num: int) -> bool:
   
3.         if num == 0:
   
4.             return True
   
5.         return num % 10 != 0

复制代码

2120. Execution of All Suffix Instructions Staying in a Grid

1. class Solution:
   
2.     def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
   
3.         ans = [0] * len(s)
   
4.         moves = {'L':(0, -1), 'R':(0, 1), 'U':(-1, 0), 'D':(1, 0)}
   
5.         for i in range(len(s)):
   
6.             curr_row, curr_col = startPos[0],  startPos[1]
   
7.             curr_step = 0
   
8.             for j in range(i, len(s)):
   
9.                 tmp_row, tmp_col = curr_row + moves[s[j]][0], curr_col + moves[s[j]][1]
   
10.                 if 0 <= tmp_row < n and 0 <= tmp_col < n:
    
11.                     curr_step += 1
    
12.                     curr_row, curr_col = tmp_row, tmp_col
    
13.                 else:
    
14.                     break
    
15.             ans[i] = curr_step
    
16.         return ans

复制代码

2121. Intervals Between Identical Elements

476. Number Complement

1. class Solution:
   
2.     def findComplement(self, num: int) -> int:
   
3.         str_bin_num = [ch for ch in bin(num)[2:]]
   
4.         ans = 0
   
5. 
   
6.         for ch in str_bin_num:
   
7.             if ch == '0':
   
8.                 ans = ans * 2 + 1
   
9.             else:
   
10.                 ans = ans * 2
    
11.         return ans
    
12.    
    
13.    
    
14. """
    
15. 
    
16. One bit operations
    
17. 
    
18. """
    
19. 
    
20. class Solution:
    
21.     def findComplement(self, num):
    
22.         todo, bit = num, 1
    
23.         while todo:
    
24.             # flip current bit
    
25.             num = num ^ bit
    
26.             # prepare for the next run
    
27.             bit = bit << 1
    
28.             todo = todo >> 1
    
29.         return num
    
30.    
    
31. """
    
32. 
    
33. BitMask Operations
    
34. 
    
35. """
    
36. 
    
37. from math import log2
    
38. class Solution:
    
39.     def findComplement(self, num):
    
40.         # n is a length of num in binary representation
    
41.         n = floor(log2(num)) + 1        
    
42.         # bitmask has the same length as num and contains only ones 1...1
    
43.         bitmask = (1 << n) - 1
    
44.         # flip all bits
    
45.         return bitmask ^ num
    
46.    
    
47. """
    
48. 
    
49. BitMask Operations with Built-in Functions
    
50. 
    
51. """
    
52. class Solution:
    
53.     def findComplement(self, num):
    
54.         return (1 << num.bit_length()) - 1 - num

复制代码

Leetcode 300. Longest Increasing Subsequence (Python) 重新理解 算法原理

1. class Solution:
   
2.     def lengthOfLIS(self, nums: List[int]) -> int:
   
3.         sub = []
   
4.         for num in nums:
   
5.             i = bisect_left(sub, num)
   
6. 
   
7.             # If num is greater than any element in sub
   
8.             if i == len(sub):
   
9.                 sub.append(num)
   
10.             
    
11.             # Otherwise, replace the first element in sub greater than or equal to num
    
12.             else:
    
13.                 sub[i] = num
    
14.         
    
15.         return len(sub)

复制代码

849. Maximize Distance to Closest Person