STL-vector练习题

118. 杨辉三角

思路： 

杨辉三角有以下性质使我们要用到的： 

● 每行数字左右对称，由 1 开始逐渐变大再变小，并最终回到 1。

● 第 n 行（从 0 开始编号）的数字有 n+1 项，前 n 行共有 2n(n+1)个数。

● 每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第 n 行的第 i 个数等于第 n−1 行的第 i−1 个数和第 i 个数之和。

代码：

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv(numRows);// 二维数组for(int i = 0;i < numRows;i++){vv[i].resize(i+1,1);// 按行数缩减每一行个数，并全部赋值为1}for(int a = 2;a < numRows ;++a){for(int b = 1;b < a ;++b){ // 每个数是左上方和右上方之和vv[a][b] = vv[a-1][b] + vv[a-1][b-1];            }}return vv;}
};

260. 只出现一次的数字 III

思路：

1、相同数异或结果是0

假设数组 nums 中只出现一次的元素分别是 x1和 x2。如果把 nums 中的所有元素全部异或起来，得到结果 x，那么一定有：x = x1 ^ x2 。这是因为 nums 中出现两次的元素都会因为异或运算的性质 a ^ b ^ b = a 抵消掉，那么最终的结果就只剩下 x1和 x2的异或和。

2、区分两个单值数字到两个数组 

在异或操作中，只有当两个数字在某一位置上的二进制值不同，结果的该位置才会是1。因此，异或结果中为1的位表示了所有数字在该位上的差异。找到最后一个1的位，可以帮助我们区分数组中只出现一次的数字。通过最后一个1的位，我们可以将数组中的数字分成两组：一组在该位上为1，另一组在该位上为0。这两组数字在该位上的差异表明，至少有一个只出现一次的数字在该位上与其他数字不同。

3、找出异或值最后一个二进制为1的位置 

a & (-a) 可以获得a最低的非0位，但需要注意整形溢出，可以用unsigned int 类型接收。

▶ 例如： 

● a的二进制原码是 0000 1010，这里最低非0位是从右往左第2位。

● -a在二进制中的表示是补码形式，即先按位取反再加1，取反得 1111 0101(反码)，加1得 1111 0110(补码)。

● 原码(0000 1010) 与 补码(1111 0110) 做与运算(&)，得 0000 0010，即原码 0000 1010的LSB（最低有效位）

---

▶ 我们发现： 

● 原码最低非0位右边所有的0，经由取反后全部变为1，反码+1会导致这些1逐位发生进位并变为0，最终进位记到最低非0位

● 原最低非0位是1，取反后是0，进位到这一位0变成1，不再向左进位

● 原最低非0位左边的每一位经由取反后 和 原码 进行与运算必为0

4、处理这两个数组

对于提供的整数数组的其他数，相同的数在所找到的mask位置的二进制数肯定是相同的，所以会被分到同一个数组。分别对两个数组进行异或操作就能得到最终两个单值。

代码：

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {//取反操作就会在无符号整数的范围内进行,//对-2,147,483,648 这个最小值取反时，会超出了int类型能表示的范围unsigned int xornum = 0;// 全部异或，相同的数会被异或成0for (int n : nums) {xornum ^= n;}// mask掩码：找出异或值最后一个二进制为1的数字 (重要位置)int mask = xornum & (-xornum);// 使用 vector 来存储结果vector<int> res(2, 0); // 如果要用数组存储，最后返回值要写改成vector ：//int res[2] = {0, 0};...//return vector<int> {res[0],res[1]};for (int n : nums) {if ((n & mask) == 0) {// 重要位置的数字是0，放在数组中全部异或，会剩下一个单值res[0] ^= n;} else {// 重要位置的数字是1，放在数组中全部异或，会剩下另一个单值res[1] ^= n;}}return res;}
};

137. 只出现一次的数字 II

思路：

考虑数字的二进制形式，对于出现三次的数字，各二进制位出现的次数都是3的倍数。因此，统计所有数字的各二进制位中1的出现次数，并对3求余，结果为出现一次的数字。

方法：遍历统计

● 使用与运算，可获取二进制数字n的最右一位n1: n1 = n&i

● 配合右移操作，可获取n的所有为的值：n = n >> 1

