刷题日记 - 7

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 对气球按起点进行排序，使用Integer.compare避免溢出
        Arrays.sort(points, (int[] a, int[] b) -> Integer.compare(a[0], b[0]));
        int res = 1; // 至少需要一支箭
        int len = points.length;
        int left = points[0][0]; // 当前区间的左边界
        int right = points[0][1]; // 当前区间的右边界
        int p = 1; // 指向下一个气球
        while (p < len) {
            int curLeft = points[p][0]; // 当前气球的左边界
            int curRight = points[p][1]; // 当前气球的右边界
            // 如果当前气球的左边界大于当前区间的右边界，说明需要一支新箭
            if (curLeft > right) {
                res++; // 新增一支箭
                left = curLeft; // 更新当前区间的左边界
                right = curRight; // 更新当前区间的右边界
            } else {
                // 更新当前区间的右边界为重叠部分的最小右边界⭐ 
                left = curLeft;
                right = Math.min(curRight, right);
            }
            p++;
        }
        return res; // 返回所需的箭数
    }
}

class Solution {
    public String simplifyPath(String path) {
        // 将路径按照 "/" 分割成目录数组
        String[] dirs = path.split("/");
        // 使用双端队列来处理目录的添加和删除
        Deque<String> list = new LinkedList<>();
        
        // 从第二个元素开始遍历（第一个元素是空字符串，因为路径以 "/" 开头）
        for (int i = 1; i < dirs.length; i++) {
            String dir = dirs[i];
            
            // 如果遇到 ".." 说明要返回上一级目录
            if (dir.equals("..")) {
                // 如果队列不为空，则移除最后一个元素，表示返回上一级
                if (!list.isEmpty()) {
                    list.pollLast();
                }
            // 如果遇到 "." 或空字符串则忽略
            } else if (!(dir.equals(".") || dir.length() == 0)) {
                // 否则将当前目录添加到队列的末尾
                list.offerLast(dir);
            }
        }

        // 构建简化后的路径
        StringBuilder sb = new StringBuilder();
        while (!list.isEmpty()) {
            String dir = list.pollFirst(); // 从队列的前端取出元素
            sb.append("/");                // 添加路径分隔符 "/"
            sb.append(dir);                // 添加目录名
        }
        
        // 如果简化后的路径为空，则返回根路径 "/"
        if (sb.length() == 0) {
            return "/";
        }
        return sb.toString(); // 返回最终简化后的路径
    }
}

class Solution {
    public int evalRPN(String[] tokens) {
        // 使用栈来保存操作数
        Stack<Integer> stack = new Stack<>();
        
        // 遍历输入的每一个令牌
        for (String token : tokens) {
            // 如果令牌是加法操作符
            if (token.equals("+")) {
                // 弹出两个操作数，进行加法运算，并将结果压入栈中
                int opNum1 = stack.pop();
                int opNum2 = stack.pop();
                int res = opNum1 + opNum2;
                stack.push(res);
            }
            // 如果令牌是减法操作符
            else if (token.equals("-")) {
                // 弹出两个操作数，进行减法运算，并将结果压入栈中
                int opNum1 = stack.pop();
                int opNum2 = stack.pop();
                int res = opNum2 - opNum1; // 注意减法顺序
                stack.push(res);
            }
            // 如果令牌是乘法操作符
            else if (token.equals("*")) {
                // 弹出两个操作数，进行乘法运算，并将结果压入栈中
                int opNum1 = stack.pop();
                int opNum2 = stack.pop();
                int res = opNum1 * opNum2;
                stack.push(res);
            }
            // 如果令牌是除法操作符
            else if (token.equals("/")) {
                // 弹出两个操作数，进行除法运算，并将结果压入栈中
                int opNum1 = stack.pop();
                int opNum2 = stack.pop();
                int res = opNum2 / opNum1; // 注意除法顺序
                stack.push(res);
            }
            // 如果令牌是数字
            else {
                // 将数字转换为整数并压入栈中
                stack.push(Integer.parseInt(token));
            }
        }
        // 返回栈顶元素，即最终计算结果
        return stack.pop();
    }
}

