Differential

之前我有一篇 《差分+前缀和》的学习笔记，记录了差分的思想和基本用法。这里就只记录灵神题单的刷题记录。

1. LC 1094 拼车

我记得这是哪次每日一题来着，入门差分前缀和了。

差分数组维护每站新增的乘客（当然数量可以是≤0的），每一项在上车对应位置加。下车对应位置减即可。

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1001];
        for (int[] trip : trips) {
            diff[trip[1]] += trip[0];
            diff[trip[2]] -= trip[0];
        }
        for (int i : diff) {
            capacity -= i;
            if(capacity<0){
                return false;
            }
        }
        return true;
    }
}

2. LC 1109 航班预订统计

同样入门题。差分数组维护每站新增座位。对于每个预订项，first(i)增加对应量，而last(i)之后就不再预订这些位置，所以要减掉。

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] ans = new int[n];
        // 我有一计O(n)的差分前缀和，可做此题
        for (int[] booking : bookings) {
            ans[booking[0]-1] += booking[2];
            if(booking[1]<n){
                ans[booking[1]] -= booking[2];
            }
        }
        // 原地更新
        for (int i = 1; i < ans.length; i++) {
            ans[i] += ans[i-1];
        }
        return ans;
    }
}

3. LC 2381 字母移位Ⅱ

也是入门题。差分数组维护每个位置的移位偏移量，前缀和还原。

修改字符的时候，可以利用向左移动1等于向右移动25的技巧来规避掉对于负数的分类讨论。

import java.util.Arrays;

class Solution {
    public String shiftingLetters(String s, int[][] shifts) {
        int[] diff = new int[s.length()];
        int dir ;
        for (int[] shift : shifts) {
            dir = shift[2]==1?1:-1;
            diff[shift[0]] += dir;
            if(shift[1]<s.length()-1){
                diff[shift[1]+1] -= dir;
            }
        }
        // 原地还原
        for (int i = 1; i < diff.length; i++) {
            diff[i] += diff[i-1];
        }
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i++) {
            int offset = (ch[i] - 'a' + diff[i]) % 26;
            if(offset<0){
                ch[i] = (char) ('a'+26+offset);
            }else{
                ch[i] = (char) ('a'+offset);
            }
        }
        return String.valueOf(ch);
    }
}

class Solution {
    public String shiftingLetters(String s, int[][] shifts) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[] diff = new int[n + 1];
        for(int[] shift : shifts){
            int dir = shift[2] == 1 ? 1 : 25;
            diff[shift[0]] += dir;
            diff[shift[1] + 1] -= dir;
        }
        int t = 0;
        for(int i = 0; i < n; i++){
            t += diff[i];
            chars[i] = (char)('a' + (chars[i] + t - 'a') % 26);
        }
        return new String(chars);
    }
}