只出現(xiàn)一次的數(shù)字

力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

給你一個(gè)整數(shù)數(shù)組 nums，其中恰好有兩個(gè)元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。 找出只出現(xiàn)一次的那兩個(gè)元素。你可以按 任意順序 返回答案。

你必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法且僅使用常量額外空間來(lái)解決此問(wèn)題。

示例 1：

輸入：nums = [1,2,1,3,2,5]
輸出：[3,5]
解釋：[5, 3] 也是有效的答案。

示例 2：

輸入：nums = [-1,0]
輸出：[-1,0]

示例 3：

輸入：nums = [0,1]
輸出：[1,0]

思路

思路一：看到去重，先排序

上篇我們總結(jié)出了一個(gè)經(jīng)驗(yàn)：看到去重，就先排個(gè)序。把大小相同的放在一起，這樣，假如一個(gè)數(shù)的左鄰右舍都跟它不一樣，那這個(gè)數(shù)就是只出現(xiàn)了一次的那個(gè)。

這個(gè)道理 同樣可應(yīng)用于 這題。

class Solution {
public:
 ?  vector<int> singleNumber(vector<int>& nums) {
 ? ? ?  int sz = nums.size();
 ? ? ?  vector<int> ret;
 ? ? ?  //先考慮只有2 個(gè)元素的特殊情況
 ? ? ?  if (sz == 2) { ? ? 
 ? ? ? ? ?  for (int e : nums) {
 ? ? ? ? ? ? ?  ret.push_back(e);
 ? ? ? ? ?  }
 ? ? ? ? ?  return ret;
 ? ? ?  }
 ? ? ?  //先排序，讓相同的挨在一起
 ? ? ?  sort(nums.begin(), nums.end());
 ? ? ?  //通過(guò)左鄰右舍 來(lái)判斷是否形單影只
 ? ? ?  for (int i = 0; i < sz; i++) {
 ? ? ? ? ?  if (i == 0 && nums[i] != nums[i + 1]) {
 ? ? ? ? ? ? ?  ret.push_back(nums[i]);
 ? ? ? ? ?  }
 ? ? ? ? ?  else if (i == sz - 1 && nums[i] != nums[i - 1]) {
 ? ? ? ? ? ? ?  ret.push_back(nums[i]);
 ? ? ? ? ?  }
 ? ? ? ? ?  else if (i>0 && i<sz-1
 ? ? ? ? ? ? ?  &&nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
 ? ? ? ? ? ? ? ? {
 ? ? ? ? ? ? ? ? ?  ret.push_back(nums[i]);
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ?  return ret;
 ?  }
};

我的錯(cuò)誤記錄：

我一開(kāi)始，在if else的條件上出了bug

for (int i = 0; i < sz; i++) {
 ?  if (i == 0 && nums[i] != nums[i + 1]) {
 ? ? ?  ret.push_back(nums[i]);
 ?  }
 ?  else if (i == sz - 1 && nums[i] != nums[i - 1]) {
 ? ? ?  ret.push_back(nums[i]);
 ?  }
 ?  else{
 ? ? ?  if(nums[i] != nums[i - 1] && nums[i] != nums[i + 1]){
 ? ? ? ? ?  ret.push_back(nums[i]);
 ? ? ?  }
 ?  }
}

出了bug不要怕，我們來(lái)看看它的報(bào)錯(cuò)內(nèi)容：vector subscript out of range（subscript“下標(biāo)”，數(shù)組下標(biāo)超出范圍）

經(jīng)過(guò)檢查發(fā)現(xiàn)：

當(dāng)i=0時(shí)，它走不了前兩條if。由于第三個(gè)else沒(méi)設(shè)條件判斷的門檻，所以i=0直接就進(jìn)入了，進(jìn)去以后，i-1導(dǎo)致下標(biāo)越界。

所以說(shuō)，if else語(yǔ)句的條件判斷要多加小心！

思路二：位運(yùn)算

（假設(shè)那倆不相等的數(shù)為a、b）

Step 1.先將所有數(shù)字異或在一起，得到一個(gè)非0的值ret。

為什么ret一定非0呢？因?yàn)橹挥挟?dāng)所有數(shù)字都是成對(duì)相同的出現(xiàn)時(shí)，ret才會(huì)為0，而這里明確了有兩個(gè)不相等的數(shù)字。

因?yàn)橄嗟鹊臄?shù)異或 會(huì)抵消為0，所以這個(gè)ret就是a和b異或的值。

