Tag: 贪心算法

Posted 2022-06-25Updated 2022-06-24LeetCode / Medium2 minutes read (About 356 words)

Question

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Solution 1

记录两个最大值last1和last2，初始化为整数最小值。真值flag初始化为true用来记录是否已经有非单调递增的值出现。
遍历数组，如果当前数字num大于等于last2，则符合单调递增，更新last1和last2。

如果num小于last2，则不符合单调递增，此时将flag置为false。

如果num大于等于last1，则跳过现有的last2，将num保存在last2上。
如果num小于，则保留当前的last2

如果flag已经为false，则非单调递增的数字超过1个，返回false。
遍历完毕则返回true。

Code

class Solution {
    public boolean checkPossibility(int[] nums) {
        boolean flag = true;
        int last1 = Integer.MIN_VALUE, last2 = Integer.MIN_VALUE;
        
        for(int num : nums){
            if(num >= last2){
                last1 = last2;
                last2 = num;
            }
            else if(flag){
                flag = false;
                if(num >= last1) last2 = num;
                else continue;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Solution 2

原理和Solution 1相同，只不过采用单调栈的形式保存单调递增数字。

Code

class Solution {
    public boolean checkPossibility(int[] nums) {
        Stack<Integer> s = new Stack<>();
        boolean flag = true;
        
        for(int num : nums){
            if(s.isEmpty() || num >= s.peek()) s.push(num);
            else if(flag){
                flag = false;
                int temp = s.pop();
                if(s.isEmpty() || num >= s.peek()) s.push(num);
                else s.push(temp);
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Posted 2022-06-24Updated 2022-06-24LeetCode / Hard / 复习2 minutes read (About 335 words)

630. Course Schedule III

Question

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Solution

贪心算法，优先级队列实现。
优先选择截止日期更短的课程。
优先级队列pq记录当前已选课程，按持续时间从长到短排列。
同时维护当前的日期curDay。

当当前选择的课程截止日期晚于curDay加上当前的持续时间duration时，查看大根堆里最长的课程longestDuration。如果最长的时间大于当前时间，则将其挤出，并将当前课程加入。

如果当前课程截止日期晚于curDay，则直接将其加入队列中，并更新curDay。

Code

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int curDay = 0;
        for(int[] course : courses){
            int duration = course[0];
            int lastDay = course[1];
            
            if(curDay + duration > lastDay){    //大于截止日期
                if(pq.isEmpty()) continue;
                int longestDuration = pq.peek()[0];
                if(longestDuration > duration){ //替换到当前队列中持续日期最长的课程
                    curDay -= pq.poll()[0];
                    curDay += duration;
                    pq.offer(course);
                }
            }
            else{   //小于截止日期则加入选课
                curDay += duration;
                pq.offer(course);
            }
        }
        return pq.size();
    }
}

Posted 2022-06-21Updated 2022-06-20LeetCode / Medium / 复习2 minutes read (About 341 words)

1642. Furthest Building You Can Reach

Question

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks.

If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Solution

贪心算法+优先级队列。

从第二栋楼开始遍历当前位置，下一栋楼与当前位置的高度差为h。
如果h小于0，则无成本前进。
否则如果剩余砖块，则优先使用砖块，并将使用砖块的个数加入大根堆中。
如果剩余砖块不足，且有梯子剩余时，用梯子替换掉小号最多砖块的位置，增加剩余砖块的数量。
如果剩余砖块和梯子都不足，则返回上一个位置。

如果遍历到最后，则返回最后一个建筑物的位置。

Code

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 1; i < heights.length; i++){
            int h = heights[i] - heights[i-1];
            if(h > 0){
                pq.add(h);
                bricks-=h;
                if(bricks < 0){
                    if(ladders > 0){
                        ladders--;
                        bricks += pq.poll();
                    }
                    else{
                        return i-1;
                    }
                }
            }
        }
        return heights.length - 1;
    }
}

Posted 2022-06-18Updated 2022-06-17Hard / 复习10 minutes read (About 1452 words)

968. Binary Tree Cameras

Question

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Solution 1

贪心算法，后序遍历。每次递归根据下面两个子节点的状态来决定当前节点的状态。

每个节点一共有三种状态：

未被监控，返回0。
摄像头，返回1。
已被监控，返回2。

递归，当当前节点为空，则返回2，表示已被监控。这样叶子节点则为未被监控的状态。

如果下面的子节点有一个未被监控，则当前节点需要设置相机，返回1，计数res+1。
如果下面的子节点有一个为摄像头，则当前节点已被监控，返回2。
否则下面的节点均为已被监控，此时返回未被监控0。

Code

/**
 * 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 res = 0; //记录摄像头个数
    public int minCameraCover(TreeNode root) {
        if(judge(root) == 0) res++;  //如果根节点未被监控，则需要增加一个摄像机
        return res;
    }
    public int judge(TreeNode root){
        if(root == null) return 2;   //根节点为空时返回2，这样叶子节点变为未被监控
        int left = judge(root.left);
        int right = judge(root.right);

        if(left == 0 || right == 0){    //如果左右子节点有未被监控的节点，则当前节点设置为摄像机，结果加一，返回1
            res++;
            return 1;
        }
        if(left == 1 || right == 1) return 2;    //如果左右子节点中有摄像机，则当前节点已被监控，返回2
        return 0;   //如果左右子节点都被监控，则当前节点未被监控，返回0
    }
}

Solution 2

参考：从递归优化到树形DP

树形DP。
递归，每次返回当前节点所有子节点的最小相机数。
每一个节点有三种状态：

放置了相机。
没有相机，但是被父节点parent监控。
没有相机，但是被子节点son监控。

将三种状态分别传入minCam()方法。

递归方法 minCam()

在递归时传入两个参数hasCamera和isWatched，来判断当前节点是否有相机，是否被监控。
当当前节点为空节点时，如果设置应当有相机（做不到）则返回无限大，消除这个返回值。如果不应该有相机，则返回0。

向下递归子节点。

当当前节点应该有相机时：
子节点一定被监控因此isWatched为true。
子节点可以放置或不放置相机，因此hasCamera可以为true或false。
注意当前位置放置相机，则子节点最多放置一个相机，因此一共有三种组合。
由于相机至少有一个，因此返回其中的最小值+1。
当当前节点没有放置相机，但被父节点监控时：
左右节点一共有四种组合，分别同时将子节点的监控状态向下递归。
返回其中的最小值。
当当前节点没有放置相机，也没有被父节点监控，而是被子节点监控时：
子节点至少有一个相机，向下递归状态，一共有三种组合。
返回其中的最小值

然后分别调用minCam(root, true, true)和minCam(root, false, fasle)，取两者中的小值，即可得到答案。

树形dp优化剪枝

上面的方法实际采用时会超时，因为我们重复了三次调用一个子树下的三种状态的minCam。
因此我们可以将三种状态下的minCam分别保存在数组中返回。

withCam: 当前子树root有相机。
noCamWatchedByParent: 当前子树root没有相机，被父节点监控。
noCamWatchedBySon: 当前子树root没有相机，被子节点监控。

在每次递归时，获取数组minCam(root.left)和minCam(root.right)。
然后根据左右子节点的三个参数来计算当前节点的新的三个参数，将其返回。

Code

/**
 * 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 int minCameraCover(TreeNode root) {
        return Math.min(minCam(root, true, true), minCam(root, false, false));
    }
    
    private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){
        if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;

        if(hasCamera){
            int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true));
            min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true));
            return 1 + min;
        }
        else if(isWatched){
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false));
            return min;
        }
        else{
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            return min;
        }
    }
}

Code

/**
 * 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 int minCameraCover(TreeNode root) {
        int[] res = minCam(root);
        return Math.min(res[0], res[2]);
    }
    
    private int[] minCam(TreeNode root){
        if(root == null){
            return new int[] {Integer.MAX_VALUE/2, 0, 0};
        }
        int[] left = minCam(root.left);
        int[] right = minCam(root.right);

        int withCam = 1 + Math.min(left[1] + right[1], Math.min(left[0] + right[1], left[1] + right[0]) );
        int noCamWatchedByParent = Math.min( left[0] + right[0], Math.min( left[0] + right[2], Math.min( left[2] + right[0], left[2] + right[2] )));
        int noCamWatchedBySon = Math.min( left[0] + right[0], Math.min( left[0] + right[2], left[2] + right[0]));
        return new int[] {withCam, noCamWatchedByParent, noCamWatchedBySon};
    }
}

Posted 2022-05-06Updated 2022-05-05LeetCode / 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

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 2022-05-01Updated 2022-08-07LeetCode / 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

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

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 2022-04-28Updated 2022-04-28LeetCode / Medium / 复习3 minutes read (About 409 words)

1631. Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

A*算法，启发式搜索。BFS搜索结合Priority Queue。
采用一个数组储存当前访问点的位置，以及其effort。
采用优先队列，优先搜索effort最小的方向。
每次循环倾倒出队列中所有的元素。
计算上一个节点和当前节点的差值作为nextEffort，并和上一个节点的effort作比较，较大的作为当前节点的effort，
将effort作为权重，优先搜索一个层级内effort较小的路径。
将所有操作加入队列，并排除越界的位置。
当当前节点为最后一个节点时，返回其effort。

class Solution {
    int min;
    public int minimumEffortPath(int[][] heights) {
        int[][] operations = {{1,0},{-1,0},{0,1},{0,-1}};
        int m = heights.length, n = heights[0].length;
        
        Queue<int[]> q = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        int[] point = {0, 0, 0};
        int size = 1;
        int[][] visited = new int[m][n];
        
        q.add(point);
        while(!q.isEmpty()){
            
            for(int k = 0; k < size; k++){
                int[] curr = q.poll();
                int i = curr[0], j = curr[1], currEffort = curr[2];
                if(visited[i][j] == 1) continue;
                visited[i][j] = 1;
                if(i == m-1 && j == n-1) return currEffort;
                for(int[] operation : operations){
                    int nextX = i + operation[0];
                    int nextY = j + operation[1];
                    if(nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) continue;
                    int nextEffort = Math.max(currEffort, Math.abs(heights[i][j] - heights[nextX][nextY]));
                    int[] next = {nextX, nextY, nextEffort};
                    
                    q.add(next);
                }
            }
            size = q.size();
        }
        return -1;
    }
}

Posted 2022-04-28Updated 2022-04-27LeetCode / Medium / 复习a minute read (About 209 words)

45. Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

设置一个当前可以访问的最大范围limit，在遍历中对其进行更新。
和当前可访问位置中的最远距离end，每次访问到达end时，计算步数。

遍历数组，比较limit和当前i能访问的最远距离i+nums[i]，保留较大值。
当i达到end时，更新end为之前记录的可访问最远距离limit。步数+1。

class Solution {
    public int jump(int[] nums) {
        int count = 0;
        int limit = 0;
        int end = 0;
        
        for(int i = 0; i < nums.length-1; i++){
            limit = Math.max(limit, i + nums[i]);
            if(i == end){
                end = limit;
                count++;
            }
        }
        
        return count;
    }
}

Posted 2022-04-27Updated 2022-04-26LeetCode / Medium / 复习3 minutes read (About 440 words)

55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

反向查找，动态规划。
到达目标点前必须到达上一个节点，且上一个节点能前进的步数必须大于目标点。
设置目标点goal，反向遍历goal以外的点。
如果该点能前进的步数加上自身的位置i大于目标点，则可以从上一个点到达goal。
更新goal的位置到上一个点。
如果遍历结束后，能返回到起始点0，则可以到达终点。

class Solution {
    public boolean canJump(int[] nums) {
        int goal = nums.length-1;
        for(int i = nums.length-2; i >=0; i--){
            if(nums[i] >= goal - i) goal = i;
        }
        return goal == 0;
    }
}

贪心算法，储存一个到i时可以到达的最远值maxJump。
遍历数组，如果i大于maxJump，则无法到达下一个点，返回false。
在当前点可以到达的最大范围为nums[i]+i，如果大于maxJump则更新该值。
遍历完毕返回true。

class Solution {
    public boolean canJump(int[] nums) {
        int maxJump = 0;
        for(int i = 0; i < nums.length; i++){
            if(i > maxJump) return false;
            maxJump = Math.max(maxJump, nums[i] + i);
        }
        return maxJump >= nums.length-1;
    }
}

设置一个数组记录可访问的范围。
当遍历时，如果可以访问，则将当前位置可以进一步访问的位置变为1。
如果访问范围大于等于数组末尾，则返回真。

class Solution {
    public boolean canJump(int[] nums) {
        int[] reach = new int[nums.length];
        reach[0] = 1;
        
        for(int i = 0; i < nums.length; i++){
            if(reach[i] == 1){
                if(i == nums.length-1) return true;
                for(int j = 0; j < nums[i]; j++){
                    if(i+j+1 >= nums.length) return true;
                    reach[i+j+1] = 1;
                }
            }
        }
        return false;
    }
}

Posted 2022-04-21Updated 2022-04-21LeetCode / Mediuma minute read (About 219 words)

763. Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

将英文字母出现的首尾作为intervals看待。
根据字符创建数组并填入左右的index。
根据左侧index排序数组。

从左至右，如果intervals有交集，则合并。
否则在答案中添加当前interval的长度。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[][] alphabet = new int[26][2];
        int head = s.charAt(0) - 'a';
        for(int i = 0; i < s.length(); i++){
            int index = s.charAt(i) - 'a';
            if(head != index && alphabet[index][0] == 0) alphabet[index][0] = i;
            alphabet[index][1] = i;
        }
        
        Arrays.sort(alphabet, (a,b) -> a[0] - b[0]);
        
        List<Integer> ans = new ArrayList();
        int[] hold = alphabet[0];
        for(int i = 1; i < alphabet.length; i++){
            if(alphabet[i][0] <= hold[1]){
                hold[1] = Math.max(hold[1], alphabet[i][1]);
            }
            else{
                ans.add(hold[1]-hold[0]+1);
                hold = alphabet[i];
            }
        }
        ans.add(hold[1]-hold[0]+1);
        return ans;
        
    }
}

Posted 2022-04-20Updated 2022-04-20LeetCode / Medium / 复习3 minutes read (About 511 words)

334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

贪心算法。
将first与second初始化为最大值。
first保存遍历过的最小值。
second保存遍历过的大于之前最小值的最小值。

遍历数组。
条件一：如果数字小于现在第一个值，则更新第一个值。
（此时一定不满足条件二，因此可以安全地更新更小的数字。）
条件二：如果数字大于第一个值，且小于第二个值，则更新第二个值。
（此时第一个值已经被更新过了，满足第一个值小于第二个值。）
条件三：如果数字大于第二个值，则返回true。
（此时两个值一定都被更新过了，满足第一个值小于第二个值小于第三个值。）

注意：
更新first后，second不会更新，但是second的存在可以确保曾经存在first小于second。
如果此时数字大于second，则数组中存在Triplet Subsequence。

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        
        for(int num : nums){
            if(num < first){
                first = num;
            }
            else if(num > first && num < second){
                second = num;
            }
            else if(num > second){
                return true;
            }   
        }
        return false;
    }
}

双向遍历，逐渐收紧搜索窗口。设置i，k两个指针分别在头尾。
当nums[j] <= nums[i]，则更新i指针为j。
当nums[j] >= nums[k]，则更新k指针为j。
如果找到符合条件的nums[i] < nums[j] < nums[k]则返回。

class Solution {
    public boolean increasingTriplet(int[] nums) {
        boolean flag = true;
        int i = 0;
        int k = nums.length -1 ;
        int j;
        int count = 1;
        
        while(i < k && i + count < k){
            if(flag){
                j = i + count;
                if(nums[i] >= nums[j]){
                    i = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] < nums[k]){
                    return true;
                }
                flag = !flag;
            }
            else{
                j = k - count;
                if(nums[k] <= nums[j]){
                    k = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] > nums[i]){
                    return true;
                }
                else{
                    count++;
                }
                flag = !flag;
            }
        }
        return false;
    }
}

Posted 2022-04-19Updated 2022-04-19LeetCode / Medium2 minutes read (About 353 words)

986. Interval List Intersections

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

设置两个指针，分别指向两个intervals的头部。
循环，相交的left等于两者左端的较大值。right等于两者右端的较小值。
只有在left小于right时，两个interval才相交，填入列表。
然后更新两个interval中右端较小的指针。

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> ans = new ArrayList(); 
        int i = 0;
        int j = 0;
        
        while(i < firstList.length && j < secondList.length){
            int left = Math.max( firstList[i][0], secondList[j][0] );
            int right = Math.min( firstList[i][1], secondList[j][1] );
            if(left <= right){
                ans.add(new int[]{left, right});
            }
            if(firstList[i][1] < secondList[j][1]) i++;
            else j++;

        }
        
        int[][] ret = new int[ans.size()][2];
        ans.toArray(ret);
        return ret;
    }
}

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int i = 0;
        int j = 0;
        ArrayList<int[]> ans = new ArrayList(); 
        int[] holdA;
        int[] holdB;

        while(i < firstList.length && j < secondList.length){
            holdA = firstList[i];
            holdB = secondList[j];
            
            int[] arr = new int[2];
            
            if(holdA[0] <= holdB[0] && holdA[1] >= holdB[1]){
                ans.add(holdB);
                j++;
            }
            else if(holdA[0] >= holdB[0] && holdA[1] <= holdB[1]){
                ans.add(holdA);
                i++;
            }
            else if(holdA[0] <= holdB[0] && holdA[1] >= holdB[0]){
                arr[0] = holdB[0];
                arr[1] = holdA[1];
                ans.add(arr);
                i++;
            }
            else if(holdA[0] >= holdB[0] && holdB[1] >= holdA[0]){
                arr[0] = holdA[0];
                arr[1] = holdB[1];
                ans.add(arr);
                j++;
            }
            else if(holdA[1] <= holdB[1]){
                i++;
            }
            else{
                j++;
            }
        }
        int[][] ret = new int[ans.size()][2];
        ans.toArray(ret);
        return ret;
    }
}

Posted 2022-04-19Updated 2022-04-19LeetCode / 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的最大值。
返回总数。

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 2022-04-06Updated 2022-04-05LeetCode / Medium / 复习2 minutes read (About 346 words)

11. Container With Most Water

问题
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

双指针在首尾，二者容量取决于两者中较小的一个。
贪心算法，保留两个指针上较大的元素，移动较小一边的指针。
由于指针移动时距离只会减小，因此当新的元素比上一个更大时才有可能比之前的容量更大。
遍历一次找到最大容量。
时间复杂度：O(n)

感觉这个移动有点博弈论的味了，每次都移动自己最差的一边，虽然可能变得更差，但是总比不动（或者减小）强，动最差的部分可能找到更好的结果，但是动另一边总会更差或者不变，兄弟们，这不是题，这是人生，逃离舒适圈！！（这解释我觉得无敌了，哈哈哈）

class Solution {
    public int maxArea(int[] height) {
        int best = 0;
        
        int i = 0;
        int j = height.length - 1;
        
        while ( i < j ){
            int product = 0;
            if (height[i] < height[j]){
                product = height[i] * ( j -i );
                i++;
            }
            else{
                product = height[j] * ( j -i );
                j--;
            }
            if ( product > best){
                best = product;
            }
        }
        return best;
    }
}

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

递归方法 minCam()

树形dp优化剪枝

Code

Code

Question

Solution

Code

Question

Solution

贪心算法

二分搜索

Code

Solution 2

Code

Recents

Archives

Links