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; }};这一篇写了好久~ (ಥ﹏ಥ) (ಥ﹏ಥ) (ಥ﹏ಥ)