Step 2.假設(shè)得到的ret是101000，那為1的比特位 就是一道“分水嶺”，因?yàn)檫@個(gè)比特位上，一定是0和1異或在一起，才會(huì)得到1。

所以，我們可以找到ret中最低位的那個(gè)1，這個(gè)比特位把數(shù)組元素分為兩大陣營(yíng)：組A. 此比特位為0 ，組B. 此比特位為1。

Step 3. 組A內(nèi)的所有元素異或在一起，得到a；組B內(nèi)的所有元素異或在一起，得到b。

class Solution {
public:
 ?  vector<int> singleNumber(vector<int>& nums) {
 ? ? ?  int ret=0;
 ? ? ?  for(int e:nums){
 ? ? ? ? ?  ret^=e;
 ? ? ?  }
 ? ? ?  //找到為1的最低比特位
 ? ? ?  int i=0;
 ? ? ?  for(i=0;i<32;i++){
 ? ? ? ? ?  if((ret>>i)&1==1){
 ? ? ? ? ? ? ?  break;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ?  //分組
 ? ? ?  int group1_ret=0,group2_ret=0;
 ? ? ?  for(int e:nums){
 ? ? ? ? ?  if((e>>i)&1==1){ ? //該比特位為1的為group1
 ? ? ? ? ? ? ?  group1_ret^=e;
 ? ? ? ? ?  }
 ? ? ? ? ?  else{ ? ? ? ? ? //該比特位為1的為group2
 ? ? ? ? ? ? ?  group2_ret^=e;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ?  return {group1_ret,group2_ret}; ?
 ?  }
};

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

力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。

示例 1：

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

輸入：digits = ""
輸出：[]

示例 3：

輸入：digits = "2"
輸出：["a","b","c"]

思路

假設(shè)digits="23"，我們把2、3視為“一層”：

遍歷每一層，用n次遞歸的方式。

遍歷一層中的每一個(gè)元素，用范圍for。

class Solution {
public:
 ?  string num_to_str[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
?
 ?  void combine_letter(string digits,int di,string unit_ret,vector<string>& ret){
 ? ? ?  if(di==digits.size()){
 ? ? ? ? ?  ret.push_back(unit_ret);  //每一層訪問(wèn)完畢，得出一個(gè)unit_ret ?
 ? ? ? ? ?  return; ? ? ? ? 
 ? ? ?  }
 ? ? ?  int n=digits[di]-'0';
 ? ? ?  string str=num_to_str[n];
 ? ? ?  for(auto c:str){
 ? ? ? ? ?  combine_letter(digits,di+1,unit_ret+c,ret); ? //訪問(wèn)下一層
 ? ? ?  }
 ?  }
 ?  vector<string> letterCombinations(string digits) {
 ? ? ?  vector<string> ret;
 ? ? ?  string unit_ret;
 ? ? ?  if(digits==""){ ? //先考慮特殊情況
 ? ? ? ? ?  return ret;
 ? ? ?  }
 ? ? ? ?
 ? ? ?  combine_letter(digits,0,unit_ret,ret);
 ? ? ?  return ret; ? 
 ?  }
};

?

注意：1.要將數(shù)組num_to_str設(shè)為類域里的全局變量，這樣函數(shù)combine_letter就能直接訪問(wèn)了。

我一開(kāi)始把數(shù)組num_to_str寫在函數(shù)letterCombinations里，并用static修飾，使之成為靜態(tài)的局部變量。

然而，我弄混了，靜態(tài)的局部變量并不會(huì)改變它的作用域，只是使它的生命周期變長(zhǎng)了。

static局部變量出作用域不會(huì)被銷毀，但是別的函數(shù)是沒(méi)法訪問(wèn)到它的，它的作用域不變。

正確的做法是寫在letterCombinations外，使之稱為（類域里的）全局變量。

失敗記錄

雖然我知道，能用遞歸寫的循環(huán)也能寫，但這道題我還是不會(huì)循環(huán)的寫法，花了好多時(shí)間……

用遞歸的好處是能把復(fù)雜的大事 轉(zhuǎn)化成 好解決的小事。

第一次沒(méi)寫出來(lái)，我就去看題解。結(jié)果遞歸那一塊老是不懂，好暈。這時(shí)，最好的辦法是，打開(kāi)IDE，把代碼拷進(jìn)去，自己調(diào)試時(shí)走一遍代碼，就能理解透了：

現(xiàn)在我們來(lái)梳理下這個(gè)遞歸：

??一開(kāi)始錯(cuò)誤的認(rèn)知：（假設(shè)digits==“23”）：

我以為，先是找到2對(duì)應(yīng)的a，給a開(kāi)個(gè)棧幀，在此棧幀里找到3對(duì)應(yīng)的d，給d開(kāi)棧幀，然后再開(kāi)新棧幀；最后，新棧幀、d的棧幀、a的棧幀逐一銷毀。

再開(kāi)b的棧幀……

??正確的認(rèn)知：

而實(shí)際上，開(kāi)新棧幀的因素是di。di==0時(shí)，開(kāi)棧幀1號(hào)；在棧幀1號(hào)里，di ==1，開(kāi)棧幀2號(hào)；在棧幀2號(hào)里，di ==2，開(kāi)棧幀3號(hào)。

然后，3號(hào)銷毀，而2號(hào)并不會(huì)隨之銷毀。2號(hào)棧幀里要完成對(duì)def三個(gè)字母的遍歷，所以，會(huì)開(kāi)3次棧幀3號(hào)。

當(dāng)def三個(gè)字母都完成啦遍歷，棧幀2號(hào)才會(huì)銷毀，此時(shí)回到棧幀1號(hào)。

棧幀1號(hào)同樣要完成abc三個(gè)字母的遍歷，才會(huì)銷毀。所以，一共開(kāi)3次棧幀2號(hào)，每個(gè)棧幀2號(hào)里又要開(kāi)3次棧幀3號(hào)，一共開(kāi)9次棧幀3號(hào)。

要注意的細(xì)節(jié)

??1.注意區(qū)分+和+= ！

+：用來(lái)計(jì)算兩個(gè)數(shù)值的和，計(jì)算結(jié)束后會(huì)產(chǎn)生一個(gè)新的值。

+=：用來(lái)計(jì)算兩個(gè)數(shù)值的和，計(jì)算結(jié)果會(huì)賦值給+=運(yùn)算符前的參數(shù)。

拿這里來(lái)舉例：

for(auto c:str){
 ?  combine_letter(digits,di+1,unit_ret+c,ret); ? 
}

寫法一：unit_ret+c的結(jié)果 作為新的unit_ret參數(shù)，傳給下一個(gè)調(diào)用的combine_letter函數(shù)，而實(shí)際上，unit_ret的值并未被改變。

如果寫成這樣，就錯(cuò)了：

for(auto c:str){
    unit_ret+=c; ? ? //寫法二
 ?  combine_letter(digits,di+1,unit_ret,ret); ? 
}

寫法二：unit_ret+c的結(jié)果會(huì)賦給unit_ret，拷貝unit_ret的值作為形參，傳給下一個(gè)調(diào)用的combine_letter函數(shù)。unit_ret的值被改變。

??2.unit_ret注意是傳值傳參！不能傳引用傳參。

void combine_letter(string digits,int di,string unit_ret,vector<string>& ret);

為什么不能傳引用傳參呢？

如果傳引用過(guò)去，那在這一步里，unit_ret每次加的c，都會(huì)保留下來(lái)。而如果傳值傳參，每個(gè)棧幀里的unit_ret都是拷貝出來(lái)的值，當(dāng)棧幀銷毀，拷貝的unit_ret也就銷毀了，而實(shí)際的unit_ret不受影響。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-738937.html

for(auto c:str){
    combine_letter(digits,di+1,unit_ret+c,ret); ? //訪問(wèn)下一層
}

到了這里，關(guān)于【vector題解】只出現(xiàn)一次的數(shù)字 | 電話號(hào)碼的數(shù)字組合的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！