Posted Updated LeetCode / Hard3 minutes read (About 380 words)

2302. Count Subarrays With Score Less Than K

Question

The score of an array is defined as the product of its sum and its length.

  • For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

A subarray is a contiguous sequence of elements within an array.

Solution

第一次在contest中做出hard题目，而且还是超过100%，庆祝一下！（不过因为前一道题做的太久没提交上去……

滑动窗口

数组内全部为正整数，当选择的子数组的尺寸增加时，其乘积是单调递增的。因此可以采用滑动窗口，在循环时维护窗口内数字的和sum和当前的乘积product。

每次将一个新的右侧元素滑入窗口，更新窗口内的sum值，并计算product值。当当前product大于k时，则将左侧的元素滑出窗口，并更新sum和product值。

调整完窗口尺寸后，由于新的right位置可以和前面的每一个子数组组成一个新的数组，因此将count加上当前的left到right的个数即可。

循环结束后返回count。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public long countSubarrays(int[] nums, long k) {
        long count = 0, sum = 0;
        int left = 0, right = 0;
        
        while(right < nums.length){
            sum += nums[right]; //右侧滑入窗口
            long product = sum * (right - left + 1);
            
            while(product >= k){    //当乘积大于k时，左侧滑出窗口
                sum -= nums[left];
                left++;
                product = sum * (right - left + 1);
            }
            count += right - left + 1;  //计算新的right位置可组成的新组合
            right++;
        }
        return count;
    }
}
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;
    }
}
Posted Updated LeetCode / Easy2 minutes read (About 255 words)

2299. Strong Password Checker II

Question

A password is said to be strong if it satisfies all the following criteria:

  • It has at least 8 characters.

  • It contains at least one lowercase letter.

  • It contains at least one uppercase letter.

  • It contains at least one digit.

  • It contains at least one special character. The special characters are the characters in the following string: "!@#$%^&*()-+".

  • It does not contain 2 of the same character in adjacent positions (i.e., "aab" violates this condition, but "aba" does not).

Given a string password, return true* if it is a strong password*. Otherwise, return false.

Solution

直接遍历，记录四个真值对应四个符号，初始化为false，和上一个字符last。
每次遍历检查当前字符，如果等于上个字符则直接返回false。
根据字符范围来改变四个真值，最后返回四个真值的和运算。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean strongPasswordCheckerII(String password) {
        if(password.length() < 8) return false;
        char last = ' ';
        boolean hasLower = false, hasUpper = false, hasDigit = false, hasSpecial = false;
        char[] word = password.toCharArray();
        
        for(int i = 0; i < password.length(); i++){
            char cur = word[i];
            if(last == cur) return false;
            if(cur >= 'a' && cur <= 'z') hasLower = true;
            else if(cur >= 'A' && cur <= 'Z') hasUpper = true;
            else if(cur >= '0' && cur <= '9') hasDigit = true;
            else hasSpecial = true;
            last = cur;
        }
        
        return hasLower && hasUpper && hasDigit && hasSpecial;
    }
}
Follow

Recents

Archives

Links

×