【vector题解】杨辉三角 | 删除有序数组中的重复项 | 只出现一次的数字Ⅱ

杨辉三角

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

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

示例 2:

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

知识点

这道题涉及的知识点有：1. vector创建二维数组。 2. 杨辉三角的表示法。

vector如何创建数组？

创建一维数组的方法：

vector<int> v(5);  //创建5个int，初始化成默认值0
​
vector<int> v(5,1);  //创建5个int，初始化成1
​
vector<int> v={1,2,3};  //创建3个int，分别是1，2，3

创建二维数组的方法：

vectorint>>(5);    //创建5行。 若想要定义列的大小，用resize()
​
vectorint>>(5,vector<int>(4));   //创建5行4列，初始化成默认值0
​
vectorint>>(5,vector<int>(4,9));  //创建5行4列，初始化成默认值9

这道题的二维数组，每行的大小都不一样的：

大小我们用resize()去调整。

至于杨辉三角的表示法，它的规律是：每行的开头和末尾为1，其他的数之间的关系 用找规律法可以得出：v[i] [j]=v[i-1] [j-1] + v[i-1] [j]

解答

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

删除有序数组中的重复项

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。

• 返回 k 。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

思路与实现

这道题我想到了两个思路。

思路一：

设两个迭代器：fast、slow。它们初始都指向nums的第一个元素。

fast一步一步地持续往前走，slow暂时待在原地。每当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;
    }
};

思路二：

把数组遍历一遍，遇到和上一个相同的就删除。

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条件，那它也没法自增，程序就陷入死循环了
                it=nums.erase(it);
                }
            }
            else{
                it++;
            }
        }
        int k=nums.size();
        return k;
    }
};

这样写的问题，还是出在erase那边。之前我强调过，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
            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;
    }
};

原来，是因为我循环里的erase操作，会导致size()被修改，sz的值失效了。

只出现一次的数字Ⅱ

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

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

示例 2：

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

思路

这道题乍一看，长得像单身狗问题，但实际并不能用异或的方法去做，两个相同的值异或在一起为0，而这里是三个相同的值。

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

这题其实可以借鉴刚刚那道“删除数组中的重复项”，把乱序的数组排序，使得大小相同的数字紧挨在一起，当一个数和前后都不相同，那这个数就只出现了一次。

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
            //先考虑第一个和最后一个，这俩位置比较尴尬，容易越界访问
            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;
    }
};

思路二：位运算

先撇开那个只出现一次的数字不看（我们就叫它A），其他数字都是三个三个出现的。

此时将十进制的数字用二进制的视角来看的话，32个比特位，1出现的次数一定是3的倍数。

而加进来A以后，我们将目光投到任意一个比特位上。如果A的这个比特位是0，那1的次数依然是3的倍数；如果是1，那这个次数模3等于1。

也就是说，我们可以通过1的次数 倒推出A的 其中一个比特位了：设1出现x次，x%3==0，那A的这一位就是0；x%3 ==1,这一位就是1。

A一共有32个比特位，复刻这个方法，可以推出A的每一个比特位，A的值自然也就出来了。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //一共32个比特位，每一位的0、1值我们都要获知
        int ret=0;
        for(int i=0;i<32;i++){
            //统计1出现的次数n
            int n=0;
            for(int num:nums){
                if((num>>i)&1==1){
                    n++;
                }
            }
            if(n%3==1){
                ret|=1<//注意：二进制的加法就用|
            }            //刚刚右移了i位，现在再左移回来
        }
        return ret;
    }
};

小结

1.“去重”问题往往可以考虑先排个序。

2.按位或 相当于是二进制中的加法。