2025-3月算法刷题

有效的括号

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        if(s.length()%2!=0){
            return false;
        }
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{'){
                st.push(s.charAt(i));
            }
            else if(s.charAt(i)==')'||s.charAt(i)==']'||s.charAt(i)=='}'){
                if (st.isEmpty()) {
                    return false; // No matching opening bracket
                }
                char a=st.pop();
                if(a=='('&&s.charAt(i)==')'){
                    continue;
                }else if(a=='['&&s.charAt(i)==']'){
                    continue;
                }else if(a=='{'&&s.charAt(i)=='}'){
                    continue;
                }else{
                    return false;
                }
            }
        }
        return st.isEmpty();
    }
}

简化路径

拆分字符串后对每个单独的目录进行判断后再进行拼接。

https://www.runoob.com/java/java-stringbuffer.html

class Solution {
    public String simplifyPath(String path) {
        Stack<String> st=new Stack<>();
        String[] components=path.split("/");
        for(String component:components){
            if(component.equals("..")){
                if(!st.isEmpty()){
                    st.pop();
                }
            }else if(!component.equals(".")&&!component.isEmpty()){
                st.push(component);
            }       
        }
        StringBuilder result = new StringBuilder();
        for(String dir:st){
            result.append("/").append(dir);
        }
        return result.length() == 0 ? "/" : result.toString();
    }
}

最小栈

class MinStack {
    private int[] stack;
    private int[] minStack;
    private int top;
    private int minTop;

    public MinStack() {
        stack = new int[10000];
        minStack = new int[10000];
        top=-1;
        minTop=-1;
    }
    
    public void push(int val) {
        top++;
        stack[top]=val;
        if(minTop==-1||minStack[minTop]>=val){
            minTop++;
            minStack[minTop]=val;
        }
    }
    
    public void pop() {
        if(minStack[minTop]==stack[top]){
            minTop--;
        }
        top--;
    }
    
    public int top() {
        return stack[top];
    }
    
    public int getMin() {
        return minStack[minTop];
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

逆波兰表达式求值

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> nst = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].matches("-?\\d+")) {
                nst.push(Integer.parseInt(tokens[i]));
            } else {
                int b = nst.pop();
                int a = nst.pop();
                String operator = tokens[i]; 
                nst.push(calculator(a, b, operator));
            }
        }
        
        return nst.pop(); 
    }
    
    private int calculator(int a, int b, String operator) {
        switch (operator) {
            case "+":
                return a + b;
            case "-":
                return a - b;
            case "*":
                return a * b;
            case "/":
                return a / b;
            default:
                throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
}

基本计算器

就是处理运算顺序上的难点。

(ch - '0')将当前字符数字转换为整数

https://www.runoob.com/java/character-isdigit.html

import java.util.Stack;

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        int sign = 1; // 1 表示正，-1 表示负
        int num = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            // 如果是数字，累加到 num
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            }
            // 如果是 '+' 或 '-'
            else if (ch == '+' || ch == '-') {
                // 将之前的 num 和 sign 累加到 result
                result += sign * num;
                num = 0; // 重置 num
                sign = (ch == '+') ? 1 : -1; // 更新 sign
            }
            // 如果是 '('
            else if (ch == '(') {
                // 将当前的 result 和 sign 压入栈
                stack.push(result);
                stack.push(sign);
                // 重置 result 和 sign
                result = 0;
                sign = 1;
            }
            // 如果是 ')'
            else if (ch == ')') {
                // 将当前的 num 和 sign 累加到 result
                result += sign * num;
                num = 0; // 重置 num
                // 弹出栈顶的 sign 和 result
                result *= stack.pop(); // 弹出 sign
                result += stack.pop(); // 弹出 result
            }
            // 如果是空格，跳过
        }

        // 处理最后的 num
        result += sign * num;
        return result;
    }
}

环形链表

我靠题目没看懂。。。

两数相加

fkfkfk

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(0);
        ListNode current = dummyNode;
        int carry=0;
        while(l1!=null||l2!=null){
            int x= l1!=null?l1.val:0;
            int y= l2!=null?l2.val:0;
            int sum=x+y+carry;
            carry=sum/10;
            current.next= new ListNode(sum%10);
            current=current.next;
            if(l1!=null) l1=l1.next;
            if(l2!=null) l2=l2.next;
        }
        if(carry>0){
            current.next = new ListNode(carry);
        }
        return dummyNode.next;
    }
}

合并两个有序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyNode = new ListNode(0);
        ListNode current = dummyNode;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                current.next = list1;
                current = current.next;
                if (list1!=null) list1=list1.next;
            }else{
                current.next = list2;
                current = current.next;
                if(list2!=null) list2=list2.next;
            }
        }
        if(list1!=null){
            current.next = list1;
            current = current.next;
            list1=list1.next;
        }else if(list2!=null){
            current.next = list2;
            current = current.next;
            list2=list2.next;
        }
        return dummyNode.next;
    }
}

随机链表的复制

