刷题日记 - 9

class Solution {
    public ListNode partition(ListNode head, int x) {
        
        ListNode dummy1 = new ListNode(-111); // 赋值为-111，标记这是dummy节点
        ListNode dummy2 = new ListNode(-111); // dummy1链表是小于x的节点，dummy2是大于等于x的节点
        ListNode t1 = dummy1,t2 = dummy2;    
        ListNode p = head;
        
        while(p!=null){                // 遍历整个初始链表，按照每个节点的值分别放入不同的dummy中
            int val = p.val;
            if(val<x){
                t1.next = p;
                t1 = t1.next;
            }else if(val>=x){
                t2.next = p;
                t2 = t2.next;
            }
            p = p.next;
        }

        ListNode dummy = new ListNode(-1); // 最后将dummy1和dummy2串成一串。
        ListNode t = dummy;
        if(t1.val!=-111){
            t.next = dummy1.next;
            t = t1;
        }
        if(t2.val!=-111){
            t.next = dummy2.next;
            t = t2;
        }
        t.next = null;
        return dummy.next;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();  // 用于存储最终的层次遍历结果
        if (root == null) return res;  // 如果根节点为空，直接返回空列表

        Queue<TreeNode> queue = new LinkedList<>();  // 创建一个队列，用于广度优先搜索
        queue.offer(root);  // 将根节点入队
        queue.offer(null);  // 用 null 作为层与层之间的分隔符

        while (true) {
            List<Integer> cur = new ArrayList<>();  // 用于存储当前层的节点值
            while (queue.peek() != null) {  // 当队列前端不是 null 时，处理当前层的所有节点
                TreeNode curNode = queue.poll();  // 出队一个节点
                cur.add(curNode.val);  // 将该节点的值添加到当前层的列表中
                if (curNode.left != null) queue.offer(curNode.left);  // 如果左子节点不为空，入队
                if (curNode.right != null) queue.offer(curNode.right);  // 如果右子节点不为空，入队
            }
            res.add(cur);  // 将当前层的结果添加到最终结果列表中
            queue.poll();  // 移除层与层之间的分隔符（即 null）
            if (queue.isEmpty()) break;  // 如果队列为空，说明遍历结束，跳出循环
            queue.offer(null);  // 在队列末尾加入新的层分隔符
        }
        return res;  // 返回最终的层次遍历结果
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();  // 用于存储前序遍历结果
        if (root == null) return res;  // 如果根节点为空，返回空列表
        
        Stack<TreeNode> stack = new Stack<>();  // 创建一个栈用于模拟递归调用
        stack.push(root);  // 将根节点压入栈中

        while (!stack.isEmpty()) {  // 当栈不为空时，继续遍历
            TreeNode p = stack.pop();  // 弹出栈顶节点
            res.add(p.val);  // 将该节点的值加入结果列表中

            // 由于栈是后进先出 (LIFO)，我们先压入右子节点，后压入左子节点
            // 这样在下一次循环中，左子节点会先被处理，实现了前序遍历的顺序
            if (p.right != null) stack.push(p.right);  // 如果右子节点不为空，将右子节点压入栈
            if (p.left != null) stack.push(p.left);  // 如果左子节点不为空，将左子节点压入栈
        }

        return res;  // 返回前序遍历结果
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();  // 用于存储中序遍历结果
        if (root == null) return res;  // 如果根节点为空，返回空列表
        
        Stack<TreeNode> stack = new Stack<>();  // 创建一个栈用于模拟递归调用
        stack.push(root);  // 将根节点压入栈中

        while (!stack.isEmpty()) {  // 当栈不为空时，继续遍历
            TreeNode p = null;
            
            // 将当前节点的所有左孩子压入栈
            while (true) {
                p = stack.peek();  // 查看栈顶节点
                if (p.left != null) {  // 如果当前节点有左子节点
                    stack.push(p.left);  // 将左子节点压入栈
                } else break;  // 如果没有左子节点，停止压栈
            }
            
            // 依次弹出栈中的节点并处理
            TreeNode pop;
            while (!stack.isEmpty()) {
                pop = stack.pop();  // 弹出栈顶节点 ⭐ 栈顶节点的左孩子要么没有，要么被处理完了
                res.add(pop.val);  // 将节点的值加入结果列表中
                
                // 如果弹出的节点有右子节点，将其压入栈中 ⭐
                if (pop.right != null) {
                    stack.push(pop.right);  // 压入右子节点
                    break;  // 进入下一轮循环处理右子树
                }
            }
        }

        return res;  // 返回中序遍历结果
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // 结果列表，用于存储后序遍历的节点值
        List<Integer> res = new ArrayList<>();
        // 如果根节点为空，直接返回空的结果列表
        if (root == null) return res;
        
        // 使用栈来模拟递归调用的过程
        Stack<TreeNode> stack = new Stack<>();
        // 记录最后一个被弹出的节点，用于判断右子树是否已经被访问
        TreeNode lastPop = null;
        // 将根节点压入栈中
        stack.push(root);
        
        // 只要栈不为空，继续遍历
        while (!stack.isEmpty()) {
            // 递归入栈左孩子
            TreeNode p = null;
            while (true) {
                p = stack.peek(); // 获取栈顶节点
                if (p.left != null) {
                    // 如果有左孩子，将左孩子入栈
                    stack.push(p.left);
                } else break;  // 如果没有左孩子，退出内循环
            }
            
            // 开始出栈
            TreeNode cur = null;
            while (!stack.isEmpty()) { // 处理栈顶的节点
                cur = stack.peek();  // 获取当前栈顶节点  ⭐还不能pop
                
                // 如果右孩子存在且右孩子还未被处理
                if (cur.right != null && lastPop != cur.right) {
                    // 将右孩子入栈，并退出内循环以继续处理右子树
                    stack.push(cur.right);
                    break;
                } else {
                    // 否则，右子树已经处理完毕，可以安全地访问当前节点
                    res.add(cur.val);  // 将当前节点的值加入结果列表
                    stack.pop();       // 弹出当前节点
                    lastPop = cur;     // 更新最后一个被弹出的节点
                }
            }
        }
        // 返回结果列表
        return res;
    }
}

