刷题记录帖子

1913        Maximum Product Difference Between Two Pairs        Easy

1914        Cyclically Rotating a Grid

找规律 慢慢来

1. class Solution:
   
2.     def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
   
3.         m, n = len(grid), len(grid[0])
   
4.         res = []
   
5.         for _ in range(m):
   
6.             res.append([0] * n)
   
7.         num_layers = min(m, n) // 2
   
8. 
   
9.         for i_layer in range(num_layers):
   
10.             w_m, w_n = m - 2* i_layer, n - 2*i_layer
    
11.             row = m - i_layer
    
12.             col = n - i_layer
    
13.             print(w_m, w_n)
    
14.             period = 2*w_m + 2*w_n - 4
    
15.             dis = k % period
    
16.             layer = []
    
17.             pos = []
    
18.             
    
19.             # get layer elements
    
20.             for i in range(i_layer, col):
    
21.                 layer.append(grid[i_layer][i])
    
22.                 pos.append((i_layer, i))
    
23.             for j in range(i_layer+1, row):
    
24.                 layer.append(grid[j][i])
    
25.                 pos.append((j, i))
    
26.             for p in range(i-1, i_layer-1, -1):
    
27.                 layer.append(grid[j][p])
    
28.                 pos.append((j, p))
    
29.             for q in range(j-1, i_layer, -1):
    
30.                 layer.append(grid[q][p])
    
31.                 pos.append((q, p))
    
32. 
    
33.             # Fill res
    
34.             count = 0
    
35.             while count <= period:
    
36.                 r,c = pos[count%period]
    
37.                 res[r][c] = layer[dis%period]
    
38.                 dis += 1
    
39.                 count += 1
    
40.         return res

复制代码

1004        Max Consecutive Ones III        Medium        5        Sliding Window with fixed Zeros

1. class Solution:
   
2.     def longestOnes(self, nums: List[int], k: int) -> int:
   
3.         l, num_zeros, r = 0, 0, 0
   
4.         ans = 0
   
5.         
   
6.         while r < len(nums):
   
7.             if nums[r] == 0: num_zeros += 1
   
8.             while num_zeros > k:
   
9.                 # 1 1 1 0 0 1 1 1 1 1 0
   
10.                 #         l           r           
    
11.                 # move l to keep the same window
    
12.                 if nums[l] == 0: num_zeros -= 1
    
13.                 l += 1
    
14. 
    
15.             ans = max(ans, r-l+1)
    
16.             r += 1
    
17.         return ans

复制代码

1220         Count Vowels Permutation         Hard

有限状态机

1. class Solution:
   
2.     def countVowelPermutation(self, n: int) -> int:
   
3.         # dp[i,j]
   
4.         # j is from CharIndDict,{'a':0, 'e':1. 'i':2, 'o':3, 'u':4}
   
5.         # i is the length of new string
   
6.         # dp[i,j] using Char_j as ending with length i permutation numbers
   
7.         """
   
8.         Each vowel 'a' may only be followed by an 'e'.
   
9.         Each vowel 'e' may only be followed by an 'a' or an 'i'.
   
10.         Each vowel 'i' may not be followed by another 'i'.
    
11.         Each vowel 'o' may only be followed by an 'i' or a 'u'.
    
12.         Each vowel 'u' may only be followed by an 'a'.
    
13.         
    
14.         So each sting ending with
    
15.         
    
16.         'a' is from: 'e', 'i', 'u'
    
17.         'e' is from: 'a', 'i'
    
18.         'i' is from: 'e', 'o'
    
19.         'o' is from: 'i'
    
20.         'u' is from: 'o', 'i'
    
21.         """
    
22.         # edge case
    
23.         if n == 1: return 5
    
24.         
    
25.         # {'a':0, 'e':1. 'i':2, 'o':3, 'u':4}
    
26.         dp0 = [1] * 5
    
27.         dp1 = [0] * 5
    
28.         mod = 10**9 + 7
    
29.         while n-1>0:
    
30.             for i in range(5):
    
31.                 if i == 0: # 'a' is from: 'e', 'i', 'u'
    
32.                     dp1[0] = (dp0[1] + dp0[2] + dp0[4]) % mod
    
33.                 elif i == 1: # 'e' is from: 'a', 'i'
    
34.                     dp1[1] = (dp0[0] + dp0[2]) % mod
    
35.                 elif i == 2: #'i' is from: 'e', 'o'
    
36.                     dp1[2] = (dp0[1] + dp0[3]) % mod
    
37.                 elif i == 3: # 'o' is from: 'i'
    
38.                     dp1[3] = dp0[2] % mod
    
39.                 else: #'u' is from: 'o', 'i'
    
40.                     dp1[4] = (dp0[3] + dp0[2]) % mod
    
41.             n -= 1
    
42.             # deep copy
    
43.             for i in range(5): dp0[i] = dp1[i]
    
44.         return sum(dp0)%mod
    
45.                
    
46.             
    
47.             

复制代码

658. Find K Closest Elements

Looking for starting index of k subarray
Starting index range 0 ~ N-k
Let L = 0, R = N-k
Mid = (L+R) // 2

L ------- Mid -------- R

If x in L ~ Mid:

L ---x---- Mid -------- R ==>> R = mid, starting index must be in left part


But if x in Mid ~ R
Starting index can be either in left part or right part

Case1: L ------- Mid -x-------(Mid+k)----- R

Case2: L ------- Mid ----|----(Mid+k)----- R

Case3: L ------- Mid ---------(Mid+k)---x- R

So actually (Mid+k) and Mid is the key comparing factors

1. class Solution:
   
2.     def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
   
3.         # Initialize binary search bounds
   
4.         left = 0
   
5.         right = len(arr) - k
   
6.         
   
7.         # Binary search against the criteria described
   
8.         while left < right:
   
9.             mid = (left + right) // 2
   
10.             if x - arr[mid] > arr[mid + k] - x:
    
11.                 left = mid + 1
    
12.             else:
    
13.                 right = mid
    
14. 
    
15.         return arr[left:left + k]

复制代码

566        Reshape the Matrix
简单的 LOOP 注意 edge cases 和坐标匹配

1338        Reduce Array Size to The Half
Bucket Sort优化

1. class Solution:
   
2.     def minSetSize(self, arr: List[int]) -> int:
   
3.         cnt = Counter(arr)
   
4.         frequencies = list(cnt.values())
   
5.         maxFreq = max(frequencies)
   
6.         bucket = [0] * (maxFreq + 1)
   
7.         for freq in frequencies:
   
8.             bucket[freq] += 1
   
9. 
   
10.         ans, removed, half = 0, 0, len(arr) // 2
    
11.         freq = maxFreq
    
12.         while removed < half:
    
13.             ans += 1
    
14.             while bucket[freq] == 0: freq -= 1
    
15.             removed += freq
    
16.             bucket[freq] -= 1
    
17.         return ans

复制代码

378        Kth Smallest Element in a Sorted Matrix        Medium

真是精彩的解答。一步步利用信息从 N2logN to nlogn to n

89         Gray Code        Medium

镜像法

位移法, i ^ (i//2)

1925        Count Square Sum Triples        Easy        1       
1930        Unique Length-3 Palindromic Subsequences        Medium        5        Using Freq Count to solve it
1929        Concatenation of Array        Easy        1