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

Leetcode算法题练习(一)

目录

一、前言

二、移动零

三、复写零

四、快乐数

五、电话号码的字母组合

六、字符串相加


一、前言

大家好,我是dbln,从本篇文章开始我就会记录我在练习算法题时的思路和想法。如果有错误,还请大家指出,帮助我进步。谢谢!


二、移动零

链接:移动零

题目描述:给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操作。

51e905280c474dc99160762ae34c2267.png

思路:我们可以使用双指针来帮助我们解决这个问题。

1、如果cur位置是0,则cur++

2、如果cur位置是非0,则我们将dest+1位置的数和cur位置的数交换,然后cur++, dest++

2f82c0c3472b4d22961d9a76a0a164cf.png

代码实现:

void swap(int* a, int* b)
{int c = *a;*a = *b;*b = c;
}void moveZeroes(int* nums, int numsSize)
{int cur = 0;int dest = -1;while(cur < numsSize){if(nums[cur] == 0){cur++;}else{swap(&nums[dest+1], &nums[cur]);dest++;cur++;}}
}

b783bcbe497c4725b3bc9d5f1e9d0d6f.png


三、复写零

链接:复写零

题目描述:给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。注意:请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改,不要从函数返回任何东西。

cb838519bd004d2d93398ea120964a5a.png

思路:1、我们首先需要找到最后一个需要复写的数字,这里我们可以使用双指针算法(指针cur用来扫描数组,判断该位置是否为0,指针dest用来表示cur位置的数字的复写次数,如果非0,dest移动一步,否则移动两步,当dest >= n-1就结束,cur位置结束最后一个需要复写的数字)

c337b2c3793a46728c370eafbdce7e37.png

           2、然后从后往前进行复写

           3、提交后发现没有通过,原来还有一些特殊情况没有处理,如下图。我们发现下面这种情况的数组在执行完步骤1后,dest已经越界了,如果这时我们仍然进行复写就会出错,因此我们需要修正一下边界:将dest-1的位置修改为0,cur--,dest -= 2。然后正常进行复写。

5c1dc2ad8d7249ed98c8bfd376425b86.png

代码实现:

class Solution 
{
public:void duplicateZeros(vector<int>& arr) {//1、找到最后一个需要复写的数字int cur = 0, dest = -1;int n = arr.size();while(cur < n){if(arr[cur] != 0){dest++;}else{dest += 2;}if(dest >= n-1){break;}cur++;}//修正边界 [1,0,2,3,0,4]if(dest == n){arr[n-1] = 0;cur--;dest -= 2;}//3、从后往前复写while(cur >= 0){if(arr[cur] == 0){arr[dest--] = 0;arr[dest--] = 0;cur--;}else{arr[dest--] = arr[cur--];}}}
};

21e90f5f67d848c09f8f3045f108a124.png


四、快乐数

链接:快乐数

题目描述:

编写一个算法来判断一个数 n 是不是快乐数。

快乐数的定义为:

对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果这个过程结果为 1,那么这个数就是快乐数。如果 n 是快乐数就返回 true ;不是,则返回 false 。

3cee113111ae4c65bf2ec4f0680f3bc3.png

思路:根据下面的图我们来进行分析

          1、首先,我们根据第二组数所形成的一个环形可以大胆地推测这道题或许和快慢指针的追及相遇问题有关。然后,我们根据题意就可以知道快乐数经过有限次的变化会变成1,而非快乐数就会无限循环,永远不会到1,我们就断定我们可以根据快慢指针的思想判断是否有环,来判断是否是快乐数。

         2、我们可以先封装一个函数专门来计算一个数每个位置上的数字的平方和。

         3、然后慢指针表示第一个数,快指针表示第二个数。

         4、慢指针一次移动一步,快指针依次移动两步。

         5、如果最后慢指针变成了1,那么这个数就是快乐数,如果两者相遇,就不是快乐数。

aeb31d86829a439c8eeb96a59c9e28ba.png

代码实现: 

class Solution 
{
public:int SquareSum(int n){int sum = 0;while(n){int t = n % 10;sum += t*t;n /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast = SquareSum(n);while(slow != fast){slow = SquareSum(slow);fast = SquareSum(SquareSum(fast));}return slow==1;}
};

cd6286007143431c8e052ad55b9ad984.png


五、电话号码的字母组合

链接:电话号码的字母组合

题目描述:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

3b0c2fdcf2304289abeeabb7e6ca78b7.png

思路: 1、首先我们可以先定义一个数字到对应字符串的映射的数组。