class Solution {
    int res; // 用于记录最终的结果数量

    public int atMostNGivenDigitSet(String[] digits, int n) {
        // 将 String[] 数组转换为 char[] 数组 
        // 因为后面用char[]数组，最后才发现给的原来是String[]...
        char[] chars = new char[digits.length];
        for (int i = 0; i < digits.length; i++) {
            chars[i] = digits[i].charAt(0);
        }
        // 调用辅助函数计算结果
        return fun(chars, n);
    }

    public int fun(char[] digits, int n) {
        String nString = String.valueOf(n); // 将 n 转换为字符串以便逐位处理
        int len = nString.length(); // 获取 n 的位数

        res = 0; // 初始化结果为 0
        Arrays.sort(digits); // 对数字数组进行排序
        int digitsNum = digits.length; // 获取可用数字的数量

        // 计算位数比 n 小的所有可能数的数量
        for (int i = 1; i <= len - 1; i++) {
            res += (int) Math.pow(digitsNum, i);
        }

        // 处理与 n 位数相同的情况
        dfs(nString.toCharArray(), digits, 0, false);
        return res;
    }

    private void dfs(char[] n, char[] digits, int pos, boolean flag) {
        int len = n.length; // n 的长度
        int digitsNum = digits.length; // 可用数字的数量
        if (pos == len) { // 极端情况下 需要跳出dfs
            if (flag) res += 1; // 如果 flag 为 true，表示构造的这个数等于n
            return;
        }

        char cur = n[pos]; // 当前处理的 n 中的字符
        int targetCurIdx = -1; // 用于记录小于当前位数字的最大可用数字的索引
        for (int i = digitsNum - 1; i >= 0; i--) { // 从大到小遍历 digits 数组
            if (digits[i] == cur) {
                // 如果当前位数字等于 n 中对应位数字
                dfs(n, digits, pos + 1, true); // 当前这一位相等，在下一位寻找<=的值
            }
            if (digits[i] < cur) {
                // 如果找到一个小于 n 当前位的数字 只要这一位小于，后面的剩余位都可以随便放置
                targetCurIdx = i; // 记录其索引
                break;
            }
        }

        // 计算小于当前位但位数相同的所有可能数的数量
        int useableNum = targetCurIdx + 1;
        res += useableNum * Math.pow(digitsNum, len - pos - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        int[] digits = {2, 5, 4};
        int n = 2544;
        System.out.println(new Solution().fun(digits, n));
    }
}

class Solution {

