简单题需要get的点：
0、通识技巧：
A、每次循环都只进行一次操作，要么是删除，要么是赋值；
B、每次判断一个结点的值的时候，先判断该结点是否存在；

     // 删除一个链表中的指定的值的结点。
     ListNode* removeElements(ListNode* head, int val) {
           // 最难的是判断：为空和为1的情况
           if(!head) return head;
           while(head&&head->val==val) head=head->next;   // 把头节点中需要删除的结点给去掉
           ListNode* begin = head;
           while(head){
                if(head->next&&head->next->val==val) head->next=head->next->next;  
                else head = head->next;
           }
           return begin;
      }

C、任何逻辑，都有因果关系，所以在进行逻辑判断的时候，一定是根据某个逻辑来进行改变

1、字符串类：
A、【字符型可以看成是数字型，一样可以用来 "异或"；最开始指向NULL即可；（我不知道这样写好不好，如果不好，就把tmp初始化为字符串第一个字符）】

       char findTheDifference(string s, string t) {
            char tmp=NULL;      // 可以初始化字符串的第一个字母
            for(auto c:s) tmp=tmp^c;
            for(auto c:t) tmp=tmp^c;
            return tmp;
        }

B、【字符串相关的一个很好的数据结构是 字符数组，通过用字符的相对位置进行字符压缩！这个方法在这里可能不是唯一的，而是可以用标准的unordered_map来进行统计】
给一个字符串，找到在字符串中第一个没有重复出现的字符，并返回它的下标，如果不存在，就返回-1；
（这里可以用 record，也可以 用 unordered_map 来做，因为只是做个统计，然后再遍历一遍字符串，找出那个统计次数为1的值）
（该题目做两个字符串的异序判断也是很好用的，比一个unordered_map效率都高很多）

int firstUniqChar(string s) {
     vector<int> record(26);
     for(auto c:s){
            record[c-'a']++;
     }
     for(int i=0;i<s.size();i++){
            if(record[s[i]-'a']==1) return i;
     }
     return -1;
       }

C：字符串模拟数字操作--二进制数相加：
tip：这里有几个很重要的点：
1）因为是字符串模拟数字，所以每一个单独的字符转化到数字的时候用-'0'的方式完成；同理，在给结果串赋值的时候，也需要加上'0'：

class Solution {
public:
    string addBinary(string a, string b) {
        // 将两个字符串进行逆转
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        // 设置进位符和总长度和结果串
        int flag = 0;
        int lenth = 0;
        string res = "";
        if(a.size()>b.size()){
            lenth = a.size();
            res = a; 
        }else{
            lenth = b.size();
            res = b;             
        }
        // 对字符串中每一个字符逐次进行相加比较
        for(int i=0;i<lenth;i++){
            int int_a = i<a.size()?a[i]-'0':0;
            int int_b = i<b.size()?b[i]-'0':0;
            if((int_a+int_b+flag)>1){
                if(int_a+int_b+flag==2) res[i]='0';
                if(int_a+int_b+flag==3) res[i]='1';
                flag=1;
            }else{
                res[i]=int_a+int_b+flag+'0';  
                flag=0;
            } 
        }
        if(flag==1) res=res+"1";
        reverse(res.begin(),res.end());
        return res;
    }
};

2、数值类（逻辑题和选择题都有可能出）：
A：有些 x%4==0 的计算可以转换为位的运算：
x&3==0（需要注意的是，单目运算符的优先级很低，所以需要加括号），总的而言，效率还是提高了很多。（Nim game)

B：与数值运算很相关的一系列操作：

     （1）int tmp = num & (~num+1)   // 找到 num 中最右边的那个1所对应的数值：例如：num: 11000；tmp: 1000 
     （2）int tmp = num - (~num+1)    //  消掉 num 中最右边的那个1后所对应的数值：例如：num: 11000；tmp: 10000

