Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間11月前 (2025/01/05 20:58)推噓1(1推 0噓 0→)

※ 引述《dont (dont)》之銘言： : 2381. Shifting Letters II 測資的s長度給 5*10^4，然後可以操作 5*10^4 次，如果操作 [0:n] 5*10^4 次一定會 TLE，對區間進行高效率操作可以想到差分數組，只是因為可以左移和右移需要多考慮負數的情況，操作 shift 完後用差分數組還原位移後字串就好。 Java Code: ---------------------------------------------------------- class Solution { public String shiftingLetters(String s, int[][] shifts) { int n = s.length(); int[] diff = new int[n]; diff[0] = s.charAt(0) - 'a'; for (int i = 1; i < n; i++) { diff[i] = matchLetter(s.charAt(i) - s.charAt(i - 1)); } for (int[] shift : shifts) { int i = shift[0], j = shift[1], dir = shift[2]; doShift(diff, i, j, dir); } StringBuilder sb = new StringBuilder(); int ch = 0; for (int i = 0; i < n; i++) { ch = matchLetter(ch + diff[i]); sb.append((char) ('a' + ch)); } return sb.toString(); } int matchLetter(int n) { return n < 0 ? n + 26 : n % 26; } void doShift(int[] diff, int i, int j, int dir) { int x = (dir == 0 ? -1 : 1); diff[i] = matchLetter(diff[i] + x); if (j + 1 < diff.length) { diff[j + 1] = matchLetter(diff[j + 1] - x); } } } ---------------------------------------------------------- -- https://i.imgur.com/ZfdGodg.jpeg