LeetCode Weekly Contest 23 之 541. Reverse String II
LeetCode Weekly Contest 23 之 541. Reverse String II
LeetCode Weekly Contest 23
业余时间做做算法题还是挺有意思的，这些题目都是每周的限时竞赛题目，新鲜出炉，所以还有很多可以改进的地方。但对我来说，该系列的总结给我带来的是：
- 在有限的时间内，突破自身能力限制，在没有任何算法经验的情况下，训练自己的临时解题能力，能够极大效率地提升算法能力。
- 记录整个解题的思维过程，以及赛后的复盘，力求发现赛题背后的本质，举一反三。
- 完善算法细节，构建一整套算法解题印象，不断完善自己的解题方法树。算法逻辑决定解题框架，而算法细节决定成败，两者缺一不可。
赛题
本次周赛主要分为一下4道题：
- 541 Reverse String II (3分)
- 539 Minimum Time Difference (5分)
- 536 Construct Binary Tree from String (6分)
- 527 Word Abbreviation (8分)
541 Reverse String II
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时有些不太灵活。
可优化空间：
- 对于while中的for循环，完全可以去掉，这里只需知道逆序元素的头index和尾index。
- 在for循环的判断语句
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数组，在数组中直接定位要逆序的元素，进行一个逆序交换算法，其余位置不变，返回结果。