目錄
備注
1-Play with Chips-easy。數組
2-Longest Arithmetic Subsequence of Given Difference-medium。哈希表、DP
3-Path with Maximum Gold-medium。BFS
4-Count Vowels Permutation-hard。DP、BFS
備注
- Q1。對問題做轉化是一種需要訓練的模組化思想。比如第一題，把cost轉化成求奇偶數的個數，這裡標明哪個位置最小已經不重要了，重要的是抽象成標明位置是奇還是偶，對應的cost
- Q2。由于等差數列的性質，運用DP，這裡隻需知道上一個數對應的最長長度。注意思考與LIS問題的異同
- Q3。網格類尋寶的問題可以有很多種遊戲設定，分為2類，一類是到達終點的路徑優化，一類是沿途收益優化，還有就是兩者的結合了，這裡是第二類。是以周遊所有起始點的可能性，找出對應的收益求最值，在找的過程中，單一路徑的求和記得用局部變量傳參
- Q4。披着拓撲排序影子的DP問題，這裡知道圖關系（可以建圖，也可以寫在邏輯裡），找到上一時刻和下一時刻的變換關系。原先是想在BFS過程中把整顆搜尋樹的某一層保留在一個隊列裡，開銷很大，這裡其實隻需保留每棵子樹的葉子結點個數，因為每個葉子節點分别對應的aeiou，而後續生長關系又是确定的，是以隻需保留節點個數，在下一次疊代時用他們之間的連接配接關系更新即可。
1-Play with Chips-easy。數組
There are some chips, and the i-th chip is at position
chips[i]
.
You can perform any of the two following types of moves any number of times (possibly zero) on any chip:
- Move the
i
- Move the
i
There can be two or more chips at the same position initially.
Return the minimum cost needed to move all the chips to the same position (any position).
Example 1:
Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.
Example 2:
Input: chips = [2,2,2,3,3]
Output: 2
Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.
Constraints:
-
1 <= chips.length <= 100
-
1 <= chips[i] <= 10^9
乍看很難，看chips長度，暴力應該能接受，一開始看測試用例了解錯了，以為下标就是在數軸上的位置，其實元素值才代表在數軸上的位置.
優化的解法是統計數組裡的奇偶數的個數，奇數個數代表標明偶數坐标為終點時的cost，因為此時偶數之間transfer是沒有cost的。偶數vice versa。巧妙
# 暴力
class Solution:
def minCostToMoveChips(self, chips: List[int]) -> int:
if not chips:
return 0
n = len(chips)
res = n+1
for i in chips:
cur = 0
for j in chips:
if abs(i-j) & 1:
cur += 1
res = min(res, cur)
return res
# 優化解法
class Solution:
def minCostToMoveChips(self, chips: List[int]) -> int:
if not chips:
return 0
n = len(chips)
l = r = 0
for i in chips:
if i & 1:
l += 1
else:
r += 1
return min(l, r)
2-Longest Arithmetic Subsequence of Given Difference-medium。哈希表、DP
Given an integer array
arr
and an integer
difference
, return the length of the longest subsequence in
arr
which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals
difference
.
Example 1:
Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4]. Example 2:
Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.
Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].
Constraints:
-
1 <= arr.length <= 10^5
-
-10^4 <= arr[i], difference <= 10^4
這道題一直想着用LIS，LIS的O(n^2)方法逾時，O(nlogn)沒想出來怎麼改寫。看大神的解法是用字典記錄每個元素，上一個valid的值對應的長度，很妙，因為這裡是等差的，是以可以順利索引到上一個值是什麼，但LIS問題隻要求遞增，不要求數與數的關系才會導緻要一個個周遊之前的數的，此處不用，很巧妙。
class Solution:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
if not arr:
return 0
n = len(arr)
dic = {}
res = 1
for n in arr:
dic[n] = dic.get(n-difference, 0) + 1
res = max(res, dic[n])
return res
3-Path with Maximum Gold-medium。BFS
In a gold mine
grid
of size
m * n
, each cell in this mine has an integer representing the amount of gold in that cell,
if it is empty.
Return the maximum amount of gold you can collect under the conditions:
- Every time you are located in a cell you will collect all the gold in that cell.
- From your position you can walk one step to the left, right, up or down.
- You can't visit the same cell more than once.
- Never visit a cell with gold.
- You can start and stop collecting gold from any position in the grid that has some gold.
Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
[5,8,7],
[0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.
Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
Constraints:
-
1 <= grid.length, grid[i].length <= 15
-
0 <= grid[i][j] <= 100
- There are at most 25 cells containing gold.
比較典型的BFS題，和以往不同的是這裡1是沒有起始點，從任何一個非0點開始都可以也就意味着有多重拾金子的路徑，2是沒有設定目标點也就是沒有結束判定，是以要自己設定結束判定，我設的是當周圍無路可走時就把收集到的gold求和，再判斷是否為截至目前的最大值。
但做法1還是太耗空間了，這裡用grid自身标記的方法，而且也不必記錄沿途收集過的金币，用一個局部變量cur記錄即可，傳參進去，這樣不同路徑的cur是互不幹擾的，是以這裡cur一定不能用全局變量，如果用的話相當于走過的地方全被記上了
# DIY做法1
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
if not grid:
return 0
m = len(grid)
n = len(grid[0])
self.res = 0
around = [[-1, 0], [1, 0], [0, -1], [0, 1]]
visited = [[False for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] > 0:
visited[i][j] = True
self.dfs(grid, around, i, j, m, n, [grid[i][j]], visited)
visited[i][j] = False
return self.res
def dfs(self, grid, around, i, j, m, n, path, visited):
flag = False
for d in around:
n_i = i + d[0]
n_j = j + d[1]
if n_i < 0 or n_i >= m or n_j < 0 or n_j >= n or grid[n_i][n_j] <= 0 or visited[n_i][n_j]:
continue
flag = True
path.append(grid[n_i][n_j])
visited[n_i][n_j] = True
self.dfs(grid, around, n_i, n_j, m, n, path, visited)
visited[n_i][n_j] = False
path.pop()
if not flag:
self.res = max(self.res, sum(path))
return
# 優化後的做法2
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
if not grid:
return 0
m = len(grid)
n = len(grid[0])
self.res = 0
around = [[-1, 0], [1, 0], [0, -1], [0, 1]]
for i in range(m):
for j in range(n):
if grid[i][j] > 0:
cur = 0
self.dfs(grid, around, i, j, m, n, cur)
return self.res
def dfs(self, grid, around, i, j, m, n, cur):
cur += grid[i][j]
grid[i][j] = -grid[i][j] # 這是個好辦法，比置0更友善
self.res = max(self.res, cur)
for d in around:
n_i = i + d[0]
n_j = j + d[1]
if n_i < 0 or n_i >= m or n_j < 0 or n_j >= n or grid[n_i][n_j] <= 0:
continue
self.dfs(grid, around, n_i, n_j, m, n, cur)
grid[i][j] = -grid[i][j]
return
4-Count Vowels Permutation-hard。DP、BFS
Given an integer
n
, your task is to count how many strings of length
n
can be formed under the following rules:
- Each character is a lower case vowel (
'a'
'e'
'i'
'o'
'u'
- Each vowel
'a'
'e'
- Each vowel
'e'
'a'
'i'
- Each vowel
'i'
'i'
- Each vowel
'o'
'i'
'u'
- Each vowel
'u'
'a'.
Since the answer may be too large, return it modulo
10^9 + 7.
Example 1:
Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".
Example 2:
Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".
Example 3:
Input: n = 5
Output: 68
Constraints:
-
1 <= n <= 2 * 10^4
這道題我了解是存儲好圖的關系，在再用BFS去生長所有路徑，最後子節點的個數就是結果，但到n=144之後的TLE了。
估計是維護一個隊列，進出很耗開銷，嘗試把具體字元換成對應的數。看看大神的做法，簡潔精彩
class Solution:
def countVowelPermutation(self, n: int) -> int:
if n < 1:
return 0
mod = 10**9 + 7
a, e, i, o, u = 1, 1, 1, 1, 1
for _ in range(n-1):
a_ = e + i + u
e_ = a + i
i_ = e + o
o_ = i
u_ = o + i
a, e, i, o, u = a_, e_, i_, o_, u_
res = (a%mod + e%mod + i%mod + o%mod + u%mod) % mod
return res
![leetcode189周賽[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)