每日算法刷题Day49:7.16:leetcode 差分5道题，用时2h_力扣差分数组题

9.57.插入区间(中等,模拟思考全面)

57. 插入区间 - 力扣（LeetCode）

思想

1.给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
2.分类讨论:

• (1)intervals为空，直接插入newinterval
• (2)否则,对于intervals内某个元素x:
  • (2.1)x[0]<=new[0],直接插入x，
  • (2.2)否则，
    • (2.2.1)x未插入过,先插入new,再插入x
    • (2.2.2)x插入过，只插x
• (3)intervals内所有x都在new前面，即遍历完intervals``new都没插入，插入x
  注意上面的插入，都有考虑跟res合并区间，且整合完都要插入x

代码

class Solution {public: vector<vector> insert(vector<vector>& intervals, vector& newInterval) { int n = intervals.size(), m = newInterval.size(); vector<vector> res; bool tag = false; if (intervals.empty()) { res.push_back(newInterval); return res; } for (auto& x : intervals) { if (!tag && x[0] >= newInterval[0]) { if (!res.empty() && res.back()[1] >= newInterval[0]) {  res.back()[1] = max(res.back()[1], newInterval[1]); } else {  res.push_back(newInterval); } tag = true; } // 都要插入x if (!res.empty() && res.back()[1] >= x[0]) { res.back()[1] = max(res.back()[1], x[1]); } else { res.push_back(x); } } if (!tag) { if (!res.empty() && res.back()[1] >= newInterval[0]) { res.back()[1] = max(res.back()[1], newInterval[1]); } else { res.push_back(newInterval); } } return res; }};

10.2406.将区间分为最少组数(中等)

2406. 将区间分为最少组数 - 力扣（LeetCode）

思想

1.给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。
你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。
请你返回 最少 需要划分成多少个组。
如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。
2.看成[[五.差分#5.1094.拼车(中等)]]模型，区间[left,right]加1，然后最终答案就是被最多区间覆盖的点的值

代码

class Solution {public: typedef long long ll; int minGroups(vector<vector>& intervals) { int n = intervals.size(); int max_end = INT_MIN; for (auto& x : intervals) max_end = max(max_end, x[1]); vector d(max_end + 2, 0); for (auto& x : intervals) { ++d[x[0]]; --d[x[1] + 1]; } int res = 0, sum = 0; for (int i = 0; i < max_end + 1; ++i) { sum += d[i]; res = max(res, sum); } return res; }};

11.3453.分割正方形I(中等，学习浮点二分转变成整数二分或者差分扫描线方法)

思想

1.给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。
找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。
答案如果与实际答案的误差在 10-5 以内，将视为正确答案。
注意：正方形 可能会 重叠。重叠区域应该被 多次计数 。
2.一开始分析最小的y坐标，且一旦一个y满足条件，大于等于它的必定满足条件，所以满足单调性，可以用二分，但是y是浮点数，不知道怎么做了，所以想着转成整数二分来做
因为答案y为浮点数，且误差在1e-5内，所以整数二分的枚举值设为y*1e5.最终答案为二分查找答案除以1e5,整个化简流程如下所示
![[浮点二分变成整数二分.jpg]]
3.差分+扫描线:
![[扫描线举例.png]]
想象一根水平扫描鲜从下往上扫描，从y1到y2的面积增加量就为(y2-y1)*suml,其中suml为当前在两条线范围内的正方形的累计长度，即等价为一个矩形，通过下面的数学公式推导如下
![[差分和扫描线.jpg]]
而在区间[y,y+l)的增加长度l,就可以用差分数组来实现

代码

1.浮点二分变成整数二分

class Solution {public: typedef long long ll; const ll M = 1e5; ll sumS = 0; bool check(vector<vector>& squares, ll mid) { ll sum = 0; for (auto& x : squares) { int y = x[1], l = x[2]; if (mid > M * y) { sum += 1LL * l * min(mid - M * y, M * l); if (2 * sum >= M * sumS)  return true; } } return false; } double separateSquares(vector<vector>& squares) { int n = squares.size(); ll maxY = INT_MIN; for (auto& x : squares) { sumS += 1LL * x[2] * x[2]; maxY = max(maxY, 1LL * (x[1] + x[2])); } ll left = 0, right = maxY * M, res = 0; while (left > 1); if (check(squares, mid)) { res = mid; right = mid - 1; } else left = mid + 1; } return 1.0 * res / M; }};

差分+扫描线

class Solution {public: typedef long long ll; double separateSquares(vector<vector>& squares) { // int n=squares.size(); map diff; ll tot_area = 0; for (auto& sq : squares) { int y = sq[1], l = sq[2]; tot_area += 1LL * l * l; // [y,y+l) diff[y] += l; diff[y + l] -= l; } ll sum_l = 0, area = 0; for (auto it = diff.begin();;) { int y1 = it->first, sl = it->second, y2 = (++it)->first; // [y1,y2) sum_l += sl; area += sum_l * (y2 - y1); if (area * 2 >= tot_area) { return y2 - (area * 2 - tot_area) / (sum_l * 2.0); } } }};

12.2381.字母移位II(中等)

思想

1.给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [starti, endi, directioni] 。对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。
将一个字符 向后 移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 \'z\' 变成 \'a\'）。类似的，将一个字符 向前 移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 \'a\' 变成 \'z\' ）。
请你返回对 s 进行所有移位操作以后得到的最终字符串。
2.[start,end]向后移位就加1，向前移位就减1，利用差分实现。
但是因为要取余，且次数会很大，所以要先加上26变成正数，然后边加变取余，不让数字过大

代码

class Solution {public: typedef long long ll; string shiftingLetters(string s, vector<vector>& shifts) { int n = s.size(); vector d(n + 1, 0); for (auto& sh : shifts) { int st = sh[0], end = sh[1], dir = sh[2]; if (dir == 1) { ++d[st]; --d[end + 1]; } else { --d[st]; ++d[end + 1]; } } ll sum = 0; string res = s; for (int i = 0; i < n; ++i) { // 防止为负数要加上26 sum = (sum + d[i] + 26) % 26; // 防止太大要边加边取余 ll tmp = (s[i] - \'a\' + 26 + sum) % 26; res[i] = \'a\' + tmp; } return res; }};

二维差分

1.套路

【图解】从一维差分到二维差分
![[二维差分.png]]

class Solution {public: vector<vector> rangeAddQueries(int n, vector<vector>& queries) { vector<vector> d(n + 1, vector(n + 1, 0)); for (auto& q : queries) { int x1 = q[0], y1 = q[1], x2 = q[2], y2 = q[3]; // 左上角[x1,y1],右下角[x2,y2] ++d[x1][y1]; --d[x1][y2 + 1]; --d[x2 + 1][y1]; ++d[x2 + 1][y2 + 1]; } vector<vector> res(n, vector(n, 0)); // 法一:二维前缀和还原 res[0][0]=d[0][0]; for(int j=1;j<n;++j){ res[0][j]=res[0][j-1]+d[0][j]; } for(int i=1;i<n;++i){ res[i][0]=res[i-1][0]+d[i][0]; } for(int i=1;i<n;++i){ for(int j=1;j<n;++j){ // 二维前缀和,i,j都有大于等于1 res[i][j]=res[i-1][j]+res[i][j-1]-res[i-1][j-1]+d[i][j]; } } /* // 法二: 分别计算差分数组行和列的一维前缀和 for (int i = 0; i < n; ++i) { for (int j = 1; j < n; ++j) { // 一行的前缀和,j大于等于1 d[i][j] += d[i][j - 1]; } } for (int j = 0; j < n; ++j) { for (int i = 1; i < n; ++i) { // 一列的前缀和,i大于等于1 d[i][j] += d[i - 1][j]; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { res[i][j] = d[i][j]; } } */ return res; }};

2.题目描述

1.给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。
另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1i, col1i, row2i, col2i] ，请你执行下述操作：

• 找出 左上角 为 (row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵，将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i <= x <= row2i 和 col1i <= y <= col2i 的 mat[x][y] 加 1 。
  返回执行完所有操作后得到的矩阵 mat(答案) 。

3.学习经验

1.一个二维区间加上/减去一个数，先算差分数组，然后差分数组求前缀和就是原数组，求前缀和借鉴二维前缀和的思想，但是算法类比一维差分还原前缀和

1. 2536.子矩阵元素加1(中等)

思想

1.给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。
另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1i, col1i, row2i, col2i] ，请你执行下述操作：

• 找出 左上角 为 (row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵，将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i <= x <= row2i 和 col1i <= y <= col2i 的 mat[x][y] 加 1 。
  返回执行完所有操作后得到的矩阵 mat 。

代码

class Solution {public: vector<vector> rangeAddQueries(int n, vector<vector>& queries) { vector<vector> d(n + 1, vector(n + 1, 0)); for (auto& q : queries) { int x1 = q[0], y1 = q[1], x2 = q[2], y2 = q[3]; // 左上角[x1,y1],右下角[x2,y2] ++d[x1][y1]; --d[x1][y2 + 1]; --d[x2 + 1][y1]; ++d[x2 + 1][y2 + 1]; } vector<vector> res(n, vector(n, 0)); // 法一:二维前缀和还原 res[0][0]=d[0][0]; for(int j=1;j<n;++j){ res[0][j]=res[0][j-1]+d[0][j]; } for(int i=1;i<n;++i){ res[i][0]=res[i-1][0]+d[i][0]; } for(int i=1;i<n;++i){ for(int j=1;j<n;++j){ // 二维前缀和,i,j都有大于等于1 res[i][j]=res[i-1][j]+res[i][j-1]-res[i-1][j-1]+d[i][j]; } } /* // 法二: 分别计算差分数组行和列的一维前缀和 for (int i = 0; i < n; ++i) { for (int j = 1; j < n; ++j) { // 一行的前缀和,j大于等于1 d[i][j] += d[i][j - 1]; } } for (int j = 0; j < n; ++j) { for (int i = 1; i < n; ++i) { // 一列的前缀和,i大于等于1 d[i][j] += d[i - 1][j]; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { res[i][j] = d[i][j]; } } */ return res; }};