Question

You are given a 0-indexed integer array nums and an integer threshold.

Find the length of the longest subarray of numsstarting at index l and ending at index r (0 <= l <= r < nums.length) that satisfies the following conditions:

• nums[l] % 2 == 0
• For all indices i in the range [l, r - 1], nums[i] % 2 != nums[i + 1] % 2
• For all indices i in the range [l, r], nums[i] <= threshold

Question

You are given an integer n. We say that two integers x and y form a prime number pair if:

• 1 <= x <= y <= n
• x + y == n
• x and y are prime numbers

Return the 2D sorted list of prime number pairs [xi, yi]. The list should be sorted in increasing order of xi. If there are no prime number pairs at all, return an empty array.

Note: A prime number is a natural number greater than 1 with only two factors, itself and 1.

Question

You are given two 0-indexed integer arrays nums1 and nums2, both of length n.

You can choose two integers left and right where 0 <= left <= right < n and swap the subarray nums1[left...right] with the subarray nums2[left...right].

• For example, if nums1 = [1,2,3,4,5] and nums2 = [11,12,13,14,15] and you choose left = 1 and right = 2, nums1 becomes [1,<strong><u>12,13</u></strong>,4,5] and nums2 becomes [11,<strong><u>2,3</u></strong>,14,15].

You may choose to apply the mentioned operation once or not do anything.

The score of the arrays is the maximum of sum(nums1) and sum(nums2), where sum(arr) is the sum of all the elements in the array arr.

Return the maximum possible score.

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Solution

滑动窗口。一开始想用dp解决的。
后来发现可以优化到直接记录连续的最大差值即可。
以后有提到连续的一定要想到滑动窗口实现。

辅助方法getMinContigouousDiff()用来计算两个数组间连续的最小的差值和。
当sum为负数时，窗口向右侧扩展，将新的位置加入sum，并更新最小值min。
当扩展后sum大于0时，则放弃之前的所有元素，将sum归零。
最后返回最小值min。

计算两个数组的所有数字之和t1和t2。分别计算nums1[]和nums2[]的差min1和nums2[]和nums1[]的差min2。
在其中替换连续的部分则为t1-min1，t2-min2。取两者中较大的数字返回即可。

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

class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int t1 = 0, t2 = 0;
        for(int i = 0; i < n ;i++){ //计算两个数组未替换前的和
            t1 += nums1[i];
            t2 += nums2[i];
        }
        int min1 = getMinContiguousDiff(nums2, nums1);
        int min2 = getMinContiguousDiff(nums1, nums2);
        return Math.max(t1 - min1, t2 - min2);  //替换连续的部分，两者中取最大值
    }
    
    private int getMinContiguousDiff(int[] nums1, int[] nums2){ //滑动窗口，求连续元素间的最小差值
        int sum = 0, min = 0;
        for(int i = 0; i < nums1.length; i++){
            if(sum <= 0){   //当sum为负数时，窗口向右侧扩展，将新的位置加入sum
                int diff = nums2[i] - nums1[i];
                sum += diff;
                if(diff < 0) min = Math.min(min, sum);  //更新最小值
                if(sum > 0) sum = 0;    //当sum为正数时，抛弃前面的元素，重新开始计算sum
            }
        }
        return min;
    }
}

Question

There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed.

Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

Note that if a house is placed on the i<sup>th</sup> plot on one side of the street, a house can also be placed on the i<sup>th</sup> plot on the other side of the street.

Solution

计算单侧河道可以放置的种类。
一开始用的是DFS搜素来计算可以放置的种类。
计算后发现是以（2，3）开始的斐波那契数列。

因此直接计算n位置的斐波那契数列值即可。
然后两边可以匹配的种类就是其平方。

记忆化搜索

在计算斐波那契数列时，由于要多次重复计算前面的位置，因此可以采用记忆化搜索记录对应的斐波那契额值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    long[] memo;
    public int countHousePlacements(int n) {
        memo = new long[n+1];
        long res = fibo(n);
        res *= res;
        res %= 1000000007;
        return (int) res;
    }
    
    private long fibo(int n){
        if(n == 1) return 2;
        else if(n == 2) return 3;
        if(memo[n] != 0) return memo[n];
        memo[n] = fibo(n-1) % 1000000007 + fibo(n-2) % 1000000007;

        return memo[n];
    }
}

Question

A square matrix is said to be an X-Matrix if both of the following conditions hold:

1. All the elements in the diagonals of the matrix are non-zero.
2. All other elements are 0.

