【LeetCode每日一题】2381. 字母移位 II&&2406. 将区间分为最少组数 (差分数组)_leetcode 字母位移

差分数组案例

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("");
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
    };
    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

d’d