ps：follow 代码随想录
剑指Offer 05 替换空格
题目描述：
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
解析：
在Java中可以使用str.reverseAll(String old, String new)直接替换。
在这里，需要自己实现一个函数完成。
双指针：因为是把一个字符(空格)替换成三个字符(%20)，所以需要扩大字符串长度以及移动空格后面的字符。
针对扩充数据：可以计算出空格的个数，然后扩充原数组，不必开辟新的空间针对移动：可以从后向前遍历数组，避免移动指针。
解答：
class Solution {
public String replaceSpace(String s) {
if(s.length() == 0 && s == null) return s;
StringBuffer stringBuffer = new StringBuffer();
//计算需要扩充后的字符串长度
for(char i : s.toCharArray()){
if(i == 's'){
//扩充成2倍
stringBuffer.append(" ");
}
}
if(stringBuffer.length() == 0){
return s;
}
int left = s.length() - 1;
s += stringBuffer.toString();
int right = s.length() - 1;
char[] charStr = s.toCharArray();
while(left >= 0){
if(charStr[left] == 's'){
charStr[right--] = '0';
charStr[right--] = '2';
charStr[right--] = '%';
}else{
charStr[right--] = charStr[left];
}
left-- ;
}
return new String(charStr);
}
}
使用额外空间如下：
class Solution {
public String replaceSpace(String s) {
if(s.length() == 0 && s == null) return s;
StringBuffer stringBuffer = new StringBuffer();
for(char i : s.toCharArray()){
if(i == 's'){
stringBuffer.append("%20");
}else{
stringBuffer.append(i);
}
}
return stringBuffer.toString();
}
}
151 翻转字符串里的单词
题目描述：
给你一个字符串 s ，逐个翻转字符串中的所有单词 。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明：
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。翻转后单词间应当仅用一个空格分隔。翻转后的字符串中不应包含额外的空格。
解答：
方法一：使用java内置函数：str.trim(),str.split()
class Solution {
public String reverseWords(String s) {
if(s == null || s.length() == 0){
return s;
}
//去掉首尾的空格
s = s.trim();
String[] str = s.split("s+");
StringBuffer stringBuffer = new StringBuffer();
for(int i = str.length - 1; i >= 0; i--){
stringBuffer.append(str[i]);
if(i != 0){
stringBuffer.append(" ");
}
}
return stringBuffer.toString();
}
}
方法二：
暴力算法：在字符串里找到每个单词，保存到list中，在拼接成String
class Solution {
public String reverseWords(String s) {
StringBuffer stringBuffer = new StringBuffer();
List temp = new ArrayList<>();
boolean flag = false;
//把每个单词提取出来
for(char i : s.toCharArray()){
if(i != 's'){
flag = true;
stringBuffer.append(i);
}else{
if(flag){
temp.add(stringBuffer.toString());
stringBuffer.delete(0, stringBuffer.length());
flag = false;
}
}
}
//提取最后一个单词
if(flag){
temp.add(stringBuffer.toString());
}
//单词反转
String result = new String();
for(int i = temp.size() - 1; i >= 0; i--){
result += temp.get(i);
result += ' ';
}
return result.substring(0, result.length() - 1);
}
}
方法三：双指针法 不使用辅助空间，空间复杂度要求为
O
(
1
)
O(1)
O(1)。
对字符串进行处理时，可以使用StringBuffer，这是个引用对象，可以多个类直接进行操作。
去除多余的空格
之前“替换空格”使用的双指针，因为那道题是扩充字符串，所以要从后向前；这道题是缩小字符串，就要从前向后遍历。翻转整个字符串翻转单词
class Solution {
public String reverseWords(String s) {
//去掉多余空格
StringBuilder sb = removeSpace(s);
//整个字符串翻转
reverse(sb, 0, sb.length() - 1);
//翻转每个单词
reverseEachWord(sb);
return sb.toString();
}
public StringBuilder removeSpace(String s){
StringBuilder sb = new StringBuilder();
//left指向新字符串，right指向旧字符串
int left = 0, right = s.length() - 1;
//去除首尾空格
while(s.charAt(left) == 's') left++;
while(s.charAt(right) == 's') right--;
while(left <= right){
if(s.charAt(left) != 's' || sb.charAt(sb.length() - 1) != 's'){
sb.append(s.charAt(left));
}
left++;
}
return sb;
}
public void reverse(StringBuilder sb, int begin, int end){
while(end > begin){
char temp = sb.charAt(begin);
sb.setCharAt(begin, sb.charAt(end));
sb.setCharAt(end, temp);
begin++;
end--;
}
}
public void reverseEachWord(StringBuilder sb){
//双指针法
int begin = 0, end = 0;
while(end < sb.length()){
if(sb.charAt(end) == 's'){
reverse(sb, begin, end - 1);
begin = end + 1;
}
end++;
}
reverse(sb, begin, end - 1);
}
}
剑指 Offer 58 - II. 左旋转字符串
题目描述：
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
方法一：暴力解法
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuffer stringBuffer = new StringBuffer();
for(int i = n; i < s.length(); i++){
stringBuffer.append(s.charAt(i));
}
for(int i = 0; i < n; i++){
stringBuffer.append(s.charAt(i));
}
return stringBuffer.toString();
}
}
方法二：
先翻转前n个字符再翻转n后字符最后翻转所有字符
class Solution {
public String reverseLeftWords(String s, int n) {
//原地修改
StringBuilder stringBuilder = new StringBuilder(s);
//翻转前n个字符
reverse(stringBuilder, 0, n - 1);
//再翻转n后字符
reverse(stringBuilder, n, s.length() - 1);
//最后整个字符串翻转
reverse(stringBuilder, 0, s.length() - 1);
return stringBuilder.toString();
}
public void reverse(StringBuilder sb, int begin, int end){
while(begin < end){
char temp = sb.charAt(begin);
sb.setCharAt(begin, sb.charAt(end));
sb.setCharAt(end,temp);
begin++;
end--;
}
}
}
总结：
char[]转String的两种方法：String.valueof(char[] charStr)和new String(char[] charStr)str.trim() 方法用于删除字符串的头尾空白符str.split() 方法根据匹配给定的正则表达式来拆分字符串sb.setCharAt(int index, char ch)将给定索引处的字符设置为 chStringBuilder比StringBuffer速度更快
