2020年9月刷题日志

import java.util.LinkedList;

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // stk用来暂存遍历的结点
        Deque<TreeNode> stk= new LinkedList<>();
        // ans用来存放后序遍历的结果
        List<Integer> ans = new ArrayList<>();
        stk.push(root);
        // prev用来记录上一个遍历完成的结点
        TreeNode prev = null;
        while(!stk.isEmpty()||root!=null){
            // 先把左子树遍历完
            while(root!=null){
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            if(root.right == null || root.right == prev){
                // 当右子树为空或者右子树已经记录时 记录当前结点的值
                ans.add(root.val);
                prev = root;
                root = null;
            }else{
                // 右子树非空且没被记录过，就继续遍历右子树
                stk.push(root);
                root = root.right;
            }
        }
        return ans;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root == null){
            return null;
        }
        Node cur = root;
        // cur来记录每层的最左边的结点
        while(cur!=null){
            // dummy结点方便我们遍历下一层
            Node dummy = new Node();
            Node pre = dummy;
            while(cur!=null){
                // 去判断cur的左右子结点
                if(cur.left != null){
                    // 当子节点存在时，就更新pre.next结点和pre结点
                    pre.next = cur.left;
                    pre = cur.left;
                }
                if(cur.right != null){
                    pre.next = cur.right;
                    pre = cur.right;
                }
                cur = cur.next;
            }
            cur = dummy.next;
        }
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathToP = getPath(root, p);
        List<TreeNode> pathToQ = getPath(root, q);
        TreeNode ans = new TreeNode();
        for(int i = 0;i<pathToP.size() && i<pathToQ.size();i++){
            if (pathToP.get(i)==pathToQ.get(i)){
                ans = pathToP.get(i);
            }else{
                break;
            }
        }
        return ans;
    }
    private List<TreeNode> getPath(TreeNode root, TreeNode target){
        List<TreeNode> path = new ArrayList<>();
        while(root!=target){
            path.add(root);
            if(root.val>target.val){
                root = root.left;
            }else{
                root = root.right;
            }
        }
        path.add(root);
        return path;
    }
}

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();
        dfs(nums, res, 0, path);
        return res;
    }
    private void dfs(int[] nums, List<List<Integer>> res, int begin, ArrayList<Integer> path){
        res.add(new ArrayList<>(path));
        if(nums.length == path.size()){
            return;
        }
        for(int i = begin;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums, res, i+1, path);
            path.remove(path.size()-1);
        }

    }
}

// java就是单纯的翻译一遍上面的代码
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return add(root, false);
    }

    private int add(TreeNode root, boolean flag){
        if(root == null){
            return 0;
        }
        if(flag && root.left == null && root.right == null){
            return root.val;
        }
        return add(root.left, true)+add(root.right, false);
    }
}

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();
        dfs(nums, res, 0, path);
        return res;
    }
    private void dfs(int[] nums, List<List<Integer>> res, int begin, ArrayList<Integer> path){
        res.add(new ArrayList<>(path));
        if(nums.length == path.size()){
            return;
        }
        for(int i = begin;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums, res, i+1, path);
            path.remove(path.size()-1);
        }

    }
}

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int len = edges.length;
        // 先记录所有点的入度
        int[] inDegree = new int[len+1];
        for(int[] edge:edges){
            inDegree[edge[1]]++;
        }
        for(int i = len-1;i >= 0;i--){
            if(inDegree[edges[i][1]] == 2){
                // 尝试删除入度为2的边
                if(!judgeCircle(edges,len,i)){
                    // 删除该边后如果不形成环，说明就是要删除的那条变
                    return edges[i];
                }
            }
        }
        for(int i = len-1;i>=0;i--){
            if(inDegree[edges[i][1]] == 1){
                // 尝试删除入度为1的边
                if(!judgeCircle(edges,len,i)){
                    // 同理，删除后不成环就返回边
                    return edges[i];
                }
            }
        }
        return new int[0];
    }
    
    private boolean judgeCircle(int[][] edges, int len, int remove){
        UnionFind unionFind = new UnionFind(len+1);
        // 尝试删除某条边之后 判断是否成环
        for(int i = 0;i<len;i++){
            if (i == remove){
                continue;
            }
            if(!unionFind.union(edges[i][0], edges[i][1])){
                // 如果合并失败，说明edges[i][0]和edges[i][1]在一个联通分量离
                return true;
            }
        }
        return false;
    }

    private class UnionFind{
        private int[] parent;

        public UnionFind(int n){
            parent = new int[n];
            for(int i = 0;i<n;i++){
                parent[i] = i;
            }
        }

        public int find(int x){
            while(x!=parent[x]){
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public boolean union(int x, int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY){
                return false;
            }
            parent[rootX] = rootY;
            return true;
        }
    }
}

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

}

