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

Commitc3c8966

Browse files
authored
Added tasks 2914-2918
1 parente8f5215 commitc3c8966

File tree

15 files changed

+514
-0
lines changed

15 files changed

+514
-0
lines changed
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
packageg2901_3000.s2914_minimum_number_of_changes_to_make_binary_string_beautiful;
2+
3+
// #Medium #String #2023_12_28_Time_3_ms_(99.56%)_Space_44.7_MB_(6.68%)
4+
5+
publicclassSolution {
6+
publicintminChanges(Strings) {
7+
intans =0;
8+
for (inti =0;i <s.length();i +=2) {
9+
if (s.charAt(i) !=s.charAt(i +1)) {
10+
ans++;
11+
}
12+
}
13+
returnans;
14+
}
15+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
2914\. Minimum Number of Changes to Make Binary String Beautiful
2+
3+
Medium
4+
5+
You are given a**0-indexed** binary string`s` having an even length.
6+
7+
A string is**beautiful** if it's possible to partition it into one or more substrings such that:
8+
9+
* Each substring has an**even length**.
10+
* Each substring contains**only**`1`'s or**only**`0`'s.
11+
12+
You can change any character in`s` to`0` or`1`.
13+
14+
Return_the**minimum** number of changes required to make the string_`s`_beautiful_.
15+
16+
**Example 1:**
17+
18+
**Input:** s = "1001"
19+
20+
**Output:** 2
21+
22+
**Explanation:** We change s[1] to 1 and s[3] to 0 to get string "1100". It can be seen that the string "1100" is beautiful because we can partition it into "11|00". It can be proven that 2 is the minimum number of changes needed to make the string beautiful.
23+
24+
**Example 2:**
25+
26+
**Input:** s = "10"
27+
28+
**Output:** 1
29+
30+
**Explanation:** We change s[1] to 1 to get string "11". It can be seen that the string "11" is beautiful because we can partition it into "11". It can be proven that 1 is the minimum number of changes needed to make the string beautiful.
31+
32+
**Example 3:**
33+
34+
**Input:** s = "0000"
35+
36+
**Output:** 0
37+
38+
**Explanation:** We don't need to make any changes as the string "0000" is beautiful already.
39+
40+
**Constraints:**
41+
42+
* <code>2 <= s.length <= 10<sup>5</sup></code>
43+
*`s` has an even length.
44+
*`s[i]` is either`'0'` or`'1'`.
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2901_3000.s2915_length_of_the_longest_subsequence_that_sums_to_target;
2+
3+
importjava.util.List;
4+
5+
// #Medium #Array #Dynamic_Programming #2023_12_28_Time_23_ms_(91.30%)_Space_44.5_MB_(66.47%)
6+
7+
publicclassSolution {
8+
publicintlengthOfLongestSubsequence(List<Integer>nums,inttarget) {
9+
int[]dp =newint[target +1];
10+
for (inti =1;i <=target;i++) {
11+
dp[i] = -1;
12+
}
13+
dp[0] =0;
14+
for (intnum :nums) {
15+
for (intj =target;j >=num;j--) {
16+
if (dp[j -num] != -1) {
17+
dp[j] =Math.max(dp[j],dp[j -num] +1);
18+
}
19+
}
20+
}
21+
if (dp[target] == -1) {
22+
return -1;
23+
}
24+
returndp[target];
25+
}
26+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
2915\. Length of the Longest Subsequence That Sums to Target
2+
3+
Medium
4+
5+
You are given a**0-indexed** array of integers`nums`, and an integer`target`.
6+
7+
Return_the**length of the longest subsequence** of_`nums`_that sums up to_`target`._If no such subsequence exists, return_`-1`.
8+
9+
A**subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[1,2,3,4,5], target = 9
14+
15+
**Output:** 3
16+
17+
**Explanation:** There are 3 subsequences with a sum equal to 9:[4,5],[1,3,5], and[2,3,4]. The longest subsequences are[1,3,5], and[2,3,4]. Hence, the answer is 3.
18+
19+
**Example 2:**
20+
21+
**Input:** nums =[4,1,3,2,1,5], target = 7
22+
23+
**Output:** 4
24+
25+
**Explanation:** There are 5 subsequences with a sum equal to 7:[4,3],[4,1,2],[4,2,1],[1,1,5], and[1,3,2,1]. The longest subsequence is[1,3,2,1]. Hence, the answer is 4.
26+
27+
**Example 3:**
28+
29+
**Input:** nums =[1,1,5,4,5], target = 3
30+
31+
**Output:** -1
32+
33+
**Explanation:** It can be shown that nums has no subsequence that sums up to 3.
34+
35+
**Constraints:**
36+
37+
*`1 <= nums.length <= 1000`
38+
*`1 <= nums[i] <= 1000`
39+
*`1 <= target <= 1000`
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
packageg2901_3000.s2916_subarrays_distinct_element_sum_of_squares_ii;
2+
3+
// #Hard #Array #Dynamic_Programming #Segment_Tree #Binary_Indexed_Tree
4+
// #2023_12_28_Time_77_ms_(83.65%)_Space_56.5_MB_(83.65%)
5+
6+
publicclassSolution {
7+
privatestaticfinalintMOD = (int) (1e9) +7;
8+
privateintn;
9+
privatelong[]tree1;
10+
privatelong[]tree2;
11+
12+
publicintsumCounts(int[]nums) {
13+
n =nums.length;
14+
tree1 =newlong[n +1];
15+
tree2 =newlong[n +1];
16+
intmax =0;
17+
for (intx :nums) {
18+
if (x >max) {
19+
max =x;
20+
}
21+
}
22+
int[]last =newint[max +1];
23+
longans =0;
24+
longcur =0;
25+
for (inti =1;i <=n;i++) {
26+
intx =nums[i -1];
27+
intj =last[x];
28+
cur +=2 * (query(i) -query(j)) + (i -j);
29+
ans +=cur;
30+
update(j +1,1);
31+
update(i +1, -1);
32+
last[x] =i;
33+
}
34+
return (int) (ans %MOD);
35+
}
36+
37+
intlowbit(intindex) {
38+
returnindex & (-index);
39+
}
40+
41+
voidupdate(intindex,intx) {
42+
intv =index *x;
43+
while (index <=n) {
44+
tree1[index] +=x;
45+
tree2[index] +=v;
46+
index +=lowbit(index);
47+
}
48+
}
49+
50+
longquery(intindex) {
51+
longres =0;
52+
intp =index +1;
53+
while (index >0) {
54+
res +=p *tree1[index] -tree2[index];
55+
index -=lowbit(index);
56+
}
57+
returnres;
58+
}
59+
}
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
2916\. Subarrays Distinct Element Sum of Squares II
2+
3+
Hard
4+
5+
You are given a**0-indexed** integer array`nums`.
6+
7+
The**distinct count** of a subarray of`nums` is defined as:
8+
9+
* Let`nums[i..j]` be a subarray of`nums` consisting of all the indices from`i` to`j` such that`0 <= i <= j < nums.length`. Then the number of distinct values in`nums[i..j]` is called the distinct count of`nums[i..j]`.
10+
11+
Return_the sum of the**squares** of**distinct counts** of all subarrays of_`nums`.
12+
13+
Since the answer may be very large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
14+
15+
A subarray is a contiguous**non-empty** sequence of elements within an array.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[1,2,1]
20+
21+
**Output:** 15
22+
23+
**Explanation:** Six possible subarrays are:
24+
25+
[1]: 1 distinct value
26+
27+
[2]: 1 distinct value
28+
29+
[1]: 1 distinct value
30+
31+
[1,2]: 2 distinct values
32+
33+
[2,1]: 2 distinct values
34+
35+
[1,2,1]: 2 distinct values
36+
37+
The sum of the squares of the distinct counts in all subarrays is equal to 1<sup>2</sup> + 1<sup>2</sup> + 1<sup>2</sup> + 2<sup>2</sup> + 2<sup>2</sup> + 2<sup>2</sup> = 15.
38+
39+
**Example 2:**
40+
41+
**Input:** nums =[2,2]
42+
43+
**Output:** 3
44+
45+
**Explanation:** Three possible subarrays are:
46+
47+
[2]: 1 distinct value
48+
49+
[2]: 1 distinct value
50+
51+
[2,2]: 1 distinct value
52+
53+
The sum of the squares of the distinct counts in all subarrays is equal to 1<sup>2</sup> + 1<sup>2</sup> + 1<sup>2</sup> = 3.
54+
55+
**Constraints:**
56+
57+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
58+
* <code>1 <= nums[i] <= 10<sup>5</sup></code>
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2901_3000.s2917_find_the_k_or_of_an_array;
2+
3+
// #Easy #Array #Bit_Manipulation #2023_12_28_Time_2_ms_(96.79%)_Space_44.2_MB_(6.69%)
4+
5+
publicclassSolution {
6+
publicintfindKOr(int[]nums,intk) {
7+
int[]dp =newint[31];
8+
for (intnum :nums) {
9+
inti =0;
10+
while (num >0) {
11+
if ((num &1) ==1) {
12+
dp[i] +=1;
13+
}
14+
i +=1;
15+
num =num >>1;
16+
}
17+
}
18+
intans =0;
19+
for (inti =0;i <31;i++) {
20+
if (dp[i] >=k) {
21+
ans += (1 <<i);
22+
}
23+
}
24+
returnans;
25+
}
26+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
2917\. Find the K-or of an Array
2+
3+
Easy
4+
5+
You are given a**0-indexed** integer array`nums`, and an integer`k`.
6+
7+
The**K-or** of`nums` is a non-negative integer that satisfies the following:
8+
9+
* The <code>i<sup>th</sup></code> bit is set in the K-or**if and only if** there are at least`k` elements of nums in which bit`i` is set.
10+
11+
Return_the**K-or** of_`nums`.
12+
13+
**Note** that a bit`i` is set in`x` if <code>(2<sup>i</sup> AND x) == 2<sup>i</sup></code>, where`AND` is the bitwise`AND` operator.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[7,12,9,8,9,15], k = 4
18+
19+
**Output:** 9
20+
21+
**Explanation:**
22+
23+
Bit 0 is set at nums[0], nums[2], nums[4], and nums[5].
24+
25+
Bit 1 is set at nums[0], and nums[5].
26+
27+
Bit 2 is set at nums[0], nums[1], and nums[5].
28+
29+
Bit 3 is set at nums[1], nums[2], nums[3], nums[4], and nums[5].
30+
31+
Only bits 0 and 3 are set in at least k elements of the array, and bits i >= 4 are not set in any of the array's elements. Hence, the answer is 2^0 + 2^3 = 9.
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[2,12,1,11,4,5], k = 6
36+
37+
**Output:** 0
38+
39+
**Explanation:** Since k == 6 == nums.length, the 6-or of the array is equal to the bitwise AND of all its elements. Hence, the answer is 2 AND 12 AND 1 AND 11 AND 4 AND 5 = 0.
40+
41+
**Example 3:**
42+
43+
**Input:** nums =[10,8,5,9,11,6,8], k = 1
44+
45+
**Output:** 15
46+
47+
**Explanation:** Since k == 1, the 1-or of the array is equal to the bitwise OR of all its elements. Hence, the answer is 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15.
48+
49+
**Constraints:**
50+
51+
*`1 <= nums.length <= 50`
52+
* <code>0 <= nums[i] < 2<sup>31</sup></code>
53+
*`1 <= k <= nums.length`
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
packageg2901_3000.s2918_minimum_equal_sum_of_two_arrays_after_replacing_zeros;
2+
3+
// #Medium #Array #Greedy #2023_12_28_Time_3_ms_(98.52%)_Space_60.7_MB_(8.70%)
4+
5+
publicclassSolution {
6+
publiclongminSum(int[]nums1,int[]nums2) {
7+
longs1 =0;
8+
longs2 =0;
9+
longl =0;
10+
longr =0;
11+
for (inti :nums1) {
12+
s1 +=i;
13+
if (i ==0) {
14+
l++;
15+
}
16+
}
17+
for (inti :nums2) {
18+
s2 +=i;
19+
if (i ==0) {
20+
r++;
21+
}
22+
}
23+
if (s1 ==s2 &&l ==0 &&r ==0) {
24+
returns1;
25+
}
26+
longx =Math.abs(s1 -s2);
27+
if (s1 >s2) {
28+
if (r ==0 || (l ==0 &&r >x)) {
29+
return -1;
30+
}
31+
if (l ==0) {
32+
returns1;
33+
}
34+
returns1 +Math.max(l,r -x);
35+
}else {
36+
if (l ==0 || (r ==0 &&l >x)) {
37+
return -1;
38+
}
39+
if (s1 ==s2) {
40+
returns1 +Math.max(l,r);
41+
}
42+
if (r ==0) {
43+
returns2;
44+
}
45+
returns2 +Math.max(r,l -x);
46+
}
47+
}
48+
}

0 commit comments

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