【C++】7道经典面试题带你玩转vector

2024-08-06 09:00:20 浏览数 (3)

一.只出现一次的数字

题目链接:

136. 只出现一次的数字

https://leetcode.cn/problems/single-number/

题目描述:

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

题目详情:

解题思路:

将数组中的所有元素相异或,异或的结果就是要求的解.

对于这种题目的异或解法详细原理原理我在之前有写过C语言版本,下图是文章中节选出的部分推理过程,感兴趣的朋友可以移步: 【C语言】找单身狗问题

解题代码:

代码语言：javascript复制
//数组元素异或法
class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret=0;
        for(auto e:nums)
        {
            ret^=e;
        }
        return ret;
    }
};

提交运行:

二.杨辉三角

题目链接:

118. 杨辉三角

icon-default.png?t=N7T8icon-default.png?t=N7T8

https://leetcode.cn/problems/pascals-triangle/

题目描述:

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。

题目详情:

解题思路:

创建一个vector<vector<int>>的对象集合,集合中的元素是vector<int>.实际相当于一个二维数组,结构图示如下:

然后我们按照每一行的杨辉三角规律,将第一个和最后一个数置为1,其余数置为左上数加右上数的和即可.详细过程见代码注释.

解题代码:

代码语言：javascript复制
class Solution 
{
public:
    vector<vector<int>> generate(int numRows) 
    {
        vector<vector<int>> vv;
        vv.resize(numRows);//numRows行,vv<int>就有多少个v<int>元素

        for(int i=0; i < numRows; i  )
        {
            vv[i].resize(i 1,0);//第n行就有n个int, 1因为下标从0开始,行数从1开始

            for(int j=0; j < vv[i].size(); j  )
            {
                //如果,不是每一行的第一个数字也不是最后一个数字,就等于左上加右上数字的和
                if(j > 0 && j != i)
                {
                    vv[i][j] = vv[i-1][j-1]   vv[i-1][j];
                }
                else  //否则,就是1
                {
                    vv[i][j] = 1;
                }
            }
        }
        return vv;
    }
};

提交运行:

三.删除有序数组中的重复项

题目链接:

26. 删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

题目描述:

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

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

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

判题标准:

系统会用下面的代码来测试你的题解:

代码语言：javascript复制
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i  ) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

题目详情:

解题思路:

解题思路见下图:

解题代码:

代码语言：javascript复制
class Solution 
{
public:
    int removeDuplicates(vector<int>& nums) 
    {
        //因为vector的erase接口接收的参数类型是迭代器,
        //所以我们创建一个nums的初始迭代器,方便后续传参
        vector<int>::iterator it = nums.begin();

        //用i循环遍历数组
        for(int i = 0; i < nums.size()-1; i  )
        {
            //如果i指向的数据和i 1相等,那么我们就删除数据i
            while(nums[i] == nums[i 1])
            {       
                nums.erase(it   i); 
                
                //如果删除后数组只剩下一个元素或i已经是数组最后一个元素
                //终止循环
                if(nums.size() == 1 || i >= nums.size()-1)
                {
                    break;
                }
            }
        }

        //数组的元素个数即为数组中唯一元素的个数
        return nums.size();
    }
};

提交运行:

四.只出现一次的数字 II

题目链接:

137. 只出现一次的数字 II

https://leetcode.cn/problems/single-number-ii/

题目描述:

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

题目详情:

解题思路:

首先,我们可以观察一下题目的特征:

然后我们需要了解一下整型数据在内存中的存储,详细的内容可以移步这篇博客: 【C语言】整形数据和浮点型数据在内存中的存储

然后我们举一组数据的例子来帮助大家理解一下这个解法的过程:

还有一点需要注意的是,如果结果为负数,我们要按补码的方式计算十进制数:

解题代码:

代码语言：javascript复制
class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        vector<int> v;
        v.resize(32,0);

        for(int i=0 ; i<nums.size() ; i  )
        {
            for(int j=0 ; j<32 ; j  )
            {
                //将num[i]的二进制位的数字累加到v中
                if(((nums[i] >> j) & 1) == 1)
                {
                   v[31-j]  ;
                }
            }
        }
        //消除所有位上呈3次出现的1
        for(int i=0;i<v.size();i  )
        {
            v[i]%=3;
        }
        
        //留下的数据就是没有出现过三次的,而是只出现过一次的
        int ret=0;
        //负数的话按补码的方式计算原码的十进制数,即先取反再 1;
        if(v[0]==1)
        {
            for(int i=1;i<v.size();i  )
            {
                if(v[i]==0)//相反的位才是有效数据
                {
                     ret  = pow(2 , (31 - i));
                }
            }
            return -ret-1;
        }
        else//不是负数,按正常原码计算十进制数
        {
            for(int i=1;i<v.size();i  )
            {
                if(v[i]!=0)
                {
                     ret  = pow(2 , (31 - i));
                }
            }
            return ret;
        }
    }
};

提交运行:

五.只出现一次的数字 III

题目链接:

260. 只出现一次的数字 III

https://leetcode.cn/problems/single-number-iii/

题目描述:

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

题目详情:

解题思路:

这个问题的解题思路推导在我之前的一个博客里有详细的解释,感兴趣的朋友可以移步:【C语言】找单身狗问题 在这里我简单截取一些博文中的解释,方便大家理解:

