算法·每日一题（详解+多解）-- day14

class Solution {
    //定义结果集
    List<List<Integer>> result = new ArrayList<>();
    //定义临时结果集
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        // 将 used 全部赋值为 false
        Arrays.fill(used, false);
        // 对传进来的数组进行排序
        Arrays.sort(nums);
        // 进入回溯主体
        backTrack(nums, used);
        // 返回最终结果集
        return result;
    }
    // 实现回溯
    private void backTrack(int[] nums, boolean[] used) {
        // 当临时结果集存储的个数跟传进来的数组的长度相等时说明排序完毕
        if (path.size() == nums.length) {
            // 将排序好的结果加入结果集中
            result.add(new ArrayList<>(path));
            return;
        }
        // 开始遍历
        for (int i = 0; i < nums.length; i++) {
            // 如果同⼀树层 nums[i - 1] 使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀ nums[i] 没使⽤过开始处理
            if (used[i] == false) {
                //标记同⼀树⽀ nums[i] 使⽤过，防止同一树支重复使用
                used[i] = true;
                path.add(nums[i]);
                backTrack(nums, used);
                //回溯，说明同⼀树层 nums[i] 使⽤过，防止下一树层重复
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
}

class Solution {
     public int jump(int[] nums) {
        // 对传进来的数组进行判空
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        //记录跳跃的次数
        int count = 0;
        //当前的覆盖最大区域
        int curDistance = 0;
        //最大的覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(maxDistance,i + nums[i]);
            //说明当前一步，再跳一步就到达了末尾
            if (maxDistance >= nums.length - 1){
                count++;
                break;
            }
            //走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if (i == curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        // 返回最终结果
        return count;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        // 定义结果集
        List<int[]> res = new ArrayList<>();
        // 若传进来的 intervals 为空，则直接返回，记得 toArray 成题目最终返回要求
        if (intervals.length == 0 || intervals == null){
            return res.toArray(new int[0][]);
        }
        // 这是函数式编程，实现的是 Comparator 接口，对起点进行从小到大排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        // 定义一个循环维护的变量
        int i = 0;
        // 当 i 的值小于 intervals 中的集合个数时，进入循环
        while (i < intervals.length) {
            // 每次遍历都取出区间的左右端点
            int left = intervals[i][0];
            int right = intervals[i][1];
            // 若当前区间的右端点比下一个区间的左端点还大，则说明区间有重叠
            while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
                // 将当前右端点的值与下一个区间右端点的值进行比较，取较大的值作为新区间右端点
                right = Math.max(right, intervals[++i][1]);
            }
            // 将新区间放入结果集中
            res.add(new int[]{left, right});
            // 接着判断下一个区间
            i++;
        }
        // 返回最终结果集，将 List<int[]> 类型转换成 0 行 n 列的格式的数组类型 ，即一维数组转二维数组
        return res.toArray(new int[0][]);
    }
}

/**
 * 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;
        // 任一节点一个为空另一个非空，则说明是不同的树了
        } else if (p == null || q == null) {
            return false;
        // 两节点都有值，但是值不同也是不同的树
        } else if (p.val != q.val) {
            return false;
        // 若两节点有值且相同，则继续往下遍历，对应的左子节点与右子节点均要相同，递归直到结束，若都相同则为相同的树，否则不是相同的树
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}