LeetCode笔记:Weekly Contest 360
- LeetCode笔记:Weekly Contest 360
- 0. 吐槽
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 解题思路
- 2. 代码实现
- 比赛链接:https://leetcode.com/contest/weekly-contest-360/
0. 吐槽
这次的题目真的是,一言难尽,难倒是不难,就是各种特殊情况,边界条件,得想的很清楚,然后代码写起来就很丑,完全就是一坨一坨的,思路上感觉没啥难度,实现上各种复杂……
然后一看出题的公司,呵,果然又是国内公司,真的是,感觉每次出现这种思路不复杂但是各种边界条件坑的一逼的题目大都是国内公司出的,做完感觉除了浪费时间之外完全学不到东西,鸡肋的一逼……
国内公司这个出题的风格,真的是完全不明白他们出题的目的是什么……
1. 题目一
给出题目一的试题链接如下:
- 2833. Furthest Point From Origin
1. 解题思路
这一题没啥难度,左右符号的数目相减取绝对值然后加上下划线符号的数目即可得到可行走的最远距离。
2. 代码实现
给出python代码实现如下:
class Solution:def furthestDistanceFromOrigin(self, moves: str) -> int:cnt = Counter(moves)return abs(cnt["L"] - cnt["R"]) + cnt["_"]
提交代码评测得到:耗时31ms,占用内存16.1MB。
2. 题目二
给出题目二的试题链接如下:
- 2834. Find the Minimum Possible Sum of a Beautiful Array
1. 解题思路
这一题其实和上周的题目2829差不多(LeetCode笔记:Weekly Contest 359),也都是从小的数开始取,然后block与其pair的数,剩下不足的从target开始依次补足即可。
然后,知道取法之后,我们就可以优化一下直接用求和公式给出结果了。
2. 代码实现
给出python代码实现如下:
class Solution:def minimumPossibleSum(self, n: int, target: int) -> int:if n <= target // 2:return n * (n+1) // 2else:m = target // 2return m * (m+1) // 2 + (n-m) * (target+target+n-m-1) // 2
提交代码评测得到:耗时38ms,占用内存16.4MB。
3. 题目三
给出题目三的试题链接如下:
- 2835. Minimum Operations to Form Subsequence With Target Sum
1. 解题思路
这一题就是一个贪婪算法的思路,我们首先可以对给出的nums进行统计,获得所有 2 n 2^n 2n的个数。
然后,我们将target数用 2 n 2^n 2n的求和表示出来,即将其用二进制表示出来,然后依次看各个位上的数字能否在nums里面找到即可。
而这里说的贪婪算法的思路其实就是我们从小到大依次看target的各个二进制组成:
- 如果这个值直接在nums中存在,那么直接取用;
- 如果这个值可以用一系列比它的二进制数拼出来,那么就用这些更小的数来拼成这个值;
- 如果上述两者都不存在,那么就找到当前nums中比这个值大的最小的数,然后将其拆分到这个值的程度,并更新nums;
- 如果nums不存在比这个值大的数,那么返回-1即可。
2. 代码实现
给出python代码实现如下:
class Solution:def minOperations(self, nums: List[int], target: int) -> int:cnt = [0 for _ in range(32)]for num in nums:idx = 0while num != 1:num = num // 2idx += 1cnt[idx] += 1def is_possible(idx):need = 1for i in range(idx, -1, -1):if cnt[i] >= need:return Trueneed -= cnt[i]need *= 2return Falseres = 0idx = 0while target != 0:if target % 2 != 0:if is_possible(idx):need = 1for i in range(idx, -1, -1):if cnt[i] >= need:cnt[i] -= needbreakneed -= cnt[i]cnt[i] = 0need *= 2else:if all(cnt[i] == 0 for i in range(idx+1, 32)):return -1i = idx + 1while cnt[i] == 0:i += 1cnt[i] -= 1for j in range(idx, i):cnt[j] += 1res += 1delta = (target % 2) * pow(2, idx)target = target // 2 idx += 1return res
提交代码评测得到:耗时69ms,占用内存16.5MB。
4. 题目四
给出题目四的试题链接如下:
- 2836. Maximize Value of Function in a Ball Passing Game
1. 解题思路
这一题其实也不复杂,就是实现上麻烦一点。
本质上来说,这道题就是找到所有完整路径,然后统计一下其中长度为 k k k的所有子路径当中的最大值。
因此,事实上问题就拆分成了两步:
- 找到所有的路径;
- 在每一条路径当中,计算所有走过 k k k步的遍历长度,亦即所有长度为 k + 1 k+1 k+1的所有子路径。
关于第一个问题,事实上就是一个拓扑序列的问题,显然,这里所有的路径最后都会进入到一个环当中,这里就有两种情况:
- 起点不在环当中,也就是先走过一段直线,然后进入到一个环当中;
- 起点就在环当中,也就是整条路径就是一个无限循环的圈;
而要找全这两种路径其实也简单,首先对于第一种情况,显然起点不会出现在receiver当中,因此我们对所有receiver当中没出现过的值作为起点分别考察一下即可。
然后,对于第二种情况,我们只要在处理完了第一种情况之后的剩余点当中逐一考察每一个点作为起点的情况遍历其路径即可。
而每一种遍历方法都一样,就是不断地走直到下次出现的点在已走过的路径当中已经出现过即可。
然后,我们考察对于一条给定的路径,如何求所有长度为 k + 1 k+1 k+1的所有子路径。
这个同样不复杂,就是考察以路径上每一个点作为起点时后续连续长度为 k + 1 k+1 k+1的子串,但是这里同样有些特殊情况,因为最后可能会进入到子环当中,因此后面的路径可能就会有循环,因此不够的部分我们需要用环来补充,然后这部分的操作事实上我们可以用环的长度进行求余来快速处理,即我们计算出环需要循环的次数和剩下需要多走的步数,然后直接计算即可。
2. 代码实现
给出python代码实现如下:
class Solution:def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:n = len(receiver)status = [0 for _ in range(n)]def get_max_value(visited, idx):n = len(visited)m = n-idxaccums = [0] + list(accumulate(visited))d = k+1def get_value(i):if i + d <= n:return accums[i+d] - accums[i]r = i+d - na, b = r // m, r % mreturn accums[-1] - accums[i] + a * (accums[-1]-accums[idx]) + accums[idx+b] - accums[idx]res = max(get_value(i) for i in range(n))return resres = 0nxt = set(receiver)inits = [i for i in range(n) if i not in nxt]for i in inits:idx = iseen = set()visited = []while idx not in seen:status[idx] = 1seen.add(idx)visited.append(idx)idx = receiver[idx]res = max(res, get_max_value(visited, visited.index(idx)))for i in range(n):if status[i] == 1:continueidx = iseen = set()visited = []while idx not in seen:status[idx] = 1seen.add(idx)visited.append(idx)idx = receiver[idx]res = max(res, get_max_value(visited, visited.index(idx)))return res
提交代码评测得到:耗时581ms,占用内存38.4MB。
相关文章:
LeetCode笔记:Weekly Contest 360
LeetCode笔记:Weekly Contest 360 0. 吐槽1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接:https://leetcode.com/contest/weekly-contest-360/ 0.…...
【树DP】2021ICPC南京 H
Problem - H - Codeforces 题意: 思路: 这题应该算是铜牌题 铜牌题 简单算法 基础思维 简单复盘一下思路 首先,我们发现有个很特殊的条件: ti < 3 然后看一下样例: 注意到,对于一个结点 u &#…...
Leedcode19. 删除链表的倒数第 N 个结点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 输入:head [1,2,3,4,5], n 2 输出:[1,2,3,5] 示例 2: 输入:head [1], n 1 输出:[] 示例 3: 输入࿱…...
Mysql-索引查询相关
一、单表查询 1.1 二级索引为null 不论是普通的二级索引,还是唯一二级索引,它们的索引列对包含 NULL 值的数量并不限制,所以我们采用key IS NULL 这种形式的搜索条件最多只能使用 ref 的访问方法,而不是 const 的访问方法 1.2 c…...
C++ Pimpl
Pimpl(Pointer to implementation,指向实现的指针) 是一种减少代码依赖和编译时间的C编程技巧,其基本思想是将一个外部可见类(visible class)的实现细节(一般是所有私有的非虚成员)放在一个单独的实现类(implementation class)中&…...
rust学习-类型转换
基本类型转换 // 不显示类型转换产生的溢出警告。 #![allow(overflowing_literals)]fn main() {let decimal 65.4321_f32;// 错误!不提供隐式转换// let integer: u8 decimal;// 可以显式转换let integer decimal as u8;let character integer as char;println…...
算法通过村第四关-栈青铜笔记|手写栈操作
文章目录 前言1. 栈的基础概要1.1 栈的特征1.2 栈的操作1.3 Java中的栈 2. 栈的实现(手写栈)2.1 基于数组实现2.2 基于链表实现2.3 基于LinkedList实现 总结 前言 提示:我自己一个人的感觉很好 我并不想要拥有你 除非你比我的独处更加宜人 --…...
Python计算加速利器
迷途小书童的 Note 读完需要 6分钟 速读仅需 2 分钟 1 简介 Python 是一门应用非常广泛的高级语言,但是,长久以来,Python的运行速度一直被人诟病,相比 c/c、java、c#、javascript 等一众高级编程语言,完全没有优势。 那…...
PyTorch 深度学习实践 第10讲刘二大人
总结: 1.输入通道个数 等于 卷积核通道个数 2.卷积核个数 等于 输出通道个数 1.单通道卷积 以单通道卷积为例,输入为(1,5,5),分别表示1个通道,宽为5,高为5。假设卷积核大小为3x3,…...
Linux特殊指令
目录 1.dd命令 2.mkfs格式化 3.df命令 4.mount实现硬盘的挂载 5.unshare 1.dd命令 dd命令可以用来读取转换并输出数据。 示例一: if表示infile,of表示outfile。这里的/dev/zero是一个特殊文件,会不断产生空白数据。 bs表示复制一块的大…...
MPI之主从模式的一般编程示例
比如,我们可以选举0号进程为master进程,其余进程为slaver进程 #include "mpi.h" #include <unistd.h> #include <iostream>int main(int argc, char *argv[]) {int err MPI_Init(&argc,&argv);int rank,size;MPI_Comm_r…...
基于野狗算法优化的BP神经网络(预测应用) - 附代码
基于野狗算法优化的BP神经网络(预测应用) - 附代码 文章目录 基于野狗算法优化的BP神经网络(预测应用) - 附代码1.数据介绍2.野狗优化BP神经网络2.1 BP神经网络参数设置2.2 野狗算法应用 4.测试结果:5.Matlab代码 摘要…...
C语言面向对象的编程思想
面向对象编程 面向对象编程Object-Oriented Programming,OOP) 作为一种新方法,其本质是以建立模型体现出来的抽象思维过程和面向对象的方法。模型是用来反映现实世界中事物特征的。任何一个模型都不可能反映客观事物的一切具体特征࿰…...
MPI之非阻塞通信中通信完成检测接口简介
在之前的文章中,简单的写了一个非阻塞的通信代码介绍最最基本的使用: int main(int argc, char *argv[]) {int err MPI_Init(&argc,&argv);int rank,size;MPI_Comm_rank(MPI_COMM_WORLD,&rank);MPI_Comm_size(MPI_COMM_WORLD, &size);…...
Excel:如何实现分组内的升序和降序?
一、POWER 1、构建辅助列D列,在D2单元格输入公式: -POWER(10,COUNTA($A$2:A2)3)C2 2、选中B1:D10,注意不能宣导A列的合并单元格,进行以下操作: 3、删除辅助列即可 二、COUNTA 第一步,D2建立辅助列…...
深度学习论文: Segment Any Anomaly without Training via Hybrid Prompt Regularization
深度学习论文: Segment Any Anomaly without Training via Hybrid Prompt Regularization Segment Any Anomaly without Training via Hybrid Prompt Regularization PDF: https://arxiv.org/pdf/2305.10724.pdf PyTorch代码: https://github.com/shanglianlm0525/CvPytorch Py…...
【算法训练-字符串】一 最长无重复子串
废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是最长无重复子串或最长无重复子数组,这类题目出现频率还是很高的。 最长无重复子串【MID】 先来看字符串数据结构的题目 题干 解题思…...
【数据结构】手撕顺序表
一,概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储; 在数组上完成数据的增删查改。 1, 静态顺序表:使用定长数组存储元素。 2.,动态顺序表࿱…...
景联文科技数据标注:人体关键点标注用途及各点的位置定义
人体关键点标注是一种计算机视觉任务,指通过人工的方式,在指定位置标注上关键点,例如人脸特征点、人体骨骼连接点等,常用来训练面部识别模型以及统计模型。这些关键点可以表示图像的各个方面,例如角、边或特定特征。在…...
typescript基础之never
TypeScript 的 never 类型是一种特殊的类型,它表示的是那些永远不存在的值的类型。例如,一个抛出异常或无限循环的函数的返回值类型就是 never,因为它们永远不会返回任何值。never 类型是所有类型的子类型,也就是说,任…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
用鸿蒙HarmonyOS5实现国际象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的国际象棋小游戏的完整实现代码,使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├── …...
