代码随想录第八天， 哈希表完成，开始String
今日任务
● 344.反转字符串
● 541. 反转字符串II
● 剑指Offer 05.替换空格
● 151.翻转字符串里的单词
● 剑指Offer58-II.左旋转字符串
双指针
时间复杂度： O(N)
空间复杂度： O(1)
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while(left < right){
char temp = s[right];
s[right] = s[left];
s[left] = temp;
left++;
right--;
}
}
}
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
思路：
把string 转换为character array, 与344.反转字符相似，串利用双指针将两个index之间字符反转。
注意：
每隔2k个字符才有反转操作，所以遍历时step为2k, 即 i = i + 2*k;
最后一个循环对剩余字符(length % 2k)的操作： 如果剩余字符少于 k 个，则将剩余字符全部反转 ；如果剩余字符小于 2k 但大于或等于 k 个，则与之前循环相同，反转前k个字符， 所以要反转区间的upper bound 为 Math.min(i+k-1, length - 1)
class Solution {
public String reverseStr(String s, int k) {
int n = s.length();
char[] arr = s.toCharArray();
for(int i = 0; i < n; i = i + 2 * k){
//in last iteration, if there are fewer than k characters left,
// reverse all of them
reverse(arr, i, Math.min(i + k -1, n - 1));
}
return new String(arr); //convert char array back to Stringx
}
private void reverse(char[] arr, int left, int right){
while(left < right){
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
时间复杂度： O(N)
空间复杂度： O(n) 将String转化为char array 的长度
剑指Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
return s.replace(" ","%20");
方法一： 将string 转化为char array, 新建一个stringBuilder 进行修改
StringBuilder in Java represents a mutable sequence of characters. StringBuilder class provides an alternative to String Class, as it creates a mutable sequence of characters.
与StringBuffer区别： String Builder is not thread-safe and high in performance compared to String buffer. StringBuffer is synchronized, thread-safe.
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for(Character c : s.toCharArray()){
if(c == ' ') sb.append("%20");
else sb.append(c);
}
return sb.toString();
}
}
时间复杂度： O(N)
空间复杂度： O(n)
方法二： 双指针法
首先扩充数组到每个空格替换成"%20"之后的大小。
然后从后向前替换空格，也就是双指针法
class Solution {
public String replaceSpace(String s) {
char[] sArr = s.toCharArray();
int n = s.length();
int count = 0; //记录空格数量
for(int i = 0; i < n; i++){
if(s.charAt(i) == ' ') count++;
}
//添加完 "%20" 后的字符长度,string is immutable, so use charArray
//newArr 是 length 为 n + 2 * count的 empty char array
char[] newArr = new char[n + 2 * count];
//倒序遍历修改：i 指向原字符数组尾部元素， j 指向新字符数组V 尾部元素；
//newArr is an empty array, 所以要遍历完整个sArr to fill all the values
for(int i = n - 1, j = newArr.length - 1; i >= 0; i--, j--){
//当 s[i] 不为空格时：执行 s[j] = s[i]
if(sArr[i] != ' '){
newArr[j] = sArr[i];
}else{
//当 s[i] 为空格时：将字符串闭区间 [j-2, j] 的元素修改为 "%20" ；
//由于修改了 3 个元素，因此需要 j -= 2
newArr[j] = '0';
newArr[j - 1] = '2';
newArr[j - 2] = '%';
j -= 2;
}
}
return new String(newArr);
}
}
时间复杂度： O(N)
空间复杂度： O(n) 字符数组
151. 翻转字符串里的单词
方法一：
利用StringBuilder
双指针从右向左遍历， 遇到space时说明得到一个word,放入StringBuilder
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
int r = s.length()-1, l = r;
//after processed the first character(last in loop), position of l is -1
while (l >= -1)
{
if (l > -1 && s.charAt(l) != ' ')
l--;
else if (l < r)
{ // l reaches " ", now between [l +1, r] is one word
//The substring begins at the specified beginIndex
//and extends to the character at index endIndex - 1
sb.append(s.substring(l+1, r+1) + " ");
l--;
r = l;
}
else // l == r && charAt(l) == ' '
{
l--;
r--;
}
}
sb.deleteCharAt(sb.length()-1); //remove space at the end
return sb.toString();
}
}
时间复杂度： O(N)
空间复杂度： O(n) StringBuilder
方法二 库函数
class Solution {
public String reverseWords(String s) {
s = s.trim();
List<String> words = Arrays.asList(s.split("\\s+"));
Collections.reverse(words);
return String.join(" ", words);
}
}
时间复杂度： O(N)
空间复杂度： O(n) list
方法三：
移除多余空格
将整个字符串反转
将每个单词反转
举个例子，源字符串为："the sky is blue "
移除多余空格 : "the sky is blue"
字符串反转："eulb si yks eht"
单词反转："blue is sky the"
class Solution {
public String reverseWords(String s) {
/**
* 不使用Java内置方法实现
* <p>
* 1.去除首尾以及中间多余空格
* 2.反转整个字符串
* 3.反转各个单词
*/
// 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) {
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 n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}
时间复杂度： O(N)
空间复杂度： O(n) java string 不能原地修改，利用StringBuilder 空间为n
剑指Offer58-II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
方法一： substring
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
int len = s.length();
if( len <= n ) return s;
//string index 0 to len-1
sb.append(s.substring(n));
sb.append(s.substring(0,n));
return new String(sb);
}
}
时间复杂度： O(n) substring 复杂度O(n)
As of update 6 within Java 7's lifetime, the behaviour of substring changed to create a copy - so every String refers to a char[] which is not shared with any other object. So at that point, substring() became an O(n) operation where n is the numbers in the substring.
空间复杂度： O(n) StringBuilder
方法二：列表遍历拼接
算法流程：
新建一个 list(Python)、StringBuilder(Java) ，记为 res ；
先向 res 添加 “第 n+1 位至末位的字符” ；
再向res 添加 “首位至第 n 位的字符” ；
将 res 转化为字符串并返回。
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
int len = s.length();
if( len <= n ) return s;
//string index 0 to len-1
for(int i = n; i < len; i++){
sb.append(s.charAt(i));
}
for(int i = 0; i < n; i++){
sb.append(s.charAt(i));
}
return new String(sb);
}
}
时间复杂度： O(n)
空间复杂度： O(n)
方法三：三次反转
与151题相似， 依然可以通过局部反转+整体反转 达到左旋转的目的。
具体步骤为：
反转区间为前n的子串
反转区间为n到末尾的子串
反转整个字符串
C++ 可达到空间复杂度为O(1)
java python String 不可修改，仍然要用到StringBuilder O(n)
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder(s);
int len = s.length();
if( len <= n ) return s;
//string index 0 to len-1
reverseString(sb, 0, n - 1);
reverseString(sb, n, len - 1);
//reverseString(sb, 0, len - 1);
//return new String(sb);
return sb.reverse().toString();
}
private void reverseString(StringBuilder sb, int startIndex, int endIndex){
char temp;
while(startIndex < endIndex){
temp = sb.charAt(startIndex);
//public void setCharAt(int index, char ch)
sb.setCharAt(startIndex, sb.charAt(endIndex));
sb.setCharAt(endIndex, temp);
startIndex++;
endIndex--;
}
}
}
