Article directory
- Biweekly 105
-
- [2706. Buy two chocolates](https://leetcode.cn/problems/buy-two-chocolates/)
-
- greedy
- [2707. Extra characters in a string](https://leetcode.cn/problems/extra-characters-in-a-string/)
-
- memory search
- Memory search ==> DP (recursion)
- [2708. The maximum strength of a group](https://leetcode.cn/problems/maximum-strength-of-a-group/)
-
- sort + greedy
- DFS enumerates all subsets
- Dynamic programming (O(n))
- [2709. Greatest common divisor traversal](https://leetcode.cn/problems/greatest-common-divisor-traversal/)
-
- Decompose prime factor + union lookup
Two-week competition 105
2706. Buy two chocolates
Difficulty easy 0
You are given an integer array prices that represents the price of a number of chocolates in a store. At the same time, give you an integer money , indicating the amount of money you have at the beginning.
You must buy exactly two chocolates, and the remaining amount must be non-negative. At the same time you want to minimize the total cost of buying the two chocolates.
Please return the maximum amount of money left after purchasing two chocolates. If buying any two chocolates is more than the money you have, please return money . Note that the remaining money must be a non-negative number.
Example 1:
Input: prices = [1,2,2], money = 3 output: 0 Explanation: Buy chocolates with prices 1 and 2 respectively. You are left with 3 - 3 = 0 bucks. So we return 0 .
Example 2:
Input: prices = [3,2,3], money = 3 Output: 3 Explanation: Buying any 2 chocolates would exceed the amount of money you have, so we return 3.
Tip:
2 <= prices. length <= 501 <= prices[i] <= 1001 <= money <= 100
Greedy
class Solution {<!-- -->
public int buyChoco(int[] prices, int money) {<!-- -->
Arrays. sort(prices);
if(prices[0] + prices[1] > money)
return money;
return money - prices[0] - prices[1];
}
}
2707. Extra characters in string
Moderate difficulty 0
You are given a string s with subscripts starting at 0 and a dictionary of words dictionary . You need to split s into several non-overlapping substrings, each of which appears in dictionary. There may be some extra characters in s not in any substring.
Please adopt the optimal strategy to split s so that the remaining characters are minimum.
Example 1:
Input: s = "leetscode", dictionary = ["leet","code","leetcode"] Output: 1 Explanation: Split s into two substrings: "leet" with subscripts from 0 to 3 and "code" with subscripts from 5 to 8. Only 1 character is not used (subscript 4), so we return 1 .
Example 2:
Input: s = "sayhelloworld", dictionary = ["hello","world"] Output: 3 Explanation: Split s into two substrings: "hello" with subscripts 3 to 7 and "world" with subscripts 8 to 12. The characters with subscripts 0 , 1 and 2 are not used, so we return 3 .
Tip:
1 <= s.length <= 501 <= dictionary. length <= 501 <= dictionary[i].length <= 50dictionary[i]andscontain only lowercase English letters.- The words in the
dictionaryare different from each other.
Memorized Search
class Solution {<!-- -->
Set<String> set;
int res;
int[][] cache;
String s;
public int minExtraChar(String s, String[] dictionary) {<!-- -->
set = new HashSet<>();
for(String d : dictionary){<!-- -->
set. add(d);
}
this.s = s;
res = s. length();
cache = new int[res + 1][res + 1];
for(int i = 0; i < res; i ++ ){<!-- -->
Arrays.fill(cache[i], -1);
}
return dfs(0, s. length());
}
// Define dfs(i, last) means that when s[i] is enumerated, s adopts the optimal segmentation strategy, and the last characters are left, then
// If the current s[i] does not participate in the split dfs(i, last) = dfs(i + 1, last)
// If the current s[i] participates in the segmentation, use s[i] as the initial letter of the segmentation: dfs(i, last) = dfs(j + 1, last - (j + 1-i))
// , where j satisfies (set.contains(s[i,j + 1]) and j < len(s))
public int dfs(int i, int last){<!-- -->
if(i == s.length()){<!-- -->
return last;
}
if(cache[i][last] != -1) return cache[i][last];
int res = dfs(i + 1, last); // the current character is not divided
// current character split
for(int j = i; j < s. length(); j ++ ){<!-- -->
if(set. contains(s. substring(i, j + 1)))
res = Math.min(res, dfs(j + 1, last - (j + 1 - i)));
}
return cache[i][last] = res;
}
}
Memorized search ==> DP (recursion)
Will not memorize forwarding
Another way of thinking about memory search
For the case where the same state can be transferred from multiple states, it is best to write in dp, dp[i] indicates how many characters need to be removed from the substring starting from i to n at least, and the transfer equation is
dp[i] = dp[i + 1] + 1 Directly remove the i character, transfer from i + 1
dp[i] = min(dp[j]) if s[i:j] in d for j in range(i + 1,n) does not remove the first i characters, you need to find substring matches in d and delete them together
class Solution {<!-- -->
Set<String> set;
int res;
int[] cache;
String s;
public int minExtraChar(String s, String[] dictionary) {<!-- -->
set = new HashSet<>();
for(String d : dictionary){<!-- -->
set. add(d);
}
this.s = s;
res = s. length();
cache = new int[res + 1];
Arrays. fill(cache, -1);
return dfs(0);
}
// The time complexity of memory search is related to the number of states
public int dfs(int i){<!-- --> // O(n) n states
if(i == s. length())
return 0; // Indicates that there is no need to remove characters now
if(cache[i] >= 0) return cache[i];
int ans = dfs(i + 1) + 1; // remove the character at the current position i, transfer from dfs(i + 1)
// Do not remove the character at the current i position, it needs to be transferred from d
for(int j = i; j < s. length(); j ++ ){<!-- --> // O(n)
if(set. contains(s. substring(i, j + 1))) // O(n)
ans = Math.min(ans, dfs(j + 1));
}
return cache[i] = ans;
}
}
Time complexity: O(n^3)
Turn to recursion
class Solution {<!-- -->
// Define f(i) means only splitting the first i characters, and how many characters can be left at the end
// State transition equation:
// f(i) = f(i-1) + 1, this character is the rest
// f(i) = f(j), if s[j + 1, i] is in the dictionary
// Take the minimum value of the two, namely: f(i) = min(f(i-1) + 1, f(j))
// initial value f(0) = 0
// Finally return f(n)
public int minExtraChar(String s, String[] dictionary) {<!-- -->
Set set = new HashSet<>();
for(String d : dictionary){<!-- -->
set. add(d);
}
int n = s. length();
int[] f = new int[n + 1];
for(int i = 1; i <= n; i ++ ){<!-- -->
f[i] = Integer.MAX_VALUE;
}
f[0] = 0;
for(int i = 1; i <= n; i ++ ){<!-- -->
// i does not participate in the division, transfer directly
f[i] = f[i-1] + 1;
// i participates in segmentation, enumerates all js starting from [0,i]
for(int j = 0; j < i; j ++ ){<!-- -->
if(set. contains(s. substring(j, i)))
f[i] = Math.min(f[i], f[j]);
}
}
return f[n];
}
}
2708. The maximum strength of a group
Moderate difficulty 0
You are given an integer array nums with subscripts starting from 0 , which represents the grades of all students in a class in a test. The teacher wants to select some students to form a non-empty group, and the strength value of this group is the largest, if the subscript of the students in this group is i0, i1, i2, … , ik , then the strength value of this group is defined as nums[i0] * nums[i1 ] * nums[i2] * ... * nums[ik].
Please return the maximum strength value that the group created by the teacher can get.
Example 1:
Input: nums = [3,-1,-5,2,5,-9] Output: 1350 Explanation: One way to form the maximum skill group is to select the students whose subscripts are [0,2,3,4,5]. The strength value is 3 * (-5) * 2 * 5 * (-9) = 1350 , which is the maximum strength value that can be obtained.
Example 2:
Input: nums = [-4,-5,-4] Output: 20 Explanation: Select the student whose index is [0, 1]. The resulting Strength value is 20. We can't get more strength value.
Tip:
1 <= nums. length <= 13-9 <= nums[i] <= 9
Sorting + Greedy
Sorting + The maximum strength value of the greedy group has nothing to do with the position of the element. Sort first, after sorting, from negative to positive from left to right, traverse from the left to 0 value, if there are two negative numbers, multiply and calculate the answer, the smaller Multiplying negative numbers of , contributes more to the answer. Start from the right and traverse and multiply all positive numbers.
class Solution {<!-- -->
public long maxStrength(int[] nums) {<!-- -->
if(nums. length == 1) return nums[0];
Arrays. sort(nums);
long ans = 1l;
for(int i = 0; i + 1 < nums.length & amp; & amp; nums[i] < 0 & amp; & amp; nums[i + 1] < 0; i + = 2){<!- - -->
ans *= nums[i] * nums[i + 1];
}
// // Special judgment: [0,-1], [-4,-5,-4], [-1, -1]
if((ans == 1l & amp; & amp; nums[nums. length-1] <= 0) & amp; & amp; (nums[1] >= 0)) return nums[nums. length-1] ;
for(int i = nums.length-1; i >= 0 & amp; & amp; nums[i] > 0; i -= 1){<!-- -->
ans *= nums[i];
}
return ans;
}
}
DFS enumerates all subsets
class Solution {<!-- -->
// Enumerate all subsets and calculate the maximum answer
long ans = Long.MIN_VALUE;
int[] nums;
public long maxStrength(int[] nums) {<!-- -->
this.nums = nums;
dfs(0, 1l, true);
return ans;
}
// Because the empty set is to be removed, use is_empty to judge whether it is an empty set, and the initial state is an empty set
public void dfs(int i, long prod, boolean is_empty){<!-- -->
if(i == nums. length){<!-- -->
if(!is_empty)
ans = Math.max(ans, prod);
return;
}
// don't choose
dfs(i + 1, prod, is_empty);
// select
dfs(i + 1, prod * nums[i], false);
}
}
Dynamic programming (O(n))
class Solution {<!-- -->
/**
Select or not select model ==> dynamic programming:
Since there are negative numbers, consider the minimum and maximum values:
There are four cases where the maximum value is transferred:
mx[i] = mx[i-1] do not select nums[i]
= nums[i] nums[i] is its own maximum value
= mx[i-1] * nums[i] select nums[i]
= mn[i-1] * nums[i] select nums[i]
*/
public long maxStrength(int[] nums) {<!-- -->
long max = nums[0], min = nums[0];
for(int i = 1; i < nums. length; i ++ ){<!-- -->
long tmp = max;
max = Math.max(Math.max(max, nums[i]), Math.max(max * nums[i], min * nums[i]));
min = Math.min(Math.min(min, nums[i]), Math.min(tmp * nums[i], min * nums[i]));
}
return max;
}
}
2709. Greatest common divisor traversal
Difficulty Hard 1
Given an array nums of integers with indices starting at 0 , you can iterate between indices. For two subscripts i and j (i != j), if and only if gcd(nums[i], nums[j]) > 1, we can pass between two subscripts, where gcd is the Greatest Common Divisor of the two numbers.
You need to determine any two subscripts i and j in the , whether there are several passes that can be traversed from nums array that satisfy i < j i to j.
Returns true if any matching subscript pair can be traversed, otherwise returns false .
Example 1:
Input: nums = [2,3,6] Output: true Explanation: In this example, there are a total of 3 subscript pairs: (0, 1) , (0, 2) and (1, 2) . From subscript 0 to subscript 1, we can traverse 0 -> 2 -> 1, we can go from subscript 0 to 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1 , from subscript 2 to 1 is because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1 . From subscript 0 to subscript 2, we can traverse directly, because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1 . Similarly, we can also go from subscript 1 to 2 because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1 .
Example 2:
Input: nums = [3,9,5] output: false Explanation: We cannot go from index 0 to 2, so return false.
Example 3:
Input: nums = [4,3,12,8] Output: true Explanation: There are 6 subscript pairs in total: (0, 1) , (0, 2) , (0, 3) , (1, 2) , (1, 3) and (2, 3) . There is a feasible traversal between all subscript pairs, so return true .
Tip:
1 <= nums. length <= 1051 <= nums[i] <= 105
Decomposition of prime factors + union search
Treat each position in nums as a point, and all prime numbers as a point. If nums[i] is divisible by the prime number p, then connect an edge from the position point i to the prime number point p . Since each number can only be divisible by at most log? prime numbers, the total number of connected edges is O(nlogA).
In this way, the problem becomes: check whether all location points are in the same connected block. It can be solved by searching and set.
For any two subscripts i and j satisfying i < j in the nums array, whether there are several passes that can be traversed from i to j. In other words, it is to judge whether the nums array is a connected component as a whole, which is suitable for union search.
We consider under what circumstances we can connect edges. Obviously, the time complexity of calculating gcd between two pairs and then connecting edges is O(n^2), which cannot pass this question.
We can connect each number in nums with its own prime factor, so that when gcd(nums[i],nums[j]) >= 2, At this time, i and j will definitely connect them indirectly through a prime factor.
When the code is implemented, the Esperanza sieve is used to quickly find the prime factor of each number in the range, and the first MX nodes in the search set are the prime factors, and the last n nodes are the subscripts in the array, through the prime factor method Indirect connection, and finally determine the connectivity.
https://leetcode.cn/circle/discuss/lOcuHV/
class Solution {<!-- -->
private class DSU{<!-- -->
int[] parent;
public DSU(int N) {<!-- -->
parent = new int[N];
for (int i = 0; i < N; + + i) {<!-- -->
parent[i] = i;
}
}
public int find(int x) {<!-- -->
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {<!-- -->
parent[find(x)] = find(y);
}
}
public boolean canTraverseAllPairs(int[] nums) {<!-- -->
HashMap<Integer, Integer> map = new HashMap<>();
DSU uf = new DSU(nums. length);
for (int i = 0; i < nums. length; + + i) {<!-- -->
int t = nums[i];
for (int j = 2; j * j <= t; + + j) {<!-- -->
while (t % j == 0) {<!-- -->
t /= j;
if (!map. containsKey(j)) {<!-- -->
map. put(j, i);
} else {<!-- -->
uf. union(map. get(j), i);
}
}
}
if (t != 1) {<!-- -->
if (!map. containsKey(t)) {<!-- -->
map. put(t, i);
} else {<!-- -->
uf. union(map. get(t), i);
}
}
}
int f = uf. find(0);
for (int i = 0; i < nums. length; + + i) {<!-- -->
if (uf.find(i) != f) {<!-- -->
return false;
}
}
return true;
}
}