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

Commite8f5215

Browse files
authored
Added tasks 2908-2913
1 parent8a1030e commite8f5215

File tree

15 files changed

+624
-0
lines changed

15 files changed

+624
-0
lines changed
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
packageg2901_3000.s2908_minimum_sum_of_mountain_triplets_i;
2+
3+
// #Easy #Array #2023_12_27_Time_1_ms_(99.90%)_Space_42.2_MB_(5.53%)
4+
5+
publicclassSolution {
6+
publicintminimumSum(int[]nums) {
7+
intoutput =Integer.MAX_VALUE;
8+
for (inti =0;i <nums.length -2;i++) {
9+
for (intj =i +1;j <nums.length -1;j++) {
10+
if (nums[i] >nums[j]) {
11+
break;
12+
}
13+
for (intk =j +1;k <nums.length;k++) {
14+
if (nums[i] <nums[j] &&nums[k] <nums[j]) {
15+
intmin =nums[i] +nums[k] +nums[j];
16+
output =Math.min(min,output);
17+
}
18+
}
19+
}
20+
}
21+
returnoutput ==Integer.MAX_VALUE ? -1 :output;
22+
}
23+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2908\. Minimum Sum of Mountain Triplets I
2+
3+
Easy
4+
5+
You are given a**0-indexed** array`nums` of integers.
6+
7+
A triplet of indices`(i, j, k)` is a**mountain** if:
8+
9+
*`i < j < k`
10+
*`nums[i] < nums[j]` and`nums[k] < nums[j]`
11+
12+
Return_the**minimum possible sum** of a mountain triplet of_`nums`._If no such triplet exists, return_`-1`.
13+
14+
**Example 1:**
15+
16+
**Input:** nums =[8,6,1,5,3]
17+
18+
**Output:** 9
19+
20+
**Explanation:** Triplet (2, 3, 4) is a mountain triplet of sum 9 since:
21+
- 2 < 3 < 4
22+
- nums[2] < nums[3] and nums[4] < nums[3]
23+
24+
And the sum of this triplet is nums[2] + nums[3] + nums[4] = 9. It can be shown that there are no mountain triplets with a sum of less than 9.
25+
26+
**Example 2:**
27+
28+
**Input:** nums =[5,4,8,7,10,2]
29+
30+
**Output:** 13
31+
32+
**Explanation:** Triplet (1, 3, 5) is a mountain triplet of sum 13 since:
33+
- 1 < 3 < 5
34+
- nums[1] < nums[3] and nums[5] < nums[3]
35+
36+
And the sum of this triplet is nums[1] + nums[3] + nums[5] = 13. It can be shown that there are no mountain triplets with a sum of less than 13.
37+
38+
**Example 3:**
39+
40+
**Input:** nums =[6,5,4,3,4,5]
41+
42+
**Output:** -1
43+
44+
**Explanation:** It can be shown that there are no mountain triplets in nums.
45+
46+
**Constraints:**
47+
48+
*`3 <= nums.length <= 50`
49+
*`1 <= nums[i] <= 50`
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
packageg2901_3000.s2909_minimum_sum_of_mountain_triplets_ii;
2+
3+
// #Medium #Array #2023_12_27_Time_2_ms_(99.79%)_Space_57.3_MB_(69.77%)
4+
5+
publicclassSolution {
6+
publicintminimumSum(int[]nums) {
7+
intn =nums.length;
8+
int[]leftSmallest =newint[n];
9+
int[]rightSmallest =newint[n];
10+
intcurrSmallest =nums[0];
11+
leftSmallest[0] = -1;
12+
for (inti =1;i <n;i++) {
13+
if (currSmallest >=nums[i]) {
14+
leftSmallest[i] = -1;
15+
currSmallest =nums[i];
16+
}else {
17+
leftSmallest[i] =currSmallest;
18+
}
19+
}
20+
currSmallest =nums[n -1];
21+
rightSmallest[n -1] = -1;
22+
for (inti =n -2;i >=0;i--) {
23+
if (currSmallest >=nums[i]) {
24+
rightSmallest[i] = -1;
25+
currSmallest =nums[i];
26+
}else {
27+
rightSmallest[i] =currSmallest;
28+
}
29+
}
30+
intans =Integer.MAX_VALUE;
31+
for (inti =0;i <n;i++) {
32+
if (leftSmallest[i] != -1 &&rightSmallest[i] != -1) {
33+
ans =Math.min(ans,leftSmallest[i] +rightSmallest[i] +nums[i]);
34+
}
35+
}
36+
if (ans ==Integer.MAX_VALUE) {
37+
return -1;
38+
}
39+
returnans;
40+
}
41+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2909\. Minimum Sum of Mountain Triplets II
2+
3+
Medium
4+
5+
You are given a**0-indexed** array`nums` of integers.
6+
7+
A triplet of indices`(i, j, k)` is a**mountain** if:
8+
9+
*`i < j < k`
10+
*`nums[i] < nums[j]` and`nums[k] < nums[j]`
11+
12+
Return_the**minimum possible sum** of a mountain triplet of_`nums`._If no such triplet exists, return_`-1`.
13+
14+
**Example 1:**
15+
16+
**Input:** nums =[8,6,1,5,3]
17+
18+
**Output:** 9
19+
20+
**Explanation:** Triplet (2, 3, 4) is a mountain triplet of sum 9 since:
21+
- 2 < 3 < 4
22+
- nums[2] < nums[3] and nums[4] < nums[3]
23+
24+
And the sum of this triplet is nums[2] + nums[3] + nums[4] = 9. It can be shown that there are no mountain triplets with a sum of less than 9.
25+
26+
**Example 2:**
27+
28+
**Input:** nums =[5,4,8,7,10,2]
29+
30+
**Output:** 13
31+
32+
**Explanation:** Triplet (1, 3, 5) is a mountain triplet of sum 13 since:
33+
- 1 < 3 < 5
34+
- nums[1] < nums[3] and nums[5] < nums[3]
35+
36+
And the sum of this triplet is nums[1] + nums[3] + nums[5] = 13. It can be shown that there are no mountain triplets with a sum of less than 13.
37+
38+
**Example 3:**
39+
40+
**Input:** nums =[6,5,4,3,4,5]
41+
42+
**Output:** -1
43+
44+
**Explanation:** It can be shown that there are no mountain triplets in nums.
45+
46+
**Constraints:**
47+
48+
* <code>3 <= nums.length <= 10<sup>5</sup></code>
49+
* <code>1 <= nums[i] <= 10<sup>8</sup></code>
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
packageg2901_3000.s2910_minimum_number_of_groups_to_create_a_valid_assignment;
2+
3+
// #Medium #Array #Hash_Table #Greedy #2023_12_27_Time_36_ms_(68.99%)_Space_61_MB_(33.33%)
4+
5+
importjava.util.HashMap;
6+
importjava.util.Map;
7+
8+
publicclassSolution {
9+
publicintminGroupsForValidAssignment(int[]nums) {
10+
Map<Integer,Integer>count =getCountMap(nums);
11+
Map<Integer,Integer>countFreq =getCountFrequencyMap(count);
12+
intminFrequency =getMinFrequency(countFreq);
13+
for (intsize =minFrequency;size >=1;size--) {
14+
intgroup =calculateGroups(countFreq,size);
15+
if (group >0) {
16+
returngroup;
17+
}
18+
}
19+
return -1;
20+
}
21+
22+
privateMap<Integer,Integer>getCountMap(int[]nums) {
23+
Map<Integer,Integer>count =newHashMap<>();
24+
for (intnum :nums) {
25+
count.merge(num,1,Integer::sum);
26+
}
27+
returncount;
28+
}
29+
30+
privateMap<Integer,Integer>getCountFrequencyMap(Map<Integer,Integer>count) {
31+
Map<Integer,Integer>countFreq =newHashMap<>();
32+
for (intc :count.values()) {
33+
countFreq.merge(c,1,Integer::sum);
34+
}
35+
returncountFreq;
36+
}
37+
38+
privateintgetMinFrequency(Map<Integer,Integer>countFreq) {
39+
returncountFreq.keySet().stream()
40+
.min(Integer::compareTo)
41+
.orElseThrow(() ->newIllegalStateException("Count frequency map is empty"));
42+
}
43+
44+
privateintcalculateGroups(Map<Integer,Integer>countFreq,intsize) {
45+
intgroup =0;
46+
for (Map.Entry<Integer,Integer>entry :countFreq.entrySet()) {
47+
intlen =entry.getKey();
48+
intrem =len % (size +1);
49+
intg =len / (size +1);
50+
if (rem ==0) {
51+
group +=g *entry.getValue();
52+
}else {
53+
intneed =size -rem;
54+
if (g >=need) {
55+
group += (g +1) *entry.getValue();
56+
}else {
57+
return -1;
58+
}
59+
}
60+
}
61+
returngroup;
62+
}
63+
}
Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
2910\. Minimum Number of Groups to Create a Valid Assignment
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` of length`n`.
6+
7+
We want to group the indices so for each index`i` in the range`[0, n - 1]`, it is assigned to**exactly one** group.
8+
9+
A group assignment is**valid** if the following conditions hold:
10+
11+
* For every group`g`, all indices`i` assigned to group`g` have the same value in`nums`.
12+
* For any two groups <code>g<sub>1</sub></code> and <code>g<sub>2</sub></code>, the**difference** between the**number of indices** assigned to <code>g<sub>1</sub></code> and <code>g<sub>2</sub></code> should**not exceed**`1`.
13+
14+
Return_an integer denoting__the**minimum** number of groups needed to create a valid group assignment._
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[3,2,3,2,3]
19+
20+
**Output:** 2
21+
22+
**Explanation:** One way the indices can be assigned to 2 groups is as follows, where the values in square brackets are indices:
23+
24+
group 1 ->[0,2,4]
25+
26+
group 2 ->[1,3]
27+
28+
All indices are assigned to one group.
29+
30+
In group 1, nums[0] == nums[2] == nums[4], so all indices have the same value.
31+
32+
In group 2, nums[1] == nums[3], so all indices have the same value.
33+
34+
The number of indices assigned to group 1 is 3, and the number of indices assigned to group 2 is 2.
35+
36+
Their difference doesn't exceed 1.
37+
38+
It is not possible to use fewer than 2 groups because, in order to use just 1 group, all indices assigned to that group must have the same value.
39+
40+
Hence, the answer is 2.
41+
42+
**Example 2:**
43+
44+
**Input:** nums =[10,10,10,3,1,1]
45+
46+
**Output:** 4
47+
48+
**Explanation:** One way the indices can be assigned to 4 groups is as follows, where the values in square brackets are indices:
49+
50+
group 1 ->[0]
51+
52+
group 2 ->[1,2]
53+
54+
group 3 ->[3]
55+
56+
group 4 ->[4,5]
57+
58+
The group assignment above satisfies both conditions.
59+
60+
It can be shown that it is not possible to create a valid assignment using fewer than 4 groups.
61+
62+
Hence, the answer is 4.
63+
64+
**Constraints:**
65+
66+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
67+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
packageg2901_3000.s2911_minimum_changes_to_make_k_semi_palindromes;
2+
3+
// #Hard #String #Dynamic_Programming #Two_Pointers
4+
// #2023_12_27_Time_15_ms_(98.23%)_Space_45.2_MB_(45.13%)
5+
6+
publicclassSolution {
7+
privatestaticfinalintINF =200;
8+
privatefinalDivisor[]divisors =getDivisors();
9+
privatechar[]cs;
10+
privateint[][]cost;
11+
privateint[][]dp;
12+
13+
publicintminimumChanges(Strings,intk) {
14+
cs =s.toCharArray();
15+
intn =cs.length;
16+
cost =newint[n -1][n +1];
17+
dp =newint[n +1][k +1];
18+
returncalc(n,k) -k;
19+
}
20+
21+
privateintcalc(inti,intk) {
22+
if (k ==1) {
23+
returnchange(0,i);
24+
}
25+
if (dp[i][k] >0) {
26+
returndp[i][k];
27+
}
28+
intmin =INF;
29+
for (intj = (k -1) *2;j <i -1; ++j) {
30+
min =Math.min(min,calc(j,k -1) +change(j,i));
31+
}
32+
dp[i][k] =min;
33+
returnmin;
34+
}
35+
36+
privateintchange(intstart,intend) {
37+
if (cost[start][end] >0) {
38+
returncost[start][end];
39+
}
40+
intmin =INF;
41+
for (Divisordivisor =divisors[end -start];divisor !=null;divisor =divisor.next) {
42+
intd =divisor.value;
43+
intcount =0;
44+
for (inti =0;i <d; ++i) {
45+
intleft =start +i;
46+
intright =end -d +i;
47+
while (left +d <=right) {
48+
if (cs[left] !=cs[right]) {
49+
count++;
50+
}
51+
left +=d;
52+
right -=d;
53+
}
54+
}
55+
if (count <min) {
56+
min =count;
57+
}
58+
}
59+
cost[start][end] =min +1;
60+
returnmin +1;
61+
}
62+
63+
privateDivisor[]getDivisors() {
64+
Divisor[]list =newDivisor[200 +1];
65+
for (intd =1;d <200; ++d) {
66+
for (intlen =d +d;len <200 +1;len +=d) {
67+
list[len] =newDivisor(d,list[len]);
68+
}
69+
}
70+
returnlist;
71+
}
72+
73+
privatestaticclassDivisor {
74+
intvalue;
75+
Divisornext;
76+
77+
Divisor(intdivisor,Divisornext) {
78+
this.value =divisor;
79+
this.next =next;
80+
}
81+
}
82+
}

0 commit comments

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