由上述推导可得,该题目解题步骤如下:

  1. 将数组所有元素相异或
  2. 找到可以区分两个只出现一次的数的二进制位
  3. 根据这个不同的二进制将数据分为两组分别异或
  4. 两组异或的结果就是两个只出现了一次的数字

解题代码:

代码语言：javascript复制
class Solution 
{
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        //求出两个只出现一次的元素相异或的结果
        int test=0;
        for(int i=0 ; i<nums.size() ; i  )
        {
            test^=nums[i];
        }

        //根据异或结果求出它们哪个二进制位不相等
        int pos=0;
        for(int i=0 ; i<32 ; i  )
        {
            //检查将test右移1位后末位是否为1,如果是1,记录下右移的位数
            if(((test >> i) & 1) == 1)
            {
                pos=i;
                break;
            }
        }

        //以test右移pos位后末位是1还是0为条件,将nums数组元素分为两组,分别相异或
        int ret1=0;
        int ret2=0;
        for(int i=0 ; i<nums.size() ; i  )
        {
            if(((nums[i] >> pos) & 1) == 1)
            {
                ret1^=nums[i];
            }
            else
            {
                ret2^=nums[i];
            }
        }
        
        //分组相异或的结果,就是两个只出现一次的数字,将其通过vector返回
        vector<int> vRet;
        vRet.push_back(ret1);
        vRet.push_back(ret2);

        return vRet;
    }
};

对于上述代码中的这行代码,很多朋友可能不太理解,我在这里详细解释一下:

代码语言：javascript复制
if(((test >> i) & 1) == 1)

代码解析

  1. 位运算符 >>：
    • test >> i：这个操作是将整数 test 的二进制表示右移 i 位。
    • 右移操作会将整数的所有位向右移动 i 位，移动出来的位会被丢弃，左侧将用符号位填充（即对于正数填充0，对于负数填充1）。

    例如，对于 test = 10（即二进制 1010）和 i = 1，则： 10 (二进制 1010) 右移 1 位 -> 0101 (即 5)

  2. 位与运算符 &：
    • (test >> i) & 1：这个操作会对右移后的结果和 1 进行按位与操作。
    • 1 的二进制表示是 ...0001，所以这个操作的目的是检查右移后的结果的最低位（也就是现在的第 i 位）是否为 1。

    继续上面的例子： 右移后结果：0101 (5) 0101 & 0001 = 0001 (保留最低位，结果为 1)

  3. 判断是否等于 1：
    • ((test >> i) & 1) == 1：最终的判断是检查上面的操作结果是否等于 1。
    • 如果结果是 1，则说明原始的 test 在第 i 位上是 1；如果结果是 0，则说明第 i 位上是 0。

提交运行:

六.数组中出现次数超过一半的数字

题目链接:

JZ39 数组中出现次数超过一半的数字

https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&&tqId=11181&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

题目描述:

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。 数据范围：n≤50000，数组中元素的值 0≤val≤10000 要求：空间复杂度：O(1)，时间复杂度 O(n)

题目详情:

解题思路:

利用哈希的思想,创建一个数据范围内大小的vector,用于 统计各个数据出现的次数.然后遍历数组numbers,每遍历一个数据就给其对应哈希映射的对应数据 1,然后 判断其映射数据是否大于numbers数组长度的一半,如果大于,则该数据即为待求数据.解题过程图示如下:

解题代码:

代码语言：javascript复制
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) 
    {
        // write code here

        vector<int> ret;
        ret.resize(10001, 0);
        for(int i=0;i<numbers.size();i  )
        {
            ret[numbers[i]]  ;
            if(ret[numbers[i]]>(numbers.size()/2))
            {
                return numbers[i];
            }
        }
        return 0;
    }
};

提交运行:

七.电话号码的字母组合

题目链接:

17. 电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

题目描述:

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

题目详情:

解题思路:

该题我们首先要创建一个字符串数组来将数字和字符的映射关系存储起来,方便我们后续取用数字对应的映射关系:

代码语言：javascript复制
string strA[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

其次我们通过画图可知,digits字符串有几个数字,我们的组合层数就会有几层,而每一层和下一层的组合逻辑都是相似的,所以我们可以尝试使用递归来将每一层组合出的字符组合在一起,这样直到递归到最后一层,就可以得到这次组合的结果,详细的过程见解题代码注释:

解题代码:

代码语言：javascript复制
//多路递归
class Solution 
{
    //构造字符串映射关系
    string strA[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    //            题目的digits            递归过程中的记录组合变量
    void Combine(string digits,int level,string combineStr,vector<string>& vs)
    //                         表示传到第level层了    最终要把得到的字符串存进vector里
    {
        //首先先确定自己在第几层,同时设定递归的递出条件
        if(level == digits.size())
        {
            vs.push_back(combineStr);
            return ;
        }

        //num代表取strA数组的哪个映射
        int num = digits[level] - '0';
        //取映射字符串
        string str = strA[num];

        //依次取字符串里的字符
        for(int i=0 ; i<str.size() ; i  )
        {
            Combine(digits,level 1,combineStr   str[i],vs);
        }
    }

    vector<string> letterCombinations(string digits) 
    {
        vector<string> vs;
        if(digits.size()==0)
        {
            return vs;
        }
        Combine(digits,0,"",vs);

        return vs;
    }
};

提交运行:

结语

希望通过上面的题目能使大家对vector对象集合的理解以及运用能够更上一层楼,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

c++ vector 数据 数组 字符串

0 人点赞