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

Commit2b6ef65

Browse files
authored
Added tasks 2862-2867
1 parent63a7f05 commit2b6ef65

File tree

15 files changed

+617
-0
lines changed

15 files changed

+617
-0
lines changed
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg2801_2900.s2862_maximum_element_sum_of_a_complete_subset_of_indices;
2+
3+
// #Hard #Array #Math #Number_Theory #2023_12_20_Time_3_ms_(78.95%)_Space_44.4_MB_(88.16%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publiclongmaximumSum(List<Integer>nums) {
9+
longans =0;
10+
intn =nums.size();
11+
intbound = (int)Math.floor(Math.sqrt(n));
12+
int[]squares =newint[bound +1];
13+
for (inti =1;i <=bound +1;i++) {
14+
squares[i -1] =i *i;
15+
}
16+
for (inti =1;i <=n;i++) {
17+
longres =0;
18+
intidx =0;
19+
intcurr =i *squares[idx];
20+
while (curr <=n) {
21+
res +=nums.get(curr -1);
22+
curr =i *squares[++idx];
23+
}
24+
ans =Math.max(ans,res);
25+
}
26+
returnans;
27+
}
28+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2862\. Maximum Element-Sum of a Complete Subset of Indices
2+
3+
Hard
4+
5+
You are given a**1****\-indexed** array`nums` of`n` integers.
6+
7+
A set of numbers is**complete** if the product of every pair of its elements is a perfect square.
8+
9+
For a subset of the indices set`{1, 2, ..., n}` represented as <code>{i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>k</sub>}</code>, we define its**element-sum** as: <code>nums[i<sub>1</sub>] + nums[i<sub>2</sub>] + ... + nums[i<sub>k</sub>]</code>.
10+
11+
Return_the**maximum element-sum** of a**complete** subset of the indices set_`{1, 2, ..., n}`.
12+
13+
A perfect square is a number that can be expressed as the product of an integer by itself.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[8,7,3,5,7,2,4,9]
18+
19+
**Output:** 16
20+
21+
**Explanation:** Apart from the subsets consisting of a single index, there are two other complete subsets of indices: {1,4} and {2,8}.
22+
23+
The sum of the elements corresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 8 + 5 = 13.
24+
25+
The sum of the elements corresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 7 + 9 = 16.
26+
27+
Hence, the maximum element-sum of a complete subset of indices is 16.
28+
29+
**Example 2:**
30+
31+
**Input:** nums =[5,10,3,10,1,13,7,9,4]
32+
33+
**Output:** 19
34+
35+
**Explanation:** Apart from the subsets consisting of a single index, there are four other complete subsets of indices: {1,4}, {1,9}, {2,8}, {4,9}, and {1,4,9}.
36+
37+
The sum of the elements corresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 5 + 10 = 15.
38+
39+
The sum of the elements corresponding to indices 1 and 9 is equal to nums[1] + nums[9] = 5 + 4 = 9.
40+
41+
The sum of the elements corresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 10 + 9 = 19.
42+
43+
The sum of the elements corresponding to indices 4 and 9 is equal to nums[4] + nums[9] = 10 + 4 = 14.
44+
45+
The sum of the elements corresponding to indices 1, 4, and 9 is equal to nums[1] + nums[4] + nums[9] = 5 + 10 + 4 = 19.
46+
47+
Hence, the maximum element-sum of a complete subset of indices is 19.
48+
49+
**Constraints:**
50+
51+
* <code>1 <= n == nums.length <= 10<sup>4</sup></code>
52+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2801_2900.s2864_maximum_odd_binary_number;
2+
3+
// #Easy #String #Math #Greedy #2023_12_20_Time_1_ms_(100.00%)_Space_41.8_MB_(93.74%)
4+
5+
publicclassSolution {
6+
publicStringmaximumOddBinaryNumber(Strings) {
7+
intlen =s.length();
8+
intcount =0;
9+
StringBuildersb =newStringBuilder();
10+
for (inti =0;i <len;i++) {
11+
if (s.charAt(i) =='1') {
12+
count++;
13+
}
14+
}
15+
if (count ==len) {
16+
returns;
17+
}
18+
len -=count;
19+
while (count >1) {
20+
sb.append('1');
21+
count--;
22+
}
23+
while (len >0) {
24+
sb.append('0');
25+
len--;
26+
}
27+
sb.append('1');
28+
returnsb.toString();
29+
}
30+
}
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
2864\. Maximum Odd Binary Number
2+
3+
Easy
4+
5+
You are given a**binary** string`s` that contains at least one`'1'`.
6+
7+
You have to**rearrange** the bits in such a way that the resulting binary number is the**maximum odd binary number** that can be created from this combination.
8+
9+
Return_a string representing the maximum odd binary number that can be created from the given combination._
10+
11+
**Note** that the resulting string**can** have leading zeros.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "010"
16+
17+
**Output:** "001"
18+
19+
**Explanation:** Because there is just one '1', it must be in the last position. So the answer is "001".
20+
21+
**Example 2:**
22+
23+
**Input:** s = "0101"
24+
25+
**Output:** "1001"
26+
27+
**Explanation:** One of the '1's must be in the last position. The maximum number that can be made with the remaining digits is "100". So the answer is "1001".
28+
29+
**Constraints:**
30+
31+
*`1 <= s.length <= 100`
32+
*`s` consists only of`'0'` and`'1'`.
33+
*`s` contains at least one`'1'`.
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
packageg2801_2900.s2865_beautiful_towers_i;
2+
3+
// #Medium #Array #Stack #Monotonic_Stack #2023_12_20_Time_13_ms_(74.26%)_Space_43.4_MB_(45.54%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
privatelongfun(List<Integer>maxHeights,intpickId) {
9+
longans =maxHeights.get(pickId);
10+
longmin =maxHeights.get(pickId);
11+
for (inti =pickId -1;i >=0;i--) {
12+
min =Math.min(min,maxHeights.get(i));
13+
ans +=min;
14+
}
15+
min =maxHeights.get(pickId);
16+
for (inti =pickId +1;i <maxHeights.size();i++) {
17+
min =Math.min(min,maxHeights.get(i));
18+
ans +=min;
19+
}
20+
returnans;
21+
}
22+
23+
publiclongmaximumSumOfHeights(List<Integer>maxHeights) {
24+
intn =maxHeights.size();
25+
longans =0;
26+
for (inti =0;i <n;i++) {
27+
if (i ==0
28+
||i ==n -1
29+
|| (maxHeights.get(i) >=maxHeights.get(i -1)
30+
&&maxHeights.get(i) >=maxHeights.get(i +1))) {
31+
ans =Math.max(ans,fun(maxHeights,i));
32+
}
33+
}
34+
returnans;
35+
}
36+
}
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
2865\. Beautiful Towers I
2+
3+
Medium
4+
5+
You are given a**0-indexed** array`maxHeights` of`n` integers.
6+
7+
You are tasked with building`n` towers in the coordinate line. The <code>i<sup>th</sup></code> tower is built at coordinate`i` and has a height of`heights[i]`.
8+
9+
A configuration of towers is**beautiful** if the following conditions hold:
10+
11+
1.`1 <= heights[i] <= maxHeights[i]`
12+
2.`heights` is a**mountain** array.
13+
14+
Array`heights` is a**mountain** if there exists an index`i` such that:
15+
16+
* For all`0 < j <= i`,`heights[j - 1] <= heights[j]`
17+
* For all`i <= k < n - 1`,`heights[k + 1] <= heights[k]`
18+
19+
Return_the**maximum possible sum of heights** of a beautiful configuration of towers_.
20+
21+
**Example 1:**
22+
23+
**Input:** maxHeights =[5,3,4,1,1]
24+
25+
**Output:** 13
26+
27+
**Explanation:** One beautiful configuration with a maximum sum is heights =[5,3,3,1,1]. This configuration is beautiful since:
28+
- 1 <= heights[i] <= maxHeights[i]
29+
- heights is a mountain of peak i = 0.
30+
31+
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.
32+
33+
**Example 2:**
34+
35+
**Input:** maxHeights =[6,5,3,9,2,7]
36+
37+
**Output:** 22
38+
39+
**Explanation:** One beautiful configuration with a maximum sum is heights =[3,3,3,9,2,2]. This configuration is beautiful since:
40+
- 1 <= heights[i] <= maxHeights[i]
41+
- heights is a mountain of peak i = 3.
42+
43+
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.
44+
45+
**Example 3:**
46+
47+
**Input:** maxHeights =[3,2,5,5,2,3]
48+
49+
**Output:** 18
50+
51+
**Explanation:** One beautiful configuration with a maximum sum is heights =[2,2,5,5,2,2]. This configuration is beautiful since:
52+
- 1 <= heights[i] <= maxHeights[i]
53+
- heights is a mountain of peak i = 2.
54+
55+
Note that, for this configuration, i = 3 can also be considered a peak. It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.
56+
57+
**Constraints:**
58+
59+
* <code>1 <= n == maxHeights <= 10<sup>3</sup></code>
60+
* <code>1 <= maxHeights[i] <= 10<sup>9</sup></code>
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
packageg2801_2900.s2866_beautiful_towers_ii;
2+
3+
// #Medium #Array #Stack #Monotonic_Stack #2023_12_20_Time_35_ms_(89.02%)_Space_72.5_MB_(5.49%)
4+
5+
importjava.util.Deque;
6+
importjava.util.LinkedList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
publiclongmaximumSumOfHeights(List<Integer>mH) {
11+
intn =mH.size();
12+
Deque<Integer>st =newLinkedList<>();
13+
int[]prevSmaller =newint[n +1];
14+
for (inti =0;i <n;i++) {
15+
while (!st.isEmpty() &&mH.get(st.peek()) >=mH.get(i)) {
16+
st.pop();
17+
}
18+
if (st.isEmpty()) {
19+
prevSmaller[i] = -1;
20+
}else {
21+
prevSmaller[i] =st.peek();
22+
}
23+
st.push(i);
24+
}
25+
st.clear();
26+
int[]nextSmaller =newint[n +1];
27+
for (inti =n -1;i >=0;i--) {
28+
while (!st.isEmpty() &&mH.get(st.peek()) >=mH.get(i)) {
29+
st.pop();
30+
}
31+
if (st.isEmpty()) {
32+
nextSmaller[i] =n;
33+
}else {
34+
nextSmaller[i] =st.peek();
35+
}
36+
st.push(i);
37+
}
38+
long[]leftSum =newlong[n];
39+
leftSum[0] =mH.get(0);
40+
for (inti =1;i <n; ++i) {
41+
intprevSmallerIdx =prevSmaller[i];
42+
intequalCount =i -prevSmallerIdx;
43+
leftSum[i] = ((long)equalCount *mH.get(i));
44+
if (prevSmallerIdx != -1) {
45+
leftSum[i] +=leftSum[prevSmallerIdx];
46+
}
47+
}
48+
long[]rightSum =newlong[n];
49+
rightSum[n -1] =mH.get(n -1);
50+
for (inti =n -2;i >=0;i--) {
51+
intnextSmallerIdx =nextSmaller[i];
52+
intequalCount =nextSmallerIdx -i;
53+
rightSum[i] = ((long)equalCount *mH.get(i));
54+
if (nextSmallerIdx !=n) {
55+
rightSum[i] +=rightSum[nextSmallerIdx];
56+
}
57+
}
58+
longans =0;
59+
for (inti =0;i <n;i++) {
60+
longtotalSum =leftSum[i] +rightSum[i] -mH.get(i);
61+
ans =Math.max(ans,totalSum);
62+
}
63+
returnans;
64+
}
65+
}
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
2866\. Beautiful Towers II
2+
3+
Medium
4+
5+
You are given a**0-indexed** array`maxHeights` of`n` integers.
6+
7+
You are tasked with building`n` towers in the coordinate line. The <code>i<sup>th</sup></code> tower is built at coordinate`i` and has a height of`heights[i]`.
8+
9+
A configuration of towers is**beautiful** if the following conditions hold:
10+
11+
1.`1 <= heights[i] <= maxHeights[i]`
12+
2.`heights` is a**mountain** array.
13+
14+
Array`heights` is a**mountain** if there exists an index`i` such that:
15+
16+
* For all`0 < j <= i`,`heights[j - 1] <= heights[j]`
17+
* For all`i <= k < n - 1`,`heights[k + 1] <= heights[k]`
18+
19+
Return_the**maximum possible sum of heights** of a beautiful configuration of towers_.
20+
21+
**Example 1:**
22+
23+
**Input:** maxHeights =[5,3,4,1,1]
24+
25+
**Output:** 13
26+
27+
**Explanation:** One beautiful configuration with a maximum sum is heights =[5,3,3,1,1]. This configuration is beautiful since:
28+
- 1 <= heights[i] <= maxHeights[i]
29+
- heights is a mountain of peak i = 0.
30+
31+
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.
32+
33+
**Example 2:**
34+
35+
**Input:** maxHeights =[6,5,3,9,2,7]
36+
37+
**Output:** 22
38+
39+
**Explanation:** One beautiful configuration with a maximum sum is heights =[3,3,3,9,2,2]. This configuration is beautiful since:
40+
- 1 <= heights[i] <= maxHeights[i]
41+
- heights is a mountain of peak i = 3.
42+
43+
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.
44+
45+
**Example 3:**
46+
47+
**Input:** maxHeights =[3,2,5,5,2,3]
48+
49+
**Output:** 18
50+
51+
**Explanation:** One beautiful configuration with a maximum sum is heights =[2,2,5,5,2,2]. This configuration is beautiful since:
52+
- 1 <= heights[i] <= maxHeights[i]
53+
- heights is a mountain of peak i = 2.
54+
55+
Note that, for this configuration, i = 3 can also be considered a peak. It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.
56+
57+
**Constraints:**
58+
59+
* <code>1 <= n == maxHeights <= 10<sup>5</sup></code>
60+
* <code>1 <= maxHeights[i] <= 10<sup>9</sup></code>

0 commit comments

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