农村学校资源网站建设与研究,广告营销策划公司,恶意点击广告软件,定制 网站目录
一、前言
二、移动零
三、复写零
四、快乐数
五、电话号码的字母组合
六、字符串相加 一、前言
大家好#xff0c;我是dbln#xff0c;从本篇文章开始我就会记录我在练习算法题时的思路和想法。如果有错误#xff0c;还请大家指出#xff0c;帮助我进步。谢谢我是dbln从本篇文章开始我就会记录我在练习算法题时的思路和想法。如果有错误还请大家指出帮助我进步。谢谢 二、移动零
链接移动零
题目描述给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。请注意 必须在不复制数组的情况下原地对数组进行操作。 思路我们可以使用双指针来帮助我们解决这个问题。
1、如果cur位置是0则cur
2、如果cur位置是非0则我们将dest1位置的数和cur位置的数交换然后cur, dest 代码实现
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[dest1], nums[cur]);dest;cur;}}
} 三、复写零
链接复写零
题目描述给你一个长度固定的整数数组 arr 请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。注意请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改不要从函数返回任何东西。 思路1、我们首先需要找到最后一个需要复写的数字这里我们可以使用双指针算法指针cur用来扫描数组判断该位置是否为0指针dest用来表示cur位置的数字的复写次数如果非0dest移动一步否则移动两步当dest n-1就结束cur位置结束最后一个需要复写的数字 2、然后从后往前进行复写 3、提交后发现没有通过原来还有一些特殊情况没有处理如下图。我们发现下面这种情况的数组在执行完步骤1后dest已经越界了如果这时我们仍然进行复写就会出错因此我们需要修正一下边界将dest-1的位置修改为0cur--dest - 2。然后正常进行复写。 代码实现
class Solution
{
public:void duplicateZeros(vectorint 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--];}}}
}; 四、快乐数
链接快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。
快乐数的定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是无限循环但始终变不到 1。如果这个过程结果为 1那么这个数就是快乐数。如果 n 是快乐数就返回 true 不是则返回 false 。 思路根据下面的图我们来进行分析 1、首先我们根据第二组数所形成的一个环形可以大胆地推测这道题或许和快慢指针的追及相遇问题有关。然后我们根据题意就可以知道快乐数经过有限次的变化会变成1而非快乐数就会无限循环永远不会到1我们就断定我们可以根据快慢指针的思想判断是否有环来判断是否是快乐数。 2、我们可以先封装一个函数专门来计算一个数每个位置上的数字的平方和。 3、然后慢指针表示第一个数快指针表示第二个数。 4、慢指针一次移动一步快指针依次移动两步。 5、如果最后慢指针变成了1那么这个数就是快乐数如果两者相遇就不是快乐数。 代码实现
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 slow1;}
}; 五、电话号码的字母组合
链接电话号码的字母组合
题目描述给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 思路 1、首先我们可以先定义一个数字到对应字符串的映射的数组。 2、 代码实现
class Solution
{
public:char* numtostr[10] { , , abc, def, ghi, jkl, mno,
pqrs, tuv, wxyz};void combine(string digits, int di, vectorstring 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, di1, v, combinestrch);}}vectorstring letterCombinations(string digits) {vectorstring retv;string str;if(digits.empty()){return retv;}combine(digits, 0, retv, str);return retv;}
}; 六、字符串相加 链接字符串相加
题目描述给定两个字符串形式的非负整数 num1 和num2 计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库比如 BigInteger 也不能直接将输入的字符串转换为整数形式。 思路
对两个字符串从后往前逐位相加并将其转换成字符插入到新的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(end10 || end20){int val1 end10 ? num1[end1] - 0 : 0;int val2 end20 ? 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;}
};
