当前位置：首页 > article >正文

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

article 2025/1/18 13:05:59

差分数组案例

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