当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.541.Reverse String II

LeetCode.541.Reverse String II


题目描述

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

  1. The string consists of lower English letters only.
  2. Length of the given string and k will in the range [1, 10000]

解题过程

典型的字符串操作题,注意考虑全面就行,尤其注意不足k个或者不足2k个字符时的情况。
我的代码用的全都是Java String类操作,导致速度很慢,不过为了更熟悉Java类,还是应该多使用现成的类方法。

class Solution {
    public String reverseStr(String s, int k) {
        StringBuilder result = new StringBuilder("");
        int i=0;
        int lastIndex=0;//上一个下标位
        int lastEvenEndIndex=-1;//上一个偶数段结束位
        while(i<s.length()){
            if((i+1)%k==0){//遍历到一个完整的奇数段
                result.append(new StringBuilder(s.substring(i-k+1, i+1)).reverse());//加上奇数段反转
                result.append(s.substring(i+1,i+k+1>s.length() ? s.length() : i+k+1));//加上偶数段
                lastIndex = i;//上一个下标位
                lastEvenEndIndex = i+k;//上一个偶数段结束位
                i+=k+1;//跳过偶数段
            }else{
                lastIndex = i;
                i++;
            }
        }
        if(lastIndex == i-1){//在奇数段结束,即剩余字符不足k个
            result.append(new StringBuilder(s.substring(lastEvenEndIndex+1)).reverse());//加上剩余奇数段的反转
        }
        return result.toString();
    }
}

提交后发现速度快的代码都是先转为char数组再操作,当然具体的方法各不相同。其中最简洁清晰的是下面这个:

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

GitHub代码


上一篇 LeetCode.283.Move Zeroes

下一篇 LeetCode.349.Intersection of Two Arrays

阅读
483
阅读预计2分钟
创建日期 2018-01-26
修改日期 2018-01-29
类别
百度推荐