常见的代码技巧

1. 双指针法（定长，变长）

2. 数组记忆化，空间换时间；

　　494. 目标和

 1 //纯粹的DFS
 2 class Solution {
 3 public:
 4     int dfs(vector<int> &nums, int i, int target) {
 5         if(i == nums.size()) return 0 == target;
 6         int ret = 0;
 7         ret += dfs(nums, i + 1, target - nums[i]);
 8         ret += dfs(nums, i + 1, target + nums[i]);
 9         return ret;
10     }
11 
12     int findTargetSumWays(vector<int>& nums, int target) {
13         return dfs(nums, 0, target);
14     }
15 };
16 
17 
18 //记忆化搜索
19 class Solution {
20 public:
21     typedef pair<int,int> PII;
22     struct CMP {
23         int operator() (const PII& a) const {
24             return a.first ^ a.second;
25         }
26     };
27     unordered_mapint, CMP> record;
28 
29     int dfs(int i, vector<int> &nums, int target) {
30         if(i == nums.size()) return 0 == target;
31 
32         if(record.find(PII(i, target)) != record.end()) return  record[PII(i, target)];
33         int cnt = 0;
34         cnt += dfs(i + 1, nums, target - nums[i]);
35         cnt += dfs(i + 1, nums, target + nums[i]);
36         record[PII(i, target)] = cnt;
37         return cnt;
38     }
39 
40     int findTargetSumWays(vector<int>& nums, int target) {
41         return dfs(0, nums, target);
42     }
43 };

　　2.1 搜索减枝： 但当状态定义较为复杂时候，会导致记忆化数值复杂度 及 重复性降低，这时候就要考虑搜索减枝的方式减少DFS 的深度；　

　　473. 火柴拼正方形 ： 利用减枝优化查找效率，但是减枝的具体方法都要基于具体情况进行处理；

 1 //没有任何减枝优化,很容易超时
 2 class Solution {
 3 public:
 4     bool dfs(vector<int> &matchsticks, int index, array<int, 4> &sticks) {
 5         if(index == matchsticks.size()) return true;
 6         
 7         for(int i = 0; i < 4; ++i) {
 8             int temp = sticks[i]  - matchsticks[index];
 9             if(temp < 0) continue;
10             sticks[i] = temp;
11             if(dfs(matchsticks, index + 1, sticks)) return true;
12             sticks[i] = temp + matchsticks[index];
13         }
14 
15         return false;
16     }
17 
18     bool makesquare(vector<int>& matchsticks) {
19         int total = 0;
20         for(auto &x : matchsticks) total += x;
21         if(total % 4) return false;
22         total /= 4;
23 
24         array<int, 4> sticks = {total, total, total, total};
25         return dfs(matchsticks, 0, sticks);
26 
27     }
28 };
29 
30 
31 
32 //rev1:有效利用搜索减枝改善查找效率
33 class Solution {
34 public:
35     bool dfs(vector<int> &ms, vector<int> &arr, int ind) {
36         //状态定义比较复杂，增加记忆化数据的复杂度，重复性降低，使用搜索减枝的情况会更好；
37         //1.最长的火柴比当前边长要长，所以这个树节点的其中一个分支不可能找到结果了
38         //2. 当前边基于当前火柴处理后，还有剩余的话，如果比 最短的火柴还要短，那也不可能拼出来了
39 
40         if(ind < 0)  return true;
41         for(int i = 0; i < 4; i++) {
42             if(arr[i] < ms[ind]) continue;
43             if(arr[i] == ms[ind] || arr[i] >= ms[ind]+ ms[0]) {
44                 arr[i] -= ms[ind];
45                 if(dfs(ms, arr, ind - 1)) return true;
46                 arr[i] += ms[ind];
47             }
48         }
49         return false;
50     }
51 
52     bool makesquare(vector<int>& matchsticks) {
53         int all_sum = 0;
54         for(auto x : matchsticks) all_sum += x;
55         if(all_sum % 4) return false;
56         vector<int> arr(4, all_sum / 4);
57         //一个很好想法，排序以后从大到小查找，减少不必要继续查找；
58         sort(matchsticks.begin(), matchsticks.end());
59 
60         return dfs(matchsticks, arr, matchsticks.size() - 1);
61     }
62 };

