1964. Find the Longest Valid Obstacle Course at Each Position
Posted Updated LeetCode / Hard / Review3 minutes read (About 398 words)

1964. Find the Longest Valid Obstacle Course at Each Position

Question

You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the ith obstacle.

For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:

  • You choose any number of obstacles between 0 and i inclusive.
  • You must include the ith obstacle in the course.
  • You must put the chosen obstacles in the same order as they appear in obstacles.
  • Every obstacle (except the first) is taller than or the same height as the obstacle immediately before it.

Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.

Read more
34. Find the Element in Sorted Array
Posted Updated LeetCode / Mediuma minute read (About 155 words)

34. Find the Element in Sorted Array

Question

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Solution

二分搜索，首先搜索target。如果搜索到结果为负数，则返回[-1, -1]。
如果搜索到target，则记录index。
然后从index向两边搜索，直到找到界限并返回。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        int index = 0;
        index = Arrays.binarySearch(nums, target);
        if(index < 0){
            ret[0] = -1;
            ret[1] = -1;
            return ret;
        }
        int less = index, more = index;
        while(less >= 0 && nums[less] == target) less--;
        while(more < nums.length && nums[more] == target) more++;
        
        ret[0] = less + 1;
        ret[1] = more - 1;
        return ret;
    }
}
Posted Updated LeetCode / Medium / 复习4 minutes read (About 574 words)

2300. Successful Pairs of Spells and Potions

Question

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the i<sup>th</sup> spell and potions[j] represents the strength of the j<sup>th</sup> potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the i<sup>th</sup> spell.

Solution 1

排序+二分搜索。同时记录success与spells[i]的比值来减小计算量。

排序

首先对potions[]进行排序，这样可以使用二分搜索查找分界值。
数组scales[]记录success与spells[i]的比值，以此为界大于等于scales[i]的位置都可以计入ret[]数组。

二分搜索

这里有一些tricky。

由于Arrays.binarySearch()方法无法返回重复的数字，因此在搜索时我们将查找值scale减去一个小值，保证在搜索时一定返回负值。（查找值的插入位置的负数-1）
将ret[i]记录为potions[]的总数减去正确的插入位置即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ret = new int[spells.length];
        
        Arrays.sort(potions);
        double[] scales = new double[potions.length];
        
        for(int i = 0; i < potions.length; i++){
            scales[i] = (double) potions[i];
        }
        
        for(int i = 0; i < spells.length; i++){
            double scale = (double) success / spells[i] - 0.000001;   //确保浮点数不在scale中出现，binarySearch方法返回的结果必定为上一个插入位置
            int index = Arrays.binarySearch(scales, scale);
            ret[i] = potions.length + (index + 1);
        }
        return ret;
    }
}

Solution 2

由于Arrays.binarySearch()无法正确的搜索有重复元素的数组，因此采用辅助方法binarySearch()来搜索最左侧的下标。

直接在binarySearch()方法中查找target，比较的对象为spell和potions[i]的乘积。

为了搜寻重复的第一个元素，当遇到target时不直接返回，而是继续修改right的位置，直到left等于right。

如果未搜索到，则返回数组的总长度。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ret = new int[spells.length];
        Arrays.sort(potions);
        for(int i = 0; i < spells.length; i++){
            int index = binarySearch(potions, spells[i], success);
            ret[i] = potions.length - index;
        }
        return ret;
    }
    
    private int binarySearch(int[] potions, long spell, long target){
        int left = 0, right = potions.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(potions[mid] * spell < target) left = mid + 1;
            else right = mid;
        }
        return potions[left] * spell < target ? potions.length : left;
    }
}
673. Number of Longest Increasing Subsequence
Posted Updated LeetCode / Medium / 复习4 minutes read (About 538 words)

673. Number of Longest Increasing Subsequence

Question

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Solution

本题还有贪心算法+前缀和+二分查找的算法。

本题是300. Longest Increasing Subsequence的拓展。
同样采用动态规划，数组dp[i]记录到i为止最长递增数列长度。
可以用一个新的数组cnt[i]记录到i为止可以组成的最长递增数列的数量。

对于每个新位置i，cnt[i]的最小值为i。
遍历i之前的所有位置j。如果nums[j] < nums[i]，则i可以比dp[j]组成更长的递增数列，其长度为dp[j]+1。
如果dp[i] < dp[j]+1。则可以更新dp[i]。同时，cnt[i]可以从cnt[j]继承其计数。
如果dp[i] == dp[j]+1。则之前已经更新过dp[i]。说明有新的组合同样可以组成更长的递增数列。此时将cnt[j]加入当前的cnt[i]。

