字符串——541. 反转字符串 II

简介: 本专栏按照数组—链表—哈希—字符串—栈与队列—二叉树—回溯—贪心—动态规划—单调栈的顺序刷题,采用代码随想录所给的刷题顺序,一个正确的刷题顺序对算法学习是非常重要的,希望对大家有帮助

1 题目描述

  1. 反转字符串 II

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

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

2 题目示例

示例 1:
输入:s = "abcdefg", k = 2
输出:"bacdfeg"

示例 2:
输入:s = "abcd", k = 2
输出:"bacd"

3 题目提示

1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104

4 思路

方法一:模拟
我们直接按题意进行模拟:反转每个下标从 2k2k 的倍数开始的,长度为 kk 的子串。若该子串长度不足 kk,则反转整个子串。
一些同学可能为了处理逻辑:每隔2k个字符的前k的字符,写了一堆逻辑代码或者再搞一个计数器,来统计2k,再统计前k个字符。

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

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

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

复杂度分析

时间复杂度:O(n),其中 n 是字符串 s 的长度。

空间复杂度:O(1) 或 O(n),取决于使用的语言中字符串类型的性质。如果字符串是可修改的,那么我们可以直接在原字符串上修改,空间复杂度为 O(1),否则需要使用 O(n) 的空间将字符串临时转换为可以修改的数据结构(例如数组),空间复杂度为 O(n)。

5 我的答案

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }

    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}
//解法二(似乎更容易理解点)
//题目的意思其实概括为 每隔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);
    }
}
相关文章
|
1月前
字符串反转
字符串反转
53 14
|
6月前
反转字符串
反转字符串
44 1
|
6月前
|
Python
ptthon字符串的逆序输出
字符串的逆序输出
39 0
|
测试技术 索引
根据首尾字符串截取中间字符串
今天分享一个函数:虽然它非常简单,但是真的很好用!也很常用!比如 “我今天真的很高兴” 这句话,要把 `今天` 截取出来,我们可以直接调用函数拿到结果,不需要匹配索引、也不用写正则!
72 0
撕碎字符串反转【C】
首先我们对题目进行分析,反转字符串就是将数组中的元素位置进行互换从而达到效果,但是当我们对字符串前后进行互换时,会出现”.gnijieb ekil I"这与我们预先的目标不一致,这个题就特殊在这里。我们要进行二次交换,对字符串中的每个单词进行交换,把每一个单词看作一个整体在进行一次数组交换即可。
63 0
逆序字符串 和 字符串的逆序输出 的区别~
逆序字符串 和 字符串的逆序输出 的区别~
110 0
字符串的倒序与大小写转换
字符串的倒序与大小写转换
113 0
|
算法 C++
在 C/C++ 中反转字符串的不同方法
给定一个字符串,编写一个 C/C++ 程序来反转它。
127 0
C/C++编程题之字符串反转
C/C++编程题之字符串反转