SouthLeetCode-打卡24年02月第3周

// Date : 2024/02/12 ~ 202X/02/18

049.反轉字符串

(1) 題目描述

049	#LeetCode.344.	簡單	題目鏈接	#Monday	2024/02/12

編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 s 的形式給出。

不要給另外的數組分配額外的空間，你必須**原地修改輸入數組**、使用 O(1) 的額外空間解決這一問題。

(2) 題解代碼

class Solution {void swap(char[] s, int i, int j){char temp = s[i];s[i] = s[j];s[j] = temp;} public void reverseString(char[] s) {int len = s.length;int left = 0; int right = len - 1;while(left <= right){swap(s, left, right);left++; right--;}}
}

050.反轉字符串 II

(1) 題目描述

050	#LeetCode.541.	簡單	題目鏈接	#Monday	2024/02/12

給定一個字符串 s 和一個整數 k，從字符串開頭算起，每計數至 2k 個字符，就反轉這 2k 字符中的前 k 個字符。

如果剩余字符少于 k 個，則將剩余字符全部反轉。
如果剩余字符小于 2k 但大于或等于 k 個，則反轉前 k 個字符，其余字符保持原樣。

(2) 題解代碼

class Solution {class Box{char[] s;int len;Box(String str){this.len = str.length();this.s = new char[this.len];for(int i=0 ; i<len ; i++){s[i] = str.charAt(i);}}void swap(int i, int j){char temp = s[i];s[i] = s[j];s[j] = temp;}void reveStr(int start, int end) {int len = end - start;int left = start; int right = end;while(left <= right){swap(left, right);left++; right--;}}void reverseStrInBox(int k) {int cur = 0;int stk = cur + 2*k - 1;int remd = 0;while(stk <= len){reveStr(cur,cur+k-1);cur = stk+1;stk = cur + 2*k - 1;}remd = len - cur;System.out.println(cur);if(remd < k){reveStr(cur,len-1);}else if(remd < 2*k){reveStr(cur,cur+k-1);}}}public String reverseStr(String s, int k) {Box box = new Box(s);box.reverseStrInBox(k);return new String(box.s);}
}

051.替換數字

(1) 題目描述

051	#KamaCoder.54.	簡單	題目鏈接	#Tuesday	2024/02/13

給定一個字符串 s，它包含小寫字母和數字字符，請編寫一個函數，

將字符串中的字母字符保持不變，而將每個數字字符替換為number。

例如，對于輸入字符串 “a1b2c3”，函數應該將其轉換為 “anumberbnumbercnumber”。

輸入描述：輸入一個字符串 s,s 僅包含小寫字母和數字字符。

輸出描述：打印一個新的字符串，其中每個數字字符都被替換為了number

(2) 題解代碼

/* 給定一個字符串 s，它包含小寫字母和數字字符，請編寫一個函數，* 將字符串中的字母字符保持不變，而將每個數字字符替換為number。* 例如，對于輸入字符串 "a1b2c3"，函數應該將其轉換為 "anumberbnumbercnumber"。*/
// 輸入描述：輸入一個字符串 s,s 僅包含小寫字母和數字字符。
// 輸出描述：打印一個新的字符串，其中每個數字字符都被替換為了number
import java.util.*;public class Main {public static void main(String[] args){Scanner sc = new Scanner(System.in);String s = sc.nextLine();List<Character> list = new ArrayList<>();int len = s.length();Character[] numArray = {'n','u','m','b','e','r'};List<Character> numList = Arrays.asList(numArray);for(int i=0 ; i<len ; i++){char ch = s.charAt(i);if('a' <= ch && ch <= 'z'){list.add(ch);}else{list.addAll(numList);}}StringBuilder stringBuilder = new StringBuilder();for (Character ch : list) {stringBuilder.append(ch);}String result = stringBuilder.toString();System.out.println(result);} }

052.右旋字符串

(1) 題目描述

052	#LeetCode.55.	簡單	題目鏈接	#Tuesday	2024/02/13

字符串的右旋轉操作是把字符串尾部的若干個字符轉移到字符串的前面。

給定一個字符串 s 和一個正整數 k，請編寫一個函數，將字符串中的后面 k 個字符移到字符串的前面，實現字符串的右旋轉操作。