3. 前缀节点（哨兵节点）

4. 前缀和（差分和）， 树状数组（FenwickTree)

5. 递归 ：（欧拉公式，辗转相除法）

　　a: 数学归纳法  --> 结构归纳法： 证明程序的正确性， 而不是通过不断展开；

　　　　　　step1: k₀ 已知； // 确定边界条件；

　　　　　　step 2: 假设 k_i 可以推导出  k_i+1;  // 赋予递归函数一个明确定义，确定相互关系（等式）

　　　　　　step3: 所以通过k₀ 可以 一直推导出k_i；// 实现递归过程代码；

　　递归问题中，难点在于如何给予递归函数一个更好的定义，下面题目，两个递归方式实现：面试题 04.12. 求和路径 : 个人感觉第一种方案，通过两个函数的递归更加优美。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int getPath(TreeNode *r, int sum) {
13         if(!r) return 0;
14         int left = sum - r->val;
15         return (sum == r->val) + getPath(r->left,left) + getPath(r->right, left);
16     }
17 
18     int pathSum(TreeNode* root, int sum) {
19         if(!root) return 0;
20         return getPath(root, sum) +
21             pathSum(root->left, sum) +
22             pathSum(root->right, sum);
23     }
24 };

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int __pathSum(TreeNode *r, int depth, int sum) {
13         if(!r) return 0;
14         int left = sum - r->val,
15             ret = (left == 0);
16 
17         if(0 == depth) {
18             ret += __pathSum(r->left, 0, sum);
19             ret += __pathSum(r->right, 0, sum);
20         } 
21 
22         ret += __pathSum(r->left, depth + 1, left);
23         ret += __pathSum(r->right, depth + 1, left);
24 
25         return ret;
26     }
27 
28     int pathSum(TreeNode* root, int sum) {
29         return __pathSum(root, 0, sum);
30     }
31 };

6. 方向数组 ： 通常在查找中通过方向数组 定义 下一个状态 可能存在的变化范围；

7. 公式化简：leetcode1829

8. 枚举法：求质数，

9. 分治算法：(典型就是 mergeSort， 将一个大问题拆分，分别计算出各个部分的结果，然后再计算横跨不同部分的结果);

10. C++ 中 string to  int 有 stoi, 那么int to string 没有函数，可以使用 stringstream 方式（也可以自己写转换函数）；

11. 分块处理问题（快速幂计算， leetcode372; leetcode60)

 　　快速幂：

 1 #define MOD_NUM ((long long) 1337)
 2     long long _pow(long long base, long long n) {
 3         long long ret = 1;
 4         while(n) {
 5             if(n & 1)  ret = (ret * base) % MOD_NUM;
 6             base = base * base % MOD_NUM;
 7             n >>= 1;
 8         }
 9         return ret;
10     }

 12. 摩尔投票法：（leetcode229）

　　本质是将根据数量，进行相互抵消，直到最后剩下的值，再进行判断；

　　抵消有两种方式实现，一种是自身 + 1, 另一种是其他所有的都 -1，这两种方式都等价于抵消操作；

