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

金属加工网站怎么做seo流量排名工具

金属加工网站怎么做,seo流量排名工具,网站建设维护工作经验,专业简历制作软件Leetcode 第 135 场双周赛题解 Leetcode 第 135 场双周赛题解题目1:3222. 求出硬币游戏的赢家思路代码复杂度分析 题目2:3223. 操作后字符串的最短长度思路代码复杂度分析 题目3:3224. 使差值相等的最少数组改动次数思路代码复杂度分析 题目4…

Leetcode 第 135 场双周赛题解

  • Leetcode 第 135 场双周赛题解
    • 题目1:3222. 求出硬币游戏的赢家
      • 思路
      • 代码
      • 复杂度分析
    • 题目2:3223. 操作后字符串的最短长度
      • 思路
      • 代码
      • 复杂度分析
    • 题目3:3224. 使差值相等的最少数组改动次数
      • 思路
      • 代码
      • 复杂度分析
    • 题目4:3225. 网格图操作后的最大分数
      • 思路
      • 代码
      • 复杂度分析

Leetcode 第 135 场双周赛题解

题目1:3222. 求出硬币游戏的赢家

思路

要用价值为 75 和 10 的硬币凑出价值总和为 115 的硬币,唯一的可能是 1 个 75 + 4 个 10。

如果一开始 Alice 就没法选,或者偶数轮后 Alice 没法选,那么 Bob 胜出,否则 Alice 胜出。

设 k=min(x, ⌊y/4⌋),这是能玩的回合数,判断 k 的奇偶性即可。

代码

/** @lc app=leetcode.cn id=3222 lang=cpp** [3222] 求出硬币游戏的赢家*/// @lc code=start
class Solution
{
public:string losingPlayer(int x, int y){return min(x, y / 4) % 2 ? "Alice" : "Bob";}
};
// @lc code=end

复杂度分析

时间复杂度:O(1)。

空间复杂度:O(1)。

题目2:3223. 操作后字符串的最短长度

思路

操作次数取决于每种字母的出现次数,与字母的位置无关。

假设某个字母出现了 c 次,那么操作后该字母最少能剩下多少?

根据题意,只有当 c≥3 时才能操作,每次操作可以把 c 减少 2。

  • 如果 c=3, 5, 7,⋯ 是奇数,那么不断减 2,最终 c=1。
  • 如果 c=4, 6, 8,⋯ 是偶数,那么不断减 2,最终 c=2。

累加每种字母最终剩下的 c,即为答案。

代码

/** @lc app=leetcode.cn id=3223 lang=cpp** [3223] 操作后字符串的最短长度*/// @lc code=start
class Solution
{
public:int minimumLength(string s){unordered_map<char, int> freq;for (char &c : s)freq[c]++;int ans = 0;for (auto &[c, cnt] : freq)ans += cnt % 2 ? 1 : 2;return ans;}
};
// @lc code=end

复杂度分析

时间复杂度:O(n+∣Σ∣),其中 n 是字符串 s 的长度,∣Σ∣ 是字符集合的大小,本题字符均为小写字母,所以 ∣Σ∣=26。

空间复杂度:O(∣Σ∣),其中 ∣Σ∣ 是字符集合的大小,本题字符均为小写字母,所以 ∣Σ∣=26。

题目3:3224. 使差值相等的最少数组改动次数

思路

想一想,什么情况下答案是 0?什么情况下答案是 1?

如果答案是 0,意味着所有 ∣nums[i]−nums[n−1−i]∣ 都等于同一个数 X。

如果答案是 1,意味着有 n/2−1 个 ∣nums[i]−nums[n−1−i]∣ 都等于同一个数 X。我们只需要修改那对不相等的,设这两个数分别为 p=nums[i], q=nums[n−1−i]。

不妨设 p≤q,分类讨论:

  • 如果修改 p,那么把 p 改成 0 可以让差值尽量大,此时差值为 q。
  • 如果修改 q,那么把 q 改成 k 可以让差值尽量大,此时差值为 k−p。
  • 如果 max(q,k−p)≥X,改其中一个数就行。
  • 如果 max(q,k−p)<X,p 和 q 两个数都要改。

注意题目保证 n 是偶数。

在这里插入图片描述

代码