Given a 2D integer array grid of size n x n representing a square matrix, return true* if grid is an X-Matrix*. Otherwise, return false.

Solution

遍历，直接判断是否在对角线上，如果在且位置为0，则返回false。
如果不在对角线上，且位置部位0，则返回false。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j || i + j == n - 1){
                    if(grid[i][j] == 0) return false;
                }
                else if(grid[i][j] != 0) return false;
            }
        }
        return true;
    }
}

Question

You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:

1. The greatest common divisor of any adjacent values in the sequence is equal to 1.
2. There is at least a gap of 2 rolls between equal valued rolls. More formally, if the value of the i<sup>th</sup> roll is equal to the value of the j<sup>th</sup> roll, then abs(i - j) > 2.

Return the* total number** of distinct sequences possible*. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

Two sequences are considered distinct if at least one element is different.

Solution

DFS+记忆化搜索剪枝。
辅助方法getValidNext计算前两个位置为last1和last2时的所有的下一个有效值，将返回值储存在next[][]数组中。

DFS搜索

DFS搜索，传入剩余骰子数量n，前两个骰子的值x和y。
从next[x][y]中得到所有有效值。并进行递归。
将返回结果加和并返回。
当n等于0时，只有一个组合，因此返回1。

记忆化搜索

在搜索时会重复计算很多相同的x，y与n的组合，因此可以采用记忆化搜索进行剪枝。
用memo[][][]数组记录x，y与n的状态。如果此前已经计算过其结果，则直接返回memo[x][y][n]。

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
34
35
36
37
38
39

class Solution {
    List<Integer>[][] next;
    int[][][] memo;
    public int distinctSequences(int n) {
        next = new ArrayList[7][7];
        for(int i = 0; i <= 6; i++){
            for(int j = 0; j <= 6; j++){
                next[i][j] = getValidNext(i, j);
            }
        }
        memo = new int[7][7][10001];
        return count(n, 0, 0);
    }
    
    private int count(int n, int x, int y){
        if(n == 0) return 1;
        if(memo[x][y][n] != 0) return memo[x][y][n];
        List<Integer> validNext = next[x][y];
        int sum = 0;
        for(int z : validNext){
            sum += count(n-1, y, z);
            sum %= 1000000007;
        }
        memo[x][y][n] = sum;
        return sum;
    }
    
    private List<Integer> getValidNext(int last1, int last2){
        List<Integer> arr = new ArrayList<>();
        for(int i = 1; i <= 6; i++){
            if(last1 == 0 && last2 == 0) arr.add(i);
            else if(i == last1 || i == last2) continue;
            else if((last2 & 1) == 0 && (i & 1) == 0) continue;
            else if((last2 == 3 || last2 == 6) && (i == 3 || i == 6)) continue;
            else arr.add(i);
        }
        return arr;
    }
}

Question

You are given a 0-indexed integer array nums. In one operation, select any non-negative integer x and an index i, then update nums[i] to be equal to nums[i] AND (nums[i] XOR x).

Note that AND is the bitwise AND operation and XOR is the bitwise XOR operation.

Return the maximum possible bitwise XOR of all elements of nums after applying the operation any number of times.

Solution

异或运算相当于不进位的加和。
和运算相当于掩码操作。
或运算相当于保留该位上的1。

由于我们要对所有数字进行异或运算，因此只要能改变某一位对应的数字，我们就可以确保这一位在进行异或运算时结果可以为1。（当不改变时改为的异或运算结果为0，则我们只需要改变改为即可得到1）

将所有我们可以操作的位置变为1，就可以得到最大值。

因此，我们只需要确定哪些位是我们可以操作的即可：

• nums[i]与任意正整数进行异或运算可以得到任意整数。在这个条件下我们可以得到任意的32位整数。
• 然而和运算相当于掩码操作，如果nums[i]对应二进制的某一位上位0，则我们无法通过和运算将这一位改变为1。

只要该位出现过1，则我们可以控制这个位。因此我们可以通过或运算所有数字，保留所有可控制的位。

Code

1
2
3
4
5
6
7
8
9

class Solution {
    public int maximumXOR(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum |= num;
        }
        return sum;
    }
}

Question

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [a<sub>i</sub>, b<sub>i</sub>] denotes that there exists an undirected edge connecting nodes a<sub>i</sub> and b<sub>i</sub>.

Return the number of pairs of different nodes that are unreachable from each other.

Solution

并查集，将所有元素union，然后计算每个元素所在集之外的元素和相加即可。
注意由于是无向图，因此计算加和时每两个点之间都计算了两次，因此需要将结果除以2。