　　求 > 1 / n，就将数组分成 n 份。

 1 class Solution {
 2 public:
 3     vector<int> majorityElement(vector<int>& nums) {
 4 #define k 2
 5         int size = nums.size();
 6 
 7         int cnt[k] = {0}, ans[k] ={0};
 8         for(int i = 0; i < size; ++i) {
 9             int flag = false;
10             for(int ind = 0; ind < k; ++ind) {
11                 if(nums[i] == ans[ind]) {
12                     cnt[ind] += 1;
13                     flag = true;
14                     break;
15                 }
16             }
17             if(flag) continue;
18 
19             for(int ind = 0; ind < k; ++ind) {
20                 if(cnt[ind]) continue;
21                 ans[ind] = nums[i];
22                 cnt[ind] += 1;
23                 flag = true;
24                 break;
25             }
26             if(flag) continue;
27 
28             for(int ind = 0; ind < k; ++ind) cnt[ind] -= 1;
29         }
30 
31         for(int ind = 0; ind < k; ++ind) cnt[ind] = 0;
32         for(int i = 0; i < size; ++i) {
33             for(int ind = 0; ind < k; ++ind) {
34                 if(nums[i] != ans[ind]) continue;
35                 cnt[ind] += 1;
36                 break;
37             }
38         }
39         vector<int> ret;
40         //注意这里要求的是超过多少，这里以3为例；
41         for(int ind = 0, I = size /(k + 1); ind < k; ++ind) if( cnt[ind] > I) ret.push_back(ans[ind]);
42         return ret;
43     }
44 };

 13. 复杂问题简单化(扩展欧几里德算法（贝祖等式）：

 1 int ex_gcd(int a, int b, int &x, int &y){
 2     if(!b) {
 3         x = 1, y = 0;
 4         cout << a << " * " << x << " + " << b << " * " << y << " = ";
 5         return a;
 6     }
 7 
 8     int ret = ex_gcd(b, a % b, y, x);
 9     y -= a / b * x;
10     cout << a << " * " << x << " + " << b << " * " << y << " = ";
11     return ret;
12 }
13 
14 int main()
15 {
16     int a, b, x, y, ret = 0;
17 
18     while(cin >> a >> b) {
19         ret = ex_gcd(a, b, x, y);
20         cout << ret << endl;
21     }
22     return 0;
23 }
24 
25 ex_gcd

 14. 数学计算，推导结果（均匀随机数生成 leetcode470）

 1 class Solution {
 2 public:
 3     int rand10() {
 4         while(1){
 5             int ans = (rand7() - 1) * 7 + rand7();
 6             if(ans <= 40) return ans % 10 + 1;
 7 
 8             //rand
 9             int a = ans - 40;  //1 ~ 9
10             ans = (a - 1) * 7 + rand7();  // 63
11             if(ans <= 60) return ans % 10 + 1;
12 
13             a = ans - 60;  //1 ~ 3
14             ans = (a - 1) * 7 + rand7();  //21
15             if(ans <= 20) return ans % 10 + 1;
16         }
17         return 0;
18     }
19 };

15. 对于各种数据结构类型使用的考虑方式：

　　a. 判断每次提取数据类型（最近的(stack) , 最早的(deque)，最大的(priority_queue), 特定的下标(map/hash), 更改相当部分数据(前缀和，树状数组(fenwickTree));

　　b. 连同性问题： 并查集

　　c. 字符串相关： trie/ 多叉树

16. 需要返回多个查找结果时候，可以将不同查找值对应成为不同bit 位（面试题 04.08. 首个共同祖先）

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int checkNode(TreeNode *root, TreeNode *p, TreeNode *q, TreeNode* &ret) { //return valu : 1 :find p; 2 find q;, 3 find both;
13         if(!root) return 0;
14         int l = checkNode(root->left, p, q, ret),
15             r = checkNode(root->right, p, q, ret);
16         if(l == 3 || r == 3) return 3;
17         int cur = (l | r);
18         if(root == p) cur |= 1;
19         if(root == q) cur |= 2;
20         if(cur == 3) ret = root;
21         return cur;
22     }
23 
24     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
25         TreeNode* ret = nullptr;
26         checkNode(root, p, q, ret);
27         return ret;
28     }
29 };

17.leetcode  4. 寻找两个正序数组的中位数

　　对于可能两个数组需要分别选择指定数量数值，但是有可能指定数量大于 数组总数 情况下，如何取值做法;   很好的例子
        　　int cnt1 = min(k / 2, (int)nums1.size() - i), cnt2 = min(k - cnt1, (int)nums2.size() - j);
        　　cnt1 = k - cnt2; 

　　任何 涉及到位置变化的 计算部分，都要考虑 越界可能； 

