目錄

一、前言

二、移動(dòng)零

三、復(fù)寫零

四、快樂數(shù)

五、電話號(hào)碼的字母組合

六、字符串相加

---

一、前言

大家好，我是dbln，從本篇文章開始我就會(huì)記錄我在練習(xí)算法題時(shí)的思路和想法。如果有錯(cuò)誤，還請(qǐng)大家指出，幫助我進(jìn)步。謝謝！

---

二、移動(dòng)零

鏈接：移動(dòng)零

題目描述：給定一個(gè)數(shù)組 nums，編寫一個(gè)函數(shù)將所有 0 移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對(duì)順序。請(qǐng)注意?，必須在不復(fù)制數(shù)組的情況下原地對(duì)數(shù)組進(jìn)行操作。

思路：我們可以使用雙指針來幫助我們解決這個(gè)問題。

1、如果cur位置是0，則cur++

2、如果cur位置是非0，則我們將dest+1位置的數(shù)和cur位置的數(shù)交換，然后cur++, dest++

代碼實(shí)現(xiàn)：

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++;}}
}

---

三、復(fù)寫零

鏈接：復(fù)寫零

題目描述：給你一個(gè)長(zhǎng)度固定的整數(shù)數(shù)組?arr ，請(qǐng)你將該數(shù)組中出現(xiàn)的每個(gè)零都復(fù)寫一遍，并將其余的元素向右平移。注意：請(qǐng)不要在超過該數(shù)組長(zhǎng)度的位置寫入元素。請(qǐng)對(duì)輸入的數(shù)組就地進(jìn)行上述修改，不要從函數(shù)返回任何東西。

思路：1、我們首先需要找到最后一個(gè)需要復(fù)寫的數(shù)字，這里我們可以使用雙指針?biāo)惴?#xff08;指針cur用來掃描數(shù)組，判斷該位置是否為0，指針dest用來表示cur位置的數(shù)字的復(fù)寫次數(shù)，如果非0，dest移動(dòng)一步，否則移動(dòng)兩步，當(dāng)dest >= n-1就結(jié)束，cur位置結(jié)束最后一個(gè)需要復(fù)寫的數(shù)字）

? ? ? ? ? ?2、然后從后往前進(jìn)行復(fù)寫

? ? ? ? ? ?3、提交后發(fā)現(xiàn)沒有通過，原來還有一些特殊情況沒有處理，如下圖。我們發(fā)現(xiàn)下面這種情況的數(shù)組在執(zhí)行完步驟1后，dest已經(jīng)越界了，如果這時(shí)我們?nèi)匀贿M(jìn)行復(fù)寫就會(huì)出錯(cuò)，因此我們需要修正一下邊界：將dest-1的位置修改為0，cur--，dest -= 2。然后正常進(jìn)行復(fù)寫。

代碼實(shí)現(xiàn)：

class Solution 
{
public:void duplicateZeros(vector<int>& arr) {//1、找到最后一個(gè)需要復(fù)寫的數(shù)字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、從后往前復(fù)寫while(cur >= 0){if(arr[cur] == 0){arr[dest--] = 0;arr[dest--] = 0;cur--;}else{arr[dest--] = arr[cur--];}}}
};

---

四、快樂數(shù)

鏈接：快樂數(shù)

題目描述：

編寫一個(gè)算法來判斷一個(gè)數(shù) n 是不是快樂數(shù)。

快樂數(shù)的定義為：

對(duì)于一個(gè)正整數(shù)，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和。然后重復(fù)這個(gè)過程直到這個(gè)數(shù)變?yōu)?1，也可能是無限循環(huán)但始終變不到 1。如果這個(gè)過程結(jié)果為?1，那么這個(gè)數(shù)就是快樂數(shù)。如果 n 是快樂數(shù)就返回 true ；不是，則返回 false 。

思路：根據(jù)下面的圖我們來進(jìn)行分析

??????????1、首先，我們根據(jù)第二組數(shù)所形成的一個(gè)環(huán)形可以大膽地推測(cè)這道題或許和快慢指針的追及相遇問題有關(guān)。然后，我們根據(jù)題意就可以知道快樂數(shù)經(jīng)過有限次的變化會(huì)變成1，而非快樂數(shù)就會(huì)無限循環(huán)，永遠(yuǎn)不會(huì)到1，我們就斷定我們可以根據(jù)快慢指針的思想判斷是否有環(huán)，來判斷是否是快樂數(shù)。

? ? ? ? ?2、我們可以先封裝一個(gè)函數(shù)專門來計(jì)算一個(gè)數(shù)每個(gè)位置上的數(shù)字的平方和。

? ? ? ? ?3、然后慢指針表示第一個(gè)數(shù)，快指針表示第二個(gè)數(shù)。

? ? ? ? ?4、慢指針一次移動(dòng)一步，快指針依次移動(dòng)兩步。

? ? ? ? ?5、如果最后慢指針變成了1，那么這個(gè)數(shù)就是快樂數(shù)，如果兩者相遇，就不是快樂數(shù)。

代碼實(shí)現(xiàn)：?

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;}
};

---

五、電話號(hào)碼的字母組合

鏈接：電話號(hào)碼的字母組合

題目描述：給定一個(gè)僅包含數(shù)字?2-9?的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。

思路： 1、首先我們可以先定義一個(gè)數(shù)字到對(duì)應(yīng)字符串的映射的數(shù)組。

? ? ? ? ? ? 2、

代碼實(shí)現(xiàn)：

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;}
};

---

六、字符串相加

?鏈接：字符串相加

題目描述：給定兩個(gè)字符串形式的非負(fù)整數(shù)?num1 和num2?，計(jì)算它們的和并同樣以字符串形式返回。你不能使用任何內(nèi)建的用于處理大整數(shù)的庫(kù)（比如 BigInteger），?也不能直接將輸入的字符串轉(zhuǎn)換為整數(shù)形式。

?思路：

對(duì)兩個(gè)字符串從后往前逐位相加，并將其轉(zhuǎn)換成字符插入到新的string中，同時(shí)記錄下進(jìn)位情況。

記得處理特殊情況：最后可能存在進(jìn)位。

代碼實(shí)現(xiàn)：

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;}
};?