对链表的理解更近一步

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return null;
        Node curr = head;
        while(curr!=null){
            Node newNode = new Node(curr.val);
            newNode.next = curr.next;
            curr.next = newNode;
            curr = newNode.next;
        }
        curr = head;
        while(curr!=null){
            if(curr.random!=null){
                curr.next.random=curr.random.next;
            }
            curr = curr.next.next;
        }
        curr = head;
        Node newNode = head.next;
        while(curr!=null){
            Node temp = curr.next;
            curr.next = curr.next.next;
            if(temp.next!=null){
                temp.next = temp.next.next;
            }
            curr = curr.next;
        }
        return newNode;
    }
}

反转链表 II

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) {
            return head;
        }

        // 创建一个虚拟节点，用于简化边界情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        // 将 `prev` 移动到 `left` 位置的前一个节点
        for (int i = 1; i < left; i++) {
            prev = prev.next;
        }

        // `start` 是要反转的第一个节点
        ListNode start = prev.next;
        ListNode then = start.next;

        // 反转从 `left` 到 `right` 的子链表
        for (int i = 0; i < right - left; i++) {
            start.next = then.next;//start右移一位
            then.next = prev.next;//把then的指针指向left的下一个，为了把then放入开头
            prev.next = then;//left的指针指向then完成头插入
            then = start.next;//完成then的移位
        }

        return dummy.next;
    }
}

K 个一组翻转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;

        int count = 0;
        while (curr != null) {
            count++;
            if (count % k == 0) {
                prev = reverse(prev, curr.next);
                curr = prev.next;
            } else {
                curr = curr.next;
            }
        }

        return dummy.next;
    }

    private ListNode reverse(ListNode prev, ListNode next) {
        ListNode last = prev.next;
        ListNode curr = last.next;

        while (curr != next) {
            last.next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = last.next;
        }

        return last;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null||k==0) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        while(curr!=null){
            count++
            if(count%k==0){
                prev=reverse(prev,curr.next);
                curr=prev.next;
            }else{
                curr = curr.next;
            }
        }
    }
    private ListNode reverse(ListNode prev,ListNode next){
        ListNode start = prev.next;
        ListNode then = start.next;
        while(then!=next){
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return start;
    }
}

删除链表的倒数第 N 个结点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟节点，方便处理头节点的删除
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        // 快指针先移动 n 步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // 快慢指针一起移动，直到快指针到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // 删除倒数第 n 个节点
        slow.next = slow.next.next;
        
        // 返回链表的头节点
        return dummy.next;
    }
}

删除排序链表中的重复元素 II

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        
        while (curr != null) {
            if (curr.next != null && curr.val == curr.next.val) {
                int duplicateVal = curr.val;
                while (curr != null && curr.val == duplicateVal) {
                    curr = curr.next;
                }
                prev.next = curr;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}

旋转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }

        // 计算链表长度
        int n = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }

        // 计算实际需要旋转的次数
        k = k % n;
        if (k == 0) {
            return head;
        }

        // 找到新的尾节点
        ListNode newTail = head;
        for (int i = 0; i < n - k - 1; i++) {
            newTail = newTail.next;
        }

        // 执行旋转
        ListNode newHead = newTail.next;
        newTail.next = null;
        tail.next = head;

        return newHead;
    }
}

分隔链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyLess = new ListNode(0);
        ListNode dummyGreater = new ListNode(0);

        ListNode less = dummyLess;
        ListNode greater = dummyGreater;

        ListNode curr = head;
        while(curr != null){
            if(curr.val<x){
                less.next = curr;
                less = less.next;
            }else{
                greater.next=curr;
                greater=greater.next;
            }
            curr = curr.next;
        }
        greater.next=null;
        less.next=dummyGreater.next;
        return dummyLess.next;
    }
}

LRU 缓存

import java.util.HashMap;

class LRUCache {
    private static class ListNode {
        int key; // 节点数据
        int value; // 节点数据
        ListNode prev; // 指向前一个节点的指针
        ListNode next; // 指向下一个节点的指针

        // 构造方法
        ListNode(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    private final int capacity;
    private final HashMap<Integer, ListNode> map;
    private final ListNode head; // 虚拟头节点
    private final ListNode tail; // 虚拟尾节点

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new ListNode(-1, -1);
        this.tail = new ListNode(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            // 将节点移动到链表头部
            removeNode(node);
            addToHead(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            node.value = value;
            // 将节点移动到链表头部
            removeNode(node);
            addToHead(node);
        } else {
            if (map.size() >= capacity) {
                // 移除链表尾部的节点
                ListNode lastNode = tail.prev;
                removeNode(lastNode);
                map.remove(lastNode.key);
            }
            // 添加新节点到链表头部
            ListNode newNode = new ListNode(key, value);
            addToHead(newNode);
            map.put(key, newNode);
        }
    }

    private void removeNode(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(ListNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

二叉树的最大深度

递归

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

相同的树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null){
            return false;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

回文时间

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        String[] parts = input.split(":");
        int h = Integer.parseInt(parts[0]);
        int m = Integer.parseInt(parts[1]);
        int current = h * 60 + m;

        for (int i = 0; i < 1440; i++) {
            int total = (current + i) % 1440;
            int hour = total / 60;
            int minute = total % 60;
            String timeStr = String.format("%02d%02d", hour, minute);
            if (isPalindrome(timeStr)) {
                System.out.println(i);
                return;
            }
        }
    }

    private static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

翻转二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode temp = root.left;
        root.left=root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}