目錄

100296.?兩個字符串的排列差

原題鏈接

思路分析

AC代碼

100274.?從魔法師身上吸取的最大能量

原題鏈接

思路分析

AC代碼

100281.?矩陣中的最大得分

原題鏈接

思路分析

AC代碼

100312.?找出分數最低的排列

原題鏈接

思路分析

AC代碼

---

100296.?兩個字符串的排列差

原題鏈接

兩個字符串的排列差 - 力扣 (LeetCode) 競賽

思路分析

簽到題，兩次遍歷搞定

AC代碼

class Solution:def findPermutationDifference(self, s: str, t: str) -> int:mp = dict()res = 0for i, x in enumerate(s):mp[x] = ifor i, x in enumerate(t):res += abs(i - mp[x])return res

100274.?從魔法師身上吸取的最大能量

原題鏈接

從魔法師身上吸取的最大能量 - 力扣 (LeetCode) 競賽

思路分析

記憶化搜索

dfs(0)代表從0出發的最大能量，記憶化剪枝保證每個結點只走一次

時間復雜度O(n)

AC代碼

class Solution:def maximumEnergy(self, energy: List[int], k: int) -> int:n = len(energy)@cache def dfs(x: int) -> int:if x >= n:return 0return energy[x] + dfs(x + k)return max(dfs(i) for i in range(n))

100281.?矩陣中的最大得分

原題鏈接

矩陣中的最大得分 - 力扣 (LeetCode) 競賽

思路分析

典中典網格上遞推，為了拼手速還是用的記憶化搜索

不過注意起點特判，可以在遞歸函數里面多加個bool參數

時間復雜度O(n^2)

AC代碼

class Solution:def maxScore(self, g: List[List[int]]) -> int:m, n = len(g), len(g[0])@cachedef dfs(x: int, y: int, lim: bool):if x >= m or y >= n:return 0ret = -inf if lim else 0if x + 1 < m:ret = max(ret, g[x + 1][y] - g[x][y] + dfs(x + 1, y, False))if y + 1 < n:ret = max(ret, g[x][y + 1] - g[x][y] + dfs(x, y + 1, False))return retreturn max(dfs(i, j, True) for j in range(n) for i in range(m))

100312.?找出分數最低的排列

原題鏈接

找出分數最低的排列 - 力扣 (LeetCode) 競賽

思路分析

看得出數據很弱啊，全排列+最優性剪枝就過了

就是全排列的暴搜，然后如果當前已經比最優解更差了就剪枝

時間復雜度：階乘級別帶剪枝的就不分析了

AC代碼

class Solution:def findPermutation(self, nums: list[int]) -> list[int]:n = len(nums)mi = n * nret = []path = []st = set()def dfs(res: int, s: int) -> None:nonlocal mi, path, ret, st# print(path, s, mi, res)if s >= mi:returnif (not res) and s + abs(path[-1] - nums[path[0]]) < mi:mi = s + abs(path[-1] - nums[path[0]])ret = path.copy()# print(ret, s)returnfor i in range(n):if not (i in st):path.append(i)st.add(i)t = 0 if res == n else abs(nums[path[-1]] - path[-2])dfs(res - 1, s + t)path.pop()st.remove(i)dfs(n, 0)return ret