C：给出n!，然后算出n!的结果中有多少个0，这个题不仅是在逻辑题中出现过，在编程题中也出现过：
（一个阶乘里面 2肯定比5多， 所以只要5，一定能配成10；关键在于有几个5）

      int trailingZeroes(int n) {
           int res=0;
           while(n>0){
               res+=n/5;
               n=n/5;
           }
           return res;
      }

比如125！由下面的部分组成：(1+2+3+4+5+......+25) * 5
除去5之后，为25，25又由下面的部分组成：(1+2+3+4+5) * 5
除去5之后，为5，5又由下面的部分组成：1 * 5
所以最后：25 + 5 +1 =31

D：toupper() 转换为大写；tolower() 转换为小写；
E：素数，这种题虽然没有在任何一个平台上写过，但是我依然认为是很重要的：
这里需要多了解些素数的性质：
1）素数除了2以外，永远是奇数，所以只需要删掉奇数中为合数的部分。所以统计的时候是从3开始；
2）对于每一个符合素数的值t外，t*3，t*5，t*7，t*9......都是合数。
3）但是对于t而言，t*(3,5....t) 之前在 t=3,t=5,t=7 的时候，以及判断过了，所以，直接从 t*t 开始。

class Solution {
public:
    int countPrimes(int n) {
        if(n<3) return 0;
        // 2是素数中唯一的偶数，而其他的数都是奇数.
        // 如果i=3,那么 3*3, 3*(3+2), 3*(3+4)......
        // 如果i=5,那么 5*5, 5*(5+2), 5*(5+4)......【注意，5*3已经被】
        // 而素数的基本判断方法是除了自己和1以外，不能被任何数整除。
        // 感觉这也是一个动态规划统计过程。
        vector<int> vec(n,0);
        for(int i=3;i*i<n;i=i+2){
            if(vec[i]==0){
                for(int j=i*i;j<n;j=j+2*i){
                    vec[j]=1;
                }
            }
        }
        int res=1;
        for(int i=3;i<n;i=i+2){
            if(vec[i]==0) res++;
        }
        return res;
    }
};

F：数字和数字型字符串
这个轮子在很多地方都出现过，特别在一些比较复杂的题型里面：

Reverse Integer：
（一个正常的数字只需要不断通过%10 和 /10 来得到所有的数，而替换的数只需要*10+i）
    int reverse(int x) {
        long left=0; //用long 的好处在于，不怕真的越界了
        int right = x;
        while(right){
            left = left*10 + right%10;
            right= right/10;
        }
        if(left>0) return left>INT_MAX?0:left; 
        else if(left<0) return left<INT_MIN?0:left; 
        else return 0;
    }

3、二叉树相关：
A：在写深搜的时候，原函数不动，而是将其他函数作为主要的递归函数，并把中间状态值传进去。直到最后的临界条件下，进行判断。（根结点的判断方式：左&右两个子结点为空）

    int res;
    void help(TreeNode* root, int count){
 // 这里是找最大，如果是找最小，那么就需要直接剪枝，将大于全局最小值的数进行剪枝。
        if(!root->left&&!root->right){
            res = count>res?count:res;  
        } 
        if(root->left) help(root->left,count+1);
        if(root->right) help(root->right,count+1);
    }
    int maxDepth(TreeNode* root) {
        if(!root) return 0; // 对于指针，需要先判断是否为空。
        res=0;
        help(root,1);
        return res;
    }

B：平衡二叉树（AVL）：首先，平衡二叉树的定义就是左右两个子树的高度相差不超过1；如何判断是否是平衡二叉树，其实只要两个子树是平衡的，那以我为根节点的子树就是平衡的。

虽然是做判断树的平衡性，但是肯定还是深搜，而用树的高度作为返回值是合适的，如果返回值是正数，说明了两点：A:树高 ; B:该树是平衡的；如果返回值是负数，就不用说了，肯定是不平衡的，只要有一个小子树是不平衡的，那么整棵树都不是平衡的，基于此，写出下面的迭代算法：