class Solution {
    public int calculate(String s) {
        char[] sChars = s.toCharArray();
        int len = s.length();
        int INIT = 0;
        int HAVE_ONE_NUM = 1;
        int HAVE_OP = 2;

        int state = INIT;
        Stack<Character>  chStack = new Stack<>();
        Stack<Integer> numStack = new Stack<>();

        int p=0;
        while(p<len){
            // 如果当前字符是空，直接跳过
            if(sChars[p]==' '){
                p++;
            }
            if(p>=len)break;
            // 如果当前字符是数字，则进入数字逻辑
            if(Character.isDigit(sChars[p])){
                int[] tmp = findNextInt(sChars,p);  // 根据自定义函数找出，从当前位置开始的整数
                int curNum = tmp[0];
                p = tmp[1];                         // 更新p指针到当前整数的下一个位置
                if(state==INIT){                    // 如果当前状态为 INIT，表示这是这次运算的第一个整数
                    numStack.push(curNum);          // 将其加入numStack
                    state = HAVE_ONE_NUM;
                }else if(state==HAVE_OP){           // 如果当前状态为 HAVE_OP，表示这次运算已经具备了第一个整数和符号
                    char op = chStack.pop();        // 则取出运算符号，取出第一个整数，进行运算，然后将结果加入numStack
                    if(op=='+'){                    // 并且最后还将state置为 HAVE_ONE_NUM，表示已经有一个整数迎接下一次运算
                        int res = numStack.pop()+curNum;
                        numStack.push(res);
                        state = HAVE_ONE_NUM;
                    }else if(op=='-'){
                        int res = numStack.pop() - curNum;
                        numStack.push(res);
                        state = HAVE_ONE_NUM;
                    }
                }
            }else if(sChars[p]=='+'||sChars[p]=='-'){  // 如果当前的位置是运算符，看当前的状态
                if(state==HAVE_ONE_NUM){               // 如果当前状态为 HAVE_ONE_NUM
                    chStack.push(sChars[p]);           // 加上当前的运算符，则可以进化到下一个状态： HAVE_OP
                    state = HAVE_OP;
                }else if(state == INIT){                 // 如果当前状态为 INIT
                                                         // 由题意可知，这个运算符一定为'-'
                    numStack.push(0);               // 而这个-号就是用作符号的用处
                    chStack.push('-');              // 所以这里在这里手动营造出 （0 - 下一个数）的状态
                    state = HAVE_OP;                     // 所以往numStack中添加0，并且将状态改为 HAVE_OP
                }
                p++;
            }else if(sChars[p]=='('){                  // 当前位置是 '(' 状态更新为INIT，表明寻找下一轮运算
                state = INIT;
                chStack.push(sChars[p]);
                p++;
            }else if(sChars[p]==')'){                  // ')'这一轮括号已经算完了，去掉'('
                while(p<len&&(sChars[p]==')'&&chStack.peek()=='(')){
                    chStack.pop();
                    p++;
                }
                if(numStack.size()>=2){             // 如果numStack中还有两个数或者以上的数
                    int opNum1 = numStack.pop();    // 表明此时需要运算
                    int opNum2 = numStack.pop();    // 这里进行运算
                    char op = chStack.pop();
                    if(op=='+'){
                        numStack.push(opNum1+opNum2);
                    }else if(op=='-'){
                        numStack.push(opNum2-opNum1);
                    }
                }
                state = HAVE_ONE_NUM;              // 状态置为 HAVE_ONE_NUM
            }
        }
        return numStack.pop();
    }

    // p所指当前是digit
    // 返回数组第一个值是该数字，第二个值是数字的下一个字符的位置
    private int[] findNextInt(char[] sChars,int p){
        int len = sChars.length;
        int curNum = 0;
        while(p<len&&Character.isDigit(sChars[p])){
            curNum = curNum*10 + (sChars[p] - '0');
            p++;
        }
        int[] res = new int[2];
        res[0] = curNum;
        res[1] = p;
        return res;
    }

}

