算法题总结

Posted on Edited on In
  • 回溯题，当需要输出很多个等长串且第一个字符都不一样时，回溯内部需要用到for循环，否则不用。回溯函数一般返回类型都是void
  • mysql中使用三值逻辑true、false、UNKNOWN
  • 二分搜索的几种特例(while循环的判断条件为le <= ri)
    1）找到该键第一次出现的位置，一直在左半区间搜索，如果nums[mid]==target，用一个变量index记录该下标，然后hi = mid -1,继续在左半区搜，若左半区没有该元素，则index就是target第一次出现的位置。
    2）查找该键最后一次出现的位置反之
      1. 在排序数组中查找元素的第一个和最后一个位置
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        int searchRangeLeft(vector<int>& nums, int target) {
            int le = 0, ri = nums.size()-1;
            int idx = -1;
            while (le <= ri) {
                int mid = le + (ri-le)/2;
                if (nums[mid] == target) {
                    idx = mid;
                    ri = mid - 1;
                } else if (nums[mid] < target){
                    le = mid + 1;
                } else {
                    ri = mid - 1;
                }
            }
            return idx;
        }
        3）在一个有序数组中找第一个大于等于target的下标
    • 剑指 Offer II 068. 查找插入位置
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      int searchInsert(vector<int>& nums, int target) {
          int p = 0, q = nums.size()-1;
          int ret = q+1;
          while (p <= q) {  // 这里的判断条件和while循环不一致
              int mid = p + (q-p)/2;
              if (nums[mid] >= target) {
                  ret = mid;
                  q = mid - 1;
              } else {
                  p = mid + 1;
              }
          }
          return ret;
      }
  • 单调栈
    • 头部先push一个0，则不需要判断栈是否为空
    • 将下标放在栈中，栈中下标对应的元素是单调增/减的
    • 接雨水，每日温度，柱状图中最大的矩形
  • 前缀和可以用std::accumulate(nums.begin(), nums.end(), init_val);会返回当前容器的前缀和
  • 字符串
    • isspace(ch)空格
    • isalpha(ch)字母
    • isdigit(ch)数字
    • isalnum(ch)字母和数字
    • tolower(ch)转化为小写
    • toupper(ch)转换为大写
    • transform(nums.begin(), nums.end(), nums.begin(), tolower)将容器内的元素都变为小写字母，第三个参数表示替换的起始位置
  • dp背包问题
    • 分类
      • 0-1背包(空间优化时必须逆向遍历)
        • dp[i][j]表示前i件物品在物品体积不超过j的情况下的最大价值
        • 如果第i件物品不被放进背包，则dp[i][j] = dp[i-1][j]
        • 如果第i件物品被放进背包, 且该物品的体积为W，价值为V，则dp[i][j] = dp[i-1][j-W] + V;
        • 遍历过程只需要取这两种情况的最大值即可
        • 时间复杂度和空间都为O(NW)
      • 完全背包(可以直接从一维优化，因为不确定物品具体的数目)
        • 如果第i件物品不被放进背包，则dp[i][j] = dp[i-1][j]
        • 如果第i件物品被放进背包, 且该物品的体积为W，价值为V，则dp[i][j] = dp[i][j-W] + V;，注意与01背包的区别，当前状态也有同一行的状态决定
        • 比如279完全平方数，322零钱兑换，直接用一维做就可以了ii
          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          16
          17
          class Solution {
            public:
                int coinChange(vector<int>& coins, int amount) {
                    vector<int> dp(amount+1, INT_MAX-1);
                    dp[0] = 0;  // 初始条件，0块钱所需要的最少硬币数
                    // 外层物品，内层体积
                    for (int i = 1; i <= amount; ++i) {
                        for (int j = 0; j < coins.size(); ++j) {
                            if (i >= coins[j]) {  // 保证不发生越界
                                dp[i] = min(dp[i], dp[i-coins[j]] + 1);  // 1为价值，coins[j]为体积
                            }
                        }
                    }
                    return dp[amount] == INT_MAX-1? -1: dp[amount];
                }
            };

      • 一般01背包，外层物品内层体积；完全背包外层体积，内层物品
  • 寻找[1,n]重复数的常见解题思路
    • O1空间复杂度，以元素值为下标作为桶，遍历到就往桶里面(对应下标为nums[nums[i]%n]，n为数组长度)加上数组的长度，最后再遍历一次check桶里面的值。
  • dp股票问题
    • 画状态图
    • 记得设置初始状态，可能BUY和HOLD都要一起设置。如BUY[i]表示在第i天买入的最大利润，那么初始值BUY[0]应该设置为-prices[0]
    • 最后的结果可能是两个状态的最大值
  • 二维数组的二分查找，直接取矩阵的右上角作为mid来进行查找
  • C++中优先队列priority_queue的根节点在尾部，因此建立小根堆比较器为greater(即lhs > rhs)
    • 如果想使用lamda表达式来作为比较器，必须得用decltype，定义对象时还需要传入模板参数，注意lambda表达式是匿名函数，在定义比较器时需要返回bool变量
      1
      2
      3
      4
      5
      6
      7
      8
      #include <queue>

      auto cmp = [](int a, int b) {
          // 比较器的实现
          return a < b;
      };

      std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);
    • 或者自定义对象，使用仿函数来实现
      1
      2
      3
      4
      5
      6
      struct cmp {
          bool operator()(pair<int,int>& lhs, pair<int, int>& rhs) {
              return lhs.second > rhs.second;
          }
      };
      priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> que;
  • 前缀树
    • 每个node两个成员变量：isend判断该节点是否为结尾，vector<Trie*>children(26);，表示26个小写字母
    • 每个node一个方法：查询前缀树中是否有该前缀，有的话返回该前缀的尾节点，否则返回nullptr
  • 快速排序(时间O(nlogn), 空间O(logn))
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
      void quickSort(vector<int>& arr, int lo, int hi) {
        if (lo >= hi) {  // 记得这里递归要有结束条件
          return;
        }
        int mid = partition(arr, lo, hi);
        quickSort(arr, lo, mid-1);
        quickSort(arr, mid+1, hi);
      }

      int partition(vector<int>& arr, int le, int ri) {
        int pivot = arr[le];
        int i = le, j = ri;
        while (i < j) {  // 这里和二分while不一致，因为相同位置没必要进行交换
          while (i < ri && arr[i] <= pivot) i++;
          while (j > le && arr[j] >= pivot) --j;
          if (i >= j) break;  // 关键
          swap(arr[i], arr[j]);
        }
        swap(arr[j], arr[le]);
        return j;
      }
    };
  • 归并排序(时间O(nlogn), 空间O(n))
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    // 传递参数时需要mid
    void merge(vector<int>& arr, vector<int>& aux, int lo, int mid, int hi) {
      // 两个子区间的起始下标i,j
      int i = lo, j = mid+1;
      // 这里一定要更新aux数组，因为bottom-up时，arr会发生变化
      // 保存原始arr的一个副本，最后不断更改arr达到最后的效果
      for (int k = lo; k <= hi; ++k) {
          aux[k] = arr[k];
      }
      // 双指针合并数组
      for (int k = lo; k <= hi; ++k) {
          // 两种越界情况
          if (i > mid) arr[k] = aux[j++];
          else if (j > hi) arr[k] = aux[i++];
          else if (aux[i] < aux[j]) arr[k] = aux[i++];
          else arr[k] = aux[j++];
      }
    }

    void mergeSort(vector<int>& arr, vector<int>& aux, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi-lo)/2;
        // 如果区间sort[lo, mid-1]则可能会出现下标越界!!
        mergeSort(arr, aux, lo, mid);
        mergeSort(arr, aux, mid+1, hi);
        merge(arr, aux, lo, mid, hi);  // 传入mid，需要第二个区间的起始下标
    }
  • 堆排序(时间O(nlogn), 空间O(n))
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    void heapify(vector<int>& arr, int n, int i) {
      // largest记录最大值的下标
      int largest = i; // 初始化最大值为根节点
      int l = 2 * i + 1; // 左子节点
      int r = 2 * i + 2; // 右子节点

      // 如果左子节点比根节点大，则更新最大值
      if (l < n && arr[l] > arr[largest]) {
        largest = l;
      }

      // 如果右子节点比根节点大，则更新最大值
      if (r < n && arr[r] > arr[largest]) {
        largest = r;
      }

      // 如果最大值不是根节点，则交换根节点和最大值
      if (largest != i) {
        swap(arr[i], arr[largest]);
        // 递归调用heapify函数，直到所有子树都满足最大堆的性质
        heapify(arr, n, largest);
      }
    }

    void heapSort(vector<int>& arr) {
      int n = arr.size();

      // 建立最大堆
      for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
      }

      // 从最后一个元素开始，依次将最大值交换到数组末尾
      for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        // 维护最大堆的性质
        heapify(arr, i, 0);
      }
    }
  • 前缀和问题，比如560和为k的子数组。本质上就是这一个公式，若pre[j]-pre[i-1]=k，即表示[i..j]区间内的元素和为k。转化为pre[i-1] = pre[j]-k(满足说明出现了和为k的子数组)，每次遍历时都要统计前缀和为n出现的次数mp[pre]++，然后哈希表可以统计前缀和出现的次数。初始条件为map[0]=1，想想这种情况[3,4] k=7