1. Toy模板网首页
  2. > Toy博客

算法刷题-字符串-反转字符串II

7月前 作者：糖果店的幽灵 分类：Toy博客 阅读(34) 违法举报

这篇具有很好参考价值的文章主要介绍了算法刷题-字符串-反转字符串II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

简单的反转还不够，我要花式反转

541. 反转字符串II

力扣题目链接

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

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = “abcdefg”, k = 2
输出: “bacdfeg”

思路

这道题目其实也是模拟，实现题目中规定的反转规则就可以了。

一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。

其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。

所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

性能如下：

那么这里具体反转的逻辑我们要不要使用库函数呢，其实用不用都可以，使用reverse来实现反转也没毛病，毕竟不是解题关键部分。

C++代码

使用C++库函数reverse的版本如下：

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

那么我们也可以实现自己的reverse函数，其实和题目344. 反转字符串道理是一样的。

下面我实现的reverse函数区间是左闭右闭区间，代码如下：

class Solution {
public:
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s, i, i + k - 1);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
            reverse(s, i, s.size() - 1);
        }
        return s;
    }
};

另一种思路的解法

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size(),pos = 0;
        while(pos < n){
            //剩余字符串大于等于k的情况
            if(pos + k < n) reverse(s.begin() + pos, s.begin() + pos + k);
            //剩余字符串不足k的情况 
            else reverse(s.begin() + pos,s.end());
            pos += 2 * k;
        }
        return s;
    }
};

其他语言版本

C：

char * reverseStr(char * s, int k){
    int len = strlen(s);

    for (int i = 0; i < len; i += (2 * k)) {
        //判断剩余字符是否少于 k
        k = i + k > len ? len - i : k;

        int left = i;
        int right = i + k - 1;
        while (left < right) {
            char temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        }
    }

    return s;
}

Java：

//解法一
class Solution {
    public String reverseStr(String s, int k) {
        StringBuffer res = new StringBuffer();
        int length = s.length();
        int start = 0;
        while (start < length) {
            // 找到k处和2k处
            StringBuffer temp = new StringBuffer();
            // 与length进行判断，如果大于length了，那就将其置为length
            int firstK = (start + k > length) ? length : start + k;
            int secondK = (start + (2 * k) > length) ? length : start + (2 * k);

            //无论start所处位置，至少会反转一次
            temp.append(s.substring(start, firstK));
            res.append(temp.reverse());

            // 如果firstK到secondK之间有元素，这些元素直接放入res里即可。
            if (firstK < secondK) { //此时剩余长度一定大于k。
                res.append(s.substring(firstK, secondK));
            }
            start += (2 * k);
        }
        return res.toString();
    }
}

//解法二（似乎更容易理解点）
//题目的意思其实概括为 每隔2k个反转前k个，尾数不够k个时候全部反转
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i += 2 * k){
            int start = i;
            //这里是判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1, start + k - 1);
            //用异或运算反转 
            while(start < end){
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}


// 解法二还可以用temp来交换数值，会的人更多些
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0;i < ch.length;i += 2 * k){
            int start = i;
            // 判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1,start + k - 1);
            while(start < end){
                
                char temp = ch[start];
                ch[start] = ch[end];
                ch[end] = temp;

                start++;
                end--;
            }
        }
        return new String(ch);
    }
}

// 解法3
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        // 1. 每隔 2k 个字符的前 k 个字符进行反转
        for (int i = 0; i< ch.length; i += 2 * k) {
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= ch.length) {
                reverse(ch, i, i + k -1);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转
            reverse(ch, i, ch.length - 1);
        }
        return  new String(ch);

    }
    // 定义翻转函数
    public void reverse(char[] ch, int i, int j) {
    for (; i < j; i++, j--) {
        char temp  = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }

    }
}

Python：

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        """
        1. 使用range(start, end, step)来确定需要调换的初始位置
        2. 对于字符串s = 'abc'，如果使用s[0:999] ===> 'abc'。字符串末尾如果超过最大长度，则会返回至字符串最后一个值，这个特性可以避免一些边界条件的处理。
        3. 用切片整体替换，而不是一个个替换.
        """
        def reverse_substring(text):
            left, right = 0, len(text) - 1
            while left < right:
                text[left], text[right] = text[right], text[left]
                left += 1
                right -= 1
            return text
        
        res = list(s)

        for cur in range(0, len(s), 2 * k):
            res[cur: cur + k] = reverse_substring(res[cur: cur + k])
        
        return ''.join(res)

