344. 回转字符串

标题：
编写一个函数，其作用是将输入的字符串回转过来。输入字符串以字符数组s的方式给出。
不要给另外的数组分配额定的空间，你有必要**原地修正输入数组**、运用 O(1) 的额定空间解决这一问题。

思路：
暴力：直接reverse，可是卡哥说假如这道题的要害部分是用js办法去解决的，那就不要用
双指针：设置两个指针，设置一个循环，判别条件是左指针小于右指针，设置一个临时值，对前后的值进行一个交流，左指针++、右指针–

代码：

// 暴力办法
var reverseString = function(s) {
    return s.reverse()
};
// 双指针
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    let left = 0,right = s.length-1
    while (left<right) {
        let tmp = s[left]
        s[left] = s[right]
        s[right] = tmp
        left++
        right--
    }
    return s
};

优化：

其实我在做的时分就想到了要用扩展运算符，这真的是js的一个神技了，看了大佬的解法，差不多，对代码格式做一个简化

代码：

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    let left = -1,right = s.length
    while (++left<--right) {
        [s[left],s[right]] = [s[right],s[left]]
    }
};

总结：

比较简单的一道题，调查的是对字符串底回转的底层原理

541. 回转字符串 II

标题：
给定一个字符串s和一个整数k，从字符串开头算起，每计数至2k个字符，就回转这2k字符中的前k个字符。

假如剩下字符少于k个，则将剩下字符悉数回转。
假如剩下字符小于2k但大于或等于k个，则回转前k个字符，其他字符保持原样。

思路：

把字符串转换为字符串数组
设置一个索引值index=0
设置一个循环，判别条件是索引值乘k小于数组的长度
1. 设置一个规模，这个规模是要回转字符串的规模，假如（索引值+1）乘k的值大于字符串的长度，那么就要把剩下的字符串悉数回转，所以规模是字符串的长度，反之就是取当时（索引+1）乘k作为规模
2. 设置一个左指针为（index*k-1），作为每次循环开端的0-2k的初始值。设置一个右指针取range规模的值。
3. 设置一个循环，判别条件是左指针小于右指针
  1. 做一个数组内元素的替换操作。
  2. left++、right–，写在判别条件内。
4. index+=2，更新索引的值。
把数组转换为字符串后回来。

代码：

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    const res = s.split('')
    let index = 0
    while (index*k < res.length) {
        const range = (index+1)*k>res.length?res.length:(index+1)*k
        let left = index*k-1,right = range
        while (++left<--right) {
            [res[left],res[right]] = [res[right],res[left]]
        } 
        index +=2
    }
    return res.join('')
};

优化：

一些同学或许为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或许再搞一个计数器，来计算2k，再计算前k个字符。
好的，上面说的就是我，代码随想录的逻辑愈加简练，简化了我的设置索引的逻辑，设置一个循环，每次将索引值移动2k

代码：

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    const res = s.split('')
    for (let i = 0; i<res.length;i+=2*k) {
        let left = i-1,right = i+k>res.length?res.length:i+k
        while (++left<--right) {
            [res[left],res[right]] = [res[right],res[left]]
        }
    }
    return res.join('')
};

总结：

看了代码随想录的思路，发现自己确实想的太麻烦了，可是基本思路没变。

剑指 Offer 05. 替换空格

标题：
请实现一个函数，把字符串s中的每个空格替换成”%20″。

思路：
一开端没看懂标题什么意思，瞥了一下代码随想录的思路，懂了，可是也瞥到了从后遍历的双指针思路，我自己写一下试试吧。

先设置一个计数器count=0
把字符串转换成数组
设置一个左指针值为当时数组的长度
遍历数组，每找到一个空格，计数器+1
设置一个循环，次数为计数器乘2，由于是把占位为1的空格，替换成占位为3的%20，所以是每个空格要增加本来两倍的占位巨细。在循环中在数组结尾，增加循环次数的空格。
设置一个右指针值为改换后的数组的长度。
设置一个循环，判别条件是左指针小于右指针。
1. 判别当时左指针是否为空格，假如是，则对右指针进行单独的改换，填入%20，完成后同时把两个指针左移并跳出本次循环
2. 把左指针的值赋值给右指针
3. 左右指针同时左移
把数组转换为字符串回来
写完以后感觉自己的代码很笨拙，可是总之写出来了。

代码：

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(str) {
    const s = str.split('')
    let count = 0,left = s.length
    for (let i = 0;i<s.length;i++) {
        if (s[i]===' ') {
            count++
        }
    }
    for (let i = 0;i<count*2;i++) {
        s.push(' ')
    }
    console.log(s)
    let right = s.length
    while (--left < --right) {
        if (s[left]===' ') {
            s[right] = 0
            right--
            s[right] = 2
            right--
            s[right] = '%'
            continue
        }
        s[right] = s[left]
    }
    return s.join('')
};

优化：

看了一下大佬的写法，基本思路一样，仅仅把一些代码逻辑简化了，代码愈加简练。

对右指针直接用左指针+计数器*2，我用的是循环
把一切指针左移的操作放在赋值中一并执行

代码：

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(str) {
    const s = str.split('')
    let count = 0,left = s.length
    for (let i = 0;i<s.length;i++) {
        count = s[i]===' '?count+1:count
    }
    let right = s.length+count*2
    while (--left < --right) {
        if (s[left]===' ') {
            s[right--] = 0
            s[right--] = 2
            s[right] = '%'
            continue
        }
        s[right] = s[left]
    }
    return s.join('')
};

总结：

这道题的思路比较重要，写完这道题也知道了，做一些填充类算法题的时分，从后向前遍历是一种非常常用的办法

151. 回转字符串中的单词