路径压缩

在进行find()查找时，将经过的每一个节点设置为根节点。
这样做可以有效的降低树高，减少操作次数。
采用递归的形式实现。

按秩合并

用size[]数组记录当前位置的节点数量。
在合并两个数字时，将秩较小的数字指向秩较大的数字。
并更新根节点的size[]值。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    public long countPairs(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        long res = 0;
        for(int[] edge : edges){
            uf.union(edge[0], edge[1]);
        }
        
        for(int i = 0; i < n; i++){
            res +=  ( n - uf.getSize(i) );
        }
        return res/2;   //无向图，因此每两个节点计算了两次
    }
    
    class UnionFind {
        int[] parent;
        int[] size;

        public UnionFind(int n){
            parent = new int[n];
            size = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                size[i] = 1;
            }
        } 
           
        private int find(int id){
            return parent[id] == id ? id : find(parent[id]);   //路径压缩，将路径上的所有节点归结到根节点上
        }
           
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(size[p1] > size[p2]){    //按秩进行压缩
                parent[p2] = p1;
                size[p1] += size[p2];
            }
            else{
                parent[p1] = p2;
                size[p2] += size[p1];
            }
            return true;
        }

        public int getSize(int num){
            return size[find(num)];
        }
    }
}****

Question

You are given a string s, where every two consecutive vertical bars '|' are grouped into a pair. In other words, the 1st and 2nd '|' make a pair, the 3rd and 4th '|' make a pair, and so forth.

Return *the number of '*' in s, excluding the '*' between each pair of *'|'.

Note that each '|' will belong to exactly one pair.

Solution

统计“|”字符出现的数量，如果数量为偶数时，则计算出现的“*”符号。

Code

1
2
3
4
5
6
7
8
9
10

class Solution {
    public int countAsterisks(String s) {
        int num = 0, count = 0;
        for(char c : s.toCharArray()){
            if(c == '|') num++;
            else if((num & 1) == 0 && c == '*') count++;
        }
        return count;
    }
}

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

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

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

Question

As the ruler of a kingdom, you have an army of wizards at your command.

You are given a 0-indexed integer array strength, where strength[i] denotes the strength of the i<sup>th</sup> wizard. For a contiguous group of wizards (i.e. the wizards’ strengths form a subarray of strength), the total strength is defined as the product of the following two values:

• The strength of the weakest wizard in the group.
• The total of all the individual strengths of the wizards in the group.

Return the sum of the total strengths of all contiguous groups of wizards. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

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

Solution

参考连接

根据题意，我们需要的结果是所有子数列乘以该子数列中最小值之和。

数组strength[]中的每一个元素，都充当一定范围内的子数列的最小值。因此我们需要**确定每个元素充当最小值的范围(left, right)**。然后计算这个元素可以组成的子数列的和与这个元素的乘积。

我们的问题相当于确定下一个更小元素，而单调栈专门处理这一类问题——“下一个更大/更小元素”
496. Next Greater Element I

通过单调栈，我们可以确定最小值为strength[i]的子数列的范围(left, right)，并将其保存在两个数组left[]与right[]中。

最后通过前缀和的计算，来确定(left, right)范围内的子数列之和。

单调栈

新建两个数组left[]， right[]保存以strength[i]为最小值的范围。

维护两个单调栈，保证下列关系：
strength[left] < strength[i]
strength[right] <= strength[i]

其中，left取小于号，而right可以等于是为了取值不重复。

注意，单调栈保存的是下标，这样使用起来更加灵活。

前缀和

为了得到范围（left, right）内的所有子数列之和。我们可以观察left, i, right之间的关系。

…left-1, left, left + 1, left + 2, … i-1, i, i+1, … right-1, right, right+1…

• 开始于 left+1的子数列:
  sum(left+1, … i) = prefix[i + 1] - prefix[left + 1]
  sum(left+1, … i+1) = prefix[i + 2] - prefix[left + 1]
  …
  sum(left+1, … right-1) = prefix[right] - prefix[left + 1]
• 开始于left+2的子数列:
  sum(left+2, … i) = prefix[i + 1] - prefix[left + 2]
  sum(left+2, … i+1) = prefix[i + 2] - prefix[left + 2]
  …
  sum(left+2, … right-1) = prefix[right] - prefix[left + 2]
  …
• 开始于i的子数列:
  sum(i, … i) = prefix[i + 1] - prefix[i]
  sum(i, … i+1) = prefix[i + 2] - prefix[i]
  …
  sum(i, … right-1) = prefix[right] - prefix[i]

