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();
    }
}