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

030

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 个字符，其余字符保持原样。

思路：

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

代码：

/**








 * @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″。

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

  1. 先设置一个计数器count=0
  2. 把字符串转换成数组
  3. 设置一个左指针值为当前数组的长度
  4. 遍历数组，每找到一个空格，计数器+1
  5. 设置一个循环，次数为计数器乘2，因为是把占位为1的空格，替换成占位为3的%20，所以是每个空格要增加原来两倍的占位大小。在循环中在数组末尾，添加循环次数的空格。
  6. 设置一个右指针值为变换后的数组的长度。
  7. 设置一个循环，判断条件是左指针小于右指针。
    1. 判断当前左指针是否为空格，如果是，则对右指针进行单独的变换，填入%20，完成后同时把两个指针左移并跳出本次循环
    2. 把左指针的值赋值给右指针
    3. 左右指针同时左移
  8. 把数组转换为字符串返回
    写完以后感觉自己的代码很笨拙，但是总归写出来了。

代码：

/**








 * @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('')
};

优化：

看了一下大佬的写法，基本思路一样，只是把一些代码逻辑简化了，代码更加简洁。

  1. 对右指针直接用左指针+计数器*2，我用的是循环
  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. 把字符串转换为一个数组
  3. 声明一个内层空数组
  4. 对字符串数组进行循环遍历
    1. 判断如果当前的数组元素不为空格，那么把当前元素添加到内层数组中
    2. 判断如果当前元素为空格并且内层数组不为空（排除多个连续空格的情况）或者当前索引为字符串最后一个元素（包含末尾单词的情况），那么把内层数组添加到外层数组中，内层数组置空
  5. 把外层数组反转并转换为字符串后，使用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”。

思路：

  1. 把字符串转换为数组
  2. 声明一个空数组left，用来接收要左旋的元素
  3. 对数组进行循环遍历，次数为输入的整数n
    1. 每次循环把arr首位的元素移除放入left数组里
  4. 把原先的数组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总结

今天做了很多关于字符串反转的题目，平时的学习生活中对字符串接触的比较多，所以也比较熟悉，今天的题目很多都能用自己的方法做出来，但是和最优的思路还是不一样的，收获很多。

© 版权声明
文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。
THE END
代码人生
# 算法
喜欢就支持一下吧
点赞0

Warning: mysqli_query(): (HY000/3): Error writing file '/tmp/MYRcCMyc' (Errcode: 28 - No space left on device) in /www/wwwroot/583.cn/wp-includes/class-wpdb.php on line 2345
admin的头像-五八三
相关推荐
揭秘足球串子投注：多串多，一场赢了全赢？如何计算浮动奖金？-五八三
揭秘足球串子投注：多串多，一场赢了全赢？如何计算浮动奖金？
揭秘足球串子投注：多串多，一场赢了全赢？如何计算浮动奖金？
2年前 404
快速玩转 Llama2！阿里云机器学习 PAI 推出最佳实践（二）——全参数微调训练-五八三
快速玩转 Llama2！阿里云机器学习 PAI 推出最佳实践（二）——全参数微调训练
快速玩转 Llama2！阿里云机器学习 PAI 推出最佳实践（二）——全参数微调训练
2年前 124
ByteHouse+Apache Airflow：高效简化数据管理流程-五八三
ByteHouse+Apache Airflow：高效简化数据管理流程
ByteHouse+Apache Airflow：高效简化数据管理流程
2年前 99
attention总结(初版)-五八三
attention总结(初版)
attention总结(初版)
2年前 88
源码解析Collections.sort ——从一个逃过单测的 bug 说起 | 京东云技术团队-五八三
源码解析Collections.sort ——从一个逃过单测的 bug 说起 | 京东云技术团队
源码解析Collections.sort ——从一个逃过单测的 bug 说起 | 京东云技术团队
2年前 82
简单了解下最近正火的SwissTable-五八三
简单了解下最近正火的SwissTable
简单了解下最近正火的SwissTable
2年前 73
评论 抢沙发
头像
欢迎您留下宝贵的见解！
提交
头像

昵称

图形验证码
取消
昵称

请填写用户信息：

  • 昵称(必填)
  • 邮箱(必填)
代码

请输入代码：

确认
图片
文章目录
文章目录
热门推荐