Leetcode
⌨️

Leetcode

Created
May 19, 2021 01:55 PM
status
being serialized

45.跳跃游戏 II

class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1, result = 0;
        while (position != 0) {
            for (int i = 0; i < position; i++) {
                if (nums[i] + i >= position) {
                    position = i;
                    result++;
                    break;
                }
            }
        }
        return result;
    }
}

84.柱状图中最大的矩形

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for (int i = 0; i <= heights.length; i++) {
            while (!stack.isEmpty() && (i == heights.length || heights[i] < heights[stack.peek()])) {
                int index = stack.pop();
                int lastIndex = stack.isEmpty() ? -1 : stack.peek();
                result = Math.max(result, heights[index] * (i - lastIndex - 1));
            }
            if (i < heights.length) {
                stack.push(i);
            }
        }
        return result;
    }
}

85.最大矩形

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        int[] height = new int[matrix[0].length];
        for (int i = 0; i < height.length; i++) {
            height[i] = 0;
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == '1') height[j]++;
                else height[j] = 0;
            }
            for (int k = 0; k <= height.length; k++) {
                while (!stack.isEmpty() && (k == height.length || height[k] < height[stack.peek()])) {
                    int index = stack.pop();
                    int lastIndex = stack.isEmpty() ? -1 : stack.peek();
                    result = Math.max(result, height[index] * (k - lastIndex - 1));
                }
                if (k < height.length) stack.push(k);
            }
        }
        return result;
    }
}
💡
一层一层看就是84题

88.合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1, index2 = n - 1, index3 = m + n - 1;
        while (index2 >= 0) {
            if (index1 < 0) {
                nums1[index3] = nums2[index2];
                index2--;
            } else if (nums1[index1] > nums2[index2]) {
                nums1[index3] = nums1[index1];
                index1--;
            } else {
                nums1[index3] = nums2[index2];
                index2--;
            }
            index3--;
        }
    }
}

92.反转链表 II

class Solution {
    ListNode successor = null;

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left-1, right-1);
        return head;

    }

    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode newHead = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return newHead;
    }
}

141. 环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            if (fast == slow) {
                return true;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }
}

200. 岛屿数量

DFS

class Solution {
    public int numIslands(char[][] grid) {
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    mark(i, j, grid);
                }
            }
        }
        return result;
    }

    public void mark(int i, int j, char[][] grid) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
        if (grid[i][j] == '1') grid[i][j] = '0';
        mark(i + 1, j, grid);
        mark(i - 1, j, grid);
        mark(i, j + 1, grid);
        mark(i, j - 1, grid);
        return;
    }
}

并查集

class Solution {
    private int rows, cols;

    public int numIslands(char[][] grid) {
        rows = grid.length;
        if (rows == 0) return 0;
        cols = grid[0].length;
        int zeors = 0;
        UnionFind unionFind = new UnionFind(rows * cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '0') zeors++;
                else {
                    if ((i + 1) < rows && grid[i + 1][j] == '1')
                        unionFind.union(getIndex(i, j), getIndex(i + 1, j));
                    if ((j + 1) < cols && grid[i][j + 1] == '1')
                        unionFind.union(getIndex(i, j), getIndex(i, j + 1));
                }
            }
        }
        return unionFind.getCount() - zeors;
    }

    public int getIndex(int i, int j) {
        return i * cols + j;
    }


    public class UnionFind {
        private int count;
        private int[] parent;

        public int getCount() {
            return count;
        }

        public UnionFind(int num) {
            count = num;
            parent = new int[num];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
        }

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

        public void union(int pre, int cur) {
            int preRoot = find(pre);
            int curRoot = find(cur);
            if (preRoot == curRoot) return;
            else {
                parent[curRoot] = preRoot;
                count--;
            }
        }
    }
}

206.反转链表

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;
    }
}

322. 零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] need = new int[amount + 1];
        need[0] = 0;
        for (int i = 1; i < need.length; i++) {
            need[i] = amount + 1;
        }
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                need[i] = Math.min(need[i], need[i - coin] + 1);
            }
        }
        return need[amount] == amount + 1 ? -1 : need[amount];
    }
}

Loading Comments...