字符串
反转字符串(力扣344.)
-
如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。
毕竟面试官一定不是考察你对库函数的熟悉程度， 如果使用python和java 的同学更需要注意这一点，因为python、java提供的库函数十分丰富。
-
如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。
-
遍历倒置，可以用异或和取temp赋值
class Solution {
public void reverseString(char[] s) {
if(s.length==0||s.length==1){
return;
}
int a = 0;
int b = s.length - 1;
while(b > a){
//用三个异或运算完成swap
// s[b] ^= s[a];
// s[a] ^= s[b];
// s[b] ^= s[a];
char temp = s[a];
s[a] = s[b];
s[b] = temp;
b--;
a++;
}
}
}
反转字符串II(力扣541.)
- 题目：给定一个字符串
s和一个整数k，从字符串开头算起，每计数至2k个字符，就反转这2k字符中的前k个字符。- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
- 如果剩余字符少于
- 以2k为步长，每次判断是否越界；出界时复原数值，并进行接下来的处理
class Solution {
public String reverseStr(String s, int k) {
StringBuffer res = new StringBuffer();
int num = 2 * k;
for(;num < s.length();num += 2 * k){
StringBuffer temp = new StringBuffer();
if(num >= s.length()){
break;
}
temp.append(s.substring(num - 2 * k,num - k));
res.append(temp.reverse());
res.append(s.substring(num - k,num));
}
num -= 2 * k;
if(s.length() - num >= k){
StringBuffer temp = new StringBuffer();
temp.append(s.substring(num,num + k));
res.append(temp.reverse());
res.append(s.substring(num + k,s.length()));
return res.toString();
}else{
StringBuffer temp = new StringBuffer();
temp.append(s.substring(num,s.length()));//substring方法是左闭右开
res.append(temp.reverse());
return res.toString();
}
}
}
要点：
- 必须用stringbuffer才可以变化字符串
- substring方法截取字符串区间是左闭右开
替换空格（剑指offer 05.）
-
题目：请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
-
思路：首先扩充数组到每个空格替换成"%20"之后的大小。
然后从后向前替换空格，也就是双指针法，过程如下：
i指向新长度的末尾，j指向旧长度的末尾。
-
很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
-
先计算字符串长度及空格个数，以此新建结果字符串长度，最后遍历一遍原字符串得到结果
class Solution {
public String replaceSpace(String s) {
int count = 0;
for(int i = 0;i < s.length();i++){
if(s.charAt(i) == ' '){
count++;
}
}
int len = s.length() - 1;
char[] temp = new char[s.length() + 2 * count];
for(int j = temp.length - 1;j >= 0;j--){
if(s.charAt(len) != ' '){
temp[j] = s.charAt(len);
len--;
if(len < 0){
break;
}
continue;
}
temp[j] = '0';
temp[j - 1] = '2';
temp[j - 2] = '%';
j = j - 2;
len--;
}
return new String(temp);
}
}
翻转字符串里的单词(力扣151.)
-
题目：给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个 -
移除多余空格
-
字符串反转
-
单词反转
class Solution {
/**
* 不使用Java内置方法实现
* <p>
* 1.去除首尾以及中间多余空格
* 2.反转整个字符串
* 3.反转各个单词
*/
public String reverseWords(String s) {
// System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
// 1.去除首尾以及中间多余空格
StringBuilder sb = removeSpace(s);
// 2.反转整个字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反转各个单词
reverseEachWord(sb);
return sb.toString();
}
private StringBuilder removeSpace(String s) {
int start = 0;
int end = s.length() - 1;
while(s.charAt(start) == ' '){start++;}
while(s.charAt(end) == ' '){end--;}
StringBuilder sb = new StringBuilder();
while(start <= end){
char c = s.charAt(start);
//对于条件的设定,用或关系和两个不等于
if(c!=' '||sb.charAt(sb.length() - 1)!=' '){
sb.append(c);
}
start++;
}
return sb;
}
/**
* 反转字符串指定区间[start, end]的字符
*/
public void reverseString(StringBuilder sb, int start, int end) {
// System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
while(start < end){
char temp = sb.charAt(start);
sb.setCharAt(start,sb.charAt(end));
sb.setCharAt(end,temp);
start++;
end--;
}
// System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
}
private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int len = sb.length();
while(start<len){
while(end < len&&sb.charAt(end) != ' '){
end++;
}
reverseString(sb,start,end - 1);
start = end+1;
end = start + 1;
}
}
}
左旋转字符串(剑指offer 58-II)
-
题目：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"限制：
1 <= k < s.length <= 10000 -
不能申请额外空间
-
先反转区间为前n的子串，反转区间为n到末尾的子串，反转整个字符串
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
sb.append(s);
reverseString(sb,0,n - 1);
reverseString(sb,n,sb.length() - 1);
return sb.reverse().toString();
}
public void reverseString(StringBuilder sb,int start,int end){
while(start < end){
char temp = sb.charAt(start);
sb.setCharAt(start,sb.charAt(end));
sb.setCharAt(end,temp);
start++;
end--;
}
}
}
//解法二：空间复杂度：O(1)。用原始数组来进行反转操作
//思路为：先整个字符串反转，再反转前面的，最后反转后面 n 个
class Solution {
public String reverseLeftWords(String s, int n) {
char[] chars = s.toCharArray();
reverse(chars, 0, chars.length - 1);
reverse(chars, 0, chars.length - 1 - n);
reverse(chars, chars.length - n, chars.length - 1);
return new String(chars);
}
public void reverse(char[] chars, int left, int right) {
while (left < right) {
chars[left] ^= chars[right];
chars[right] ^= chars[left];
chars[left] ^= chars[right];
left++;
right--;
}
}
}