业余时间做做算法题还是挺有意思的,这些题目都是每周的限时竞赛题目,新鲜出炉,所以还有很多可以改进的地方。但对我来说,该系列的总结给我带来的是:
本次周赛主要分为一下4道题:
Problem:
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]
这是一道字符逆序操作题,没有什么特别需要指出的东西,简单的一次循环遍历就可以AC。
My First Solution (15ms)
public String reverseStr(String s, int k) {
int len = s.length();
if(len == 0) return "";
StringBuilder sb = new StringBuilder();
int index = 0;
while (index < len){
StringBuilder tmp = new StringBuilder();
for (int i = index; i < k + index && i < len; i++){ // 就是求最小值的情况 Math.min(k + index,len)
tmp.append(s.charAt(i));
}
index += k;
sb.append(tmp.reverse().toString());
for (int i = index; i < k + index && i < len; i++){
sb.append(s.charAt(i));
}
index += k;
}
return sb.toString();
}
这是我看到这赛题第一想到的能够AC的答案,但里面有些细节值得注意的,如在整个遍历过程,我分为了逆序和正序,通过index的while循环来记录,完成index的在遍历的动态控制。为什么没有使用for,因为在我的【算法解题细节网络】中,for在控制index时有些不太灵活。
可优化空间:
i < k + index && i < len
可以由Math.min(K+index,s.length())
来代替。My second Solution(9ms)
public String reverseStr(String s, int k) {
int len = s.length();
if(len == 0) return "";
StringBuilder sb = new StringBuilder();
int index = 0;
while(index < len){
int last = index + k < s.length() ? index+k : s.length();
sb.append(new StringBuilder(s.substring(index, last)).reverse().toString());
index = last;
last = index + k < s.length() ? index + k : s.length();
sb.append(s.substring(index,last));
index = last;
}
return sb.toString();
}
解决方案的运行时间又少了点,看来还是有效果的,有空得研究研究subString()方法咯。做了两点改进,去掉了冗长的判断和while中的for循环。还能优化么?
可优化空间: 1. 如果没有看C++AC解的答案的话,我可能是再也想不出来的,其实我们可以直接对s中要逆序的元素进行操作就可以了。
此时,我们就用到了for循环,而非while了!!!用while也可以吧,没多大关系,但这里for循环代码更优美,各位看观自行品味。
My third solution(9ms)
public String reverseStr(String s, int k) {
char[] res = s.toCharArray();
for (int i = 0; i < s.length(); i += 2 * k) {
int j = Math.min(res.length - 1, i + k - 1);
// 找出开头逆序的所有元素
for (int h = i; h <= (i + j) / 2; h++) { // 进行数组交换
char tmp = res[h];
res[h] = res[i + j - h];
res[i + j - h] = tmp;
}
}
return new String(res);
}
还是9ms,好吧,但未尝不是一个更加优美的答案,思路很简单,把s转换成了char数组,在数组中直接定位要逆序的元素,进行一个逆序交换算法,其余位置不变,返回结果。