代码随想录算法训练营第七天 | leetcode:反转字符串,反转字符串||,翻转字符串里的单词

Problem: 151. 反转字符串中的单词

需要注意的问题

  1. 反转后的字符串中不能存在前导空格和尾随空格。
  2. 如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。
  3. 字符串中使用至少一个空格将字符串中的 单词 分隔开。
  4. 返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

解题方法

  1. 去除多余空格。在遍历字符串时,把所有空格都去掉,并且在单词后面加上新的空格。具体逻辑为:使用快慢指针,初始化都指向字符串起始位置。当快指针遍历不为空格时,把快指针的值赋给慢指针位置,慢指针判断不是0起始位置,则在后一位赋值为空格。这样快指针赋值完成的同时,后面时刻保持有一位空格。最后需要裁剪慢指针位置。
  2. 反转字符串,去除多余空格,再把整个字符串反转之后,根据空格为标志,把单词再反转回来。就达到反转单词的效果了。
    代码随想录算法训练营第五天 | leetcode:344. 反转字符串,541. 反转字符串 II ,151. 反转字符串中的单词

复杂度

时间复杂度:

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

需要注意的问题

  1. for循环的间隔递进关系如何处理
  2. 边界处理
    • 如果剩余字符少于 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 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!