Home

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// 考察的是对二叉数执行顺序
class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        // 从根节点开始访问，根节点深度是0
        dfs(root,0);
        return res;

    }
    private void dfs(TreeNode root,int deepth){
        if (root ==null) return;
        // 先访问 当前节点，再递归地访问 右子树 和 左子树
        if(deepth==res.size()) res.add(root.val);// 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
        deepth++;
        dfs(root.right,deepth);
        dfs(root.left,deepth);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// 考察的是对二叉数执行顺序
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0;i<size;i++){
                TreeNode node = queue.poll();
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null) {
                    queue.offer(node.right);
                }
                if (i==size-1) {
                    res.add(node.val); //将当前层的最后一个节点放入结果列表
                }
            }

        }
        return res;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<Integer> queue = new PriorityQueue<>((i1, i2) -> Integer.compare(i2, i1));

        // 合并链表元素到队列
        for(ListNode node:lists){
            while (node != null){
                queue.offer(node.val);
                node = node.next;
            }
        }
        // 把队列中元素添加到了新的链表
        ListNode ans = null;
        while (!queue.isEmpty()){
            ListNode curr = new ListNode(queue.poll()); // 每次拿出最大元素，并删除
            curr.next = ans;
            ans = curr;
        }
        return ans;


    }
}

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        int[] nums1 = Arrays.copyOfRange(nums, 1, nums.length);
        int[] nums2 = Arrays.copyOfRange(nums, 0, nums.length - 1);
        return Math.max(subrob(nums1), subrob(nums2));
    }
    private int subrob(int[] nums){
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[len - 1];
    }
}

public int rob(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    // 子问题：
    // f(k) = 偷 [0..k) 房间中的最大金额

    // f(0) = 0
    // f(1) = nums[0]
    // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }

    int N = nums.length;
    int[] dp = new int[N+1];
    dp[0] = 0;
    dp[1] = nums[0];
    for (int k = 2; k <= N; k++) {
        dp[k] = Math.max(dp[k-1], nums[k-1] + dp[k-2]);
    }
    return dp[N];
}

public int rob(int[] nums) {
    int prev = 0;
    int curr = 0;

    // 每次循环，计算“偷到当前房子为止的最大金额”
    for (int i : nums) {
        // 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
        // dp[k] = max{ dp[k-1], dp[k-2] + i }
        int temp = Math.max(curr, prev + i);
        prev = curr;
        curr = temp;
        // 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
    }

    return curr;
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null) {
            if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                root = root.left; // 遍历至左子节点
            else break;
        }
        return root;
    }
}

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0) // 如果为负数，直接返回 false
            return false;
        int cur = 0;
        int num = x;
        while(num != 0) {
            cur = cur * 10 + num % 10;
            num /= 10;
        }
        return cur == x; // 最后比较 数值反转前后是否相等
    }
}

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0){ // 如果为负数，直接返回 false
            return false;
        }
        String strNum = String.valueOf(x);
        for(int i = 0;i<=strNum.length()/2;i++) {
            int a = strNum.charAt(i);
            int b = strNum.charAt(strNum.length()-1-i);
            if(a != b) {
                return false;
            }
        }
        return true;

    }
}

class Solution {
    public boolean isPalindrome(int x) {
        //思考：这里大家可以思考一下，为什么末尾为 0 就可以直接返回 false
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

/**
 * 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 isSubtree(TreeNode s, TreeNode t) {
        // 递归的结束条件
        if(s == null && t == null)
            return true;
        if (s == null || t == null)
            return false;
        return subTree(s,t) || isSubtree(s.left,t) || isSubtree(s.right,t);


    }
    public boolean subTree(TreeNode s,TreeNode t) {
        // 递归的结束条件
        if(s == null && t == null)
            return true;
        if (s == null || t == null)
            return false;
        return s.val==t.val && subTree(s.left, t.left) && subTree(s.right,t.right);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 配合map 记录最多出现次数的子树
    private int max = 0;

    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null)
            return new int[0];
        Map<Integer, Integer> map = new HashMap<>();
        helper(root, map);
        // 然后求出map中value最大值对应的Key
        List<Integer> res = new LinkedList<>();
        for (Integer i : map.keySet()) {
            if (map.get(i) == max)
                res.add(i);
        }
        // 转数组
        int[] resArr = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            resArr[i] = res.get(i);
        }
        return resArr;
    }

    public int helper(TreeNode root, Map<Integer, Integer> map) {
        if (root == null)
            return 0;
        int left = helper(root.left, map);
        int right = helper(root.right, map);
        // 当前节点为根的元素和
        int val = left + right + root.val;
        map.put(val, map.getOrDefault(val, 0) + 1);
        max = Math.max(max, map.get(val));
        return val;
    }
}