            2、

f07594c297144c5e86c2988f0a694ecf.png

代码实现:

class Solution 
{
public:char* numtostr[10] = {" ", " ", "abc", "def", "ghi", "jkl", "mno", 
"pqrs", "tuv", "wxyz"};void combine(string digits, int di, vector<string>& v, string combinestr){if(di == digits.size()){v.push_back(combinestr);return;}int num = digits[di] - '0';string str = numtostr[num];for(auto ch : str){combine(digits, di+1, v, combinestr+ch);}}vector<string> letterCombinations(string digits) {vector<string> retv;string str;if(digits.empty()){return retv;}combine(digits, 0, retv, str);return retv;}
};

06be4227bda6411cae5f58a709eae5cc.png


六、字符串相加

 链接:字符串相加

题目描述:给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。

9616d35c7d584058b625b48d42ca65fd.png

 思路:

对两个字符串从后往前逐位相加,并将其转换成字符插入到新的string中,同时记录下进位情况。

记得处理特殊情况:最后可能存在进位。

代码实现:

class Solution 
{
public:string addStrings(string num1, string num2) {int end1 = num1.size()-1;int end2 = num2.size()-1;int next = 0;string strRet;while(end1>=0 || end2>=0){int val1 = end1>=0 ? num1[end1] - '0' : 0;int val2 = end2>=0 ? num2[end2] - '0' : 0;int ret = val1 + val2 + next;next = ret > 9 ? 1 : 0;strRet.insert(0, 1, '0' + (ret%10));end1--;end2--;}if(next)strRet.insert(0, 1, '0' + 1);return strRet;}
};​

53f4ca392d97461298ec0a991b488d2b.png

相关文章:

Leetcode算法题练习(一)

目录 一、前言 二、移动零 三、复写零 四、快乐数 五、电话号码的字母组合 六、字符串相加 一、前言 大家好&#xff0c;我是dbln&#xff0c;从本篇文章开始我就会记录我在练习算法题时的思路和想法。如果有错误&#xff0c;还请大家指出&#xff0c;帮助我进步。谢谢&…...

Xilinx FPGA 7系列 GTX/GTH Transceivers (5)-- Aurora 8b10b 信号传输实战--小试牛刀

第一节:Xilinx FPGA 7系列 GTX/GTH Transceivers (1)–了解了GTX硬件的基础知识 第二节:IBERT GTX --通过Ibert IP测试链路通信 第三节:aurora 8b10b single lane 4byte–学习官方历程 第四节:aurora 8b10b single lane 4byte–修改官方例子,发收递增数。 GTX/GTH Transc…...

第三章:最新版零基础学习 PYTHON 教程(第七节 - Python 运算符—Python 成员身份和身份运算符)

Python 提供了两个成员资格运算符来检查或验证值的成员资格。它测试序列(例如字符串、列表或元组)中的成员资格。 in 运算符: “in”运算符用于检查序列中是否存在字符/子字符串/元素。如果在序列中找到指定元素,则求值为 True,否则求值为 False。例如, CSDNforCSDN 中…...

【Java 基础篇】Java 注解详解

在 Java 编程中&#xff0c;注解&#xff08;Annotation&#xff09;是一种元数据&#xff0c;它提供了关于程序代码的额外信息。注解不直接影响程序的执行&#xff0c;但可以在运行时提供有关程序的信息&#xff0c;或者让编译器执行额外的检查。 本文将详细介绍 Java 注解的…...

MVVM框架下两窗口的消息传递

副窗口关闭的时候将bool类型传递出去 var message new CloseWindowMessage {MedicineView_DialogResult true }; //CloseWindowMessage是存储bool类型的标记类 Messenger.Default.Send(message); 主窗体中添加关闭处理的方法 private void HandleCloseWindowMessage(Clo…...

ROS2 从头开始​​:第6部分 - ROS2 中的 DDS,用于可靠的机器人通信

一、说明 在这篇文章中,我们将重点关注 ROS 2的通信栈DDS,其中这是介于管理节点通信与控制节点通信环节,是上位机决策体系与下位机的控制体系实现指令-执行-反馈的关键实现机制。 二、ROS工程的概念框架 现代机器人系统非常复杂,因为需要集成各种类型的传感器、执行器和其…...

WebSocket的那些事(6- RabbitMQ STOMP目的地详解)

目录 一、目的地类型二、Exchange类型目的地三、Queue类型目的地四、AMQ Queue类型目的地五、Topic类型目的地 一、目的地类型 在上节 WebSocket的那些事&#xff08;5-Spring STOMP支持之连接外部消息代理&#xff09;中我们已经简单介绍了各种目的地类型&#xff0c;如下图&…...

SQL SELECT 语句基础

在数字化的世界中,数据已经成为了一种无处不在的资源。从游戏开发到商业智能,数据分析都是不可或缺的一部分。SQL(结构化查询语言)是一种用于与数据库进行交互的编程语言,而SELECT 语句则是其中最基础也最常用的查询方式。 本文将通过对《三国志》游戏的角色数据进行分析…...

golang工程——protobuf使用及原理

相关文档 源码&#xff1a;https://github.com/grpc/grpc-go 官方文档&#xff1a;https://www.grpc.io/docs/what-is-grpc/introduction/ protobuf编译器源码&#xff1a;https://github.com/protocolbuffers/protobuf proto3文档&#xff1a;https://protobuf.dev/programmin…...

CocosCreator3.8研究笔记(二十三)CocosCreator 动画系统-动画编辑器相关功能面板说明

国庆假期&#xff0c;闲着没事&#xff0c;在家研究技术~ 上一篇&#xff0c;我们介绍了动画剪辑、动画组件以及基本的使用流程&#xff0c;感兴趣的朋友可以前往阅读&#xff1a; CocosCreator 动画系统-动画剪辑和动画组件介绍。 今天&#xff0c;主要介绍动画编辑器相关功能…...

免费 AI 代码生成器 Amazon CodeWhisperer 初体验

文章作者&#xff1a;浪里行舟 简介 随着 ChatGPT 的到来&#xff0c;不由让很多程序员感到恐慌。虽然我们阻止不了 AI 时代到来&#xff0c;但是我们可以跟随 AI 的脚步&#xff0c;近期我发现了一个神仙 AI 代码生产工具 CodeWhisperer &#xff0c;它是一项基于机器学习的服…...

谷歌扩展下载

Chrome 扩展下载安装网站推荐 # 1. 极简插件优质crx应用 ●地址&#xff1a;https://chrome.zzzmh.cn ●推荐&#xff1a;★★★★★ 一个非常良心 & 干净 & 简洁的 Chrome 扩展下载网站&#xff0c;体验非常不错&#xff01; 侧边栏可以通过类型对扩展进行筛选和排序&…...

Mac上如何修复损坏的音频?试试iZotope RX 10,对音频进行处理,提高音频质量!

iZotope RX 10是一款由iZotope公司开发的音频修复和编辑软件。它被广泛用于电影、电视、音乐和游戏等行业的音频后期制作&#xff0c;以及声音设计和修复工作。 在RX 10中&#xff0c;iZotope从头开始重新设计了全新的Repair Assistant修复助手&#xff0c;并且推出了相应的修…...

Mysql各种锁

一.不同存储引擎支持的锁机制 Mysql数据库有多种数据存储引擎&#xff0c;Mysql中不同的存储引擎支持不同的锁机制 MyISAM和MEMORY存储引擎采用的表级锁 InnoDB存储引擎支持行级锁&#xff0c;也支持表级锁&#xff0c;默认情况下采用行级锁 二.锁类型的划分 按照数据操作…...

【算法导论】快速排序

文章目录 1. 快速排序的描述 1.1基本描述1.2 PARTITOION函数1.3 快速排序C完整代码 2. 快速排序的性能2.1 最坏时间复杂度2.2 平均时间复杂度 1. 快速排序的描述 1.1基本描述 快速排序是一种时间复杂度为 O(n^2) 的排序算法。虽然最坏情况时间复杂度很差&#xff0c;但他的平…...

QT之QScriptEngine的用法介绍

QT之QScriptEngine的用法介绍 成员函数用法举例 成员函数 1&#xff09;QScriptEngine::evaluate(const QString &program, const QString &fileName QString(), int lineNumber 1) 执行 JavaScript 代码并返回结果。 2&#xff09;QScriptEngine::evaluate(const…...

vim 工具的使用

注&#xff1a;以下操作都在普通模式下进行 光标的移动操作 gg 定位到代码的第一行 shiftg 定位到代码的最后一行 nshiftg 定位到第n行 shift6: 特定一行的开始 shift4 特定一行的结尾 上下左右的移动光标 h: 向左移动光标 j: 向下移动光标 k: 向上移动光标 l: 向右移动光标 …...

RPA有什么优势?RPA的8大优势!建议学习!

随着科技的不断发展&#xff0c;越来越多的企业开始寻求数字化转型&#xff0c;以提高生产力和效率。在这个过程中&#xff0c;RPA&#xff08;Robotic Process Automation&#xff09;机器人流程自动化技术逐渐成为企业数字化转型的重要工具之一。本文将从八个方面阐述RPA的优…...

初级篇—第二章SELECT查询语句

文章目录 什么是SQLSQL 分类SQL语言的规则与规范阿里巴巴MySQL命名规范数据导入指令 显示表结构 DESC基本的SELECT语句SELECTSELECT ... FROM列的别名 AS去除重复行 DISTINCT空值参与运算着重号查询常数过滤数据 WHERE练习 运算符算术运算符加减符号乘除符号取模符号 符号比较运…...

PostMan的学习

PostMan的学习 目录 环境变量和全局变量接口关联内置动态参数以及自定义动态参数实现业务闭环Postman断言批量运行collection数据驱动之CSV文件和JSON文件测试必须带请求头的接口Mock Serviers 服务器Cookie鉴权NewmanPostManNewManjenkins实现接口测试持续集成 参考资料&am…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...