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;
// 全部异或，相同的数会被异或成0
for (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的结果是1
counts[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;
}
};这一篇写了好久~ (ಥ﹏ಥ) (ಥ﹏ಥ) (ಥ﹏ಥ)