代码随想录算法训练营第七天 | leetcode：反转字符串,反转字符串||,翻转字符串里的单词
0 / 0 / 创建于 1年前 /
_zzh 的个人博客
Problem: 151. 反转字符串中的单词
需要注意的问题
- 反转后的字符串中不能存在前导空格和尾随空格。
- 如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
- 字符串中使用至少一个空格将字符串中的 单词 分隔开。
- 返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
解题方法
- 去除多余空格。在遍历字符串时，把所有空格都去掉，并且在单词后面加上新的空格。具体逻辑为：使用快慢指针，初始化都指向字符串起始位置。当快指针遍历不为空格时，把快指针的值赋给慢指针位置，慢指针判断不是0起始位置，则在后一位赋值为空格。这样快指针赋值完成的同时，后面时刻保持有一位空格。最后需要裁剪慢指针位置。
- 反转字符串，去除多余空格，再把整个字符串反转之后，根据空格为标志，把单词再反转回来。就达到反转单词的效果了。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)
解法1
/**
* @param String $s
* @return String
*/
function reverseWords($s) {
$this->removeExtraSpaces($s);
$this->reverseString($s, 0 , strlen($s)-1);
$slow = 0;
//这里<= strlen($s) 是需要在字符串最后 再多移一位与单词后一位的空格位置匹配，统一处理$fast-1；
for($fast = 0; $fast <= strlen($s); $fast++){
if($fast == strlen($s) || $s[$fast] == ' '){
$this->reverseString($s, $slow, $fast-1);
$slow = $fast + 1;
}
}
return $s;
}
//去除多余空格
function removeExtraSpaces(&$s){
$slow = 0;
for($fast = 0; $fast < strlen($s); $fast++){
//快指针指向的值不等于空时把快指针的值放到慢指针位置
if($s[$fast] != ' '){
//第一次进来会跳过，后续给慢指针赋值为空格
if($slow != 0){
$s[$slow] = ' ';
$slow++;
}
//while结束此时slow指向第一个单词的结尾
while($fast < strlen($s) && $s[$fast] != ' '){
$s[$slow] = $s[$fast];
$slow++;
$fast++;
}
}
}
//循环结束后$slow指向更新后的字符串最后一位，需要裁剪掉后续的
$s = substr($s,0,$slow);
return;
}
//反转字符串
function reverseString(&$s, $start, $end){
for($i = $start,$j = $end; $i < $j; $i++,$j--){
$temp = $s[$i];
$s[$i] = $s[$j];
$s[$j] = $temp;
}
return;
}Problem: 344. 反转字符串
解题方法
这题比较简单，左右双指针相向移动，利用temp中间变量交换值即可。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)
code
function reverseString(&$s) {
$left = 0;
$right = count($s) - 1;
while($left < $right){
$temp = $s[$right];
$s[$right] = $s[$left];
$s[$left] = $temp;
$left++;
$right--;
}
return $s;
}Problem: 541. 反转字符串 II
需要注意的问题
- for循环的间隔递进关系如何处理
- 边界处理
- 如果剩余字符少于 k 个，则将剩余字符全部反转。
- 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
- k = 1,不用处理
解题方法
这题与上题逻辑基本相同，for循环中多了区间判断与反转区间处理。以2 * k为循环递进间隔，再到 2 * k区间中分别处理反转逻辑。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)
code
class Solution {
/**
* @param String $s
* @param Integer $k
* @return String
*/
function reverseStr($s, $k) {
if($k==1){
return $s;
}
$len = strlen($s);
//其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。
for($i = 0; $i < $len; $i += (2 * $k)){
$left = $i;
//判断反转右边界时需要判断是否超过字符串s长度，超过则右边界为strlen($s) - 1，没超过则$i + $k - 1
$right = min(strlen($s) - 1, $i + $k - 1);
while($left < $right){
$temp = $s[$right];
$s[$right] = $s[$left];
$s[$left] = $temp;
$left++;
$right--;
}
}
return $s;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号