第一题344.反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
ψ(｀∇´)ψ 我的思路
- 取到字符串的中点，依次交换前后两部分的位置
package string;
public class ReverseString {
public static void reverseString(char[] s) {
char temp;
for (int i = 0; i < (s.length)/2; i++) {
temp = s[s.length-i-1];
s[s.length-i-1] = s[i];
s[i] = temp;
}
}
}
时间复杂度为O(n)
- 我记得有个reverse方法可以反转字符串，但是当时做题的时候没有找到使用方法，提交后查了一下，reverse是StringBuilder和String Buffer的方法
第二题 541. 反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
- 真费劲呐，读题读了半天，这题目翻译过来就是
每隔2k个反转前k个，尾数不够k个时候全部反转
ψ(｀∇´)ψ 我的思路
package string;
public class ReverseStr {
public static String reverseStr(String s, int k) {
StringBuilder sb = new StringBuilder();
StringBuilder res = new StringBuilder();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if((i+1)%(2*k)==0){//每隔2k
sb.append(chars,(i-2*k+1),k).reverse();
res.append(sb);//反转前k个字符串
sb.delete(0,k);//清空字符串
res.append(chars,(i-k+1),k);//拼接后k个字符串
}
}
//长度不足2k的剩下的字符串
String left = s.substring(res.length());
if(left.length()>=k){
sb.append(chars,(res.length()),k).reverse();
res.append(sb);//反转前k个字符串
sb.delete(0,k);//清空字符串
int len = res.length();
res.append(chars,(res.length()),(s.length()-len));
} else {
sb.append(left).reverse();
res.append(sb);//把剩下的所有的字符串反转并追加
}
return res.toString();
}
public static void main(String[] args) {
String res = reverseStr("abcd", 2);
System.out.println(res);
}
}
时间复杂度为O(n)
- 本来想着一个StringBuilder 就能解决问题，结果发现反转的时候，需要局部反转再拼接，所以只能用两个StringBuilder
第三题 剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
ψ(｀∇´)ψ 我的思路
package string;
public class ReplaceSpace {
public static String replaceSpace(String s) {//方法一：遍历替换
StringBuilder sb = new StringBuilder();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i]==' '){
sb.append("%20");
} else {
sb.append(chars[i]);
}
}
return sb.toString();
}
public static String replaceSpace2(String s) {//方法二：API
String replace = s.replace(" ","%20");
return replace;
}
public static void main(String[] args) {
String s = "We are happy.";
System.out.println(replaceSpace2(s));
}
}
时间复杂度为O(n)
第四题 151. 反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。