代码随想录刷题-字符串、栈与队列

字符串

1.反转字符串

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

/**
 * Description: 344. 反转字符串
 *
 * @Author sun
 * @Create 2024/11/27 17:12
 * @Version 1.0
 */
public class T4_1 {

    public static void reverseString(char[] s) {
        // 直接双指针
        int left = 0, right = s.length - 1;
        while (left < right) {
            // 交换
            char temp = ' ';
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left ++;
            right--;
        }
    }
}

2.思路

太简单了

2.反转字符串 II

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

/**
 * Description: 541. 反转字符串 II
 *
 * @Author sun
 * @Create 2024/11/27 17:17
 * @Version 1.0
 */
public class T4_2 {

    public static String reverseStr(String s, int k) {
        // 滑动窗口定义：窗口内的元素个数为2k
        int slow = 0;
        // 窗口计数
        int count = 0;
        char[] charArray = s.toCharArray();
        for (int fast = 0; fast < charArray.length; fast++) {
            // 加入窗口
            count++;
            // 不满足窗口要求时触发
            if (count == 2 * k) {
                // 反转
                int left = slow, right = slow + k - 1;
                reverse(left, right, charArray);
                // 重新计数
                count = 0;
                // 移动左指针
                slow = fast + 1;
            }
        }
        // 如果剩余字符少于 k 个，则将剩余字符全部反转。
        if (count > 0 && count < k) {
            // 反转的区间
            int left = slow, right = charArray.length - 1;
            reverse(left, right, charArray);
        } else if (count > 0) {
            // 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
            int left = slow, right = slow + k - 1;
            reverse(left, right, charArray);
        }
        return new String(charArray);
    }

    private static void reverse(int left, int right, char[] charArray) {
        while (left < right) {
            char temp = ' ';
            temp = charArray[right];
            charArray[right] = charArray[left];
            charArray[left] = temp;
            left++;
            right--;
        }
    }
}

2.思路

使用滑动窗口，当窗口内的元素个数为2k时触发反转，并且在最后根据要求做不同的处理

3.替换数字（第八期模拟笔试）

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

import java.util.Scanner;

/**
 * Description: 54. 替换数字（第八期模拟笔试）
 *
 * @Author sun
 * @Create 2024/11/27 17:47
 * @Version 1.0
 */
public class T4_3 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            // 如果是数字，则拼接number
            if (input.charAt(i) >= '0' && input.charAt(i) <= '9') {
                sb.append("number");
            } else {
                // 如果不是数字，则不变
                sb.append(input.charAt(i));
            }
        }
        System.out.println(sb);
    }
}

2.思路

利用StringBuilder拼接即可

4.反转字符串中的单词

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

/**
 * Description: 151. 反转字符串中的单词
 *
 * @Author sun
 * @Create 2024/11/27 18:51
 * @Version 1.0
 */
public class T4_4 {

    public static String reverseWords(String s) {
        // 去除首尾空格
        String trim = s.trim();
        int i = trim.length() - 1;
        int j = trim.length() - 1;
        StringBuilder sb = new StringBuilder();
        while (i > 0) {
            // 遇到第一个空格时
            if (trim.charAt(i) == ' ') {
                // 截取字符串
                sb.append(trim, i + 1, j + 1);
                // 添加空格
                sb.append(' ');
                // 去除其他的空格
                while (trim.charAt(i) == ' ') {
                    i --;
                }
                // 此时的i就指向下一个单词的末尾了
                j = i;
                continue;
            }
            i --;
        }
        // 拼接最后一个元素
        sb.append(trim, 0, j + 1);
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println("reverseWords(\"  hello world  \") = " + reverseWords("  hello world  "));
    }
}

2.思路

使用双指针从后向前移动，遇到第一个空格就进行字符串截取，然后去除多余的空格，并移动右指针，等循环结束再拼接最后一个元素

5.右旋字符串（第八期模拟笔试）

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

import java.util.Scanner;

/**
 * Description: 右旋字符串（第八期模拟笔试）
 *
 * @Author sun
 * @Create 2024/11/27 19:51
 * @Version 1.0
 */
public class T4_5 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String next = sc.next();
        // 指针
        int left = next.length() - 1;
        // 移动k - 1次
        for (int i = 1; i < k; i++) {
            left --;
        }
        // 截取字符串
        StringBuilder sb = new StringBuilder();
        sb.append(next, left, next.length());
        sb.append(next, 0, left);
        System.out.println(sb);
    }
}

2.思路

就是让一个指针移动k-1次，之后进行字符串拼接即可

6.找出字符串中第一个匹配项的下标

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

/**
 * Description: 28. 找出字符串中第一个匹配项的下标
 *
 * @Author sun
 * @Create 2024/11/27 20:05
 * @Version 1.0
 */
public class T4_6 {

    public static int strStr(String haystack, String needle) {
        // 滑动窗口定义：内部元素的个数要小于needle的长度
        int length = needle.length();
        int slow = 0;
        for (int fast = 0; fast < haystack.length(); fast++) {
            // 放入窗口
            // 不满足窗口要求时处理
            while (fast - slow + 1 == length) {
                // 比较字符串是否匹配
                if (needle.equals(haystack.substring(slow, fast + 1))) {
                    return slow;
                }
                // 移动窗口
                slow ++;
            }
        }
        return -1;
    }
}

2.思路