● 建立一个32位的数组counts，通过以上方法可记录所有数字的各二进制位的 1 的出现次数

int[] counts = new int[32];
for(int i = 0; i < nums.length; i++) {for(int j = 0; j < 32; j++) {counts[j] += nums[i] & 1; // 更新第 j 位nums[i] >>= 1; // 第 j 位 --> 第 j + 1 位}
}

● 将counts各元素对3求余，成三出现的数字在%3操作后没有余数，则结果为“只出现一次的数字”的二进制位。

for(int i = 0; i < 32; i++) {counts[i] %= 3; // 得到 只出现一次的数字 的第 (31 - i) 位 
}

● 利用左移操作和或运算，可将counts数组中个二进制位的值恢复到数字res上。

for(int i = 0; i < counts.length; i++) {res <<= 1; // 左移 1 位res |= counts[31 - i]; // 恢复第 i 位的值到 res
}

代码：

class Solution {
public:int singleNumber(vector<int>& nums) {vector<int> counts(32,0);for(int n : nums){for(int j = 0;j < 32 ; j++){//n的最低位是0，那么n&1的结果是0//n的最低位是1，那么n&1的结果是1counts[j] += n & 1;//统计该位二进制数是1的个数//>>> 是一个无符号右移操作符，与有符号右移操作符 >> 不同的是，//无符号右移不考虑符号位，无论 num 是正数还是负数，左边空出的位都填充 0。n >>= 1;//从右向左依次取二进制数}}//成三出现的数字在%3操作后没有余数，只留下那个只出现一次的数字的二进制表示for(int i = 0;i < 32;i++){counts[i] %= 3;}int res = 0;for(int i = 0;i < 32;i++){//左移：最右边空出的位会被填充为0（无符号数）或保持符号位的值（有符号数）res <<= 1;res |= counts[31 - i];//或运算：比较的位中至少有一个为1，则结果位为1// 这里是31 - i，要注意二进制数存储的先后}return res;}
};

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

左右指针即可！

代码： 

class Solution {
public:int removeDuplicates(vector<int>& nums) {if(nums.size() == 0)return 0;int left = 1,right = 1;while(right < nums.size()){if(nums[right] != nums[right-1]){nums[left++] = nums[right];}++right;}return left;}
};

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

数组中出现次数超过一半的数字_牛客题霸_牛客网

思路：

用计数排序的思想，numbers数组的值与counts数组下标相同时对counts[ ]进行计数，最后将存储的计数与原数组长度的一半进行对比。

 注意这里创建新数组要开辟动态的，根据所给数组的最大值进行创建。

代码：

#include <algorithm>
class Solution {
public:int MoreThanHalfNum_Solution(vector<int>& numbers) {if (numbers.empty()) return 0;//动态数组int maxnum = 0;for(int m : numbers){// 找到数组中的最大值maxnum = max(maxnum,m);}//初始化数组vector<int> counts(maxnum + 1,0);for(int i :numbers){// 计数counts[i]++;}for(int j = 0; j < counts.size();j++){if(counts[j] > numbers.size()/2){return j;}}return 0;}
};

17. 电话号码的字母组合（666）

思路： 

对于示例1，我们利用树的形式表示出来，但实现这个过程要用到递归的思想​​​​​​​。

维护一个字符串，表示已有的字母排列，该字符串初始为空。每次取电话号码的一位数字，从字符串数组中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面。（即一个一个取第一个号码对应的字母，并与另一个号码对应字母一个一个结合）然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字。

代码： 

class Solution {string Number[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; //深度优先遍历,递归实现,像树一样往深找void dfs(int i,int len, string digits,string& path,vector<string>& ans){if(i == len){//直到找到所有组合ans.push_back(path);//两两组合后尾插到动态数组return;}for(auto e : Number[digits[i] - '0'])//根据下标找到对应数字的字符串{path[i] = e;dfs(i+1,len,digits,path,ans);//注意这里是+1，不是++，用来维护一个字符串}}
public:vector<string> letterCombinations(string digits) {int len = digits.length();if(len == 0)return {};vector<string> ans;string path(len,0);dfs(0,len,digits,path,ans);return ans;}
};

 这一篇写了好久~  (ಥ﹏ಥ)  (ಥ﹏ಥ)  (ಥ﹏ಥ)