写这种题目的时候，入口做的事情不能太多，只是做一个准备工作，比如，赋初值，比如设置迭代的状态变量，最后根据迭代的状态变量进行判断。

基本上可以这么想：叶子结点和非叶子结点，非叶子结点有两种可能：有左右子节点；只有左或右结点！
也就是说，要保证，每一步做了后，都可以判断，并影响最终的效率。

class Solution {
public:
    int help(TreeNode* root){
        int a=0,b=0;
        if(!root->left&&!root->right) return 1;  // 最好的方式是不需要深搜了，直接判断！
        if(root->left) a=help(root->left);  // 就算是暴利剪枝，也需要分别判断，在处理大数据集合的时候效果会好很多。
        if(a==-1) return -1;
        if(root->right) b=help(root->right); 
        if(b==-1) return -1;
        else if(abs(a-b)<=1) return max(a,b)+1; // 对深搜的结果进行返回，如果是动规的话，需要在这个地方对矩阵中
        else return -1;
    }

    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        if(help(root)!=-1) return true;
        else return false;
    }
};

4、数组类：
A：有道题很有意思，找出两个数组中交集的那部分的数字：时间：O(n) 空间：O(n)

关于 unordered_map 相关的：unordered_map<int,pair<int,int>> record;
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        if(nums1.size()==0||nums2.size()==0) return res;
        unordered_map<int ,int> vec;
        for(auto s:nums1) vec[s]++;
        for(auto s:nums2)       // 如果有库存的话，就直接放进入了。
if(vec[s]>=1){
res.push_back(s);
vec[s]--;
}
        return res;
    }
};

这里其实还有些需要注意的是，如果其中有一个的长度为0，那么就肯定没有交集了。

B：Sum系列
1) two_sum：两个数的和
在一个无序的数组里找到满足 target 的两个数的和：

最方便的方法是先排序(nlogn)，然后再两边夹逼来找到合适的数字(O(n))，但是总的时间复杂度为O(nlogn)；
而效率上最快的方法应该还是基于统计的，用unordered_map<int,int> 进行统计，因为查找效率为O(1)，所以每个元素最多遍历2遍，时间复杂度为O(n)

如果在已经排序的情况下：

      vector<int> twoSum(vector<int>& numbers, int target) {
          int left=0, right=numbers.size()-1;
          while(left<right){
              int rest = target - numbers[left];
              while(numbers[right]>rest) right--;
              if(numbers[right]==rest) return vector<int>{left+1,right+1};
              else left++;
          }
          return vector<int>();
      }

C：从一个已排序的数组中原地移除重复的元素

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0) return 0;
        // 用标记法将合适的数据放在合适的位置，然后返回合理的长度，最后，erase掉多余的数据
        int left=0;     // 标记应该放入元素的地方
        int i=0;
        for(;i<nums.size()-1;i++){
            while(i<nums.size()-1&&nums[i]==nums[i+1]) i++; 
            nums[left] = nums[i];
            left++;   
        }
        if(i==(nums.size()-1)) nums[left++] = nums[i];      // 将最后一个数放进去。
        nums.erase(nums.begin()+left,nums.end());
        return left;
    }
};

D：模式匹配类：

Given a pattern and a string str, find if str follows the same pattern.
Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

用空格间隔的字符串，拆分代码：

vector<string> vec;
string tmp="";
stringstream isstream(str);
while(isstream >> tmp) strvec.push_back(tmp);

注意：unordered_map 的变量是可以用 find 去进行查询的，当查询不到，是返回end()，同理，当查询到了，应该是返回对应的数值的迭代器。

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char,string> rec;
        unordered_map<string,char> rec2;
        // 拆分字符串
        vector<string> record;
        string tmp="";
        stringstream isstream(str);
        while(isstream >> tmp) record.push_back(tmp);
        // 模式匹配
        if(pattern.size()!=record.size()) return false;
        for(int i=0;i<pattern.size();i++){
            if(rec[pattern[i]]==""){
                if(rec2[record[i]]==NULL){
                    rec[pattern[i]]=record[i];
                    rec2[record[i]]=pattern[i];
                }else return false;
            }
            else{
                if(rec[pattern[i]]!=record[i]||rec2[record[i]]!=pattern[i]) return false;
            }
        }
        return true;
    }
};

