差分数组案例
2381. 字母移位 II
给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [starti, endi, directioni] 。对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。
将一个字符 向后 移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 'z' 变成 'a'）。类似的，将一个字符 向前 移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 'a' 变成 'z' ）。
请你返回对 s 进行所有移位操作以后得到的最终字符串。
思路：
- 构造一个差分数组记录每个元素需要前进或者后退
- 记录每个点到97（a ) 的距离，根据距离获得对应的字母。
- 注意：每个点到97的距离都要小于26. 记录sum为需要前进或后退的距离
- sum为-4 时 ， b - 4 -a = -3 因此 b + sum +26 -97
- x + 2 根据上面 （b + sum +26 -97）%26
- a +28 根据上面 sum%= 26，（b + sum +26 -97）%26
var shiftingLetters = function(s, shifts) {
let len = s.length;
let diff = new Array(len+1).fill(0);
for(let i = 0;i<shifts.length;i++){
const [start,end,val] = shifts[i];
if(val>0){
diff[start]++;
diff[end+1]--;
}else{
diff[start]--;
diff[end+1]++;
}
}
let sum = 0;
let strArr = s.split("");
for(let i = 0;i<len;i++){
sum+=diff[i];
sum = sum%26;
strArr[i] = String.fromCharCode((s[i].charCodeAt()+sum-97+26)%26+97);
}
return strArr.join("");
};
2406. 将区间分为最少组数
给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。
你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。
请你返回 最少 需要划分成多少个组。
如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。
思路：
- 求出重叠区间的最大个数，最少划分的组数 = 最大个数。
理由：假如重叠区间最大个数为 m 个，分成 m +1 ，那么就说明新划分出来的组里的区间无法分到现有的m个分组里 ⇒ 与m个组里的线段都有重叠 ⇒ 那么最大重叠数就是 m + 1， 这和重叠区间最大个数为m个相违背。
/** * @param {number[][]} intervals * @return {number} */ var minGroups = function(intervals) { // 求最大重叠数 intervals.sort((a, b) => b[1] - a[1]) let len = intervals[0][1] let diff = new Array(len+1).fill(0) console.log(diff) for(let i = 0; i < intervals.length; i++){ const [left, right] = intervals[i]; diff[left-1]++; diff[right]--; } let sum = 0; let res = 0; for(let i = 0; i < diff.length-1; i++){ sum += diff[i] res = Math.max(res, sum) } return res; };
d’d
