楊輝三角

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

給定一個非負整數(shù) numRows，生成「楊輝三角」的前 numRows 行。

在「楊輝三角」中，每個數(shù)是它左上方和右上方的數(shù)的和。

示例 1:

輸入: numRows = 5
輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

輸入: numRows = 1
輸出: [[1]]

知識點

這道題涉及的知識點有：1. vector創(chuàng)建二維數(shù)組。 2. 楊輝三角的表示法。

vector如何創(chuàng)建數(shù)組？

創(chuàng)建一維數(shù)組的方法：

vector<int> v(5);  //創(chuàng)建5個int，初始化成默認值0
?
vector<int> v(5,1);  //創(chuàng)建5個int，初始化成1
?
vector<int> v={1,2,3};  //創(chuàng)建3個int，分別是1，2，3

創(chuàng)建二維數(shù)組的方法：

vector<vector<int>>(5); ?  //創(chuàng)建5行。 若想要定義列的大小，用resize()
?
vector<vector<int>>(5,vector<int>(4)); ? //創(chuàng)建5行4列，初始化成默認值0
?
vector<vector<int>>(5,vector<int>(4,9));  //創(chuàng)建5行4列，初始化成默認值9

這道題的二維數(shù)組，每行的大小都不一樣的：

大小我們用resize()去調(diào)整。

至于楊輝三角的表示法，它的規(guī)律是：每行的開頭和末尾為1，其他的數(shù)之間的關(guān)系 用找規(guī)律法可以得出：v[i] [j]=v[i-1] [j-1] + v[i-1] [j]

解答

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> v(numRows); for(int i=0;i<numRows;i++){v[i].resize(i+1);v[i][0]=v[i][i]=1;for(int j=1;j<i;j++){v[i][j]=v[i-1][j-1]+v[i-1][j];}}return v;}
};

刪除有序數(shù)組中的重復(fù)項

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

給你一個 非嚴格遞增排列 的數(shù)組 nums ，請你?原地 刪除重復(fù)出現(xiàn)的元素，使每個元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度。元素的 相對順序 應(yīng)該保持 一致 。然后返回 nums 中唯一元素的個數(shù)。

考慮 nums 的唯一元素的數(shù)量為 k ，你需要做以下事情確保你的題解可以被通過：

• 更改數(shù)組 nums ，使 nums 的前 k 個元素包含唯一元素，并按照它們最初在 nums 中出現(xiàn)的順序排列。nums 的其余元素與 nums 的大小不重要。

• 返回 k 。

示例 1：

輸入：nums = [1,1,2]
輸出：2, nums = [1,2,_]
解釋：函數(shù)應(yīng)該返回新的長度 2 ，并且原數(shù)組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數(shù)組中超出新長度后面的元素。

示例 2：

輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數(shù)應(yīng)該返回新的長度 5 ， 并且原數(shù)組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 。不需要考慮數(shù)組中超出新長度后面的元素。

思路與實現(xiàn)

這道題我想到了兩個思路。

思路一：

設(shè)兩個迭代器：fast、slow。它們初始都指向nums的第一個元素。

fast一步一步地持續(xù)往前走，slow暫時待在原地。每當(dāng)fast指向的元素和slow指向的不一樣，就讓slow加加，把fast的值賦給slow。

class Solution {
public:int removeDuplicates(vector<int>& nums) {vector<int>::iterator fast=nums.begin(),slow=nums.begin();while(fast!=nums.end()){if(*fast!=*slow){slow++;*slow=*fast;}fast++;}int k=slow-nums.begin()+1;nums.resize(k);return k;}
};

思路二：

把數(shù)組遍歷一遍，遇到和上一個相同的就刪除。