例如，對于輸入字符串 “abcdefg” 和整數 2，函數應該將其轉換為 “fgabcde”。

輸入描述：輸入共包含兩行，第一行為一個正整數 k，代表右旋轉的位數。第二行為字符串 s，代表需要旋轉的字符串。

輸出描述：輸出共一行，為進行了右旋轉操作后的字符串。

(2) 題解代碼

Version1.0

import java.util.*;public class Main {static char[] strToArray(String str){int len = str.length();char[] chars = new char[len];for(int i=0 ; i<len ; i++){chars[i] = str.charAt(i);}return chars;}public static void main(String[] args){Scanner scanner = new Scanner(System.in);int k = scanner.nextInt();scanner.nextLine();String s = scanner.nextLine();int len = s.length();char[] chars = strToArray(s);char[] helper = new char[k];for(int i=0 ; i<k ; i++){helper[i] = chars[len-k+i];}for(int i=len-k-1 ; i>=0 ; i--){chars[i+k] = chars[i];}for(int i=0 ; i<k ; i++){chars[i] = helper[i];}String res = new String(chars);System.out.println(res);}
}

Version2.0

import java.util.*;public class Main {static char[] strToArray(String str){int len = str.length();char[] chars = new char[len];for(int i=0 ; i<len ; i++){chars[i] = str.charAt(i);}return chars;}public static void main(String[] args){Scanner scanner = new Scanner(System.in);int k = scanner.nextInt();scanner.nextLine();String s = scanner.nextLine();int len = s.length();StringBuilder sbk = new StringBuilder(s);StringBuilder sbo = new StringBuilder(s);sbk.delete(0, len-k);sbo.delete(len-k, len);sbk.append(sbo);String str = sbk.toString();System.out.println(str);}
}

053.反轉字符串中的單詞

(1) 題目描述

003	#LeetCode.151.	簡單	題目鏈接	#Wednesday	2024/02/0X

給你一個字符串 s ，請你反轉字符串中單詞的順序。

單詞是由非空格字符組成的字符串。s 中使用至少一個空格將字符串中的單詞分隔開。

返回單詞順序顛倒且單詞之間用單個空格連接的結果字符串。

**注意：**輸入字符串 s中可能會存在前導空格、尾隨空格或者單詞間的多個空格。返回的結果字符串中，單詞間應當僅用單個空格分隔，且不包含任何額外的空格。

(2) 題解代碼

class Solution {public String reverseWords(String s) {int left = 0;int right = s.length() - 1;while (left <= right && s.charAt(left) == ' ') {++left;}while (left <= right && s.charAt(right) == ' ') {--right;}Deque<String> d = new ArrayDeque<String>();StringBuilder word = new StringBuilder();while (left <= right) {char c = s.charAt(left);if ((word.length() != 0) && (c == ' ')) {d.offerFirst(word.toString());word.setLength(0);} else if (c != ' ') {word.append(c);}++left;}d.offerFirst(word.toString());return String.join(" ", d);}
}

054.找出字符串中第一個匹配項的下標

(1) 題目描述

004	#LeetCode.28.	簡單	題目鏈接	#Thursday	2024/02/15

(2) 題解代碼

