每日算法刷题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<int>> insert(vector<vector<int>>& intervals,vector<int>& newInterval) {int n = intervals.size(), m = newInterval.size();vector<vector<int>> 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;}// 都要插入xif (!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<int>>& intervals) {int n = intervals.size();int max_end = INT_MIN;for (auto& x : intervals)max_end = max(max_end, x[1]);vector<ll> 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<int>>& 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<int>>& 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 <= right) {ll mid = left + ((right - left) >> 1);if (check(squares, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return 1.0 * res / M;}
};

差分+扫描线

class Solution {
public:typedef long long ll;double separateSquares(vector<vector<int>>& squares) {// int n=squares.size();map<int, ll> 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<int>>& shifts) {int n = s.size();vector<ll> 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) {// 防止为负数要加上26sum = (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<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {vector<vector<int>> d(n + 1, vector<int>(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<int>> res(n, vector<int>(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都有大于等于1res[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大于等于1d[i][j] += d[i][j - 1];}}for (int j = 0; j < n; ++j) {for (int i = 1; i < n; ++i) {// 一列的前缀和,i大于等于1d[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<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {vector<vector<int>> d(n + 1, vector<int>(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<int>> res(n, vector<int>(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都有大于等于1res[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大于等于1d[i][j] += d[i][j - 1];}}for (int j = 0; j < n; ++j) {for (int i = 1; i < n; ++i) {// 一列的前缀和,i大于等于1d[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;}
};