合并这些式子，我们可以得到：

• 正数 部分:
  (prefix[i + 1] + prefix[i + 2] + ... + prefix[right]) * (i - left)
• 负数 部分:
  (prefix[left + 1] + prefix[left + 2] + ... + prefix[i]) * (right - i)

最后我们可以提前计算前缀和的前缀和来优化计算步骤，注意计算时需要将各个部分模除以保证不超过范围。
正数部分模除后需要加上MOD以保证其减去负数部分的结果大于0。

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
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    public int totalStrength(int[] strength) {
        long MOD = 1_000_000_007;
        int n = strength.length;
        
        Deque<Integer> mono = new ArrayDeque<>();
        int[] left = new int[n], right = new int[n];
        
        for(int i = 0; i < strength.length; i++){   //单调栈，记录比当前元素strength[i]小的第一个左侧位置strength[left]
            while(!mono.isEmpty() && strength[mono.peek()] >= strength[i]){
                mono.pop();
            }
            left[i] = mono.isEmpty() ? -1 : mono.peek();
            mono.push(i);
        }
        mono.clear();
        for(int i = n-1; i >=0; i--){   //单调栈，记录比当前元素strength[i]小的第一个右侧位置strength[right]
            while(!mono.isEmpty() && strength[mono.peek()] > strength[i]){
                mono.pop();
            }
            right[i] = mono.isEmpty() ? n : mono.peek();
            mono.push(i);
        }
        
        long[] prefix = new long[n+1], prefix_sum = new long[n+2];
        
        for(int i = 1; i <= strength.length; i++){  //计算前缀和
            prefix[i] = (prefix[i-1] + strength[i-1]) % MOD;
        }
        
        for(int i = 2; i <= strength.length+1; i++){    //计算前缀和的前缀和
            prefix_sum[i] = (prefix_sum[i-1] + prefix[i-1]) % MOD;
        }
        
        long res = 0;
        
        for(int i = 0; i < n; i++){
            res += ((prefix_sum[right[i] + 1] - prefix_sum[i + 1]) * (i - left[i]) % MOD + MOD -    //这里加MOD是为了保证前项大于后项，防止出现负数
                    (prefix_sum[i + 1] - prefix_sum[left[i] + 1]) * (right[i] - i) % MOD ) * strength[i];
            res %= MOD;
        }
        
        return (int) res;
    }
}

Question

You are given a 2D integer array stockPrices where stockPrices[i] = [day<sub>i</sub>, price<sub>i</sub>] indicates the price of the stock on day day<sub>i</sub> is price<sub>i</sub>. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:

Solution

如果只有一个点，无法组成线段则返回0。否则至少可以组成1条线段。

首先将所有点根据x的位置排序，然后一次比较连续的各个向量的方向。
为了防止除法精度问题，计算两个向量（三个点组成两个向量）的叉乘，如果叉乘为0，则说明两个向量是平行的，此时不需要增加计数。
如果叉乘结果不等于0，则将计数+1。

最后返回计数的结果。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minimumLines(int[][] stockPrices) {
        if(stockPrices.length == 1) return 0;
        
        Arrays.sort(stockPrices, (a,b) -> a[0] - b[0]);
        int count = 1, lastX = 0, lastY = 0;
        
        for(int i = 1; i < stockPrices.length; i++){
            int x = stockPrices[i][0] - stockPrices[i-1][0];
            int y = stockPrices[i][1] - stockPrices[i-1][1];
            
            int k = lastX * y - lastY * x;
            if(k != 0) count++;
            lastX = x;
            lastY = y;
        }
        return count;
    }
}

Question

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The i<sup>th</sup> bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags.

Return* the maximum number of bags that could have full capacity after placing the additional rocks in some bags.*

Solution

计算每个背包的剩余空间，然后进行排序。
按从小到大的顺序依次减少石头的总数。
设置i作为选取石头的计数。每次循环将i增加，直到剩余的石头数量小于0。
如果最后剩下的石头仍然大于等于0，则返回计数。
否则返回计数-1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int[] diff = new int[capacity.length];
        for(int i = 0 ; i < capacity.length; i++){
            diff[i] = capacity[i] - rocks[i];
        }
        
        Arrays.sort(diff);
        int i = 0;
        while(additionalRocks > 0 && i < diff.length){
            additionalRocks -= diff[i];
            i++;
        }
        return additionalRocks >= 0 ? i : i - 1;
    }
}