　　 　　k = 0时，k / 2 = 0, i + k / 2 -  1存在越界可能

 1 class Solution {
 2 public:
 3 
 4     double findKnum(vector<int> &nums1, vector<int> &nums2, int i, int j, int k) {
 5 
 6         //先判断是否存在越界情况；
 7         if(i == nums1.size()) return nums2[j + k - 1];
 8         if(j == nums2.size()) return nums1[i + k - 1];
 9         //在判断特殊情况， k = 0时，k / 2 = 0, i + k / 2 -  1存在越界可能;
10         //必须要特判
11         if(k == 1) return (nums1[i] > nums2[j] ? nums2[j] : nums1[i]); 
12         //对于可能存在越界情况下，如何取值做法;   很好的例子
13         int cnt1 = min(k / 2, (int)nums1.size() - i),
14             cnt2 = min(k - cnt1, (int)nums2.size() - j);
15         cnt1 = k - cnt2;  
16 
17         int index1 = i + cnt1 - 1, index2 = j + cnt2 - 1;
18         if(nums1[index1] == nums2[index2]) return nums1[index1];
19         else if(nums1[index1] < nums2[index2]) return findKnum(nums1, nums2, index1 + 1, j, k - cnt1);
20         return findKnum(nums1, nums2, i, index2 + 1, k - cnt2);
21     }
22 
23     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
24 //        int I1 = nums1.size(), I2 = nums2.size();
25 //        int mid = (I1 + I2 - 1) >> 1;
26 //        //set STL 使用，然后寻找中位数
27 //        multiset arr;
28 //        for(int i = 0; i < I1; i++) arr.insert(nums1[i]);
29 //        for(int i = 0; i < I2; i++) arr.insert(nums2[i]);
30 //        int temp = mid;
31 //        multiset::iterator iter = arr.begin();
32 //        while(temp--)  iter++;
33 //
34 //        if(mid * 2 == arr.size() - 1) return *(iter);
35 //        else return 1.0 * (*iter + *(++iter)) / 2;
36 //
37         //二分方式，找到第k个数据
38         int a = nums1.size(), b = nums2.size(), k = (a + b + 1) / 2;
39         double ret = findKnum(nums1, nums2, 0, 0, k);
40         if((a + b) % 2)  return ret;
41         int ret1 = findKnum(nums1, nums2, 0, 0, k + 1);
42         return (ret + ret1) / 2.0;
43     }
44 };

18 . 利用倒序 求某个元素后面满足某种性质的元素；

　　正序要随着后面元素压入导致需要不断更新前面的结果；

　　456. 132 模式 ： 求取某个元素后面小于它的最大值情况；(当然这题里面实际求的是它 与 大于它元素/结尾 之间的最接近它的最小值）；

 1 class Solution {
 2 public:
 3     bool find132pattern(vector<int>& nums) {
 4         //132 pattern : 对于3 来讲，要求得前面小于它的最小值， 后面小于它的最大值; 然后对比后面值 是否大于 前面值
 5         // 这里希望1 尽可能小，32 尽可能大，并接近
 6         int len = nums.size();
 7         //前面小于它的最小值，没有就为极限值，保证后面没有大于它
 8         vector<int> preMin(len, 1e9);
 9         for(int i = 1; i < len; ++i) preMin[i] = min(preMin[i - 1], nums[i - 1]);
10         
11         //后面比它小的元素中最大值 
12         //倒序求，到达当前元素时后面元素已经计算结束了；  //解题技巧！
13         //如果当前元素后面有大于它的元素，求当前元素 到 离它最近的大于它的元素中间 最接近它的且小于它的元素;
14         //因为如果 n + i 都不满足条件，n 元素 + (n + i) 后的元素 就更不可能满足条件
15         stack<int> s_dec;
16         for(int i = len - 1; i > 0 ; --i) {
17             int close_i_val = nums[i];
18             while(s_dec.size() && nums[i] > s_dec.top()) {
19                 close_i_val = s_dec.top();
20                 s_dec.pop();
21             }
22             if(close_i_val < nums[i] && preMin[i] < close_i_val) return true;
23             s_dec.push(nums[i]);
24         }
25 
26         return false;
27     }
28 };

19. 对于二进制中bit 位的交换操作：两边同时将无效位 通过&0 mask 掉，然后移位； 然后将两份处理过的值 | 即可;

190. 颠倒二进制位 :

 1 class Solution {
 2 public:
 3     uint32_t reverseBits(uint32_t n) {
 4         n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16);
 5         n = ((n & 0xFF00FF00) >> 8 ) | ((n & 0x00FF00FF) << 8);
 6         n = ((n & 0xF0F0F0F0) >> 4 ) | ((n & 0x0F0F0F0F) << 4);
 7         n = ((n & 0xCCCCCCCC) >> 2 ) | ((n & 0x33333333) << 2);
 8         n = ((n & 0xAAAAAAAA) >> 1 ) | ((n & 0x55555555) << 1);
 9 
10         return n;
11     }
12 };