Leetcode 第 135 场双周赛题解

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.rhkb.cn/news/390746.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

classical Chinese

classical Chinese 中型娃娃暑假作业背诵 文言文《伯牙鼓琴》 1&#xff09;拿到文言文&#xff0c;先看一遍 2&#xff09;用白话文&#xff08;现代文&#xff09;翻译一次 3&#xff09;用白话文对照回去文言文&#xff08;白话文中那些需要替换回文言文呢&#xff09; 虽…

神奇海洋养鱼小程序游戏广告联盟流量主休闲小游戏源码

在海洋养鱼小程序中&#xff0c;饲料、任务系统、系统操作日志、签到、看广告、完成喂养、每日签到、系统公告、积分商城、界面设计、拼手气大转盘抽奖以及我的好友等功能共同构建了一个丰富而互动的游戏体验。以下是对这些功能的进一步扩展介绍&#xff1a; 饲料 任务奖励&a…

非对称加密:数据安全的双重保障

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

单元测试JUnit

前言&#x1f440;~ 上一章我们介绍了自动化测试工具Selenium&#xff0c;今天讲解单元测试工具JUnit JUnit JUnit的使用 JUnit注解 BeforeAll和AfterAll注解 BeforeEach和AfterEach注解 参数化 方法获取参数&#xff08;动态参数&#xff09; 断言 用例执行顺序 测…

MATLAB优化模型(3)

一、前言 在MATLAB中处理各种优化问题&#xff0c;如背包问题、指派问题&#xff08;也称为分配问题&#xff09;、抽屉原理应用、旅行商问题&#xff08;TSP&#xff09;以及排队论模型&#xff0c;通常需要结合MATLAB的优化工具箱&#xff08;如Optimization Toolbox&#xf…

MTK Android12 分析system_app允许vendor_mtk_audiohal_prop SELinux 权限问题

本文将尝试分析&#xff0c;在开发 Android 12 MTK 平台时遇到了 vendor_mtk_audiohal_prop 属性相关的 SELinux 权限问题。包括如何修改 SELinux 策略以允许 system_app 设置 vendor_mtk_audiohal_prop 属性。 问题描述 希望允许 system_app 设置 vendor_mtk_audiohal_prop 属…

C# Unity 面向对象补全计划 之 初识继承方法与多态

本文仅作学习笔记与交流&#xff0c;不作任何商业用途&#xff0c;作者能力有限&#xff0c;如有不足还请斧正 本系列旨在通过补全学习之后&#xff0c;给出任意类图都能实现并做到逻辑上严丝合缝 1.继承方法 C# & Unity 面向对象补全计划 之 继承&#xff08;字段与属性&…

如何在立创EDA的PCB电路板导入logo图案

1、首先制作好logo图案&#xff0c;一般为公司logo图标&#xff0c;如下图 2、打开立创EDA的PCB文件&#xff0c;如下图 3、将PCB的图层切换到丝印层&#xff1a; 4、然后选择EDA菜单栏的放置---图片&#xff1a; 5、进入后点击选择图片&#xff0c;将logo图片导入&#xff0c;…

Depth Anything——强大的单目深度估计模型

概述 单目深度估计&#xff08;Monocular Depth Estimation, MDE&#xff09;是一项在计算机视觉领域中非常重要的技术&#xff0c;它旨在从单张图像中恢复出场景的三维结构。这项技术对于机器人导航、自动驾驶汽车、增强现实&#xff08;AR&#xff09;和虚拟现实&#xff08…

在vscode中远程连接linux进行开发

目录 引言 配置过程 1.本机安装OpenSSH 2.本机生成RSA公钥和私钥 3.将rsa公钥添加到远程linux的authorized_keys文件中 4.vscode安装Remote - SSH插件 5.在vscode中ssh连接服务器 6.在本地vscode操作远程linux文件进行开发 7.在vscode上给远程linux机器需安装插件 常…

设计模式 之 —— 抽象工厂模式