Python3 (v2):

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        # Two pointers. Another is inside the loop.
        p = 0
        while p < len(s):
            p2 = p + k
            # Written in this could be more pythonic.
            s = s[:p] + s[p: p2][::-1] + s[p2:]
            p = p + 2 * k
        return s

Go：

func reverseStr(s string, k int) string {
    ss := []byte(s)
    length := len(s)
    for i := 0; i < length; i += 2 * k {
     // 1. 每隔 2k 个字符的前 k 个字符进行反转
     // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
        if i + k <= length {
            reverse(ss[i:i+k])
        } else {
            reverse(ss[i:length])
        }
    }
    return string(ss)
}

func reverse(b []byte) {
    left := 0
    right := len(b) - 1
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}

javaScript:

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    const len = s.length;
    let resArr = s.split(""); 
    for(let i = 0; i < len; i += 2 * k) {  // 每隔 2k 个字符的前 k 个字符进行反转
        let l = i - 1, r = i + k > len ? len : i + k;
        while(++l < --r) [resArr[l], resArr[r]] = [resArr[r], resArr[l]];
    }
    return resArr.join("");
};

TypeScript：

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

Swift:

func reverseStr(_ s: String, _ k: Int) -> String {
    var ch = Array(s)

    for i in stride(from: 0, to: ch.count, by: 2 * k) {
        var left = i
        var right = min(s.count - 1, left + k - 1)
      
        while left < right {
            (ch[left], ch[right]) = (ch[right], ch[left])
            left += 1
            right -= 1
        }
    }
    return String(ch)
}

C#：

public class Solution
{
    public string ReverseStr(string s, int k)
    {
        Span<char> span = s.ToCharArray().AsSpan();
        for (int i = 0; i < span.Length; i += 2 * k)
        {
            span[i + k < span.Length ? i..(i + k) : i..].Reverse();
        }
        return span.ToString();
    }
}

Scala:

版本一: (正常解法)

object Solution {
  def reverseStr(s: String, k: Int): String = {
    val res = s.toCharArray // 转换为Array好处理
    for (i <- s.indices by 2 * k) {
      // 如果i+k大于了res的长度，则需要全部翻转
      if (i + k > res.length) {
        reverse(res, i, s.length - 1)
      } else {
        reverse(res, i, i + k - 1)
      }
    }
    new String(res)
  }
  // 翻转字符串，从start到end
  def reverse(s: Array[Char], start: Int, end: Int): Unit = {
    var (left, right) = (start, end)
    while (left < right) {
      var tmp = s(left)
      s(left) = s(right)
      s(right) = tmp
      left += 1
      right -= 1
    }
  }
}

版本二: 首先利用grouped每隔k个进行分割，再使用zipWithIndex添加每个数组的索引，紧接着利用map做变换，如果索引%2==0则说明需要翻转，否则原封不动，最后再转换为String

object Solution {
  def reverseStr(s: String, k: Int): String = {
    // s = "abcdefg", k = 2
    s.grouped(k) // Iterator ["ab", "cd", "ef", "g"]
      .zipWithIndex // Iterator [("ab", 0), ("cd", 1), ("ef", 2), ("g", 3)]
      .map {
        case (subStr, index) => 
          if (index % 2 == 0) subStr.reverse else subStr
      }
      .mkString
  }
}

版本三: (递归)

import scala.annotation.tailrec

object Solution {
  def reverseStr(s: String, k: Int): String = {
    @tailrec // 这个函数已经优化成了尾递归
    def reverse(s: String, needToReverse: Boolean, history: String): String = {
      // 截取前k个字符（判断是否翻转）
      val subStr = if (needToReverse) s.take(k).reverse else s.take(k)
      // 如果字符串长度小于k，返回结果
      // 否则，对于剩余字符串进行同样的操作
      if (s.length < k) history + subStr
      else reverse(s.drop(k), !needToReverse, history + subStr)
    }
    reverse(s, true, "")
  }
}

Rust:文章来源地址https://www.toymoban.com/news/detail-491132.html

