当前位置: 首页 > news >正文

如何做ps4游戏视频网站淄博网站营销与推广

如何做ps4游戏视频网站,淄博网站营销与推广,lol视频网站模板,网站建设合作协议Leetcode 第 397 场周赛题解 Leetcode 第 397 场周赛题解题目1:3146. 两个字符串的排列差思路代码复杂度分析 题目2:思路代码复杂度分析 题目3:3148. 矩阵中的最大得分思路代码复杂度分析 题目4:3149. 找出分数最低的排列思路代码…

Leetcode 第 397 场周赛题解

  • Leetcode 第 397 场周赛题解
    • 题目1:3146. 两个字符串的排列差
      • 思路
      • 代码
      • 复杂度分析
    • 题目2:
      • 思路
      • 代码
      • 复杂度分析
    • 题目3:3148. 矩阵中的最大得分
      • 思路
      • 代码
      • 复杂度分析
    • 题目4:3149. 找出分数最低的排列
      • 思路
      • 代码
      • 复杂度分析

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. 矩阵中的最大得分

思路

动态规划。

设经过的方格为 c1, c2, ⋯ , ck,那么得分为 (c2−c1)+(c3−c2)+⋯+(ck−ck−1)=ck−c1,也就是说得分只和路径上第一个方格以及最后一个方格有关。

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

设 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(n22n),其中 n 是数组 nums 的长度。

空间复杂度:O(n2n),其中 n 是数组 nums 的长度。

http://www.ds6.com.cn/news/68944.html

相关文章:

  • 网站维护的方法万网域名官网
  • 休闲度假村网站建设方案深圳今日重大新闻
  • windows2012做网站友链交易交易平台
  • 网站建设教程小说简介防疫测温健康码核验一体机
  • 网站换服务器怎么做苹果自研搜索引擎或为替代谷歌
  • 哪个网站能下载gif怎样做网站卖自己的产品
  • 北京做网站费用网站关键词优化的价格
  • wordpress预约订单插件百度seo是什么意思呢
  • 吉林市今天消息西安网站建设推广优化
  • 如何优化公司网站百度智能建站平台
  • 把自己做的网站开放到外网外贸独立站怎么做
  • 网站找谁备案哪家公司做seo
  • 网站怎么做内链外链2023北京封控了
  • ppt模板免费下载完整版免费无需会员网站seo检测
  • 高端电商网站开发真实有效的优化排名
  • 网站制作答辩ppt怎么做深圳快速seo排名优化
  • 网站建设方案备案链接提交入口
  • seo整站优化的思路及步骤营销工具
  • 怎么把网站排名优化中国万网域名注册官网
  • 网站有时打不开学技术的培训学校
  • 网站开发费用国家标准品牌推广计划
  • 自己做免费的网站外贸怎么找客户资源
  • 企业网站色彩搭配免费域名注册平台有哪些
  • 绍兴网站设计营销推广公司案例
  • 整站seo怎么做seo优化步骤
  • 松江做网站需要多少钱想做一个网站
  • 做平面找那些网站找活网络游戏推广员是做什么的
  • 用路由器做简单的网站店铺推广渠道有哪些
  • 汉南做网站太原百度网站快速排名
  • 自己做捕鱼网站能不能挣钱百度学术论文查重入口