/**
 * 单链表的节点定义。
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // 定义两个指针，快指针和慢指针，初始都指向链表的头节点
        ListNode fast = head;
        ListNode slow = head;
        // 定义一个布尔值，初始为false，用来表示是否存在环
        boolean res = false;

        // 开始循环，直到快指针为null
        while(fast != null){
            // 快指针每次走两步
            fast = fast.next;
            if(fast == null) break; // 如果快指针到达链表末尾，跳出循环
            fast = fast.next;
            // 慢指针每次走一步
            slow = slow.next;
            // 如果快指针和慢指针相遇，说明链表中存在环
            if(fast == slow){
                res = true;
                break; // 找到环后跳出循环
            }
        }
        // 返回是否存在环
        return res;
    }
}

/**
 * 单链表的节点定义。
 * 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) {
        // 定义指针p指向链表l1，q指向链表l2
        ListNode p = l1;
        ListNode q = l2;

        // 定义一个哑节点dummy，最后返回dummy.next作为结果链表的头节点
        ListNode dummy = new ListNode(-1);
        ListNode t = dummy;
        
        // carry表示进位
        int carry = 0;

        // 当p和q都不为null时，逐位相加
        while(p != null && q != null){
            int val = p.val + q.val + carry; // 计算当前位的和
            carry = (val >= 10) ? 1 : 0; // 判断是否有进位
            val = (val >= 10) ? val % 10 : val; // 如果和大于等于10，取个位数
            ListNode tmp = new ListNode(val); // 创建新节点存储计算结果
            t.next = tmp; // 将新节点链接到结果链表
            t = t.next; // 移动t指针
            p = p.next; // p指针后移
            q = q.next; // q指针后移
        }

        // 判断哪个链表还有剩余节点
        ListNode remainNode = (p == null) ? q : p;

        // 将剩余节点逐位相加
        while(remainNode != null){
            int val = carry + remainNode.val; // 加上可能的进位
            carry = (val >= 10) ? 1 : 0; // 判断是否有进位
            val = (val >= 10) ? val % 10 : val; // 取个位数
            ListNode tmp = new ListNode(val); // 创建新节点存储计算结果
            t.next = tmp; // 将新节点链接到结果链表
            t = t.next; // 移动t指针
            remainNode = remainNode.next; // 移动剩余链表的指针
        }

        // 如果最后还有进位，增加一个新节点
        if(carry != 0){
            t.next = new ListNode(carry);
        }

        // 返回结果链表的头节点
        return dummy.next;
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 定义指针p指向list1，q指向list2
        ListNode p = list1;
        ListNode q = list2;
        
        // 创建一个哑节点dummy，最后返回dummy.next作为结果链表的头节点
        ListNode dummy = new ListNode(-1);
        ListNode t = dummy;

        // 当p和q都不为null时，比较它们的值，将较小的节点链接到结果链表
        while(p != null && q != null){
            if(p.val >= q.val){
                t.next = q;  // 将q节点链接到结果链表
                t = t.next;  // 移动t指针
                q = q.next;  // q指针后移
            } else {
                t.next = p;  // 将p节点链接到结果链表
                t = t.next;  // 移动t指针
                p = p.next;  // p指针后移
            }
        }

        // 如果p或q还有剩余节点，直接链接到结果链表的末尾
        t.next = (p == null) ? q : p;

        // 返回结果链表的头节点
        return dummy.next;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 创建一个优先队列（最小堆），根据节点值进行排序
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            (ListNode a, ListNode b) -> (a.val - b.val)
        );

        // 将每个链表的头节点加入优先队列
        for(ListNode head : lists){
            if(head == null) continue; // 跳过空链表
            pq.offer(head);
        }

        // 创建一个哑节点dummy，用来构建最终合并的链表
        ListNode dummy = new ListNode(-1);
        ListNode t = dummy;

        // 处理优先队列中的节点，直到队列为空
        while(!pq.isEmpty()){
            t.next = pq.poll(); // 取出队列中最小值的节点并链接到结果链表
            t = t.next; // 移动指针t到新加入的节点
            if(t.next == null) continue; // 如果当前节点没有后续节点，继续循环
            pq.offer(t.next); // 将当前节点的下一个节点加入优先队列
        }

        // 返回合并后的链表的头节点
        return dummy.next;
    }
}