class Solution {
public:int removeDuplicates(vector<int>& nums) {vector<int>::iterator it=nums.begin();while(it!=nums.end()){if(it+1!=nums.end()){ ? //小心越界，加個判斷if(*it==*(it+1)){it=nums.erase(it);}else{it++;}}else{it++;}}int k=nums.size();return k;}
};

這個思路二挺容易寫錯的，看看我之前的錯誤寫法：

class Solution {
public:int removeDuplicates(vector<int>& nums) {vector<int>::iterator it=nums.begin();while(it!=nums.end()){if(it+1!=nums.end()){if(*it==*(it+1)){ ? //如果it沒走這里的if條件，那它也沒法自增，程序就陷入死循環(huán)了it=nums.erase(it);}}else{it++;}}int k=nums.size();return k;}
};

這樣寫的問題，還是出在erase那邊。之前我強調(diào)過，erase因為會引起迭代器失效，所以寫法非常講究。

正確的erase寫法：

要用if else語句，并且要用迭代器去承接erase的返回值。

而這里，我只寫了if，漏寫了else。在else里，it要加加。

錯誤記錄

這樣寫，為什么報錯呢？

class Solution {
public:int removeDuplicates(vector<int>& nums) {int sz=nums.size();int i=0;while(i<sz){if(i>0){if(nums[i]==nums[i-1]){vector<int>::iterator pos=nums.begin()+i;pos=nums.erase(pos); ? //這里要考慮迭代器失效嗎？}else{i++;}}else{i++;} ? }int k=nums.size();return k;}
};

原來，是因為我循環(huán)里的erase操作，會導(dǎo)致size()被修改，sz的值失效了。

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

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

給你一個整數(shù)數(shù)組 nums ，除某個元素僅出現(xiàn) 一次 外，其余每個元素都恰出現(xiàn) 三次 。請你找出并返回那個只出現(xiàn)了一次的元素。

你必須設(shè)計并實現(xiàn)線性時間復(fù)雜度的算法且使用常數(shù)級空間來解決此問題。

示例 1：

輸入：nums = [2,2,3,2]
輸出：3

示例 2：

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

思路

這道題乍一看，長得像單身狗問題，但實際并不能用異或的方法去做，兩個相同的值異或在一起為0，而這里是三個相同的值。

思路一：先排序，再前后比較

這題其實可以借鑒剛剛那道“刪除數(shù)組中的重復(fù)項”，把亂序的數(shù)組排序，使得大小相同的數(shù)字緊挨在一起，當(dāng)一個數(shù)和前后都不相同，那這個數(shù)就只出現(xiàn)了一次。

class Solution {
public:int singleNumber(vector<int>& nums) {int sz=nums.size();//首先要考慮特殊情況if(sz==1){return nums[0];}sort(nums.begin(),nums.end());for(int i=0;i<sz;i++){//先考慮第一個和最后一個，這倆位置比較尷尬，容易越界訪問if(i==0&&nums[i]!=nums[i+1]){return nums[i];}else if(i==sz-1&&nums[i]!=nums[i-1]){return nums[i];}else if(nums[i]!=nums[i+1]&&nums[i]!=nums[i-1]){return nums[i];}}return 0;}
};

思路二：位運算

先撇開那個只出現(xiàn)一次的數(shù)字不看（我們就叫它A），其他數(shù)字都是三個三個出現(xiàn)的。

此時將十進制的數(shù)字用二進制的視角來看的話，32個比特位，1出現(xiàn)的次數(shù)一定是3的倍數(shù)。

而加進來A以后，我們將目光投到任意一個比特位上。如果A的這個比特位是0，那1的次數(shù)依然是3的倍數(shù)；如果是1，那這個次數(shù)模3等于1。

也就是說，我們可以通過1的次數(shù) 倒推出A的 其中一個比特位了：設(shè)1出現(xiàn)x次，x%3==0，那A的這一位就是0；x%3 ==1,這一位就是1。

A一共有32個比特位，復(fù)刻這個方法，可以推出A的每一個比特位，A的值自然也就出來了。

class Solution {
public:int singleNumber(vector<int>& nums) {//一共32個比特位，每一位的0、1值我們都要獲知int ret=0;for(int i=0;i<32;i++){//統(tǒng)計1出現(xiàn)的次數(shù)nint n=0;for(int num:nums){if((num>>i)&1==1){n++;}}if(n%3==1){ret|=1<<i;   //注意：二進制的加法就用|}            //剛剛右移了i位，現(xiàn)在再左移回來}return ret;}
};

小結(jié)

1.“去重”問題往往可以考慮先排個序。

2.按位或 相當(dāng)于是二進制中的加法。