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

Commitc56a957

Browse files
authored
Added tasks 2926-2929
1 parent2c09a3e commitc56a957

File tree

9 files changed

+297
-0
lines changed

9 files changed

+297
-0
lines changed
Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
packageg2901_3000.s2926_maximum_balanced_subsequence_sum;
2+
3+
// #Hard #Array #Dynamic_Programming #Binary_Search #Segment_Tree #Binary_Indexed_Tree
4+
// #2023_12_29_Time_37_ms_(99.23%)_Space_68.2_MB_(17.41%)
5+
6+
importjava.util.Arrays;
7+
importjava.util.HashMap;
8+
importjava.util.Map;
9+
10+
publicclassSolution {
11+
publiclongmaxBalancedSubsequenceSum(int[]nums) {
12+
intn =nums.length;
13+
intm =0;
14+
int[]arr =newint[n];
15+
intmax =Integer.MIN_VALUE;
16+
for (inti =0;i <n; ++i) {
17+
intx =nums[i];
18+
if (x >0) {
19+
arr[m++] =x -i;
20+
}elseif (x >max) {
21+
max =x;
22+
}
23+
}
24+
if (m ==0) {
25+
returnmax;
26+
}
27+
Arrays.sort(arr);
28+
Map<Integer,Integer>map =newHashMap<>(m <<1);
29+
intpre =Integer.MIN_VALUE;
30+
intindex =1;
31+
for (intx :arr) {
32+
if (x ==pre) {
33+
continue;
34+
}
35+
map.put(x,index++);
36+
pre =x;
37+
}
38+
39+
BITbit =newBIT(index);
40+
longans =0;
41+
for (inti =0;i <n; ++i) {
42+
if (nums[i] <=0) {
43+
continue;
44+
}
45+
index =map.get(nums[i] -i);
46+
longcur =bit.query(index) +nums[i];
47+
bit.update(index,cur);
48+
ans =Math.max(ans,cur);
49+
}
50+
returnans;
51+
}
52+
53+
privatestaticclassBIT {
54+
long[]tree;
55+
intn;
56+
57+
publicBIT(intn) {
58+
this.n =n;
59+
tree =newlong[n +1];
60+
}
61+
62+
publicintlowbit(intindex) {
63+
returnindex & (-index);
64+
}
65+
66+
publicvoidupdate(intindex,longv) {
67+
while (index <=n &&tree[index] <v) {
68+
tree[index] =v;
69+
index +=lowbit(index);
70+
}
71+
}
72+
73+
publiclongquery(intindex) {
74+
longresult =0;
75+
while (index >0) {
76+
result =Math.max(tree[index],result);
77+
index -=lowbit(index);
78+
}
79+
returnresult;
80+
}
81+
}
82+
}
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
2926\. Maximum Balanced Subsequence Sum
2+
3+
Hard
4+
5+
You are given a**0-indexed** integer array`nums`.
6+
7+
A**subsequence** of`nums` having length`k` and consisting of**indices** <code>i<sub>0</sub> < i<sub>1</sub> < ... < i<sub>k-1</sub></code> is**balanced** if the following holds:
8+
9+
* <code>nums[i<sub>j</sub>] - nums[i<sub>j-1</sub>] >= i<sub>j</sub> - i<sub>j-1</sub></code>, for every`j` in the range`[1, k - 1]`.
10+
11+
A**subsequence** of`nums` having length`1` is considered balanced.
12+
13+
Return_an integer denoting the**maximum** possible**sum of elements** in a**balanced** subsequence of_`nums`.
14+
15+
A**subsequence** of an array is a new**non-empty** array that is formed from the original array by deleting some (**possibly none**) of the elements without disturbing the relative positions of the remaining elements.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[3,3,5,6]
20+
21+
**Output:** 14
22+
23+
**Explanation:** In this example, the subsequence[3,5,6] consisting of indices 0, 2, and 3 can be selected.
24+
25+
nums[2] - nums[0] >= 2 - 0.
26+
27+
nums[3] - nums[2] >= 3 - 2.
28+
29+
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
30+
31+
The subsequence consisting of indices 1, 2, and 3 is also valid.
32+
33+
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 14.
34+
35+
**Example 2:**
36+
37+
**Input:** nums =[5,-1,-3,8]
38+
39+
**Output:** 13
40+
41+
**Explanation:** In this example, the subsequence[5,8] consisting of indices 0 and 3 can be selected.
42+
43+
nums[3] - nums[0] >= 3 - 0.
44+
45+
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
46+
47+
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 13.
48+
49+
**Example 3:**
50+
51+
**Input:** nums =[-2,-1]
52+
53+
**Output:** -1
54+
55+
**Explanation:** In this example, the subsequence[-1] can be selected. It is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
56+
57+
**Constraints:**
58+
59+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
60+
* <code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg2901_3000.s2928_distribute_candies_among_children_i;
2+
3+
// #Easy #Math #Enumeration #Combinatorics #2023_12_29_Time_1_ms_(98.72%)_Space_40.9_MB_(6.45%)
4+
5+
publicclassSolution {
6+
publicintdistributeCandies(intn,intlimit) {
7+
intcount =0;
8+
for (inti =0;i <Math.min(limit,n) +1;i++) {
9+
for (intj =0;j <Math.min(limit,n) +1;j++) {
10+
intk =n -i -j;
11+
if (k >=0 &&k <=limit) {
12+
count++;
13+
}
14+
}
15+
}
16+
returncount;
17+
}
18+
}
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
2928\. Distribute Candies Among Children I
2+
3+
Easy
4+
5+
You are given two positive integers`n` and`limit`.
6+
7+
Return_the**total number** of ways to distribute_`n`_candies among_`3`_children such that no child gets more than_`limit`_candies._
8+
9+
**Example 1:**
10+
11+
**Input:** n = 5, limit = 2
12+
13+
**Output:** 3
14+
15+
**Explanation:** There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).
16+
17+
**Example 2:**
18+
19+
**Input:** n = 3, limit = 3
20+
21+
**Output:** 10
22+
23+
**Explanation:** There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).
24+
25+
**Constraints:**
26+
27+
*`1 <= n <= 50`
28+
*`1 <= limit <= 50`
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg2901_3000.s2929_distribute_candies_among_children_ii;
2+
3+
// #Medium #Math #Enumeration #Combinatorics #2023_12_29_Time_0_ms_(100.00%)_Space_40.7_MB_(5.70%)
4+
5+
publicclassSolution {
6+
publiclongdistributeCandies(longn,longk) {
7+
if (n <=k) {
8+
return (n +1) * (n +2) /2;
9+
}
10+
if (n <=2 *k) {
11+
return (k +1) * (k +1)
12+
- (n -k) * (n -k +1) /2
13+
- (2 *k -n) * (2 *k -n +1) /2;
14+
}
15+
if (n <=3 *k) {
16+
return (3 *k -n +1) * (3 *k -n +2) /2;
17+
}
18+
return0;
19+
}
20+
}
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
2929\. Distribute Candies Among Children II
2+
3+
Medium
4+
5+
You are given two positive integers`n` and`limit`.
6+
7+
Return_the**total number** of ways to distribute_`n`_candies among_`3`_children such that no child gets more than_`limit`_candies._
8+
9+
**Example 1:**
10+
11+
**Input:** n = 5, limit = 2
12+
13+
**Output:** 3
14+
15+
**Explanation:** There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).
16+
17+
**Example 2:**
18+
19+
**Input:** n = 3, limit = 3
20+
21+
**Output:** 10
22+
23+
**Explanation:** There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).
24+
25+
**Constraints:**
26+
27+
* <code>1 <= n <= 10<sup>6</sup></code>
28+
* <code>1 <= limit <= 10<sup>6</sup></code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2901_3000.s2926_maximum_balanced_subsequence_sum;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidmaxBalancedSubsequenceSum() {
11+
assertThat(newSolution().maxBalancedSubsequenceSum(newint[] {3,3,5,6}),equalTo(14L));
12+
}
13+
14+
@Test
15+
voidmaxBalancedSubsequenceSum2() {
16+
assertThat(
17+
newSolution().maxBalancedSubsequenceSum(newint[] {5, -1, -3,8}),equalTo(13L));
18+
}
19+
20+
@Test
21+
voidmaxBalancedSubsequenceSum3() {
22+
assertThat(
23+
newSolution().maxBalancedSubsequenceSum(newint[] {5, -1, -3,8}),equalTo(13L));
24+
}
25+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg2901_3000.s2928_distribute_candies_among_children_i;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voiddistributeCandies() {
11+
assertThat(newSolution().distributeCandies(5,2),equalTo(3));
12+
}
13+
14+
@Test
15+
voiddistributeCandies2() {
16+
assertThat(newSolution().distributeCandies(3,3),equalTo(10));
17+
}
18+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg2901_3000.s2929_distribute_candies_among_children_ii;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voiddistributeCandies() {
11+
assertThat(newSolution().distributeCandies(5,2),equalTo(3L));
12+
}
13+
14+
@Test
15+
voiddistributeCandies2() {
16+
assertThat(newSolution().distributeCandies(3,3),equalTo(10L));
17+
}
18+
}

0 commit comments

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