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

Commit70e085a

Browse files
authored
Added tasks 2836-2842
1 parentf14eb82 commit70e085a

File tree

15 files changed

+565
-0
lines changed

15 files changed

+565
-0
lines changed
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
packageg2801_2900.s2836_maximize_value_of_function_in_a_ball_passing_game;
2+
3+
// #Hard #Array #Dynamic_Programming #Bit_Manipulation
4+
// #2023_12_12_Time_235_ms_(45.00%)_Space_134.3_MB_(47.50%)
5+
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publiclonggetMaxFunctionValue(List<Integer>receiver,longk) {
10+
intupper = (int)Math.floor(Math.log(k) /Math.log(2));
11+
intn =receiver.size();
12+
int[][]next =newint[n][upper +1];
13+
long[][]res =newlong[n][upper +1];
14+
15+
int[]kBit =newint[upper +1];
16+
longcurrK =k;
17+
for (intx =0;x <n;x++) {
18+
next[x][0] =receiver.get(x);
19+
res[x][0] =receiver.get(x);
20+
}
21+
for (inti =0;i <=upper;i++) {
22+
kBit[i] = (int) (currK &1);
23+
currK =currK >>1;
24+
}
25+
26+
for (inti =1;i <=upper;i++) {
27+
for (intx =0;x <n;x++) {
28+
intnxt =next[x][i -1];
29+
next[x][i] =next[nxt][i -1];
30+
res[x][i] =res[x][i -1] +res[nxt][i -1];
31+
}
32+
}
33+
longans =0;
34+
for (intx =0;x <n;x++) {
35+
longsum =x;
36+
inti =0;
37+
intcurr =x;
38+
while (i <=upper) {
39+
if (kBit[i] ==0) {
40+
i++;
41+
continue;
42+
}
43+
sum +=res[curr][i];
44+
curr =next[curr][i];
45+
i++;
46+
}
47+
ans =Math.max(ans,sum);
48+
}
49+
returnans;
50+
}
51+
}
Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
2836\. Maximize Value of Function in a Ball Passing Game
2+
3+
Hard
4+
5+
You are given a**0-indexed** integer array`receiver` of length`n` and an integer`k`.
6+
7+
There are`n` players having a**unique id** in the range`[0, n - 1]` who will play a ball passing game, and`receiver[i]` is the id of the player who receives passes from the player with id`i`. Players can pass to themselves,**i.e.**`receiver[i]` may be equal to`i`.
8+
9+
You must choose one of the`n` players as the starting player for the game, and the ball will be passed**exactly**`k` times starting from the chosen player.
10+
11+
For a chosen starting player having id`x`, we define a function`f(x)` that denotes the**sum** of`x` and the**ids** of all players who receive the ball during the`k` passes,**including repetitions**. In other words, <code>f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver<sup>(k)</sup>[x]</code>.
12+
13+
Your task is to choose a starting player having id`x` that**maximizes** the value of`f(x)`.
14+
15+
Return_an integer denoting the**maximum** value of the function._
16+
17+
**Note:**`receiver` may contain duplicates.
18+
19+
**Example 1:**
20+
21+
Pass Number
22+
23+
Sender ID
24+
25+
Receiver ID
26+
27+
x + Receiver IDs
28+
29+
2
30+
31+
1
32+
33+
2
34+
35+
1
36+
37+
3
38+
39+
2
40+
41+
1
42+
43+
0
44+
45+
3
46+
47+
3
48+
49+
0
50+
51+
2
52+
53+
5
54+
55+
4
56+
57+
2
58+
59+
1
60+
61+
6
62+
63+
**Input:** receiver =[2,0,1], k = 4
64+
65+
**Output:** 6
66+
67+
**Explanation:** The table above shows a simulation of the game starting with the player having id x = 2. From the table, f(2) is equal to 6. It can be shown that 6 is the maximum achievable value of the function. Hence, the output is 6.
68+
69+
**Example 2:**
70+
71+
Pass Number
72+
73+
Sender ID
74+
75+
Receiver ID
76+
77+
x + Receiver IDs
78+
79+
4
80+
81+
1
82+
83+
4
84+
85+
3
86+
87+
7
88+
89+
2
90+
91+
3
92+
93+
2
94+
95+
9
96+
97+
3
98+
99+
2
100+
101+
1
102+
103+
10
104+
105+
**Input:** receiver =[1,1,1,2,3], k = 3
106+
107+
**Output:** 10
108+
109+
**Explanation:** The table above shows a simulation of the game starting with the player having id x = 4. From the table, f(4) is equal to 10. It can be shown that 10 is the maximum achievable value of the function. Hence, the output is 10.
110+
111+
**Constraints:**
112+
113+
* <code>1 <= receiver.length == n <= 10<sup>5</sup></code>
114+
*`0 <= receiver[i] <= n - 1`
115+
* <code>1 <= k <= 10<sup>10</sup></code>
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg2801_2900.s2839_check_if_strings_can_be_made_equal_with_operations_i;
2+
3+
// #Easy #String #2023_12_12_Time_1_ms_(99.09%)_Space_41.8_MB_(41.03%)
4+
5+
publicclassSolution {
6+
publicbooleancanBeEqual(Strings1,Strings2) {
7+
returnisOk(s1,s2,0) &&isOk(s1,s2,1);
8+
}
9+
10+
privatebooleanisOk(Strings1,Strings2,inti) {
11+
chara =s1.charAt(i);
12+
charb =s1.charAt(i +2);
13+
charc =s2.charAt(i);
14+
chard =s2.charAt(i +2);
15+
if (a ==c &&b ==d) {
16+
returntrue;
17+
}
18+
returna ==d &&b ==c;
19+
}
20+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
2839\. Check if Strings Can be Made Equal With Operations I
2+
3+
Easy
4+
5+
You are given two strings`s1` and`s2`, both of length`4`, consisting of**lowercase** English letters.
6+
7+
You can apply the following operation on any of the two strings**any** number of times:
8+
9+
* Choose any two indices`i` and`j` such that`j - i = 2`, then**swap** the two characters at those indices in the string.
10+
11+
Return`true`_if you can make the strings_`s1`_and_`s2`_equal, and_`false`_otherwise_.
12+
13+
**Example 1:**
14+
15+
**Input:** s1 = "abcd", s2 = "cdab"
16+
17+
**Output:** true
18+
19+
**Explanation:** We can do the following operations on s1:
20+
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbad".
21+
- Choose the indices i = 1, j = 3. The resulting string is s1 = "cdab" = s2.
22+
23+
**Example 2:**
24+
25+
**Input:** s1 = "abcd", s2 = "dacb"
26+
27+
**Output:** false
28+
29+
**Explanation:** It is not possible to make the two strings equal.
30+
31+
**Constraints:**
32+
33+
*`s1.length == s2.length == 4`
34+
*`s1` and`s2` consist only of lowercase English letters.
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2801_2900.s2840_check_if_strings_can_be_made_equal_with_operations_ii;
2+
3+
// #Medium #String #Hash_Table #Sorting #2023_12_12_Time_4_ms_(100.00%)_Space_44.6_MB_(50.60%)
4+
5+
publicclassSolution {
6+
publicbooleancheckStrings(Strings1,Strings2) {
7+
returncheck(0,s1,s2) &&check(1,s1,s2);
8+
}
9+
10+
booleancheck(intstart,Strings1,Strings2) {
11+
intstep =2;
12+
int[]buf =newint[26];
13+
for (inti =start;i <s1.length();i +=step) {
14+
buf[s1.charAt(i) -'a']++;
15+
buf[s2.charAt(i) -'a']--;
16+
}
17+
for (intj :buf) {
18+
if (j !=0) {
19+
returnfalse;
20+
}
21+
}
22+
returntrue;
23+
}
24+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2840\. Check if Strings Can be Made Equal With Operations II
2+
3+
Medium
4+
5+
You are given two strings`s1` and`s2`, both of length`n`, consisting of**lowercase** English letters.
6+
7+
You can apply the following operation on**any** of the two strings**any** number of times:
8+
9+
* Choose any two indices`i` and`j` such that`i < j` and the difference`j - i` is**even**, then**swap** the two characters at those indices in the string.
10+
11+
Return`true`_if you can make the strings_`s1`_and_`s2`_equal, and_`false`_otherwise_.
12+
13+
**Example 1:**
14+
15+
**Input:** s1 = "abcdba", s2 = "cabdab"
16+
17+
**Output:** true
18+
19+
**Explanation:** We can apply the following operations on s1:
20+
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbadba".
21+
- Choose the indices i = 2, j = 4. The resulting string is s1 = "cbbdaa".
22+
- Choose the indices i = 1, j = 5. The resulting string is s1 = "cabdab" = s2.
23+
24+
**Example 2:**
25+
26+
**Input:** s1 = "abe", s2 = "bea"
27+
28+
**Output:** false
29+
30+
**Explanation:** It is not possible to make the two strings equal.
31+
32+
**Constraints:**
33+
34+
*`n == s1.length == s2.length`
35+
* <code>1 <= n <= 10<sup>5</sup></code>
36+
*`s1` and`s2` consist only of lowercase English letters.
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
packageg2801_2900.s2841_maximum_sum_of_almost_unique_subarray;
2+
3+
// #Medium #Array #Hash_Table #Sliding_Window #2023_12_12_Time_18_ms_(97.37%)_Space_45.4_MB_(81.05%)
4+
5+
importjava.util.HashMap;
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publiclongmaxSum(List<Integer>nums,intm,intk) {
10+
HashMap<Integer,Integer>hash =newHashMap<>();
11+
intcount =0;
12+
longans =0;
13+
intleft =0;
14+
longcur =0;
15+
for (inti =0;i <nums.size();i++) {
16+
cur +=nums.get(i);
17+
if (hash.containsKey(nums.get(i))) {
18+
hash.put(nums.get(i),hash.get(nums.get(i)) +1);
19+
}else {
20+
hash.put(nums.get(i),1);
21+
count++;
22+
}
23+
if (i -left +1 ==k) {
24+
if (count >=m) {
25+
ans =Math.max(ans,cur);
26+
}
27+
if (hash.get(nums.get(left)) >1) {
28+
hash.put(nums.get(left),hash.get(nums.get(left)) -1);
29+
}else {
30+
count--;
31+
hash.remove(nums.get(left));
32+
}
33+
cur -=nums.get(left);
34+
left++;
35+
}
36+
}
37+
returnans;
38+
}
39+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2841\. Maximum Sum of Almost Unique Subarray
2+
3+
Medium
4+
5+
You are given an integer array`nums` and two positive integers`m` and`k`.
6+
7+
Return_the**maximum sum** out of all**almost unique** subarrays of length_`k`_of_`nums`. If no such subarray exists, return`0`.
8+
9+
A subarray of`nums` is**almost unique** if it contains at least`m` distinct elements.
10+
11+
A subarray is a contiguous**non-empty** sequence of elements within an array.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[2,6,7,3,1,7], m = 3, k = 4
16+
17+
**Output:** 18
18+
19+
**Explanation:** There are 3 almost unique subarrays of size`k = 4`. These subarrays are[2, 6, 7, 3],[6, 7, 3, 1], and[7, 3, 1, 7]. Among these subarrays, the one with the maximum sum is[2, 6, 7, 3] which has a sum of 18.
20+
21+
**Example 2:**
22+
23+
**Input:** nums =[5,9,9,2,4,5,4], m = 1, k = 3
24+
25+
**Output:** 23
26+
27+
**Explanation:** There are 5 almost unique subarrays of size k. These subarrays are[5, 9, 9],[9, 9, 2],[9, 2, 4],[2, 4, 5], and[4, 5, 4]. Among these subarrays, the one with the maximum sum is[5, 9, 9] which has a sum of 23.
28+
29+
**Example 3:**
30+
31+
**Input:** nums =[1,2,1,2,1,2,1], m = 3, k = 3
32+
33+
**Output:** 0
34+
35+
**Explanation:** There are no subarrays of size`k = 3` that contain at least`m = 3` distinct elements in the given array[1,2,1,2,1,2,1]. Therefore, no almost unique subarrays exist, and the maximum sum is 0.
36+
37+
**Constraints:**
38+
39+
* <code>1 <= nums.length <= 2 * 10<sup>4</sup></code>
40+
*`1 <= m <= k <= nums.length`
41+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>

0 commit comments

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