国内自建站,温州建设小学网站首页,网站建立计划书,上海建设工程咨询有限公司招聘目录 100296. 两个字符串的排列差
原题链接
思路分析
AC代码
100274. 从魔法师身上吸取的最大能量
原题链接
思路分析
AC代码
100281. 矩阵中的最大得分
原题链接
思路分析
AC代码
100312. 找出分数最低的排列
原题链接
思路分析
AC代码 100296. 两个字符串的排…目录 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) 竞赛
思路分析
看得出数据很弱啊全排列最优性剪枝就过了
就是全排列的暴搜然后如果当前已经比最优解更差了就剪枝
时间复杂度阶乘级别带剪枝的就不分析了 2024.5.1214:30
回看这道题发现就是状压dp求哈密顿回路板子题而且起点一定是0任何解可以轮转到0为起点
那么时间复杂度就是O(2^n * n)
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
状压dp
class Solution:def findPermutation(self, nums: List[int]) - List[int]:n len(nums)g [[0] * n for _ in range(n)]for i in range(n):for j in range(n):g[i][j] abs(i - nums[j])f [[inf] * n for _ in range(1 n)]ans [[ chr(ord(a) n) * n] * n for _ in range(1 n)]f[1][0] 0ans[1][0] afor i in range(1, 1 n):if i 1:for j in range(n):if i j 1:for k in range(n):if i k 1:t f[i ^ (1 j)][k] g[k][j]s ans[i ^ (1 j)][k] chr(ord(a) j)if t f[i][j]:f[i][j] tans[i][j] selif t f[i][j] and s ans[i][j]:ans[i][j] smi infret str(n) * nfor i in range(1, n):t f[(1 n) - 1][i] g[i][0]if t mi:mi f[(1 n) - 1][i] g[i][0]ret ans[(1 n) - 1][i]elif t mi and ans[(1 n) - 1][i] ret:ret ans[(1 n) - 1][i]return [ord(x) - ord(a) for x in ret]
