Re: [閒聊] 每日leetcode

[Rushia (早瀬ユウカの体操服 )]

※ 引述《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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1736081925.A.8D0.html
推 oin1104: 大師