class Solution {class Box{String str;int len;int idx;Box(String str){this.str = str;this.len = str.length();this.idx = 0;}boolean idxSafe(){return idx >= 0 && idx < len;}char getChar(){return str.charAt(idx);}void loopCnt(){this.idx++;}}public int strStr(String haystack, String needle) {Box hBox = new Box(haystack);Box nBox = new Box(needle);if(hBox.len < nBox.len){return -1;}int bigIdx = 0;while(hBox.idxSafe() && nBox.idxSafe()){while(hBox.idxSafe() && nBox.idxSafe() && hBox.getChar() == nBox.getChar()){if(nBox.idx == nBox.len-1){return hBox.idx - nBox.len + 1;}System.out.println("h : " + hBox.getChar() +", n : " + nBox.getChar());hBox.loopCnt();nBox.loopCnt();}nBox.idx = 0;hBox.idx = ++bigIdx;// nBox.loopCnt();}return -1;}
}

055.重復的子字符串

(1) 題目描述

004	#LeetCode.459.	簡單	題目鏈接	#Thursday	2024/02/15

(2) 題解代碼

class Solution {public boolean repeatedSubstringPattern(String s) {if (s.equals("")) return false;int len = s.length();s = " " + s;char[] chars = s.toCharArray();int[] next = new int[len + 1];for (int i = 2, j = 0; i <= len; i++) {while (j > 0 && chars[i] != chars[j + 1]) j = next[j];if (chars[i] == chars[j + 1]) j++;next[i] = j;}if (next[len] > 0 && len % (len - next[len]) == 0) {return true;}return false;}
}

056.棧的自我實現

(1) 題目描述

005	#LeetCode.XXX.	簡單	題目鏈接	#Friday	2024/02/16

(2) 題解代碼

// 略

057.隊列的自我實現

(1) 題目描述

005	#Self-Proposition.	簡單	題目鏈接	#Friday	2024/02/16

(2) 題解代碼

// 略

058.用棧實現隊列

(1) 題目描述

006	#LeetCode.232.	簡單	題目鏈接	#Saturday	2024/02/17

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

實現 MyQueue 類：

void push(int x) 將元素 x 推到隊列的末尾
int pop() 從隊列的開頭移除并返回元素
int peek() 返回隊列開頭的元素
boolean empty() 如果隊列為空，返回 true ；否則，返回 false

(2) 題解代碼

class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack2.push(x);}public int pop() {if(!stack1.isEmpty()){return stack1.pop();}else{int res = 0;int len2 = stack2.size();for(int i=0 ; i<len2 ; i++){res = stack2.pop();stack1.push(res);}stack1.pop();return res;}}public int peek() {if(!stack1.isEmpty()){return stack1.peek();}else{int res = 0;int len2 = stack2.size();for(int i=0 ; i<len2 ; i++){res = stack2.pop();stack1.push(res);}return res;}}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

059.用隊列實現棧

(1) 題目描述

006	#LeetCode.225.	簡單	題目鏈接	#Saturday	2024/02/0X

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。

實現 MyStack 類：

void push(int x) 將元素 x 壓入棧頂。
int pop() 移除并返回棧頂元素。
int top() 返回棧頂元素。
boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。

(2) 題解代碼

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {queue2.offer(x);}public int pop() {if(queue2.isEmpty()){return popHelper(queue2,queue1);}else{return popHelper(queue1,queue2);}}public int popHelper(Queue<Integer> queue1, Queue<Integer> queue2) {int res = 0;int len2 = queue2.size();for(int i=0 ; i<len2-1 ; i++){res = queue2.poll();queue1.offer(res);}return queue2.poll();}public int top() {int res = pop();push(res);return res;}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}

060.有效的括號

(1) 題目描述

007	#LeetCode.20.	簡單	題目鏈接	#Sunday	2024/02/0X

(2) 題解代碼

class Solution {class MapBox{Map<Character,Character> map;MapBox(){map = new HashMap<>();map.put('(',')'); map.put('{','}'); map.put('[',']');}boolean areMatch(char key, char val){return map.get(key) != null && map.get(key) == val;}}public boolean isValid(String s) {MapBox mox = new MapBox();int len = s.length();Stack<Character> stack = new Stack<>();for(int i=0 ; i<len ; i++){char cur = s.charAt(i);if(stack.isEmpty()){stack.push(cur);}else{char pre = stack.pop();if(!mox.areMatch(pre,cur)){stack.push(pre);stack.push(cur);}}}return stack.isEmpty();}
}

061.刪除字符串中的所有相鄰重復項

(1) 題目描述

007	#LeetCode.046.	簡單	題目鏈接	#Sunday	2024/02/0X

(2) 題解代碼

class Solution {public String removeDuplicates(String s) {int len = s.length();Stack<Character> stack = new Stack();for(int i=0 ; i<len ; i++){char curr = s.charAt(i);if(stack.isEmpty()){stack.push(curr);}else{char prev = stack.pop();if(prev != curr){stack.push(prev);stack.push(curr);}}}StringBuilder build = new StringBuilder();while(!stack.isEmpty()){build.insert(0, stack.pop());}return build.toString();}
}