E：给定数组的轴，然后按照这个轴进行旋转：
（这个题目变相地考过，这里可以是字符串，也可以是数组）
Rotate Array 这里有意思的是，这里
举例说明：[1,2,3,4,5,6,7] ，轴是3
首先，reverse 整个数组，变为：[7,6,5,4,3,2,1] 然后，reverse 前三个，再reverse 后四个

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k%=nums.size();
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

5、链表类（简单题一般都会出手写代码题）：
A：链表逆转的标准：判断首节点是否为空，然后判断：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return nullptr;
        ListNode* prev=nullptr; ListNode* next = nullptr;
        while(head!=nullptr){
            next = head->next;
            head->next= prev;
            prev = head;
            head = next;
        }
        return prev;
    }
};

B：合并两个链表：（合并两个排序的链表成一个排序的链表）用一个新的指针来穿针引线：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  // 新的指针
        ListNode* head = new ListNode(0);
        ListNode* tmp = head;
//  对两个指针链所共有的部分进行判断
        while(l1&&l2){
            if(l1->val<=l2->val){
                tmp->next = l1;
                l1=l1->next;
            }else{
                tmp->next = l2;
                l2=l2->next;
            }
            tmp=tmp->next;
        }
        if(l1 == nullptr) tmp->next = l2;
        else if(l2 == nullptr) tmp->next = l1;
        return head->next;
    }
};

C：链表操作之每一对链表结点相互交换：
（如果只是改变结点的值，那种不叫交换，应该是交换两个结点，只要涉及到链表的拆分，而且与前一个结点和后一个结点相关的话，就可以统一用下面的初始化：

   ListNode* next = nullptr;
   ListNode* prev = new ListNode(0);
   ListNode* res = prev;
---------------------------------------
    ListNode* swapPairs(ListNode* head) {
        ListNode* next = nullptr;
        ListNode* prev = new ListNode(0);
        ListNode* res = prev;
        while(head){
            if(head->next){
                next = head->next->next;
                prev->next =head->next;
                head->next->next = head;
                head->next = next;
                prev = head;
                head = next; 
            }else{
                if(!res->next) res->next = head;
                head = head->next;
            }
        }
        return res->next;
    }

D：先后指针：移除倒数第N个结点：
首先用一个指针，先走N步，然后，再用另一个指针指向头结点，两个指针同时走，后面的那个指针将会指向需要删除的那个结点的前一个结点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) return NULL;
        ListNode* before=head;
        ListNode* begin=head;
        while(n>0){
            before=before->next;
            n--;
        }
        while(before&&before->next){
            before= before->next;
            begin= begin->next;
        }
 // 通过对 before 的一个判断，来决定具体是删除当前结点，还是当前结点的下一个结点。
        if(!before){ // 如果 before为 nullptr, 那么说明要删除的是第一个节点
            ListNode* tmp = head;
            head=head->next;
            delete tmp;
        }else if(!before->next){ // 如果 before->next为 nullptr, 那么说明要删除的是后一个节点
            ListNode* tmp = begin->next;
            begin->next = begin->next->next;
            delete tmp;
        }
        return head;
    }
};

E：两个链表有交集，求交集的起点：
（最怕的是上下代码有黏带，最好的方式是每一次循环给变量赋一次值）

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA||!headB) return NULL;
        ListNode * head1 = headA;
        ListNode * head2 = headB;
        while(head1!=head2){
            if(head1==NULL) head1 = headB;
            else head1=head1->next;
            if(head2==NULL) head2 = headA;
            else head2=head2->next;
        }
        return head1;
    }
};