impl Solution {
    pub fn reverse(s: &mut Vec<char>, mut begin: usize, mut end: usize){
        while begin < end {
            let temp = s[begin];
            s[begin] = s[end];
            s[end] = temp;
            begin += 1;
            end -= 1;
        }
    }
    pub fn reverse_str(s: String, k: i32) -> String {
        let len = s.len();
        let k = k as usize;
        let mut s = s.chars().collect::<Vec<_>>();
        for i in (0..len).step_by(2 * k) {
            if i + k < len {
                Self::reverse(&mut s, i, i + k - 1);
            }
            else {
                Self::reverse(&mut s, i, len - 1);
            }
        }
        s.iter().collect::<String>()
    }
}

到了这里，关于算法刷题-字符串-反转字符串II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • leetcode-541. 反转字符串 II

    leetcode-541. 反转字符串 II

    2024年02月16日
    浏览(27)
  • 【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）

    【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）

    题目链接：344. 反转字符串 题目内容： 题目中重点强调了必须 原地修改 输入数组，即不能新建一个数组来完成字符串的反转。我们注意到： 原来下标为0的，反转后是size - 1【原来下标是size - 1的，反转后是0】； 原来下标是1的，反转后是size - 2【原来下标是size -2的，反转后

    2024年02月11日
    浏览(29)
  • c++：string相关的oj题（415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III）

    c++：string相关的oj题（415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III）

    传送门 首先，定义两个指针 index1 和 index2 分别指向两个输入字符串的最后一位，用来从后往前遍历字符串。 然后定义一个变量 next 用来表示进位，初始化为 0。 接下来使用一个循环来遍历两个字符串，直到 index1 和 index2 都小于 0。在循环中，每次取出 index1 和 index2 对应位置

    2024年01月23日
    浏览(40)

  • 【算法第六天7.19】反转字符串，反转字符串||，剑指 Offer 05. 替换空格，反转字符串的单词, 左旋转字符串

    ================================================ 思路 ：以中间为分界线，左右两个边界交换字符，依次向里收缩 思路 ： 首先：字符串转化为字符数组 char[] res = s.toCharArray(); 最后：将数组再转回字符串 return new String(res); 1、循环以2k为单位， 2、在这个2k长的数组中进行反转，需要有首

    2024年02月16日
    浏览(39)

  • Leetcode 557 反转字符串中的单词 III 简单

    给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。 1. 原题链接 Leetcode 557 反转字符串中的单词 III 简单 2. 题目要求 示例 1： 输入：s = “Let’s take LeetCode contest” 输出：“s’teL ekat edoCteeL tsetnoc” 示例 2: 输入： s = “God Ding”

    2024年02月07日
    浏览(31)
  • 【JavaScript数据结构与算法】字符串类（反转字符串中的单词）

    【JavaScript数据结构与算法】字符串类（反转字符串中的单词）

    个人简介 👀 个人主页： 前端杂货铺 🙋‍♂️ 学习方向： 主攻前端方向，也会涉及到服务端（Node.js） 📃 个人状态： 在校大学生一枚，已拿多个前端 offer（秋招） 🚀 未来打算： 为中国的工业软件事业效力 n 年 🥇 推荐学习：🍍前端面试宝典 🍉Vue2 🍋Vue3 🍓Vue2/3项目

    2023年04月09日
    浏览(74)

  • 算法刷题-字符串-左旋转字符串

    反转个字符串还有这么多用处？ 力扣题目链接 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串\\\"abcdefg\\\"和数字2，该函数将返回左旋转两位得到的结果\\\"cdefgab\\\"。 示例 1： 输入: s = “abcde

    2024年02月09日
    浏览(31)
  • 算法通关村第十二关——字符串反转问题解析

    算法通关村第十二关——字符串反转问题解析

    字符串反转是关于字符串算法里的重要问题，虽然不是太难，但需要考虑到一些边界问题。本篇文章就对几道字符串反转题目进行分析。 力扣344题，编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，

    2024年02月10日
    浏览(33)
  • 算法刷题-字符串-重复的子字符串

    算法刷题-字符串-重复的子字符串

    KMP算法还能干这个 力扣题目链接 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。 示例 1: 输入: “abab” 输出: True 解释: 可由子字符串 “ab” 重复两次构成。 示例 2: 输入: “aba” 输出: False 示

    2024年02月09日
    浏览(32)

  • 算法刷题-字符串-翻转字符串里的单词

    综合考察字符串操作的好题。 力扣题目链接 给定一个字符串，逐个翻转字符串中的每个单词。 示例 1： 输入: “the sky is blue” 输出: “blue is sky the” 示例 2： 输入: \\\" hello world! \\\" 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不

    2024年02月09日
    浏览(83)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包