leetcode
leetcode 751 ~ 800
字母移位

字母移位

难度:

标签:

题目描述

代码结果

运行时间: 100 ms, 内存: 26.7 MB


// Solution using Java Stream
// Here we use Streams to accumulate the total shifts and apply them to each character.
// We reverse the shifts array to make the calculation easier, then convert it back.

import java.util.stream.IntStream;

public class Solution {
    public String shiftingLetters(String s, int[] shifts) {
        char[] chars = s.toCharArray();
        int n = s.length();
        long[] totalShifts = new long[n];
        totalShifts[n - 1] = shifts[n - 1];
        // Calculate total shifts for each character starting from the end
        IntStream.range(0, n - 1)
            .mapToObj(i -> n - 2 - i)
            .forEach(i -> totalShifts[i] = (totalShifts[i + 1] + shifts[i]) % 26);
        // Apply the shifts to each character
        IntStream.range(0, n).forEach(i ->
            chars[i] = (char) ((chars[i] - 'a' + totalShifts[i]) % 26 + 'a')
        );
        return new String(chars);
    }
}

解释

方法:

此题解使用了一种巧妙的方法来避免重复计算多次移位,从而实现高效的字符串转换。首先,计算所有移位的总和,并对26取模,因为字母表循环的周期为26。然后遍历字符串中的每个字符,对于每个字符,计算其应当移位后的新位置,使用ASCII码转换来实现。在每次遍历中,通过减去当前位置的移位数并再次对26取模,动态地更新移位总和,这样可以保证每个字符都移位正确的次数。这种方法有效利用了前缀和思想,减少了重复的计算。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在计算所有移位总和时需要对26取模?
在字母表中,只有26个字母,因此任何关于字母位置的计算都需要对26取模来确保结果不会超出字母表范围。这样做可以实现循环移位,例如,超出'z'的移位可以从'a'开始重新计算。对26取模是为了处理这种周期性,并且使计算更高效,避免处理不必要的大数。
🦆
在更新字符位置时,为什么可以保证`(index + X) % 26`总是返回正确的新位置?
计算`(index + X) % 26`确保了无论X是多少,结果始终在0到25之间,这对应于字母表中的位置。这种计算考虑了所有可能的移位,并将其规范化到一个完整的字母表周期内。这意味着无论原始位置和移位的大小,最终结果总是一个有效的字母位置。
🦆
在逐个字符更新移位总和`X = (X - shifts[i]) % 26`时,是否考虑了负数取模的情况?
是的,这种方法考虑了负数取模的情况。在Python中,当使用负数进行取模运算时,结果保持为非负数,这对于保持移位总和`X`在正确的范围内是必要的。这确保了每次减去一个字符的移位值后,剩余的移位总和仍然是有效的,可以正确应用于后续的字符。
🦆
如果`shifts`数组中的某些元素非常大,对26取模后的影响是什么,是否还是有效的?
即使`shifts`数组中的元素非常大,对这些值取26的模仍然是有效的。这是因为字母表的周期是26,所以任何大于26的移位数在实际效果上等同于它除以26的余数。例如,移位100次和移位100 % 26次产生的效果相同。这样,无论移位值的大小如何,取模操作都保证了计算的正确性和效率。

相关问题