遍历完成i以内的所有j后，如果dp[i]大于当前的最长递增数列长度，则更新max。
同时更新长度的总数count为cnt[i]。
如果dp[i]等于max，则将cnt[i]加入计数count。
最后返回count。

Code

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
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        int max = 0;
        int count = 0;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            cnt[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];    //如果后面的数字大于前面的，且可以组成更长的数列，则继承之前的计数。
                    }
                    else if(dp[j] + 1 == dp[i]){    //如果之前已经更新过dp[i]，则有新的组合长度一直，加和之前的计数。
                        cnt[i] += cnt[j];
                    }
                }
            }
            if(dp[i] > max){    //如果当前的长度大于之前的最大值，则更新。
                max = dp[i];
                count = cnt[i];  //同时将之前计算的计数记录。
            }
            else if(dp[i] == max){  //如果有同样达到最大值的情况，则加和计数。
                count += cnt[i];
            }
        }
        return count;
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 237 words)

108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

以中序遍历的顺序创建节点（代码实现时先序遍历），每次选择范围的中间值mid为根节点。
根节点的左子节点递归左侧left直到mid-1的位置。
根节点的右子节点递归mid+1直到右侧right的位置。
当left > right时，返回null作为二叉树的叶子节点。

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
/**
 * 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 TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length-1);
    }
    
    private TreeNode build(int[] nums, int left, int right){
        if(left > right) return null;
        
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, left, mid-1);
        root.right = build(nums, mid+1, right);
        
        return root;
    }
}
300. Longest Increasing Subsequence
Posted Updated LeetCode / Medium / 复习4 minutes read (About 589 words)

300. Longest Increasing Subsequence

Question

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Solution

贪心算法

创建一个数组记录达到升序的长度时升序数列的最小末尾值。
如果想要增加数组的长度（即增加最大的升序数列长度），则新的数字必须要大于该数组最后一位的大小。
因此在这种情况下，该数组必然是单调递增的。

二分搜索

将第一个数字填入数组。
然后遍历数组，当新一项大于数组的最后一个值时，最大长度加一，并将其加入数组的尾部。
当新一项小于数组的最后一个值时，该数字需要与之前的数组组成新的升序数列。
我们可以替换掉之前数组中比该数字大的第一个数字，代表新组成的数组。（最长数组之间的数字无所谓，只记录最小的末尾值即可。）
我们可以用二分搜索查到该数字需要加入的index。然后替换掉数组中的数字。
单次二分搜索的时间复杂度为O($logn$)。总的时间复杂度为O($nlogn$)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int len = 1;
        ans.add(nums[0]);
    
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > ans.get(ans.size()-1)){
                ans.add(nums[i]);
                len++;
            }
            else{
                int index = Collections.binarySearch(ans, nums[i]);
                if(index < 0){
                    ans.set(-(index+1), nums[i]);
                }
            }
        }
        return len;
    }
}

Solution 2

动态规划，创建一个数组dp[]用来记录最大长度，创建max记录最大值。
遍历，先将数组dp[]上的所有位置都填上1。
从0到i-1遍历j。当nums[i] > nums[j]时，更新dp[i]为dp[i]与dp[j]+1中的较大值。
当更新dp[i]时将其和max比较，如果比max大则更新max。
最后返回max值。时间复杂度为O($n_2$)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            for(int j = i-1; j >= 0; j--){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    if(max < dp[i]){
                        max = dp[i];
                        break;
                    }
                }
            }
        }
        return max;
    }
}
Posted Updated LeetCode / Easy2 minutes read (About 256 words)

572. Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

帮助方法isEqual，DFS搜索判断两个节点的子节点是否完全相同。
DFS搜索，如果两个根节点的值相等则返回，且调用isEqual方法，如果子节点都相同则返回。

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
/**
 * 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 isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot) != null;
    }
    
    private TreeNode dfs(TreeNode root, TreeNode subRoot){
        if(root == null) return null;
        if(root.val == subRoot.val && isEqual(root, subRoot)) return root;
        if(dfs(root.left, subRoot) != null ) return dfs(root.left, subRoot);
        else return dfs(root.right, subRoot);
    }
    
    private boolean isEqual(TreeNode root, TreeNode subRoot){
        if(root == null || subRoot == null) return root == subRoot;
        if(root.val != subRoot.val) return false;
        return isEqual(root.left, subRoot.left) && isEqual(root.right, subRoot.right);
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 394 words)

162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

二分搜索，由于只需要搜索任意一个山峰，因此只要向上走，一定可以走到一个峰。
当中值的下一个值是增长时（向上爬山），则更新左侧指针的位置为中值+1。继续搜索下一个中值。
否则更新右侧指针的位置为当前中值，等于向左侧进行搜索。
最后返回左侧指针停留的位置。
时间复杂度为O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findPeakElement(int[] num) {
        int left = 0;
        int right = num.length - 1;

        while (left < right) {
            int mid1 = (right - left) / 2 + left;
            int mid2 = mid1 + 1;
            if (num[mid1] < num[mid2])
                left = mid1+1;
            else
                right = mid1;
        }
        return left;
    }
}

一次遍历，找到峰值，返回其index。
时间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findPeakElement(int[] nums) {
        int peak = 0;
        
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > nums[peak]){
                peak = i;
            }
        }
        return peak;
    }
}

分治法，每次将数组分为两组，向下递归。
当数组长度为1时返回元素，比较返回来的两个数值的大小。
返回其中的峰值index。
此解法时间为O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findPeakElement(int[] nums) {
        return findPeak(nums,0,nums.length-1);
    }
    
    private int findPeak(int[] nums, int left, int right){
        if(left == right){
            return left; 
        }
        int mid = left + (right - left) / 2;
        int i = findPeak(nums, left, mid);
        int j = findPeak(nums, mid+1, right);
        
        if(nums[i] > nums[j]){
            return i;
        }
        else{
            return j;
        }
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 256 words)

153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

二分搜索，寻找断裂点。
当left小于right时循环。
每次计算出mid，分为两种情况：

  • 如果nums[mid]小于nums[nums.length-1]，则右半侧为顺序的。
  • 反之则左半侧为顺序，右半侧为无序的。
    以此来更新搜索范围。
    由于mid计算公式向下取整。
    当更新left时更新为mid+1，向前一格。
    当更新right时更新为mid。
    最后返回nums[left]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findMin(int[] nums) {
        return findBreakPoint(nums,0,nums.length-1);
    }
    
    private int findBreakPoint(int[] nums, int left, int right){
        while(left < right){
            int mid = (right - left)/2 + left;
            if(nums[mid] < nums[nums.length-1]){
                right = mid;
            }
            else if(nums[mid] >= nums[0]){
                left = mid+1;
            }
            
        }
        return nums[left];
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 303 words)

33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

二分搜索，二分后将会形成两个区间，一个区间是顺序的，另一个是无序的。
如果target等于中间值则返回。
分别处理两种情况下移动指针的方式。
当顺序区间在左半边时：
当target在顺序区间内，则更新右指针的位置。
否则更新左指针位置。
当顺序区间在右半边时：
当target在顺序区间内，则更新左指针的位置。
否则更新右指针位置。

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
class Solution {
    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length-1;
        
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                return mid;
            }
            
            if( nums[mid] >= nums[0] ){
                if(target >= nums[0] && target < nums[mid] ){
                    right = mid - 1;
                }
                else{
                    left = mid + 1;
                }
            }
            else{
                if(target > nums[mid] && target <= nums[nums.length-1]){
                    left = mid + 1;
                }
                else{
                    right = mid -1;
                }
            }

        }
        return -1;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 315 words)

34. Find First and Last Position in Sorted Array

问题
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

二分搜索，搜索中间项。
中间项等于左侧和右侧指针的中点，根据搜索左侧边界和右侧边界选择二分向下舍去或是二分向上补足。
当中间项小于目标，则更新左侧边界。
若中间项大于目标，则更新右侧边界。
当中间项等于目标时，根据搜索左侧边界还是右侧边界选择更新左侧或右侧。
由于有可能有重复元素存在，因此需要继续二分搜索下去，直到右侧边界大于左侧边界。

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{searchLeft(nums,target),searchRight(nums,target)};
    } 

    private int searchRight(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                left = mid+1;
            }
        }
        return result;
    }
    
    private int searchLeft(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left+1)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                right = mid-1;
            }
        }
        return result;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 216 words)

74. Search a 2D Matrix

问题
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 from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

二分搜索，以整个数组尺寸作为搜索范围。
每次搜索中间值，如等于target则返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0;
        int right = (matrix.length * matrix[0].length) - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int row = mid / matrix[0].length;
            int col = mid % matrix[0].length;
            if(matrix[row][col] == target){
                return true;
            }
            else if(matrix[row][col] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return false;
    }
}

双指针，先搜索到合适的行。
再搜索到合适的列。

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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = 0;
        
        while(i < matrix.length){
            if(matrix[i][0] == target){
                return true;
            }
            else if(matrix[i][0] < target){
                i++;
            }
            else{
                break;
            }
        }
        if( i == 0 ){
            return false;
        }
        i--;
        while(j < matrix[0].length){
            if(matrix[i][j] == target){
                return true;
            }
            j++;
        }
        return false;
    }
}
Follow

Recents

Archives

Links

×