F：链表回文：
几个重要的轮子：
1）快慢指针
// 快指针的跳转分两种 A:落在最后一个真正的节点上；B：落在最后一个真正的节点的后面那个NULL上

        while(node1&&node1->next){
            node1=node1->next->next;
            node2=node2->next;
        }
        ListNode* mid=node2;
        if(node1) node2= node2->next;

2）链表逆转
// 找到了mid就是链表中间的指针，那么就有了中点了。

        node1 = head;
        ListNode* prev=NULL;
        ListNode* next=NULL;
        while(node1!=mid){
            next = node1->next;
            node1->next=prev;
            prev =node1;
            node1=next;
        }

当然，这两步可以合起来！
// 快慢指针+链表逆转

        ListNode* fast= head;
        ListNode* slow= head;
        ListNode* before =nullptr,*next=nullptr;
        //链表的逆转
        while(fast!=nullptr&&fast->next!=nullptr){
            fast=fast->next->next;
            next=slow->next;
            slow->next=before;
            before =slow;
            slow=next;
        }

G：一些小的建议：每次调一个指针的val之前先判断该指针是否存在：

   ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        while(head&&head->val==val) head=head->next;
        ListNode* begin = head;
        while(head){
            if(head->next&&head->next->val==val) head->next=head->next->next;  
            else head = head->next;
        }
        return begin;
    }

7、pow of index系列，就是给一个整数，来判断是否该数是 index 的指数，不准用循环或者递归：
首先，循环的方法是（对 index 取余，然后再除以 index 然后再取余）

bool isPowerOfThree(int n) {
    if(n<=0) return false;
    while(n>1){
         if(n%3==0) n=n/3;
         else return false;
    }
    return true;
}

非循环的方法是：（找到系统支持的范围内3的指数最大的值，然后判断它是否可以整除n，这个对于3的指数的求法是比较好的）

bool isPowerOfThree(int n) {
    if (n<=0) return false;
    int t = pow(3 , (int)( log(INT_MAX)/log(3)) );
    return (t%n == 0); 
}

特殊的，对于判断是否是2的指数的方法（因为2的倍数，也就意味着整个数的二进制位只有一个为1，所以通过 return !n&(n-1) ; 就可以判断出来）
再特殊一点，对于判断是否是4的指数的方法（首先对于2也好，4也好，都必须是只有1个1；所以，如果有两个1的数肯定是错的，然后再判断和0xaaaaaaaa相与的结果，如果为0则是真，为0xaaaaaaaa则为假。

bool isPowerOfFour(int num){
   if(num<=0) return false;
   int tmp = num&(~num+1);    //    找出最右边的一个1，并判断是否只有一个1；
   if( tmp!=num ) return false;
   else if( tmp&0xaaaaaaaa ) return false;
   return true;
}

8、概念定义的一些题：

Ugly Number ：一组正数，这组正数的质因子只包括 所指定的一些数字，比如 easy 题中的 2,3,5. 而1往往被认为是 Ugly Number，简单地处理方式是不断 while 循环去除以对应质数。

9、拟快排系列：

A：拟快排版本1：在字符串中，将元音字母的顺序进行逆转，方法就是从字符串的左右都分别找到需要进行对换的字母，然后进行交换；

      string reverseVowels(string s) {
        if(s=="") return s;
        int left=0,right=s.size()-1;
        char left_c=tolower(s[left]), right_c=tolower(s[right]);
        while(left<right){
            while(left_c!='a'&&left_c!='e'&&left_c!='i'&&left_c!='o'&&left_c!='u'){
                ++left;
                left_c=tolower(s[left]);
            }
            while(right_c!='a'&&right_c!='e'&&right_c!='i'&&right_c!='o'&&right_c!='u'){
                --right;
                right_c=tolower(s[right]);
            }
            if(left<right) swap(s[left],s[right]);
            ++left;
            left_c=tolower(s[left]);
            --right;
            right_c=tolower(s[right]);
        }
        return s;
    }

10、回文系列：

A：一个整数是否是回文的，原地判断：（整数回文相对比较复杂）
（对于数据中，所谓的一半的位置是很难真正找到的，既然这样，就需要用到递归的方法去找）
一般与数值有关的数字操作，包括>>、<<、&、|、/、%

