本文主要是介绍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);}
}
这篇关于Differential的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