标题：
给你一个字符串s，请你回转字符串中单词的次序。
单词是由非空格字符组成的字符串。s中运用至少一个空格将字符串中的单词分隔开。
回来单词次序倒置且单词之间用单个空格衔接的成果字符串。
留意：输入字符串s中或许会存在前导空格、跟随空格或许单词间的多个空格。回来的成果字符串中，单词间应当仅用单个空格分隔，且不包括任何额定的空格。

思路：
运用二维数组，把每个单词作为内层数组保存在外层数组中，然后对外层数组进行回转。

首先声明一个外层空数组
把字符串转换为一个数组
声明一个内层空数组
对字符串数组进行循环遍历
1. 判别假如当时的数组元素不为空格，那么把当时元素增加到内层数组中
2. 判别假如当时元素为空格并且内层数组不为空（扫除多个连续空格的状况）或许当时索引为字符串最终一个元素（包括结尾单词的状况），那么把内层数组增加到外层数组中，内层数组置空
把外层数组回转并转换为字符串后，运用trim删除首尾空格后回来（当然可以不用trim，在增加内层数组到外层数组时多增加一个并且结尾元素不为空格的条件就可以）

代码：

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    const arr = s.split('')
    const res = []
    let subRes = []
    for (let i =0;i<arr.length;i++) {
        if (arr[i]!==' '){
            subRes.push(arr[i])
        }
        if (arr[i]===' '&&subRes.length||i === arr.length-1&&arr[i]!==' ') {
            res.push(subRes.join(''))
            subRes = []
        }
    }
    return res.reverse().join(' ').trim()
};

优化：

看了一下代码随想录的思路，是分为三步，第一步移除多余空格，第二步把数组回转，第三步对每一个单词进行回转。

代码：

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    const arr = deleteSpace(s.split(''))
    arr.reverse()
    let start = 0
    for (let i =0;i<=arr.length;i++) {
        if (arr[i]===' '||i===arr.length){
            reverseWord(arr,start,i-1)
            start = i+1 
        }
    }
    return arr.join('')
};
const deleteSpace = (arr) => {
    let slow,fast
    slow = fast = 0
    while (fast<arr.length) {
        if (arr[fast]=== ' '&&(fast===0||arr[fast-1]===' ')) {
            fast++
        }else {
            arr[slow++] = arr[fast++]
        }
    }
    const index = arr[slow-1]=== ' '?slow-1:slow
    return arr.slice(0,index)
}
const reverseWord = (arr,start,end) => {
    while (start<end) {
        [arr[start],arr[end]] = [arr[end],arr[start]]
        start++
        end--
    }
}

总结：

代码随想录的代码结构愈加清晰，学习这种清晰的梳理思路的能力。

剑指 Offer 58 – II. 左旋转字符串

标题：
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比方，输入字符串”abcdefg”和数字2，该函数将回来左旋转两位得到的成果”cdefgab”。

思路：

把字符串转换为数组
声明一个空数组left，用来接收要左旋的元素
对数组进行循环遍历，次数为输入的整数n
1. 每次循环把arr首位的元素移除放入left数组里
把原先的数组arr和新的左旋数组拼接后转换为字符串回来

代码：

/**
 * @param {string} s
 * @param {number} n
 * @return {string}
 */
var reverseLeftWords = function(s, n) {
    const arr = s.split('')
    const left =[]
    for (let i =0;i<n;i++) {
        left.push(arr.shift())
        // console.log(arr.shift())
    }
    return arr.concat(left).join('')
};

优化：

规则不能运用额定空间来解决这道题，思路是以n的方位做一个分界，把前后的字符串别离回转，然后再把整个字符串回转。
可以直接用151中对单词进行回转的办法来操作.

代码：

/**
 * @param {string} s
 * @param {number} n
 * @return {string}
 */
var reverseLeftWords = function(s, n) {
    const arr = s.split('')
    reverseWord(arr,0,n-1)
    reverseWord(arr,n,arr.length-1)
    return arr.reverse().join('')
};
const reverseWord = (arr,start,end) => {
    while (start<end) {
        [arr[start],arr[end]] = [arr[end],arr[start]]
        start++
        end--
    }
}

总结：

这道题比较简单，假如是在原有字符串上进行修正，需求思考一下，可是在做完了151以后，想出这种思路并不难。

Day8总结

今天做了许多关于字符串回转的标题，平时的学习日子中对字符串触摸的比较多，所以也比较熟悉，今天的标题许多都能用自己的办法做出来，可是和最优的思路仍是不一样的，收成许多。

代码随想录算法训练营第八天｜344.反转字符串、541. 反转字符串II、剑指Offer 05.替换空格、151.翻转字符串里的单词、剑指Offer58-II.

344. 回转字符串

优化：

总结：

541. 回转字符串 II

优化：

总结：

剑指 Offer 05. 替换空格

优化：

总结：

151. 回转字符串中的单词

优化：

总结：

剑指 Offer 58 – II. 左旋转字符串

优化：

总结：

Day8总结

作者信息

推广

代码随想录算法训练营第八天｜344.反转字符串、541. 反转字符串II、剑指Offer 05.替换空格、151.翻转字符串里的单词、剑指Offer58-II.

344. 回转字符串

优化：

总结：

541. 回转字符串 II

优化：

总结：

剑指 Offer 05. 替换空格

优化：

总结：

151. 回转字符串中的单词

优化：

总结：

剑指 Offer 58 – II. 左旋转字符串

优化：

总结：

Day8总结

相关文章

手写裁剪图片的方案以及遇到问题的解决历程

为什么前端项目里font-weight值不推荐使用数字，而是字重描述符？

iOS 如何在Swift项目中导入OC头文件？

Databend 开源周报第 96 期

作者信息

推广