Leetcode 第 397 场周赛题解

Leetcode 第 397 场周赛题解

题目1：3146. 两个字符串的排列差

思路

模拟。

因为每个字符串中的字符都不重复，所以用一个哈希表统计字符串 s 中字符和下标，再遍历字符串 t 计算每个字符在两个字符串中位置的绝对差值之和。

代码

class Solution
{
public:int findPermutationDifference(string s, string t){int n = s.length();int diff = 0;unordered_map<char, int> idx;for (int i = 0; i < n; i++)idx[s[i]] = i;for (int i = 0; i < n; i++)diff += abs(i - idx[t[i]]);return diff;}
};

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

空间复杂度：O(n)，其中 n 是字符串 s 的长度。

题目2：

思路

外层循环枚举魔法师序列的末端，内层循环从魔法师序列的末端开始，往前间隔 k 累加求和。

因为有些魔法师可能会给你负能量，所以每累加一次能量，就要更新答案的最大值。

最后返回答案。

代码

class Solution
{
public:int maximumEnergy(vector<int> &energy, int k){int n = energy.size();int ans = INT_MIN;for (int i = n - k; i < n; i++){int sum = 0;for (int j = i; j >= 0; j -= k){sum += energy[j];ans = max(ans, sum);}}return ans;}
};

复杂度分析

时间复杂度：O(n)，其中 n 为数组 energy 的长度。

空间复杂度：O(1)。

题目3：3148. 矩阵中的最大得分

思路

动态规划。

设经过的方格为 c₁, c₂, ⋯ , c_k，那么得分为 (c₂−c₁)+(c₃−c₂)+⋯+(c_k−c_k−1)=c_k−c₁，也就是说得分只和路径上第一个方格以及最后一个方格有关。

因此问题变为：给一个矩阵，每次可以往右或往下走，求终点值-起点值的最大值。

设 dp[i][j] 表示以 (i,j) 为终点，起点的最小值，它显然是 dp[i - 1][j]、dp[i][j - 1]、grid[i][j] 三者的最小值，转移方程为：dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), grid[i][j])。

遍历 grid，每次先求以 (i,j) 为终点，起点的最小值 minGrid = min(dp[i - 1][j], dp[i][j - 1])，然后计算终点值-起点值的最大值 ans = max(ans, grid[i][j] - minGrid)，最后更新 dp[i][j] = min(grid[i][j], minGrid)。

最后返回 ans。

代码

/** @lc app=leetcode.cn id=3148 lang=cpp** [3148] 矩阵中的最大得分*/// @lc code=start
class Solution
{
public:int maxScore(vector<vector<int>> &grid){int m = grid.size(), n = m ? grid[0].size() : 0;// dp[i][j] 表示以 (i,j) 为终点，起点的最小值int dp[m][n];memset(dp, INT_MAX, sizeof(dp));int ans = INT_MIN;// 状态转移for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){int minGrid = INT_MAX;if (i > 0)minGrid = min(minGrid, dp[i - 1][j]);if (j > 0)minGrid = min(minGrid, dp[i][j - 1]);ans = max(ans, grid[i][j] - minGrid);dp[i][j] = min(grid[i][j], minGrid);}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(m*n)，其中 m 和 n 分别是矩阵 grid 的行数和列数。

空间复杂度：O(m*n)，其中 m 和 n 分别是矩阵 grid 的行数和列数。

题目4：3149. 找出分数最低的排列

思路

状压 DP。

题解：状压 DP：从记忆化搜索到递推（Python/Java/C++/Go）

代码

/** @lc app=leetcode.cn id=3149 lang=cpp** [3149] 找出分数最低的排列*/// @lc code=start
class Solution
{
public:vector<int> findPermutation(vector<int> &nums){int n = nums.size();vector<vector<int>> memo(1 << n, vector<int>(n, -1)); // -1 表示没有计算过// s 表示前面已选的下标集合，j 表示上一个位置的下标function<int(int, int)> dfs = [&](int s, int j) -> int{if (s == (1 << n) - 1){ // 所有位置都填完了，最后一个位置是下标 jreturn abs(j - nums[0]);}int &res = memo[s][j]; // 注意这里是引用if (res != -1){ // 之前计算过return res;}res = INT_MAX;// 枚举当前位置填下标 kfor (int k = 1; k < n; k++){if ((s >> k & 1) == 0){ // k 之前没填过res = min(res, dfs(s | 1 << k, k) + abs(j - nums[k]));}}return res;};vector<int> ans;// 找到最佳路径function<void(int, int)> make_ans = [&](int s, int j) -> void{ans.push_back(j);if (s == (1 << n) - 1)return;int final_res = dfs(s, j);for (int k = 1; k < n; k++){if ((s >> k & 1) == 1){ // k 之前填过continue;}if (dfs(s | 1 << k, k) + abs(j - nums[k]) == final_res){make_ans(s | 1 << k, k);break;}}};make_ans(1, 0);return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n²2ⁿ)，其中 n 是数组 nums 的长度。

空间复杂度：O(n2ⁿ)，其中 n 是数组 nums 的长度。