楊輝三角

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

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

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

示例 1:

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

示例 2:

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

知識(shí)點(diǎn)

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

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

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

vector<int> v(5);  //創(chuàng)建5個(gè)int，初始化成默認(rèn)值0
?
vector<int> v(5,1);  //創(chuàng)建5個(gè)int，初始化成1
?
vector<int> v={1,2,3};  //創(chuàng)建3個(gè)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列，初始化成默認(rèn)值0
?
vector<vector<int>>(5,vector<int>(4,9));  //創(chuàng)建5行4列，初始化成默認(rèn)值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ù)項(xiàng)

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

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

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

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

• 返回 k 。

示例 1：

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

示例 2：

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

思路與實(shí)現(xiàn)

這道題我想到了兩個(gè)思路。

思路一：

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

fast一步一步地持續(xù)往前走，slow暫時(shí)待在原地。每當(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ù)組遍歷一遍，遇到和上一個(gè)相同的就刪除。

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

這個(gè)思路二挺容易寫錯(cuò)的，看看我之前的錯(cuò)誤寫法：

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沒(méi)走這里的if條件，那它也沒(méi)法自增，程序就陷入死循環(huán)了it=nums.erase(it);}}else{it++;}}int k=nums.size();return k;}
};

這樣寫的問(wèn)題，還是出在erase那邊。之前我強(qiáng)調(diào)過(guò)，erase因?yàn)闀?huì)引起迭代器失效，所以寫法非常講究。

正確的erase寫法：

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

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

錯(cuò)誤記錄

這樣寫，為什么報(bào)錯(cuò)呢？

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

原來(lái)，是因?yàn)槲已h(huán)里的erase操作，會(huì)導(dǎo)致size()被修改，sz的值失效了。

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

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

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

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

示例 1：

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

示例 2：

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

思路

這道題乍一看，長(zhǎng)得像單身狗問(wèn)題，但實(shí)際并不能用異或的方法去做，兩個(gè)相同的值異或在一起為0，而這里是三個(gè)相同的值。

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

這題其實(shí)可以借鑒剛剛那道“刪除數(shù)組中的重復(fù)項(xiàng)”，把亂序的數(shù)組排序，使得大小相同的數(shù)字緊挨在一起，當(dāng)一個(gè)數(shù)和前后都不相同，那這個(gè)數(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++){//先考慮第一個(gè)和最后一個(gè)，這倆位置比較尷尬，容易越界訪問(wèn)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;}
};

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

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

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

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

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

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

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

小結(jié)

1.“去重”問(wèn)題往往可以考慮先排個(gè)序。

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