当前位置: 首页 > 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

http://www.lryc.cn/news/179616.html

相关文章:

  • Xilinx FPGA 7系列 GTX/GTH Transceivers (5)-- Aurora 8b10b 信号传输实战--小试牛刀
  • 第三章:最新版零基础学习 PYTHON 教程(第七节 - Python 运算符—Python 成员身份和身份运算符)
  • 【Java 基础篇】Java 注解详解
  • MVVM框架下两窗口的消息传递
  • ROS2 从头开始​​:第6部分 - ROS2 中的 DDS,用于可靠的机器人通信
  • WebSocket的那些事(6- RabbitMQ STOMP目的地详解)
  • SQL SELECT 语句基础
  • golang工程——protobuf使用及原理
  • CocosCreator3.8研究笔记(二十三)CocosCreator 动画系统-动画编辑器相关功能面板说明
  • 免费 AI 代码生成器 Amazon CodeWhisperer 初体验
  • 谷歌扩展下载
  • Mac上如何修复损坏的音频?试试iZotope RX 10,对音频进行处理,提高音频质量!
  • Mysql各种锁
  • 【算法导论】快速排序
  • QT之QScriptEngine的用法介绍
  • vim 工具的使用
  • RPA有什么优势?RPA的8大优势!建议学习!
  • 初级篇—第二章SELECT查询语句
  • PostMan的学习
  • 配置OSPF路由
  • CCF CSP认证 历年题目自练Day17
  • 基于Matlab实现多因子选股模型(附上源码+数据)
  • 【中秋国庆不断更】OpenHarmony多态样式stateStyles使用场景
  • Qt扩展-QCustomPlot绘图基础概述
  • 二、局域网联机
  • 决策树剪枝:解决模型过拟合【决策树、机器学习】
  • Ubuntu部署运行ORB-SLAM2
  • 二十,镜面IBL--打印BRDF积分贴图
  • 自动驾驶:未来的道路上的挑战与机遇
  • Go 语言 iota 的神奇力量