在做专项训练和一些随机题的时候，看别人的代码学到的一些编程小技巧。

  1. 读取字符串，同时需要分辨其中字母和数字。

    • 自己做转换的速度快，用上switch就比if-else更快。
    • 相比stringstream，少了错误处理，犯不上检查failbit，也不用clear了，速度明显提升，代码可读性也很好。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      switch (s[i]) {
                  case '0':
                  case '1':
                  case '2':
                  case '3':
                  case '4':
                  case '5':
                  case '6':
                  case '7':
                  case '8':
                  case '9': {
                      tmp_num += s[i];
                      break;
                  }
                  case 'other': {
                      int t = stoi(tmp_num);
                      // do xxx
                  }
      }

  2. 加减法变换，避免溢出

    • 后来想这可能是二分搜索出错最多的地方了。
      1
      2
      int mid = (left + right) / 2;
      int mid_right = left + (right - left) / 2;
    • 一般来说，索引都是正数，而且左右都没溢出，求中间数不应该溢出的。
    • 平方数的判断，乘法变除法，在做乘法检验。
    • 当然比较暴力的办法是换更大的类型。

  3. queue与BFS

    • 我特别喜欢用stl中的swap方法去做层级的变换。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      int cnt=0;
      queue<int> q1, q2;
      while(!q1.empty()){
          while(!q1.empty()){
              // do xx; q2.push(next);
          }
          cnt++;
          q1.swap(q2);
      }
    • 当然swap还有一些其他的妙用，下次碰上了再写。
    • 但是BFS还有一个办法，我觉得这个更妙了。
      1
      2
      3
      4
      5
      6
      7
      8
      int cnt=0;
      queue<int> q;
      while(!q.empty()){
          for (int n=q.size();n>0;n--){
              // do xx; q.push(next);
          }
          cnt++;
      }

  4. 保证某个值为小的一个

    • 这应用场景很多，像stl容器有swap方法，其他的一些类型也可以交换，然后就能保证两个值的顺序，后面的代码就能做统一处理。
      1
      2
      3
      4
      int n = nums1.size();
      int m = nums2.size();
      if(n > m)   //保证数组1一定最短
          return func(nums2,nums1);
    • 像上面这种递归调用一次自己也是一种不错的方法，尤其适用于，传入参数是引用时，这时不方便做swap，复制又太耗费时间。

  5. 数组越界的处理

    • 一般来说这种办法适用于有序数组，两端的值用INT_MAX和INT_MIN代替。
      1
      2
      3
      4
      L1 = (c1 == 0)?INT_MIN:nums1[(c1-1)/2];   //map to original element
      R1 = (c1 == 2*n)?INT_MAX:nums1[c1/2];
      L2 = (c2 == 0)?INT_MIN:nums2[(c2-1)/2];
      R2 = (c2 == 2*m)?INT_MAX:nums2[c2/2];

  6. 多值visit表示

    • 在做遍历，DFS，BFS等算法时，经常需要mark经过的点，还有一种有意思的叫法是color。
    • 有时候发现不一定只有两种状态，可以设定更多的值表明不同的状态，比如dfs拓扑排序，一个点出发不一定能经过整个图，所以会尝试从任何一个点出发，这个时候要区分成环和访问过，就会做三种状态“未访问”，“访问过”，“本次搜索访问过”，以便及时退出算法。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      if (visit[n] == 1)
              return true;
      visit[n] = -1;
      for (auto c : v[n]){
          if (visit[c] == -1 || (visit[c] == 0 && !dfs(c, v, visit, topo)))
              return false;
      }
      visit[n] = 1;
      topo.push_back(n);
      return true;

  7. 指针的指针

    • 在删除链表中元素的时候，往往要记录两个指针，因为单链表不能往前。而这样做在删除头的时候，又引入了问题。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      while (head && head->val == val){
          head = head->next;
      }
      ListNode* temp = head;
      while (temp && temp->next){
          if (temp->next->val == val)
              temp->next = temp->next->next;
          else
              temp = temp->next;
      }
      return head;
    • 当然对于这个例子，虚拟头指针也是不错的办法。
    • 但取地址来做，代码更简洁了。
      1
      2
      3
      4
      5
      6
      7
      8
      ListNode ** temp = &head;
      while(*temp){
          if ((*temp)->val == val)
              *temp = (*temp)->next;
          else
              temp = &(*temp)->next;
      }
      return head;

  8. 树结构滑动窗口

    • 滑动窗口比较直观的是数组，用树结构，插入和删除的复杂度提升，但是数据有序。
    • 有序之后查找和比较时间较少，而且可以利用二分库函数lower_bound、upper_bound。
    • 有一个需要注意的特性是出现重复元素，删除将会变得复杂，一般还是应用在不会重复，或者重复时算法就会结束。

  9. 不重复的n数之和

    • 做n数之和的套路总是先排序，然后从两端遍历。依次去掉几个数就可以归纳到两数之和。
    • 当要求找出来的解答不重复，还需要一点小技巧。
      • 用set<vector<int>>，当vector中是基本类型（其实我觉得只要是有==运算的类型都可以），vector也可以进行比较。
      • 循环中增加条件。
        1
        2
        do { left++; } while (nums[left] == nums[left - 1] && left < right);
        do { right--; } while (nums[right] == nums[right + 1] && left < right);

  10. 2的幂

    • 其实就是二进制表示，有且只有一个1的数。
    • n & (n-1) == 0

  11. 格雷编码

    • 相邻数只有一位不同（二进制）。
    • 话不多说，直接奇技淫巧。
      • 第一种
        1
        2
        3
        4
        vector<int> gray;
        for(int i=0;i<(1<<n); i++)
            gray.push_back(i^(i>>1));
        return gray;
      • 第二种
        1
        2
        3
        4
        5
        6
        7
        8
        vector<int> v = {0};
        while(n--){
            for(int i=v.size()-1;i>=0;i--){
                v[i] <<= 1;
                v.push_back(v[i] + 1);
            }
        }
        return v;

  12. 循环体中的条件语句

    • 如果只嵌套一层条件语句，可读性还算可以。 
      1
      2
      3
      4
      5
      for(int i=len-1;i>0;i--){
          if (nums[i] > nums[i-1]){
              // do xxx
          }
      }
    • 像字典序算法，需要循环两次。我觉得这时候可读性就不太好了。 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      for(int i=len-1;i>0;i--){
          if (nums[i] > nums[i-1]){
              for (int j=len-1;j>=i;j--){
                  if (nums[j] > nums[i-1]){
                      // do xxx
                  }
              }
          }
      }
      // do xxx
    • 这时候一手逆向思维，条件反转，这个太显功力了。 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      int i = len - 1;
      while (i > 0 && nums[i] <= nums[i-1]) {
          i--;
      }
      if (i > 0) {
          int j = len - 1;
          while (j >= i && nums[j] <= nums[i-1]) {
              j--;
          }
          swap(nums, i - 1, j);
      }
      reverse(nums, i);