LeetCode每日打卡-March

2021-03-25  78 次阅读

3月31日

子集⭐

⚡ 回溯算法(递归)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, nums, res, new ArrayList<Integer>());
        return res;

    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> temp){
        res.add(new ArrayList<>(temp));
        for(int j = i; j < nums.length; ++j) {
            temp.add(nums[j]);
            backtrack(j + 1, nums, res, temp);
            temp.remove(temp.size() - 1);
        }
    }
}

子集II⭐

⚡ 回溯算法

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums); //对有重复元素的数组先进行排序
        backtrack(0, nums, res, new ArrayList<Integer>());
        return res;

    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> temp){
        res.add(new ArrayList<>(temp));
        for(int j = i; j < nums.length; ++j) {
            if(j != i && nums[j] == nums[j-1]) continue; //当出现重复元素进行剪枝
            temp.add(nums[j]);
            backtrack(j + 1, nums, res, temp);
            temp.remove(temp.size() - 1);
        }
    }
}

搜索二维矩阵II

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length - 1, n = 0;
        while(m >= 0 && n < matrix[0].length) {
            if(matrix[m][n] > target) --m;
            else if(matrix[m][n] < target) ++n;
            else return true;
        }
        return false;
    }
}

3月30日

搜索二维矩阵

⚡ 单次二分查找

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int low = 0, high = m * n - 1;

        while(low <= high) {
            int mid = (low + high) / 2;
            int x = matrix[mid / n][mid % n];

            if(x < target) low = mid + 1;
            else if (x > target) high = mid - 1;
            else return true;
        }
        return false;
    }
}

二叉树的深度⭐

⚡ DFS后序遍历

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

⚡ BFS层序遍历

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;

        int res = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int currentLevelSize = queue.size();
            for(int i = 0; i < currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            res++;
        }
        return res;
    }
}

平衡二叉树⭐

⚡ DFS自底向上

class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }

    private int dfs(TreeNode root) {
        if(root == null) return 0;

        int left = dfs(root.left);
        if(left == -1) return -1;

        int right = dfs(root.right);
        if(right == -1) return -1;

        return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
    }
}

⚡ 自顶向下

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

3月29日

颠倒二进制位

⚡ 逐位颠倒

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int ret = 0;
        for(int i = 0; i < 32; ++i) {
            ret |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return ret;
    }
}

⚡ 位运算分治

public class Solution {
    // you need treat n as an unsigned value
    private static final int M1 = 0x55555555;
    private static final int M2 = 0x33333333;
    private static final int M4 = 0x0f0f0f0f;
    private static final int M8 = 0x00ff00ff;

    public int reverseBits(int n) {
        n = (n >>> 1 & M1) | ((n & M1) << 1);
        n = (n >>> 2 & M2) | ((n & M2) << 2);
        n = (n >>> 4 & M4) | ((n & M4) << 4);
        n = (n >>> 8 & M8) | ((n & M8) << 8);

        return n >>> 16 | (n << 16);
    }
}

注：>>>表示不带符号向右移动二进制数，位运算优先级高于逻辑运算可去掉部分括号。

反转链表

⚡ 迭代法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while(curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

⚡ 递归法

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newhead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newhead;
    }
}

3月28日

二叉搜索树迭代器

class BSTIterator {
    private int index;
    private List<Integer> arr;

    public BSTIterator(TreeNode root) {
        index = 0;
        arr = new ArrayList<Integer>();
        inorderTraversal(root, arr);
    }

    public int next() {
        return arr.get(index++);
    }

    public boolean hasNext() {
        return index < arr.size();
    }

    private void inorderTraversal(TreeNode root, List<Integer> arr) {
        if (root == null) return;
        inorderTraversal(root.left, arr);
        arr.add(root.val);
        inorderTraversal(root.right, arr);
    }
}

3月27日

旋转链表

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(k==0 || head==null || head.next==null) {
            return head;
        }
        int n = 1;
        ListNode q = head;
        while(q.next != null){
            q = q.next;
            n++;
        }
        int add = n - k%n;
        if(add == n) return head;
        q.next = head;

        while(add-- > 0) q = q.next;
        ListNode ret = q.next;
        q.next = null;
        return ret;
    }
}

二叉树的层序遍历⭐

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if(root == null) return ret;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for(int i = 0; i < currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            ret.add(level);
        }
        return ret;
    }
}

二叉树的中序遍历⭐

⚡ 递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        return list;
    }

    private void inorder (TreeNode node, List<Integer> list) {
        if (node == null) return;
        inorder (node.left, list);
        list.add(node.val);
        inorder (node.right, list);
    }
}

⚡ 迭代⭐

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

二叉树的后序遍历⭐

⚡ 迭代⭐

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                list.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }
}

二叉树的前序遍历

⚡ 迭代⭐

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                list.add(node.val);
                stack.push(node.right);
                stack.push(node.left);
            }
        }
        return list;
    }
}

3月26日

删除排序链表中的重复元素

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return head;

        ListNode q = head;
        while(q.next != null) {
            if(q.val == q.next.val) {
                q.next = q.next.next;
            }
            else q = q.next;
        }
        return head;
    }
}

3月25日

删除排序链表中的重复元素II⭐

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode p = dummy;
        while (p.next != null && p.next.next != null) {
            if (p.next.val == p.next.next.val) {
                int x = p.next.val;
                while (p.next != null && p.next.val == x) {
                    p.next = p.next.next;
                }
            }
            else {
                p = p.next;
            }
        }
        return dummy.next;
    }
}

3月24日

132模式⭐

⚡ 单调栈

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        Stack<Integer> candidateK = new Stack<>();
        candidateK.push(nums[n - 1]);
        int maxK = Integer.MIN_VALUE;
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < maxK) return true;
            while (!candidateK.isEmpty() && nums[i] > candidateK.peek()) {
                maxK = candidateK.pop();
            }
            if (nums[i] > maxK) {
                candidateK.push(nums[i]);
            }
        }
        return false;
    }
}
赏

Try and fail, but don't fail to try.