使用滑动窗口解决即可

栈与队列

1.用栈实现队列

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

import java.util.Stack;

/**
 * Description: 232. 用栈实现队列
 *
 * @Author sun
 * @Create 2024/11/27 20:23
 * @Version 1.0
 */
public class MyQueue {

    private Stack<Integer> stackIn;
    private Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    /**
     * 将元素 x 推到队列的末尾
     *
     * @param x
     */
    public void push(int x) {
        stackIn.push(x);
    }

    /**
     * 从队列的开头移除并返回元素
     *
     * @return
     */
    public int pop() {
        // 如果输出栈为空，就将输入栈中的元素pop到输出栈
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        // 然后pop
        return stackOut.pop();
    }

    /**
     * 返回队列开头的元素
     *
     * @return
     */
    public int peek() {
        // 如果输出栈为空，就将输入栈中的元素pop到输出栈
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.peek();
    }

    /**
     * 如果队列为空，返回 true ；否则，返回 false
     * @return
     */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

2.思路

一个输入栈、一个输出栈，输入栈，输入的时候全部输入到输入栈，在输出的时候，如果输出栈为空，则将输入栈的元素pop到输出栈，然后使用输出栈pop即可

2.有效的括号

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

import java.util.Stack;

/**
 * Description: 20. 有效的括号
 *
 * @Author sun
 * @Create 2024/11/27 20:47
 * @Version 1.0
 */
public class T6_3 {

    public static boolean isValid(String s) {
        // 左括号全部压栈，遇到右括号就出栈匹配
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '[' || c == '(' || c == '{') {
                stack.push(c);
            }
            if (c == ']' || c == ')' || c == '}') {
                // 如果栈为空，则也匹配失败
                if (stack.isEmpty()) {
                    return false;
                }
                boolean res = match(stack.pop(), c);
                if (!res) {
                    return false;
                }
            }
        }
        // 最后如果栈是空的，就是有效的括号了
        return stack.isEmpty();
    }

    private static boolean match(Character characterA, Character characterB) {
        if (characterA == '(' && characterB != ')') {
            return false;
        }
        if (characterA == '[' && characterB != ']') {
            return false;
        }
        if (characterA == '{' && characterB != '}') {
            return false;
        }
        return true;
    }
}

2.思路

左括号全部压栈，遇到右括号就出栈匹配，注意两个点，一个是左括号少：在匹配之前检查栈是否为空，如果为空就是左括号少，另一个是左括号多：在都匹配完了之后需要考虑一下栈是否为空，如果不为空就是左括号多

3.删除字符串中的所有相邻重复项

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

import java.util.Stack;

/**
 * Description: 1047. 删除字符串中的所有相邻重复项
 *
 * @Author sun
 * @Create 2024/11/27 21:03
 * @Version 1.0
 */
public class T6_4 {

    public static String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            // 如果栈为空，就直接入栈
            if (stack.isEmpty()) {
                stack.push(c);
                continue;
            }
            // 如果栈不为空，就匹配，匹配成功出栈，匹配失败入栈
            if (match(stack.peek(), c)) {
                stack.pop();
            } else {
                // 匹配失败，入栈
                stack.push(c);
            }
        }
        // 倒序
        char[] characters = new char[stack.size()];
        for (int i = stack.size() - 1; i >= 0; i--) {
            characters[i] = stack.pop();
        }
        return new String(characters);
    }

    private static boolean match(Character peek, char c) {
        return peek == c;
    }
}

2.思路

如果栈为空，就直接入栈，如果栈不为空，就匹配，匹配成功出栈，匹配失败入栈

4.滑动窗口最大值

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Description: 239. 滑动窗口最大值
 *
 * @Author sun
 * @Create 2024/11/27 21:24
 * @Version 1.0
 */
public class T6_5 {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        // 结果数组
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int index = 0;
        // 双端队列
        Deque<Integer> deque = new ArrayDeque<>();
        // 遍历
        for (int i = 0; i < nums.length; i++) {
            // 去头
            if (!deque.isEmpty() && deque.peekFirst() == i - k) {
                deque.pollFirst();
            }
            // 去尾
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            // 加入队列
            deque.offerLast(i);
            // 求结果
            if (i >= k - 1) {
                res[index++] = nums[deque.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {7, 2, 4};
        int k = 2;
        maxSlidingWindow(nums, 2);
    }
}

2.思路

使用双端队列来存索引，去头（去除掉不满足窗口要求的头部索引），去尾（去除掉尾部比当前元素要小的尾部索引），加入队列（将当前元素加入队列），求结果。

5.前 K 个高频元素

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * Description: 347. 前 K 个高频元素
 *
 * @Author sun
 * @Create 2024/11/28 11:28
 * @Version 1.0
 */
public class T6_6 {

    public static int[] topKFrequent(int[] nums, int k) {
        // 首先统计频率
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        // 构建最大堆，也就是会将频率高的放在前面
        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<>((a, b) -> {
            return b.getValue() - a.getValue();
        });
        // 放入最大堆中
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            maxHeap.add(entry);
        }
        // 取出前k个元素即可
        int[] res = new int[k];
        for (int i = 0; i < res.length; i++) {
            res[i] = maxHeap.poll().getKey();
        }
        return res;
    }
}

2.思路

首先统计一下频率，然后构建一个最大堆，将entry放到最大堆中，最后取出最大堆的前k个元素即可