目录 什么是抽象工厂模式&#xff1f; 定义 特点 抽象工厂模式&#xff08;java代码示例&#xff09; 首先定义第一个接口 实现第一个接口的类 定义第二个接口 实现第二个接口的类 * 创建抽象工厂类 创建扩展了 AbstractFactory 的工厂类 饮料工厂 食物工厂 * 创建一个…

[Meachines] [Easy] Sense PFSense防火墙RCE

信息收集 IP AddressOpening Ports10.10.10.60TCP:80,443 $ nmap -p- 10.10.10.60 --min-rate 1000 -sC -sV PORT STATE SERVICE VERSION 80/tcp open http lighttpd 1.4.35 |_http-title: Did not follow redirect to https://10.10.10.60/ |_http-server-header…

Nginx进阶-常见配置(二)

一、nginx 日志配置 nginx 日志介绍 nginx 有一个非常灵活的日志记录模式,每个级别的配置可以有各自独立的访问日志, 所需日志模块 ngx_http_log_module 的支持&#xff0c;日志格式通过 log_format 命令来定义&#xff0c;日志对于统计和排错是非常有利的&#xff0c;下面总…

Java语言程序设计——篇十一(3)

&#x1f33f;&#x1f33f;&#x1f33f;跟随博主脚步&#xff0c;从这里开始→博主主页&#x1f33f;&#x1f33f;&#x1f33f; 欢迎大家&#xff1a;这里是我的学习笔记、总结知识的地方&#xff0c;喜欢的话请三连&#xff0c;有问题可以私信&#x1f333;&#x1f333;&…

[激光原理与应用-118]:电源系统的接地详解:小信号的噪声干扰优化,从良好外壳接地开始

目录 一、电路的基本原理&#xff1a;电流回路 1、电流回路的基本概念 2、电流回路的特性 3、电流回路的类型 4、电流回路的应用 五、电流回路的注意事项 二、交流设备的接地 1.1 概述 1、交流工作接地的定义 2、交流工作接地的作用 3、交流工作接地的规范要求 4、…

C# Unity 面向对象补全计划 之 单例模式

本文仅作学习笔记与交流&#xff0c;不作任何商业用途&#xff0c;作者能力有限&#xff0c;如有不足还请斧正 本系列作为七大原则和设计模式的进阶知识&#xff0c;看不懂没关系 了解我的专栏C#面向对象与进阶:http://t.csdnimg.cn/mIitr&#xff0c;尤其是关于类的那篇文章即…

jupyter支持跨机器远程访问

1. 远程访问场景 本地往往缺少GPU设备&#xff0c;为了让我们的代码能在有GPU设备的机器上运行&#xff0c;就需要在远程机器上启动jupyter notebook, 这意味着我们要在本地机器的浏览器上访问远程机器上的jupyter notebook。但是直接按ip访问会报如下错误&#xff1a; 因为ju…

ctfshow-web入门-sql注入(web176-web180)

目录 1、web176 2、web177 3、web178 4、web179 5、web180 1、web176 1 order by 4-- 闭合后简单判断了下字段数是 3 测试联合查询注入&#xff0c;存在关键字的过滤&#xff0c;包括 select 和 union &#xff08;后面经过测试实际只过滤了 select&#xff09; 大小写绕…

Star-CCM+负体积网格检查与出现原因

要使网格可用于有限体积计算&#xff0c;每个网格单元必须具有正体积&#xff0c;否则初始化过程将失败&#xff0c;且模拟计算无法运行。 负体积网格单元可能会以多种不同的方式出现&#xff0c;但必须修复或从网格中移除&#xff0c;才能继续执行任何后续操作。 要检查体网…

力扣hot100-二叉树

文章目录 概要二叉树的基本概念常见的二叉树类型常用的二叉树遍历二叉树的常用技巧 题目&#xff1a;二叉树的中序遍历方法1--递归遍历方法2--使用栈 概要 二叉树&#xff08;Binary Tree&#xff09;是一种树形数据结构&#xff0c;其中每个节点最多有两个子节点&#xff0c;…