    public int fun(int[] digits, int n) {
        String nString = String.valueOf(n);
        int len = nString.length();
        int digitsNum = digits.length;

        Arrays.sort(digits);
        int res = dfs(nString.toCharArray(), digits, 0, 0);

        if (res == -1) {
            res = 0;
            for (int i = 1; i <= len - 1; i++) {
                res = res * 10 + digits[digitsNum - 1];
            }
        }
        return res;
    }

    private int dfs(char[] n, int[] digits, int pos, int res) {
        int len = n.length;
        int digitsNum = digits.length;
        if (pos == len) {
            return -1;
        }

        int cur = n[pos] - '0';
        int targetCurIdx = -1;
        for (int i = digitsNum - 1; i >= 0; i--) {
            if (digits[i] == cur) {
                int tmp = dfs(n, digits, pos + 1, res * 10 + digits[i]);
                if (tmp != -1) {
                    return tmp;
                }
            } else if (digits[i] < cur) {
                targetCurIdx = i;
                break;
            }
        }

        if (targetCurIdx == -1) {
            return -1;
        }

        res = res * 10 + digits[targetCurIdx];
        int leftPosCount = len - 1 - pos;
        for (int i = 0; i < leftPosCount; i++) {
            res = res * 10 + digits[digitsNum - 1];
        }
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] digits = {5, 9};
        int n = 5555;
        System.out.println(new Solution().fun(digits, n));
    }
}

class Solution {

    public int fun(int[] digits, int n) {
        int digitsNum = digits.length;
        char[] digitChars = new char[digitsNum];
        char max = '0';
        char min = '9';

        for (int i = 0; i < digitsNum; i++) {
            digitChars[i] = (char) (digits[i] + '0');
            max = digitChars[i] > max ? digitChars[i] : max;   // 记录max和min方便后续判断与赋值
            min = digitChars[i] < min ? digitChars[i] : min;
        }
        Arrays.sort(digitChars);

        char[] nChars = String.valueOf(n).toCharArray();
        int len = nChars.length;

        char[] res = new char[len];
        Arrays.fill(res, '0');

        int p = 0;
        int state = 0;
        while (p < nChars.length) {
            int targetIdx = -1;
            char cur = nChars[p];
            for (int i = digitsNum - 1; i >= 0; i--) {
                if (digitChars[i] == cur) {
                    res[p] = digitChars[i];
                    targetIdx = -2;
                    break;
                } else if (digitChars[i] < cur) {
                    targetIdx = i;
                    res[p] = digitChars[targetIdx];
                    break;
                }
            }

            if (targetIdx == -2) {  // 只有在前面都等于的时候继续
                p++;
            } else {
                if (targetIdx == -1) state = 1;
                if (targetIdx != -1) state = 2;
                break;
            }
            ;  // 退出while只有三种情况： 1. p=len,这个组合出来的数一定是等于n的   2. 在p这个位置 找到了比对应位置小的  3. 或者找不到对应小的。
        }
        // 反向
        if (state == 0) {
            p--;
            while (p >= 0 && res[p] <= min) {
                res[p] = max;
                p--;
            }
            if (p == -1) {
                res[0] = '0';
            } else {
                for (int i = digitsNum - 1; i >= 0; i--) {
                    if (digitChars[i] < res[p]) {
                        res[p] = digitChars[i];
                    }
                }
            }
        }
        if (state == 1) {
            for (int i = len - 1; i >= 0; i--) {
                if (i < p) break;
                res[i] = max;
            }
            p--;
            while (p >= 0 && res[p] <= min) {
                res[p] = max;
                p--;
            }
            if (p == -1) {
                res[0] = '0';
            } else {
                for (int i = digitsNum - 1; i >= 0; i--) {
                    if (digitChars[i] < res[p]) {
                        res[p] = digitChars[i];
                    }
                }
            }
        }
        if (state == 2) {
            for (int i = len - 1; i >= 0; i--) {
                if (i <= p) break;
                res[i] = max;
            }
        }

        // 将res转化为数字
        int resInt = 0;
        for (int i = 0; i < len; i++) {
            char cur = res[i];
            resInt = resInt * 10 + (cur - '0');
        }
        return resInt; // 返回最终结果
    }
}