class Solution {
public:
    bool isPd(int xn, int &xd) {
        if(xn / 10 == 0){   
    if((xd % 10) == xn){
            xd = xd/10;
            return true;
       }
       return false;
    }else{
            bool sign = isPd(xn/10, xd);
            if(sign && (xn % 10) == (xd%10) ){
                xd = xd/10;
                return true;
            } 
            return  false;
        }
    }
    bool isPalindrome(int x) {
        if(x < 0) return false;
        return isPd(x,x);
    }
};

B：一个链表是否是回文的，原地判断
（这个问题的解决方法是，快慢指针找到链表的中点，然后又回到起点将起点到中点这一段的链表反转，反转之后，再双向逐个比较，如果有任何一个不相同，则返回否）

C：字符串回文，含其他的多余字符，需要过滤掉其他的多余字符来进行回文比较：

    bool isPalindrome(string s) {
        // 字符串的回文理论上比较简单，但是加了很多的其他的符号，关键步骤在于左右夹逼的时候，如果遇到非字母数字的字母情况下，需要跳过，终点在于两个下标在一起。
        string res="";
        for(int i=0,j=s.size()-1;i<j;i++,j--){
            char first_letter,second_letter;
            while(!((s[i]-'a'<26 && s[i]-'a'>=0)||(s[i]-'A'<26 && s[i]-'A'>=0)||(s[i]-'0'<=9 && s[i]-'0'>=0))) i++; 
            if(i<=j) first_letter = tolower(s[i]);
            while(!((s[j]-'a'<26 && s[j]-'a'>=0)||(s[j]-'A'<26 && s[j]-'A'>=0)||(s[j]-'0'<=9 && s[j]-'0'>=0))) j--;
            if(i<=j) second_letter = tolower(s[j]);
            if(first_letter != second_letter) return false;
        }
        return true;
    }
    tip: ::isalnum 可以用来比较一个字母是不是数字和字母

11、智力题类：

A：数独：

clipboard.png

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int size = board.size();
        for(int i=0;i<size;i++)
            for(int j=0;j<size;j++){
                if(board[i][j]=='.') continue;// 能不递归就不递归
                int count=0;
                // 判断行和列是否有冲突
                for(int k=0;k<size;k++){
                    if(board[i][k]==board[i][j]) count++;  
                    if(board[k][j]==board[i][j]) count++;
                    if(count>2) return false;
                } 
                // 判断九宫格是否有冲突
                for(int l=(i/3)*3;l<(i/3)*3+3;l++)
                    for(int m=(j/3)*3;m<(j/3)*3+3;m++)
                        if(board[l][m]==board[i][j]) count++;
                if(count>3) return false;
            }
        return true;
    }
};

12、几何数学题

几何数学题需要找到合适切入角度。

13、重构题
A：Min Stack [加红的原因是，网易游戏问过]

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

这个题简单的原因在于两个stack就可以完成，push 和 pop 用来维护第二个 stack，第二个 stack 是记录最小值的。当 Push 一个数值的时候，如果比上一个数小，那么把该数放进去，如果大于，则把第二个stack的top值放进来。

14、场景题
（将算法放在一个应用场景中，然后去解决，比如之前的LRU！再比如twitte设计）、
A：First Bad Version
说得很复杂，其实也就是找到一维数组中的连续坏点的起点。因为这里只有good or bad，所以，不存在乱序的问题，最好的办法是二分查找。

class Solution {
public:
    int firstBadVersion(int n) {
        int left=1;
        int right = n;
        while(left<right){
            int mid = left+(right-left)/2;
            if(isBadVersion(mid)) right =mid;  // 这里是mid，而不是mid-1
            else left =mid+1;
        }
        return left;
    }
};

其实，二分查找有时候会因为把握不了边界而出错，但是，需要知道的是，每一次二分的时候，要尽量将正确的答案留下来。