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

Commit5b74f8e

Browse files
authored
Added tasks 2825-2829
1 parent0b142ad commit5b74f8e

File tree

15 files changed

+518
-0
lines changed

15 files changed

+518
-0
lines changed
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2801_2900.s2825_make_string_a_subsequence_using_cyclic_increments;
2+
3+
// #Medium #String #Two_Pointers #2023_12_11_Time_5_ms_(99.69%)_Space_44.9_MB_(14.37%)
4+
5+
publicclassSolution {
6+
publicbooleancanMakeSubsequence(Stringstr1,Stringstr2) {
7+
intstr1ptr =0;
8+
for (inti =0;i <str2.length();i++) {
9+
charc2 =str2.charAt(i);
10+
booleanfound =false;
11+
while (str1ptr <str1.length()) {
12+
charc1 =str1.charAt(str1ptr++);
13+
if (c1 ==c2 || (c1 -'a' +1) %26 ==c2 -'a') {
14+
found =true;
15+
break;
16+
}
17+
}
18+
if (!found) {
19+
returnfalse;
20+
}
21+
}
22+
returntrue;
23+
}
24+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2825\. Make String a Subsequence Using Cyclic Increments
2+
3+
Medium
4+
5+
You are given two**0-indexed** strings`str1` and`str2`.
6+
7+
In an operation, you select a**set** of indices in`str1`, and for each index`i` in the set, increment`str1[i]` to the next character**cyclically**. That is`'a'` becomes`'b'`,`'b'` becomes`'c'`, and so on, and`'z'` becomes`'a'`.
8+
9+
Return`true`_if it is possible to make_`str2`_a subsequence of_`str1`_by performing the operation**at most once**_,_and_`false`_otherwise_.
10+
11+
**Note:** A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.
12+
13+
**Example 1:**
14+
15+
**Input:** str1 = "abc", str2 = "ad"
16+
17+
**Output:** true
18+
19+
**Explanation:** Select index 2 in str1. Increment str1[2] to become 'd'. Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.
20+
21+
**Example 2:**
22+
23+
**Input:** str1 = "zc", str2 = "ad"
24+
25+
**Output:** true
26+
27+
**Explanation:** Select indices 0 and 1 in str1. Increment str1[0] to become 'a'. Increment str1[1] to become 'd'. Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.
28+
29+
**Example 3:**
30+
31+
**Input:** str1 = "ab", str2 = "d"
32+
33+
**Output:** false
34+
35+
**Explanation:** In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once. Therefore, false is returned.
36+
37+
**Constraints:**
38+
39+
* <code>1 <= str1.length <= 10<sup>5</sup></code>
40+
* <code>1 <= str2.length <= 10<sup>5</sup></code>
41+
*`str1` and`str2` consist of only lowercase English letters.
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg2801_2900.s2826_sorting_three_groups;
2+
3+
// #Medium #Array #Dynamic_Programming #2023_12_11_Time_4_ms_(100.00%)_Space_43.5_MB_(79.36%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publicintminimumOperations(List<Integer>nums) {
9+
intn =nums.size();
10+
int[]arr =newint[3];
11+
intmax =0;
12+
for (Integernum :nums) {
13+
intlocMax =0;
14+
intvalue =num;
15+
for (intj =0;j <value;j++) {
16+
locMax =Math.max(locMax,arr[j]);
17+
}
18+
19+
locMax++;
20+
arr[value -1] =locMax;
21+
if (locMax >max) {
22+
max =locMax;
23+
}
24+
}
25+
returnn -max;
26+
}
27+
}
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
2826\. Sorting Three Groups
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` of length`n`.
6+
7+
The numbers from`0` to`n - 1` are divided into three groups numbered from`1` to`3`, where number`i` belongs to group`nums[i]`. Notice that some groups may be**empty**.
8+
9+
You are allowed to perform this operation any number of times:
10+
11+
* Pick number`x` and change its group. More formally, change`nums[x]` to any number from`1` to`3`.
12+
13+
A new array`res` is constructed using the following procedure:
14+
15+
1. Sort the numbers in each group independently.
16+
2. Append the elements of groups`1`,`2`, and`3` to`res`**in this order**.
17+
18+
Array`nums` is called a**beautiful array** if the constructed array`res` is sorted in**non-decreasing** order.
19+
20+
Return_the**minimum** number of operations to make_`nums`_a**beautiful array**_.
21+
22+
**Example 1:**
23+
24+
**Input:** nums =[2,1,3,2,1]
25+
26+
**Output:** 3
27+
28+
**Explanation:** It's optimal to perform three operations:
29+
1. change nums[0] to 1.
30+
2. change nums[2] to 1.
31+
3. change nums[3] to 1.
32+
33+
After performing the operations and sorting the numbers in each group, group 1 becomes equal to[0,1,2,3,4] and group 2 and group 3 become empty. Hence, res is equal to[0,1,2,3,4] which is sorted in non-decreasing order.
34+
35+
It can be proven that there is no valid sequence of less than three operations.
36+
37+
**Example 2:**
38+
39+
**Input:** nums =[1,3,2,1,3,3]
40+
41+
**Output:** 2
42+
43+
**Explanation:** It's optimal to perform two operations:
44+
1. change nums[1] to 1.
45+
2. change nums[2] to 1.
46+
47+
After performing the operations and sorting the numbers in each group, group 1 becomes equal to[0,1,2,3], group 2 becomes empty, and group 3 becomes equal to[4,5]. Hence, res is equal to[0,1,2,3,4,5] which is sorted in non-decreasing order.
48+
49+
It can be proven that there is no valid sequence of less than two operations.
50+
51+
**Example 3:**
52+
53+
**Input:** nums =[2,2,2,2,3,3]
54+
55+
**Output:** 0
56+
57+
**Explanation:** It's optimal to not perform operations.
58+
59+
After sorting the numbers in each group, group 1 becomes empty, group 2 becomes equal to[0,1,2,3] and group 3 becomes equal to[4,5]. Hence, res is equal to[0,1,2,3,4,5] which is sorted in non-decreasing order.
60+
61+
**Constraints:**
62+
63+
*`1 <= nums.length <= 100`
64+
*`1 <= nums[i] <= 3`
Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
packageg2801_2900.s2827_number_of_beautiful_integers_in_the_range;
2+
3+
// #Hard #Dynamic_Programming #Math #2023_12_11_Time_7_ms_(96.77%)_Space_43.4_MB_(67.74%)
4+
5+
importjava.util.Arrays;
6+
7+
@SuppressWarnings("java:S107")
8+
publicclassSolution {
9+
privateint[][][][][]dp;
10+
privateintmaxLength;
11+
12+
publicintnumberOfBeautifulIntegers(intlow,inthigh,intk) {
13+
Stringnum1 =String.valueOf(low);
14+
Stringnum2 =String.valueOf(high);
15+
maxLength =Math.max(num1.length(),num2.length());
16+
dp =newint[4][maxLength][maxLength][maxLength][k];
17+
for (int[][][][]a :dp) {
18+
for (int[][][]b :a) {
19+
for (int[][]c :b) {
20+
for (int[]d :c) {
21+
Arrays.fill(d, -1);
22+
}
23+
}
24+
}
25+
}
26+
returndp(num1,num2,0,3,0,0,0,0,k);
27+
}
28+
29+
privateintdp(
30+
Stringlow,Stringhigh,inti,intmode,intodd,inteven,intnum,intrem,intk) {
31+
if (i ==maxLength) {
32+
returnnum %k ==0 &&odd ==even ?1 :0;
33+
}
34+
if (dp[mode][i][odd][even][rem] != -1) {
35+
returndp[mode][i][odd][even][rem];
36+
}
37+
intres =0;
38+
booleanlowLimit =mode %2 ==1;
39+
booleanhighLimit =mode /2 ==1;
40+
intstart =0;
41+
intend =9;
42+
if (lowLimit) {
43+
start =digitAt(low,i);
44+
}
45+
if (highLimit) {
46+
end =digitAt(high,i);
47+
}
48+
for (intj =start;j <=end;j++) {
49+
intnewMode =0;
50+
if (j ==start &&lowLimit) {
51+
newMode +=1;
52+
}
53+
if (j ==end &&highLimit) {
54+
newMode +=2;
55+
}
56+
intnewEven =even;
57+
if (num !=0 ||j !=0) {
58+
newEven +=j %2 ==0 ?1 :0;
59+
}
60+
intnewOdd =odd + (j %2 ==1 ?1 :0);
61+
res +=
62+
dp(
63+
low,
64+
high,
65+
i +1,
66+
newMode,
67+
newOdd,
68+
newEven,
69+
num *10 +j,
70+
(num *10 +j) %k,
71+
k);
72+
}
73+
dp[mode][i][odd][even][rem] =res;
74+
returnres;
75+
}
76+
77+
privateintdigitAt(Stringnum,inti) {
78+
intindex =num.length() -maxLength +i;
79+
returnindex <0 ?0 :num.charAt(index) -'0';
80+
}
81+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
2827\. Number of Beautiful Integers in the Range
2+
3+
Hard
4+
5+
You are given positive integers`low`,`high`, and`k`.
6+
7+
A number is**beautiful** if it meets both of the following conditions:
8+
9+
* The count of even digits in the number is equal to the count of odd digits.
10+
* The number is divisible by`k`.
11+
12+
Return_the number of beautiful integers in the range_`[low, high]`.
13+
14+
**Example 1:**
15+
16+
**Input:** low = 10, high = 20, k = 3
17+
18+
**Output:** 2
19+
20+
**Explanation:** There are 2 beautiful integers in the given range:[12,18].
21+
- 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
22+
- 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3. Additionally we can see that:
23+
- 16 is not beautiful because it is not divisible by k = 3.
24+
- 15 is not beautiful because it does not contain equal counts even and odd digits. It can be shown that there are only 2 beautiful integers in the given range.
25+
26+
**Example 2:**
27+
28+
**Input:** low = 1, high = 10, k = 1
29+
30+
**Output:** 1
31+
32+
**Explanation:** There is 1 beautiful integer in the given range:[10].
33+
- 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1. It can be shown that there is only 1 beautiful integer in the given range.
34+
35+
**Example 3:**
36+
37+
**Input:** low = 5, high = 5, k = 2
38+
39+
**Output:** 0
40+
41+
**Explanation:** There are 0 beautiful integers in the given range.
42+
- 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.
43+
44+
**Constraints:**
45+
46+
* <code>0 < low <= high <= 10<sup>9</sup></code>
47+
*`0 < k <= 20`
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg2801_2900.s2828_check_if_a_string_is_an_acronym_of_words;
2+
3+
// #Easy #Array #String #2023_12_11_Time_1_ms_(100.00%)_Space_43.8_MB_(29.48%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publicbooleanisAcronym(List<String>words,Strings) {
9+
if (s.length() !=words.size()) {
10+
returnfalse;
11+
}
12+
for (inti =0;i <words.size();i++) {
13+
if (words.get(i).charAt(0) !=s.charAt(i)) {
14+
returnfalse;
15+
}
16+
}
17+
returntrue;
18+
}
19+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2828\. Check if a String Is an Acronym of Words
2+
3+
Easy
4+
5+
Given an array of strings`words` and a string`s`, determine if`s` is an**acronym** of words.
6+
7+
The string`s` is considered an acronym of`words` if it can be formed by concatenating the**first** character of each string in`words`**in order**. For example,`"ab"` can be formed from`["apple", "banana"]`, but it can't be formed from`["bear", "aardvark"]`.
8+
9+
Return`true`_if_`s`_is an acronym of_`words`_, and_`false`_otherwise._
10+
11+
**Example 1:**
12+
13+
**Input:** words =["alice","bob","charlie"], s = "abc"
14+
15+
**Output:** true
16+
17+
**Explanation:** The first character in the words "alice", "bob", and "charlie" are 'a', 'b', and 'c', respectively. Hence, s = "abc" is the acronym.
18+
19+
**Example 2:**
20+
21+
**Input:** words =["an","apple"], s = "a"
22+
23+
**Output:** false
24+
25+
**Explanation:** The first character in the words "an" and "apple" are 'a' and 'a', respectively. The acronym formed by concatenating these characters is "aa". Hence, s = "a" is not the acronym.
26+
27+
**Example 3:**
28+
29+
**Input:** words =["never","gonna","give","up","on","you"], s = "ngguoy"
30+
31+
**Output:** true
32+
33+
**Explanation:** By concatenating the first character of the words in the array, we get the string "ngguoy". Hence, s = "ngguoy" is the acronym.
34+
35+
**Constraints:**
36+
37+
*`1 <= words.length <= 100`
38+
*`1 <= words[i].length <= 10`
39+
*`1 <= s.length <= 100`
40+
*`words[i]` and`s` consist of lowercase English letters.
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg2801_2900.s2829_determine_the_minimum_sum_of_a_k_avoiding_array;
2+
3+
// #Medium #Math #Greedy #2023_12_11_Time_1_ms_(100.00%)_Space_40.6_MB_(77.32%)
4+
5+
publicclassSolution {
6+
publicintminimumSum(intn,intk) {
7+
int[]arr =newint[n];
8+
inta =k /2;
9+
intsum =0;
10+
if (a >n) {
11+
for (inti =0;i <n;i++) {
12+
arr[i] =i +1;
13+
sum +=arr[i];
14+
}
15+
}else {
16+
for (inti =0;i <a;i++) {
17+
arr[i] =i +1;
18+
sum +=arr[i];
19+
}
20+
for (intj =a;j <n;j++) {
21+
arr[j] =k++;
22+
sum +=arr[j];
23+
}
24+
}
25+
returnsum;
26+
}
27+
}

0 commit comments

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