• 各类区间和
  • 数组不变，求区间和：— 前缀和、树状数组、线段树
  • 多次修改某个点，求区间和：— 树状数组、线段树
  • 多次修改某个区间，输出最终结果：— 差分
  • 多次修改某个区间，求区间和： — 线段树、树状数组（看修改区间范围大小）
  • 多次将某个区间变成同一个数，求区间和： — 线段树、树状数组（看修改区间范围大小）

线段树：代码很长，常数很大，实际表现不算很好。最后考虑。

1. 题型1：坐标转换

  1. // 地震预警通知
  3. 坐标<row, col>,
  4. 地图长度：mapSideLen，是gridSideLen的整数倍
  5. 栅格长度：gridSideLen, 保证是奇数
  6. n : mapSideLen / gridSideLen
  7. 属于的区间：
  8. int r = (row / gridSideLen);
  9. int c = (col / gridSideLen);
  10. int seq = r * n + c + 1; // 栅格序号
  12. 栅格的中心位置：
  13. int midRow = ((seq - 1) / n) * gridSideLen + gridSideLen / 2;
  14. int midCol = ((seq - 1) % n) * gridSideLen + gridSideLen / 2;
  16. 曼哈顿距离：
  17. int d = abs(midRow - posRow) + abs(midCol - posCol);
  19. 存储的数据结构：
  20. unordered_map<int, vector<int>> mp;
  21. // 序号， 距离，用户数
  23. vector<int> one = {seq, d, userNum}

2. 题型2：摩尔投票法

  • 概念： 又称多数投票法，主要用于解决一个数组中的众数的问题。（核心：对抗消耗）
  • 证明：
    • 如果候选人不是maj 则 maj,会和其他非候选人一起反对 会反对候选人,所以候选人一定会下台(maj==0时发生换届选举)
    • 如果候选人是maj , 则maj 会支持自己，其他候选人会反对，同样因为maj 票数超过一半，所以maj 一定会成功当选
  • 步骤：
    • 对抗阶段：分属两个候选人的票数两两对抗抵消
    • 计数阶段：计算对抗结果中最后留下的候选人票数是否有效 ```cpp // 主要元素 https://leetcode-cn.com/problems/find-majority-element-lcci/ // 数组中占比超过一半的元素称之为主要元素。 // 给定一个整数数组，找到它的主要元素。 // 若没有，返回-1。 int majorityElement(vector& nums) { int candidate = -1; int count = 0; // 对抗阶段 for (int& num : nums) { if (count == 0) {
      1.    candidate = num;
      } count += (num == candidate) ? 1 : -1; } count = 0; int length = nums.size(); for (int& num : nums) { if (num == candidate) {
      1.    count++;
      } } return count * 2 > length ? candidate : -1; }
  1. ```cpp
  2. // 多数元素 https://leetcode-cn.com/problems/majority-element/
  3. // 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
  4. // 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
  5. // 法1：哈希计数，时间复杂度O(n),空间复杂度O(n); 
  6. int majorityElement(vector<int>& nums) {
  7.     unordered_map<int, int> counts;
  8.     int majority = 0, cnt = 0;
  9.     for (int num: nums) {
  10.         ++counts[num];
  11.         if (counts[num] > cnt) {
  12.             majority = num;
  13.             cnt = counts[num];
  14.         }
  15.     }
  16.     return majority;
  17. }
  18. // 法2：排序, 返回n/2位置的数，时间复杂度O(nlogn), O(1)
  19. // 空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用O(logn) 的栈空间。
  20. // 如果自己编写堆排序，则只需要使用 O(1)O(1) 的额外空间。
  21. int majorityElement(vector<int>& nums) {
  22.     sort(nums.begin(), nums.end());
  23.     return nums[nums.size() / 2];
  24. }
  25. // 法3：摩尔投票法：时间复杂度O(n), 空间复杂度O(1)
  26. int majorityElement(vector<int>& nums) {
  27.     int candidate = -1;
  28.     int count = 0;
  29.     for (int& num : nums) {
  30.         if (count == 0) {
  31.             candidate = num;
  32.         }
  33.         count += (num == candidate) ? 1 : -1;
  34.     }
  35.     return candidate;
  36. }
  1. // 求众数II https://leetcode-cn.com/problems/majority-element-ii/
  2. // 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
  3. // 反证法可以得到，这数最多有两个。
  4. class Solution {
  5. public:
  6.     vector<int> majorityElement(vector<int>& nums) {
  7.         vector<int> ans;
  8.         int element1 = 0;
  9.         int element2 = 0;
  10.         int vote1 = 0;
  11.         int vote2 = 0;
  13.         for (auto & num : nums) {
  14.             if (vote1 > 0 && num == element1) { //如果该元素为第一个元素，则计数加1
  15.                 vote1++;
  16.             } else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素，则计数加1
  17.                 vote2++;
  18.             } else if (vote1 == 0) { // 选择第一个元素
  19.                 element1 = num;
  20.                 vote1++;
  21.             } else if (vote2 == 0) { // 选择第二个元素
  22.                 element2 = num;
  23.                 vote2++;
  24.             } else { //如果三个元素均不相同，则相互抵消1次
  25.                 vote1--;
  26.                 vote2--;
  27.             }
  28.         }
  30.         int cnt1 = 0;
  31.         int cnt2 = 0;
  32.         for (auto & num : nums) {
  33.             if (vote1 > 0 && num == element1) {
  34.                 cnt1++;
  35.             }
  36.             if (vote2 > 0 && num == element2) {
  37.                 cnt2++;
  38.             }
  39.         }
  40.         // 检测元素出现的次数是否满足要求
  41.         if (vote1 > 0 && cnt1 > nums.size() / 3) {
  42.             ans.push_back(element1);
  43.         }
  44.         if (vote2 > 0 && cnt2 > nums.size() / 3) {
  45.             ans.push_back(element2);
  46.         }
  48.         return ans;
  49.     }
  50. };

3. 矩形的交集计算