/** @lc app=leetcode.cn id=3224 lang=cpp** [3224] 使差值相等的最少数组改动次数*/// @lc code=start
class Solution
{
public:int minChanges(vector<int> &nums, int k){vector<int> cnt(k + 1), cnt2(k + 1);int n = nums.size();for (int i = 0; i < n / 2; i++){int p = nums[i], q = nums[n - 1 - i];if (p > q){ // 保证 p <= qswap(p, q);}cnt[q - p]++;cnt2[max(q, k - p)]++;}int ans = n;int sum2 = 0; // 统计有多少对 (p,q) 都要改for (int x = 0; x <= k; x++){// 其他 n/2-cnt[x] 对 (p,q) 至少要改一个数,在此基础上,有额外的 sum2 对 (p,q) 还要再改一个数ans = min(ans, n / 2 - cnt[x] + sum2);// 对于后面的更大的 x,当前的这 cnt2[x] 对 (p,q) 都要改sum2 += cnt2[x];}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度:O(n+k),其中 n 是数组 nums 的长度。

空间复杂度:O(k)。

题目4:3225. 网格图操作后的最大分数

思路

题解:【图解】DP 及其优化:从 n^4 到 n^3 到 n^2(Python/Java/C++/Go)

代码

#
# @lc app=leetcode.cn id=3225 lang=python3
#
# [3225] 网格图操作后的最大分数
## @lc code=start
class Solution:def maximumScore(self, grid: List[List[int]]) -> int:n = len(grid)# 每列的前缀和(从上到下)col_sum = [list(accumulate(col, initial=0)) for col in zip(*grid)]# pre 表示第 j+1 列的黑格个数# dec=True 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数@cachedef dfs(j: int, pre: int, dec: bool) -> int:if j < 0:return 0res = 0# 枚举第 j 列有 cur 个黑格for cur in range(n + 1):if cur == pre:  # 情况一:相等# 没有可以计入总分的格子res = max(res, dfs(j - 1, cur, False))elif cur < pre:  # 情况二:右边黑格多# 第 j 列的第 [cur, pre) 行的格子可以计入总分res = max(res, dfs(j - 1, cur, True) + col_sum[j][pre] - col_sum[j][cur])elif not dec:  # 情况三:cur > pre >= 第 j+2 列的黑格个数# 第 j+1 列的第 [pre, cur) 行的格子可以计入总分res = max(res, dfs(j - 1, cur, False) + col_sum[j + 1][cur] - col_sum[j + 1][pre])elif pre == 0:  # 情况四(凹形):cur > pre < 第 j+2 列的黑格个数# 此时第 j+2 列全黑最优(递归过程中一定可以枚举到这种情况)# 第 j+1 列全白是最优的,所以只需考虑 pre=0 的情况# 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过,这里不重复统计res = max(res, dfs(j - 1, cur, False))return res# 枚举第 n-1 列有 i 个黑格return max(dfs(n - 2, i, False) for i in range(n + 1))
# @lc code=end

复杂度分析

时间复杂度:O(n3),其中 n 是数组 grid 的长度。由于每个状态只会计算一次,动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(n2),单个状态的计算时间为 O(n),所以动态规划的时间复杂度为 O(n3)。

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

http://www.ritt.cn/news/20459.html

相关文章:

  • 公司运营策划方案广州百度seo优化排名
  • 长沙做推广的公司有多少白帽seo是什么
  • 软件开发公司网站模板百度推广工作好干吗
  • 门户网站建设情况汇报最新新闻热点事件
  • 构建一个网站需要什么网上推广app怎么做
  • 中国高清vpswindows在线观看杭州seo的优化
  • 网站必须实名认证吗发稿平台
  • 如何删除在凡科上做的网站seo推广哪家好
  • 三亚河北建设招聘信息网站外贸网站优化
  • 网站营销是什么济宁seo公司
  • 网站空间流量查询焦作关键词优化排名
  • 大兴网站定制开发网络营销工程师培训
  • dede 网站地图 模块如何自己开发软件app
  • 做网站和做软件一样吗网络优化的三个方法
  • 新网站一天做多少外链宁波网络推广方式
  • 做网站大连2023广东最新疫情
  • 自己做的网站网页滑动不网络广告文案
  • .我爱你 网站上海网络营销有限公司
  • 简述网站建设国外网站seo免费
  • 关于seo关键词选择有哪些方法竞价托管优化公司
  • 保山哪里有网站建设磁力天堂最佳搜索引擎入口
  • 遵义网站建设公司有哪些新闻头条最新消息今天发布
  • 中国网通做网站seo工程师
  • 江门网站建设推广策划上海最新发布最新
  • 网站留言板作用百度经验官网
  • wordpress爆破密码字典奉化云优化seo
  • 网站建设公司导航中国站长
  • 长沙做企业网站百度官方电话号码
  • 有哪些做调查问卷赚钱的网站美国站外推广网站
  • 徐州城乡建设局网站seo怎么收费