Tag: 双向遍历

Posted 2022-07-04Updated 2022-07-04LeetCode / Hard / 复习2 minutes read (About 227 words)

Question

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Solution

双向遍历。
先从左至右遍历数组，如果上一个数值小于当前数值，则当前糖果等于上一个糖果数+1。
然后从右至左遍历数组，同理计算right的数值。
然后保存right与left[]里较大的数值，作为需要分配的糖果数加入到res。

Code

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        for(int i = 0; i < ratings.length; i++){
            if(i > 0 && ratings[i] > ratings[i-1]){
                left[i] = left[i-1] + 1;
            }
            else{
                left[i] = 1;
            }
        }
        
        int right = 0, res = 0;
        for(int i = ratings.length-1; i >= 0; i--){
            if(i < ratings.length-1 && ratings[i] > ratings[i+1]){
                right++;
            }
            else{
                right = 1;
            }
            res += Math.max(left[i], right);
        }
        return res;
    }
}

Posted 2022-06-26Updated 2022-06-25LeetCode / Medium3 minutes read (About 390 words)

1423. Maximum Points You Can Obtain from Cards

Question

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Solution 1

这种取两端的问题可以转化为取中间连续k个元素之和最小。

计算所有数字的和sum。
然后用维护一个宽度为k的窗口内的加和temp，并记录其最小值min。

返回sum - min，结果即是取两侧时可以取的最大值。

Code

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, sum = 0;
        for(int point : cardPoints) sum += point; //求所有数值的和
        if(k == n) return sum;
        int left = 0, right = n-k, temp = 0, min = 0;
        
        for(int i = 0; i < n-k; i++){
            temp += cardPoints[i];
            min = temp;
        }
        while(right < n){   //维护窗口内的temp，并更新min
            temp += cardPoints[right] - cardPoints[left];; 
            min = Math.min(min, temp);
            right++;
            left++;
        }
        return sum - min;
    }
}

Solution 2

分别计算从两侧开始的加和并记录在两个数组left[]和right[]上。

然后分别取两个指针，左侧指针l从0开始遍历到k，右侧指针对应的位置为l+n-k。计算并更新最大值max。

Code

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, max = 0;
        int[] left = new int[n+1], right = new int[n+1];
        
        for(int i = 0; i < n; i++){
            left[i+1] = left[i] + cardPoints[i];
            right[n-i-1] = right[n-i] + cardPoints[n-i-1];
        }
        
        for(int l = 0; l <= k; l++){
            max = Math.max(max, left[l] + right[n-k+l]);
        }
        
        return max;
    }
}

Posted 2022-05-03Updated 2022-05-04LeetCode / Medium / 复习3 minutes read (About 404 words)

581. Shortest Unsorted Continuous Subarray

Question

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

Solution

未排序子数组的左侧和右侧均为单调递增的区间。
我们的目标就是找到单调递增的边界。

中段由于是乱序的，因此其最大值与最小值必定不在中段的两端。
因此我们可以从左至右的遍历数组，不断地维护一个当前的最大值max。
由于只有中段是无序的，因此只有此时后面的数值才可能小于前面的最大值max。
当这种情况发生时，则记录当前节点位置。
同理，我们也可以从右至左遍历，维护一个当前的最小值min。
只有在中段时，前面的数值才可能大于后面的最大值min。
当这种情况发生时，则记录当前节点位置。

最后如果两个指针的位置相同，则返回0。（此时数组完全有序，指针未移动。）
如果两个指针的位置不同，则返回两者的差+1。（即两者的宽度。）

Code

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        
        for(int i = 0; i < nums.length; i++){
            if(nums[i] < max) end = i;
            else max = nums[i];
            
            int j = nums.length - i - 1;
            if(nums[j] > min) start = j;
            else min = nums[j];
        }
        if(start == end) return 0;
        return end - start + 1;
    }
}

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

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Recents

Archives

Links