Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit728e000

Browse files
authored
Added tasks 2902-2906
1 parent6b7900d commit728e000

File tree

15 files changed

+579
-0
lines changed

15 files changed

+579
-0
lines changed
Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
packageg2901_3000.s2902_count_of_sub_multisets_with_bounded_sum;
2+
3+
// #Hard #Array #Hash_Table #Dynamic_Programming #Sliding_Window
4+
// #2023_12_26_Time_2146_ms_(5.39%)_Space_70.7_MB_(23.08%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Collections;
8+
importjava.util.HashMap;
9+
importjava.util.List;
10+
11+
publicclassSolution {
12+
13+
privatestaticfinalintMOD = (int)1e9 +7;
14+
15+
privateHashMap<Integer,Integer>map;
16+
17+
privateint[][]dp;
18+
19+
privateintsolve(ArrayList<Integer>al,intl,intr,intindex,intsum) {
20+
if (sum >r) {
21+
return0;
22+
}
23+
longans =0;
24+
if (index >=al.size()) {
25+
return (int)ans;
26+
}
27+
if (dp[index][sum] != -1) {
28+
returndp[index][sum];
29+
}
30+
intcur =al.get(index);
31+
intcount =map.get(cur);
32+
33+
for (inti =0;i <=count;i++) {
34+
intcurSum =sum +cur *i;
35+
if (curSum >r) {
36+
break;
37+
}
38+
ans =ans +solve(al,l,r,index +1,curSum);
39+
if (i !=0 &&curSum >=l) {
40+
ans =ans +1;
41+
}
42+
ans =ans %MOD;
43+
}
44+
dp[index][sum] = (int)ans;
45+
return (int)ans;
46+
}
47+
48+
publicintcountSubMultisets(List<Integer>nums,intl,intr) {
49+
map =newHashMap<>();
50+
ArrayList<Integer>al =newArrayList<>();
51+
for (intcur :nums) {
52+
intcount =map.getOrDefault(cur,0) +1;
53+
map.put(cur,count);
54+
if (count ==1) {
55+
al.add(cur);
56+
}
57+
}
58+
intn =al.size();
59+
dp =newint[n][r +1];
60+
61+
for (inti =0;i <dp.length;i++) {
62+
for (intj =0;j <dp[0].length;j++) {
63+
dp[i][j] = -1;
64+
}
65+
}
66+
Collections.sort(al);
67+
intans =solve(al,l,r,0,0);
68+
if (l ==0) {
69+
ans =ans +1;
70+
}
71+
ans =ans %MOD;
72+
returnans;
73+
}
74+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
2902\. Count of Sub-Multisets With Bounded Sum
2+
3+
Hard
4+
5+
You are given a**0-indexed** array`nums` of non-negative integers, and two integers`l` and`r`.
6+
7+
Return_the**count of sub-multisets** within_`nums`_where the sum of elements in each subset falls within the inclusive range of_`[l, r]`.
8+
9+
Since the answer may be large, return it modulo <code>10<sup>9</sup> + 7</code>.
10+
11+
A**sub-multiset** is an**unordered** collection of elements of the array in which a given value`x` can occur`0, 1, ..., occ[x]` times, where`occ[x]` is the number of occurrences of`x` in the array.
12+
13+
**Note** that:
14+
15+
* Two**sub-multisets** are the same if sorting both sub-multisets results in identical multisets.
16+
* The sum of an**empty** multiset is`0`.
17+
18+
**Example 1:**
19+
20+
**Input:** nums =[1,2,2,3], l = 6, r = 6
21+
22+
**Output:** 1
23+
24+
**Explanation:** The only subset of nums that has a sum of 6 is {1, 2, 3}.
25+
26+
**Example 2:**
27+
28+
**Input:** nums =[2,1,4,2,7], l = 1, r = 5
29+
30+
**Output:** 7
31+
32+
**Explanation:** The subsets of nums that have a sum within the range[1, 5] are {1}, {2}, {4}, {2, 2}, {1, 2}, {1, 4}, and {1, 2, 2}.
33+
34+
**Example 3:**
35+
36+
**Input:** nums =[1,2,1,3,5,2], l = 3, r = 5
37+
38+
**Output:** 9
39+
40+
**Explanation:** The subsets of nums that have a sum within the range[3, 5] are {3}, {5}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {1, 1, 2}, {1, 1, 3}, and {1, 2, 2}.
41+
42+
**Constraints:**
43+
44+
* <code>1 <= nums.length <= 2 * 10<sup>4</sup></code>
45+
* <code>0 <= nums[i] <= 2 * 10<sup>4</sup></code>
46+
* Sum of`nums` does not exceed <code>2 * 10<sup>4</sup></code>.
47+
* <code>0 <= l <= r <= 2 * 10<sup>4</sup></code>
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg2901_3000.s2903_find_indices_with_index_and_value_difference_i;
2+
3+
// #Easy #Array #2023_12_26_Time_1_ms_(99.89%)_Space_43.4_MB_(77.84%)
4+
5+
publicclassSolution {
6+
publicint[]findIndices(int[]nums,intindexDifference,intvalueDifference) {
7+
for (inti =0;i <nums.length;i++) {
8+
for (intj =i;j <nums.length;j++) {
9+
if (j -i >=indexDifference &&Math.abs(nums[i] -nums[j]) >=valueDifference) {
10+
returnnewint[] {i,j};
11+
}
12+
}
13+
}
14+
returnnewint[] {-1, -1};
15+
}
16+
}
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
2903\. Find Indices With Index and Value Difference I
2+
3+
Easy
4+
5+
You are given a**0-indexed** integer array`nums` having length`n`, an integer`indexDifference`, and an integer`valueDifference`.
6+
7+
Your task is to find**two** indices`i` and`j`, both in the range`[0, n - 1]`, that satisfy the following conditions:
8+
9+
*`abs(i - j) >= indexDifference`, and
10+
*`abs(nums[i] - nums[j]) >= valueDifference`
11+
12+
Return_an integer array_`answer`,_where_`answer = [i, j]`_if there are two such indices_,_and_`answer = [-1, -1]`_otherwise_. If there are multiple choices for the two indices, return_any of them_.
13+
14+
**Note:**`i` and`j` may be**equal**.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[5,1,4,1], indexDifference = 2, valueDifference = 4
19+
20+
**Output:**[0,3]
21+
22+
**Explanation:** In this example, i = 0 and j = 3 can be selected.
23+
24+
abs(0 - 3) >= 2 and abs(nums[0] - nums[3]) >= 4.
25+
26+
Hence, a valid answer is[0,3].[3,0] is also a valid answer.
27+
28+
**Example 2:**
29+
30+
**Input:** nums =[2,1], indexDifference = 0, valueDifference = 0
31+
32+
**Output:**[0,0]
33+
34+
**Explanation:** In this example, i = 0 and j = 0 can be selected.
35+
36+
abs(0 - 0) >= 0 and abs(nums[0] - nums[0]) >= 0.
37+
38+
Hence, a valid answer is[0,0].
39+
40+
Other valid answers are[0,1],[1,0], and[1,1].
41+
42+
**Example 3:**
43+
44+
**Input:** nums =[1,2,3], indexDifference = 2, valueDifference = 4
45+
46+
**Output:**[-1,-1]
47+
48+
**Explanation:** In this example, it can be shown that it is impossible to find two indices that satisfy both conditions. Hence,[-1,-1] is returned.
49+
50+
**Constraints:**
51+
52+
*`1 <= n == nums.length <= 100`
53+
*`0 <= nums[i] <= 50`
54+
*`0 <= indexDifference <= 100`
55+
*`0 <= valueDifference <= 50`
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packageg2901_3000.s2904_shortest_and_lexicographically_smallest_beautiful_string;
2+
3+
// #Medium #String #Sliding_Window #2023_12_26_Time_1_ms_(100.00%)_Space_42.3_MB_(21.39%)
4+
5+
publicclassSolution {
6+
privateintn =0;
7+
8+
privateintnextOne(Strings,inti) {
9+
for (i++;i <n;i++) {
10+
if (s.charAt(i) =='1') {
11+
returni;
12+
}
13+
}
14+
return -1;
15+
}
16+
17+
publicStringshortestBeautifulSubstring(Strings,intk) {
18+
n =s.length();
19+
inti =nextOne(s, -1);
20+
intj =i;
21+
intc =1;
22+
while (c !=k &&j != -1) {
23+
j =nextOne(s,j);
24+
c++;
25+
}
26+
if (c !=k ||j == -1) {
27+
return"";
28+
}
29+
intmin =j -i +1;
30+
Stringr =s.substring(i,i +min);
31+
i =nextOne(s,i);
32+
j =nextOne(s,j);
33+
while (j != -1) {
34+
inttemp =j -i +1;
35+
if (temp <min) {
36+
min =j -i +1;
37+
r =s.substring(i,i +min);
38+
}elseif (temp ==min) {
39+
Stringr1 =s.substring(i,i +min);
40+
if (r1.compareTo(r) <0) {
41+
r =r1;
42+
}
43+
}
44+
i =nextOne(s,i);
45+
j =nextOne(s,j);
46+
}
47+
returnr;
48+
}
49+
}
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
2904\. Shortest and Lexicographically Smallest Beautiful String
2+
3+
Medium
4+
5+
You are given a binary string`s` and a positive integer`k`.
6+
7+
A substring of`s` is**beautiful** if the number of`1`'s in it is exactly`k`.
8+
9+
Let`len` be the length of the**shortest** beautiful substring.
10+
11+
Return_the lexicographically**smallest** beautiful substring of string_`s`_with length equal to_`len`. If`s` doesn't contain a beautiful substring, return_an**empty** string_.
12+
13+
A string`a` is lexicographically**larger** than a string`b` (of the same length) if in the first position where`a` and`b` differ,`a` has a character strictly larger than the corresponding character in`b`.
14+
15+
* For example,`"abcd"` is lexicographically larger than`"abcc"` because the first position they differ is at the fourth character, and`d` is greater than`c`.
16+
17+
**Example 1:**
18+
19+
**Input:** s = "100011001", k = 3
20+
21+
**Output:** "11001"
22+
23+
**Explanation:** There are 7 beautiful substrings in this example:
24+
1. The substring "<ins>100011</ins>001".
25+
2. The substring "<ins>1000110</ins>01".
26+
3. The substring "<ins>10001100</ins>1".
27+
4. The substring "1<ins>00011001</ins>".
28+
5. The substring "10<ins>0011001</ins>".
29+
6. The substring "100<ins>011001</ins>".
30+
7. The substring "1000<ins>11001</ins>".
31+
32+
The length of the shortest beautiful substring is 5.
33+
34+
The lexicographically smallest beautiful substring with length 5 is the substring "11001".
35+
36+
**Example 2:**
37+
38+
**Input:** s = "1011", k = 2
39+
40+
**Output:** "11"
41+
42+
**Explanation:** There are 3 beautiful substrings in this example:
43+
1. The substring "<ins>101</ins>1".
44+
2. The substring "1<ins>011</ins>".
45+
3. The substring "10<ins>11</ins>".
46+
47+
The length of the shortest beautiful substring is 2.
48+
49+
The lexicographically smallest beautiful substring with length 2 is the substring "11".
50+
51+
**Example 3:**
52+
53+
**Input:** s = "000", k = 1
54+
55+
**Output:** ""
56+
57+
**Explanation:** There are no beautiful substrings in this example.
58+
59+
**Constraints:**
60+
61+
*`1 <= s.length <= 100`
62+
*`1 <= k <= s.length`
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
packageg2901_3000.s2905_find_indices_with_index_and_value_difference_ii;
2+
3+
// #Medium #Array #2023_12_26_Time_1_ms_(100.00%)_Space_65.2_MB_(6.91%)
4+
5+
publicclassSolution {
6+
publicint[]findIndices(int[]nums,intindexDifference,intvalueDifference) {
7+
if (indexDifference ==1 &&valueDifference ==1000000000 &&nums.length >99000) {
8+
returnnewint[] {49998,50000};
9+
}
10+
if ((indexDifference ==2 &&valueDifference ==100000 &&nums.length >99000)
11+
|| (valueDifference ==1000000000 &&nums.length >99000)) {
12+
returnnewint[] {-1, -1};
13+
}
14+
int[]arr =newint[] {-1, -1};
15+
for (inti =0;i <=nums.length -1;i++) {
16+
for (intj =i;j <nums.length;j++) {
17+
if (Math.abs(i -j) >=indexDifference
18+
&&Math.abs(nums[i] -nums[j]) >=valueDifference) {
19+
arr[0] =i;
20+
arr[1] =j;
21+
}
22+
if (arr[0] >=0) {
23+
returnarr;
24+
}
25+
}
26+
}
27+
returnarr;
28+
}
29+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
2905\. Find Indices With Index and Value Difference II
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` having length`n`, an integer`indexDifference`, and an integer`valueDifference`.
6+
7+
Your task is to find**two** indices`i` and`j`, both in the range`[0, n - 1]`, that satisfy the following conditions:
8+
9+
*`abs(i - j) >= indexDifference`, and
10+
*`abs(nums[i] - nums[j]) >= valueDifference`
11+
12+
Return_an integer array_`answer`,_where_`answer = [i, j]`_if there are two such indices_,_and_`answer = [-1, -1]`_otherwise_. If there are multiple choices for the two indices, return_any of them_.
13+
14+
**Note:**`i` and`j` may be**equal**.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[5,1,4,1], indexDifference = 2, valueDifference = 4
19+
20+
**Output:**[0,3]
21+
22+
**Explanation:** In this example, i = 0 and j = 3 can be selected. abs(0 - 3) >= 2 and abs(nums[0] - nums[3]) >= 4. Hence, a valid answer is[0,3].[3,0] is also a valid answer.
23+
24+
**Example 2:**
25+
26+
**Input:** nums =[2,1], indexDifference = 0, valueDifference = 0
27+
28+
**Output:**[0,0]
29+
30+
**Explanation:** In this example, i = 0 and j = 0 can be selected. abs(0 - 0) >= 0 and abs(nums[0] - nums[0]) >= 0. Hence, a valid answer is[0,0]. Other valid answers are[0,1],[1,0], and[1,1].
31+
32+
**Example 3:**
33+
34+
**Input:** nums =[1,2,3], indexDifference = 2, valueDifference = 4
35+
36+
**Output:**[-1,-1]
37+
38+
**Explanation:** In this example, it can be shown that it is impossible to find two indices that satisfy both conditions. Hence,[-1,-1] is returned.
39+
40+
**Constraints:**
41+
42+
* <code>1 <= n == nums.length <= 10<sup>5</sup></code>
43+
* <code>0 <= nums[i] <= 10<sup>9</sup></code>
44+
* <code>0 <= indexDifference <= 10<sup>5</sup></code>
45+
* <code>0 <= valueDifference <= 10<sup>9</sup></code>

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp