移动字母 II-php教程-PHP中文网

移动字母 II

Mary-Kate Olsen

发布： 2025-01-05 22:30:39

原创

319 人浏览过

Shifting Letters II

2381。移动字母 II

难度：中等

主题：数组、字符串、前缀和

给定一个由小写英文字母组成的字符串 s 和一个二维整数数组 shifts，其中 shifts[i] = [start_i, end_i, Direction_i]。对于每个 i，shift s 中的字符从索引开始_i 到索引结束_i（包含）向前 if 方向_i = 1，或者如果方向_i = 则向后移动字符0.

移动字符向前意味着将其替换为字母表中的下一个字母（环绕以使“z”变成“a”）。同样，向后移动字符意味着将其替换为字母表中的前一个字母（环绕以使“a”变成“z”）。

应用所有此类转换到 s 后的最终字符串。

示例1：

输入： s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
输出：“ace”
解释： 首先，将索引 0 的字符向后移动到索引 1。现在 s =“扎克”。

示例2：

输入： s = "dztz", shifts = [[0,0,0],[1,1,1]]
输出：“catz”
说明：首先将索引0处的字符向后移动到索引0处。现在 s =“cztz”。

约束：

_{i_{0 i_{s 由小写英文字母组成。}}}

提示：

解决方案：

我们需要避免每次移位都将字符一个一个地移动，因为这对于大输入来说太慢了。相反，我们可以通过利用称为

前缀总和. 的技术来使用更优化的方法。

步骤：

标记移位边界：我们不是立即移位每个字符，而是在每个范围的开始和结束处标记移位效果。
应用前缀和：标记所有移位后，我们可以使用前缀和技术计算每个字符的累积移位。这使我们能够有效地将累积移位应用于每个字符。
执行移位：一旦我们知道每个字符的总移位，我们就可以将移位（向前或向后）应用于字符串。

让我们用 PHP 实现这个解决方案：2381。移动字母 II

<?php
/**
 * @param String $s
 * @param Integer[][] $shifts
 * @return String
 */
function shiftingLetters($s, $shifts) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test the function
$s1 = "abc";
$shifts1 = [[0, 1, 0], [1, 2, 1], [0, 2, 1]];
echo shiftingLetters($s1, $shifts1) . "\n";  // Output: "ace"

$s2 = "dztz";
$shifts2 = [[0, 0, 0], [1, 1, 1]];
echo shiftingLetters($s2, $shifts2) . "\n";  // Output: "catz"
?>

登录后复制

解释：

对于每个移位 [开始、结束、方向]，我们将在开始处递增移位数组并在结束时递减 1。这使我们能够跟踪移位范围的开始和结束。
处理完所有移位后，我们对移位数组应用前缀和，以获得每个索引处的累积移位。
最后，我们将累积移位应用于字符串中的每个字符。

代码说明：

输入解析：我们将输入字符串 s 转换为字符数组，以便于操作。
移位数组：我们将大小为 n 1 的移位数组初始化为零。该数组用于跟踪移位效果。对于每个班次 [开始、结束、方向]，我们调整 shift[start] 和 shift[end 1] 处的值以反映班次的开始和结束。
前缀总和：我们通过迭代移位数组并维护移位的累积和来计算每个字符的总移位。
字符移位：对于字符串中的每个字符，我们使用公式 (ord(currentChar) - ord('a')totalShift) % 26 计算最终的移位字符，这说明了字符串的循环性质字母表。
返回结果：将字符数组转回字符串并返回，得到最终的字符串。