难度: Easy
Submission
运行时间: 24 ms
内存: 0.0 MB
from typing import List
class Solution:
def stringShift(self, s: str, shift: List[List[int]]) -> str:
total_shift = 0
# 计算总的移动位数
for direction, amount in shift:
if direction == 0: # 左移
total_shift -= amount
else: # 右移
total_shift += amount
# 处理移动位数超过字符串长度的情况
total_shift %= len(s)
# 根据移动位数构造结果字符串
if total_shift == 0:
return s
elif total_shift > 0:
return s[-total_shift:] + s[:-total_shift]
else:
return s[-total_shift:] + s[:-total_shift]
Explain
题解的核心思想是通过累积所有的移动指令来确定字符串s最终的位置。首先，初始化一个变量total_shift来表示总的移动位数。接着，遍历每一个移动指令，根据指令的方向（左移为0，右移为1），更新total_shift的值。左移时减少total_shift，右移时增加total_shift。完成所有指令后，使用total_shift对字符串长度进行取模操作，以处理总移动次数超过字符串长度的情况。最后，根据total_shift的值，使用字符串切片操作来生成并返回最终的字符串。如果total_shift为0，意味着移动后字符串位置不变，直接返回原字符串；如果total_shift大于0，进行右移操作；如果小于0，进行左移操作。
时间复杂度: O(n + m)
空间复杂度: O(1)
from typing import List
class Solution:
def stringShift(self, s: str, shift: List[List[int]]) -> str:
total_shift = 0
# 计算总的移动位数
for direction, amount in shift:
if direction == 0: # 左移
total_shift -= amount
else: # 右移
total_shift += amount
# 处理移动位数超过字符串长度的情况
total_shift %= len(s)
# 根据移动位数构造结果字符串
if total_shift == 0:
return s
elif total_shift > 0:
return s[-total_shift:] + s[:-total_shift] # 右移操作
else:
return s[-total_shift:] + s[:-total_shift] # 左移操作（这里和右移使用相同的代码，因为已经取模处理）
Explore
在处理字符串移动时需要对总移动次数进行取模操作，是为了优化性能并处理边界情况。取模操作可以将移动次数减少到小于或等于字符串长度的非负整数，这意味着移动操作可以在一轮内完成。如果不进行取模，当移动次数大于字符串长度时，会导致不必要的重复移动，因为每移动字符串长度那么多次，字符串实际上会回到原始位置。通过取模，我们确保每次操作都是必要且高效的。
题解中的处理方法是正确的。在取模操作之后，如果total_shift为负值，实际上表示的是应该向左移动的次数。但是，向左移动负的total_shift次等价于向右移动len(s) - (-total_shift)次（即字符串长度减去负的移动次数）。因此，使用右移的代码片段来处理这种情况是合理的，它避免了再次计算相对的左移次数，从而简化了代码逻辑。
理论上，在累计移动指令时就可以提前判断并处理total_shift为0的情况。这可以通过在每次更新total_shift后立即进行取模操作，并检查其结果是否为0来实现。如果在任何点total_shift为0，意味着当前的移动指令使字符串恢复到原始位置，可以立即返回原字符串。这种方法可以减少不必要的计算和处理，提高算法的效率。然而，这需要额外的条件检查，可能会略微增加每次循环的计算负担。