Posted Updated LeetCode / Mediuma minute read (About 183 words)

435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

首先对intervals按照后一项的大小进行排序。（直接将两数字相减作为比较值比Integer.compare方法更快。）
贪心算法，将已取得的最大值max设置为最小整数值。
遍历intervals，如果当前interval的左侧小于max，则不能选择该interval，计数加一。
反之则可以选择interval，更新max的值为interval的最大值。
返回总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
        int max = Integer.MIN_VALUE;
        int count = 0;
        for(int[] interval : intervals){
            if(interval[0] < max){
                count++;
            }
            else{
                max = interval[1];
            }
        }
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 341 words)

99. Recover Binary Search Tree

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

DFS中序搜索，额外记录访问的前一个节点。
如果当前节点与前一个节点的顺序不对，则暂且认为先后两个节点的位置均不正确。
（前一个大于后一个的值，由于是第一个不满足递增条件的位置，因此前一个的位置一定是错误的。但此时当前值不一定是错误的。）
继续递归，如果发现新的节点位置不正确，则后一个节点位置正确，更新当前节点为不正确的节点。
（由于是第二个不满足递增条件的位置，因此当前值是错误的。）
交换两个位置不正确的节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 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 {
    TreeNode prev;
    boolean flag;
    TreeNode[] wrong;
    public void recoverTree(TreeNode root) {
        wrong = new TreeNode[2];
        prev = new TreeNode(Integer.MIN_VALUE);
        flag = true;
        
        dfs(root);
        
        int swap = wrong[0].val;
        wrong[0].val = wrong[1].val;
        wrong[1].val = swap;
        
        
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        if(prev.val > root.val){
            if(flag){
                wrong[0] = prev;
                flag = false;
            }
            wrong[1] = root;
        }
        prev = root;
        dfs(root.right);
    }
}
Posted Updated LeetCode / Mediuma minute read (About 164 words)

230. Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

DFS搜索，遍历的时候更新全局变量count。
采用中序搜索，当count等于k时，将全局变量ans设置为root.val。
搜索完毕返回ans。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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 {
    int ans;
    int count;
    public int kthSmallest(TreeNode root, int k) {
        ans = -1;
        count = 0;
        dfs(root,k);
        return ans;
    }
    
    private void dfs(TreeNode root, int k){
        if(root == null){
            return;
        }
        dfs(root.left,k);
        count++;
        if (k == count){
            ans = root.val;
        }
        dfs(root.right,k);
    }
}
240. Search a 2D Matrix II
Posted Updated LeetCode / Medium / 复习a minute read (About 137 words)

240. Search a 2D Matrix II

Question

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Solution

将起始点设置为第一行的最后一列。
如果搜寻目标大于该点则向下搜索。
如果搜寻目标小于该点则向左搜索。

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        
        while(i < matrix.length && j >= 0){
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}
Posted Updated LeetCode / Easya minute read (About 137 words)

119. Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

根据杨辉三角形的规则递归。
每次递归行数-1。
根据上一行的返回值，生成新行的列表，然后返回。
如果生成行数为0则返回{1}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> getRow(int rowIndex) {
        if(rowIndex == 0){
            List<Integer> ret = new ArrayList();
            ret.add(1);
            return ret;
        }
        
        List<Integer> arr = getRow(rowIndex - 1);
        List<Integer> ret = new ArrayList();
        
        for(int i = 0; i < arr.size()+1; i++){
            if(i == 0 || i == arr.size()){
                ret.add(1);
            }
            else{
                ret.add(arr.get(i) + arr.get(i-1));
            }
        }
        return ret;
    }
}
Follow

Recents

Archives

Links

×