class Solution {
    // row[i][j] 用来记录第i+1行有没有出现过j+1这个数字
    private int[][] row = new int[9][9];
    // col[i][j] 用来记录第i+1列有没有出现过j+1这个数字
    private int[][] col = new int[9][9]; 
    // block[i][j][k] 用来记录第i+1行第j+1列的这个九宫格内是否出现过k+1这个数字
    private int[][][] block = new int[3][3][9];
    // spaces中的第i个数组[i,j]用来存储的是第i+1行，j+1列这个方格是否为空
    private List<int[]> spaces = new ArrayList<>();
    // valid用来判断数独是否已经完成
    private boolean valid = false;
    public void solveSudoku(char[][] board) {
        for(int i = 0;i<9;i++){
            for(int j = 0;j<9;j++){
                if(board[i][j] == '.'){
                    spaces.add(new int[]{i,j});
                }else{
                    int num = board[i][j] - '1';
                    row[i][num] = col[j][num] = block[i/3][j/3][num] = 1;
                }
            }
        }
        dfs(board,0);
    }

    private void dfs(char[][] board, int index){
        if(index == spaces.size()){
            valid = true;
            return;
        }else{
            int cur_i = spaces.get(index)[0];
            int cur_j = spaces.get(index)[1];
            for(int num = 1; num <= 9 && !valid;num++){
                if(row[cur_i][num-1]==0 && col[cur_j][num-1]==0 && block[cur_i/3][cur_j/3][num-1]==0){
                    row[cur_i][num-1] = col[cur_j][num-1] = block[cur_i/3][cur_j/3][num-1] = 1;
                    board[cur_i][cur_j] = (char)(num+ '0');
                    dfs(board, index+1);
                    row[cur_i][num-1] = col[cur_j][num-1] = block[cur_i/3][cur_j/3][num-1] = 0;
                }
            }
        }
    }
}

 * 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> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> stk = new LinkedList<>();
        while(!stk.isEmpty() || root!=null){
            while(root != null){
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }
}

import java.nio.file.Path;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, target, 0, ans, path);
        return ans;
    }

    public void dfs(int[] candidates, int target, int begin, List<List<Integer>> ans, Deque<Integer> path){
        if(target == 0){
            ans.add(new ArrayList<>(path));
        }else{
            for(int i = begin;i<candidates.length;i++){
                if(candidates[i] > target){
                    break;
                }else if(i > begin  && candidates[i] == candidates[i-1]){
                    continue;
                }else{
                    path.addLast(candidates[i]);
                    dfs(candidates, target-candidates[i], i+1, ans, path);
                    path.removeLast();
                }
            }
        }
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        // res存放结果，path存放在递归过程中的临时数组
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        if(k<=0 || k>n){
            return res;
        }
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k,int begin, Deque<Integer> path, List<List<Integer>> res){
        if(path.size() == k){
            // 当path中有k个元素时就把path加入到结果中
            res.add(new ArrayList<>(path));
        }else{
            // 这里处理剪枝时可以注意到i<=n其实是一个过于宽泛的条件
            // 例如n=15，k=4，path里已经有了两个数，接下来还要选择两个数
            // 搜索的起点begin值最大就是14，最后一个被选的是[14,15]
            // 也就是说i<=15条件过大，应该是i<=14,这里的14 = n-(k-path里已经有的元素数) + 1
            for(int i = begin;i<=n-(k-path.size())+1;i++){
                path.addLast(i);
                dfs(n, k, i+1, path, res);
                // 每次回溯都需要把那个加进去的值删掉再继续循环
                path.removeLast();
            }
        }
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)){
                map.put(num, map.get(num)+1);
            }else{
                map.put(num,1);
            }
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                return map.get(a)-map.get(b);
            }
        });
        for(Integer key : map.keySet()){
            if (pq.size() < k){
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())){
                pq.remove();
                pq.add(key);
            }
        }
        int[] res = new int[k];
        int i = 0;
        while(!pq.isEmpty()){
            res[i++] = pq.remove();
        }
        return res;
    }
}