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

Commit777eb7b

Browse files
authored
Added tasks 2517, 2518, 2520, 2521, 2522
1 parentb9ca7e7 commit777eb7b

File tree

16 files changed

+474
-0
lines changed

16 files changed

+474
-0
lines changed

‎README.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1848,6 +1848,11 @@ implementation 'com.github.javadev:leetcode-in-java:1.20'
18481848

18491849
| # | Title | Difficulty | Tag | Time, ms | Time, %
18501850
|------|----------------|-------------|-------------|----------|---------
1851+
| 2522 |[Partition String Into Substrings With Values at Most K](src/main/java/g2501_2600/s2522_partition_string_into_substrings_with_values_at_most_k/Solution.java)| Medium | String, Dynamic_Programming, Greedy | 6 | 84.66
1852+
| 2521 |[Distinct Prime Factors of Product of Array](src/main/java/g2501_2600/s2521_distinct_prime_factors_of_product_of_array/Solution.java)| Medium | Array, Hash_Table, Math, Number_Theory | 2 | 100.00
1853+
| 2520 |[Count the Digits That Divide a Number](src/main/java/g2501_2600/s2520_count_the_digits_that_divide_a_number/Solution.java)| Easy | Math | 0 | 100.00
1854+
| 2518 |[Number of Great Partitions](src/main/java/g2501_2600/s2518_number_of_great_partitions/Solution.java)| Hard | Array, Dynamic_Programming | 4 | 100.00
1855+
| 2517 |[Maximum Tastiness of Candy Basket](src/main/java/g2501_2600/s2517_maximum_tastiness_of_candy_basket/Solution.java)| Medium | Array, Sorting, Binary_Search | 38 | 100.00
18511856
| 2516 |[Take K of Each Character From Left and Right](src/main/java/g2501_2600/s2516_take_k_of_each_character_from_left_and_right/Solution.java)| Medium | String, Hash_Table, Sliding_Window | 6 | 94.24
18521857
| 2515 |[Shortest Distance to Target String in a Circular Array](src/main/java/g2501_2600/s2515_shortest_distance_to_target_string_in_a_circular_array/Solution.java)| Easy | Array, String | 1 | 62.21
18531858
| 2514 |[Count Anagrams](src/main/java/g2501_2600/s2514_count_anagrams/Solution.java)| Hard | String, Hash_Table, Math, Counting, Combinatorics | 22 | 100.00
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg2501_2600.s2517_maximum_tastiness_of_candy_basket;
2+
3+
// #Medium #Array #Sorting #Binary_Search #2023_04_18_Time_38_ms_(100.00%)_Space_51.8_MB_(53.92%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintmaximumTastiness(int[]price,intk) {
9+
Arrays.sort(price);
10+
intn =price.length;
11+
intleft =1;
12+
intright = (price[n -1] -price[0]) / (k -1) +1;
13+
while (left <right) {
14+
intmid =left + (right -left) /2;
15+
if (check(mid,price,k)) {
16+
left =mid +1;
17+
}else {
18+
right =mid;
19+
}
20+
}
21+
returnleft -1;
22+
}
23+
24+
privatebooleancheck(inttarget,int[]price,intk) {
25+
intcount =1;
26+
intx0 =price[0];
27+
for (intx :price) {
28+
if (x >=x0 +target) {
29+
count++;
30+
if (count >=k) {
31+
returntrue;
32+
}
33+
x0 =x;
34+
}
35+
}
36+
returnfalse;
37+
}
38+
}
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
2517\. Maximum Tastiness of Candy Basket
2+
3+
Medium
4+
5+
You are given an array of positive integers`price` where`price[i]` denotes the price of the <code>i<sup>th</sup></code> candy and a positive integer`k`.
6+
7+
The store sells baskets of`k`**distinct** candies. The**tastiness** of a candy basket is the smallest absolute difference of the**prices** of any two candies in the basket.
8+
9+
Return_the**maximum** tastiness of a candy basket._
10+
11+
**Example 1:**
12+
13+
**Input:** price =[13,5,1,8,21,2], k = 3
14+
15+
**Output:** 8
16+
17+
**Explanation:** Choose the candies with the prices[13,5,21].
18+
19+
The tastiness of the candy basket is: min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8.
20+
21+
It can be proven that 8 is the maximum tastiness that can be achieved.
22+
23+
**Example 2:**
24+
25+
**Input:** price =[1,3,1], k = 2
26+
27+
**Output:** 2
28+
29+
**Explanation:** Choose the candies with the prices[1,3].
30+
31+
The tastiness of the candy basket is: min(|1 - 3|) = min(2) = 2.
32+
33+
It can be proven that 2 is the maximum tastiness that can be achieved.
34+
35+
**Example 3:**
36+
37+
**Input:** price =[7,7,7,7], k = 2
38+
39+
**Output:** 0
40+
41+
**Explanation:** Choosing any two distinct candies from the candies we have will result in a tastiness of 0.
42+
43+
**Constraints:**
44+
45+
* <code>2 <= k <= price.length <= 10<sup>5</sup></code>
46+
* <code>1 <= price[i] <= 10<sup>9</sup></code>
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
packageg2501_2600.s2518_number_of_great_partitions;
2+
3+
// #Hard #Array #Dynamic_Programming #2023_04_18_Time_4_ms_(100.00%)_Space_41.4_MB_(98.28%)
4+
5+
publicclassSolution {
6+
privatestaticfinalintMOD =1000000007;
7+
8+
publicintcountPartitions(int[]nums,intk) {
9+
// edge cases
10+
intn =nums.length;
11+
longsum =0;
12+
for (intnum :nums) {
13+
sum +=num;
14+
}
15+
if (sum <2L *k) {
16+
return0;
17+
}
18+
// normal cases
19+
int[]dp =newint[k];
20+
dp[0] =1;
21+
for (intnum :nums) {
22+
for (inti =k -1;i >=num;i--) {
23+
dp[i] = (dp[i] +dp[i -num]) %MOD;
24+
}
25+
}
26+
intsmaller =0;
27+
for (inti =0;i <k;i++) {
28+
smaller = (smaller +dp[i]) %MOD;
29+
}
30+
return (pow(2,n) - (smaller *2) %MOD +MOD) %MOD;
31+
}
32+
33+
privateintpow(longnum,intpow) {
34+
longresult =1;
35+
while (pow !=0) {
36+
if (pow %2 ==1) {
37+
result = (result *num) %MOD;
38+
}
39+
pow /=2;
40+
num = (num *num) %MOD;
41+
}
42+
return (int)result;
43+
}
44+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2518\. Number of Great Partitions
2+
3+
Hard
4+
5+
You are given an array`nums` consisting of**positive** integers and an integer`k`.
6+
7+
**Partition** the array into two ordered**groups** such that each element is in exactly**one** group. A partition is called great if the**sum** of elements of each group is greater than or equal to`k`.
8+
9+
Return_the number of**distinct** great partitions_. Since the answer may be too large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
10+
11+
Two partitions are considered distinct if some element`nums[i]` is in different groups in the two partitions.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[1,2,3,4], k = 4
16+
17+
**Output:** 6
18+
19+
**Explanation:** The great partitions are: ([1,2,3],[4]), ([1,3],[2,4]), ([1,4],[2,3]), ([2,3],[1,4]), ([2,4],[1,3]) and ([4],[1,2,3]).
20+
21+
**Example 2:**
22+
23+
**Input:** nums =[3,3,3], k = 4
24+
25+
**Output:** 0
26+
27+
**Explanation:** There are no great partitions for this array.
28+
29+
**Example 3:**
30+
31+
**Input:** nums =[6,6], k = 2
32+
33+
**Output:** 2
34+
35+
**Explanation:** We can either put nums[0] in the first partition or in the second partition. The great partitions will be ([6],[6]) and ([6],[6]).
36+
37+
**Constraints:**
38+
39+
*`1 <= nums.length, k <= 1000`
40+
* <code>1 <= 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+
packageg2501_2600.s2520_count_the_digits_that_divide_a_number;
2+
3+
// #Easy #Math #2023_04_18_Time_0_ms_(100.00%)_Space_39.3_MB_(62.57%)
4+
5+
publicclassSolution {
6+
publicintcountDigits(intnum) {
7+
inta =num;
8+
intcount =0;
9+
while (a >0) {
10+
intr =a %10;
11+
if (r !=0 &&num %r ==0) {
12+
count++;
13+
}
14+
a /=10;
15+
}
16+
returncount;
17+
}
18+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2520\. Count the Digits That Divide a Number
2+
3+
Easy
4+
5+
Given an integer`num`, return_the number of digits in`num` that divide_`num`.
6+
7+
An integer`val` divides`nums` if`nums % val == 0`.
8+
9+
**Example 1:**
10+
11+
**Input:** num = 7
12+
13+
**Output:** 1
14+
15+
**Explanation:** 7 divides itself, hence the answer is 1.
16+
17+
**Example 2:**
18+
19+
**Input:** num = 121
20+
21+
**Output:** 2
22+
23+
**Explanation:** 121 is divisible by 1, but not 2. Since 1 occurs twice as a digit, we return 2.
24+
25+
**Example 3:**
26+
27+
**Input:** num = 1248
28+
29+
**Output:** 4
30+
31+
**Explanation:** 1248 is divisible by all of its digits, hence the answer is 4.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= num <= 10<sup>9</sup></code>
36+
*`num` does not contain`0` as one of its digits.
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
packageg2501_2600.s2521_distinct_prime_factors_of_product_of_array;
2+
3+
// #Medium #Array #Hash_Table #Math #Number_Theory
4+
// #2023_04_18_Time_2_ms_(100.00%)_Space_44.1_MB_(18.47%)
5+
6+
@SuppressWarnings("java:S1119")
7+
publicclassSolution {
8+
staticfinalint[]PRIMES =newint[] {2,3,5,7,11,13,17,19,23,29,31};
9+
10+
publicintdistinctPrimeFactors(int[]nums) {
11+
finalboolean[]hasPrime =newboolean[PRIMES.length];
12+
finalboolean[]nr =newboolean[1001];
13+
intr =0;
14+
a:
15+
for (intn :nums) {
16+
if (nr[n]) {
17+
continue;
18+
}
19+
nr[n] =true;
20+
for (inti =0;i <PRIMES.length &&n >1;i++) {
21+
finalintprime =PRIMES[i];
22+
while (n %prime ==0) {
23+
n /=prime;
24+
hasPrime[i] =true;
25+
if (nr[n]) {
26+
continuea;
27+
}
28+
nr[n] =true;
29+
}
30+
}
31+
if (n >1) {
32+
r++;
33+
}
34+
}
35+
for (booleanp :hasPrime) {
36+
if (p) {
37+
r++;
38+
}
39+
}
40+
returnr;
41+
}
42+
}
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
2521\. Distinct Prime Factors of Product of Array
2+
3+
Medium
4+
5+
Given an array of positive integers`nums`, return_the number of**distinct prime factors** in the product of the elements of_`nums`.
6+
7+
**Note** that:
8+
9+
* A number greater than`1` is called**prime** if it is divisible by only`1` and itself.
10+
* An integer`val1` is a factor of another integer`val2` if`val2 / val1` is an integer.
11+
12+
**Example 1:**
13+
14+
**Input:** nums =[2,4,3,7,10,6]
15+
16+
**Output:** 4
17+
18+
**Explanation:** The product of all the elements in nums is: 2\* 4\* 3\* 7\* 10\* 6 = 10080 = 2<sup>5</sup>\* 3<sup>2</sup>\* 5\* 7.
19+
20+
There are 4 distinct prime factors so we return 4.
21+
22+
**Example 2:**
23+
24+
**Input:** nums =[2,4,8,16]
25+
26+
**Output:** 1
27+
28+
**Explanation:** The product of all the elements in nums is: 2\* 4\* 8\* 16 = 1024 = 2<sup>10</sup>.
29+
30+
There is 1 distinct prime factor so we return 1.
31+
32+
**Constraints:**
33+
34+
* <code>1 <= nums.length <= 10<sup>4</sup></code>
35+
*`2 <= nums[i] <= 1000`
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2501_2600.s2522_partition_string_into_substrings_with_values_at_most_k;
2+
3+
// #Medium #String #Dynamic_Programming #Greedy #2023_04_18_Time_6_ms_(84.66%)_Space_43_MB_(76.70%)
4+
5+
publicclassSolution {
6+
publicintminimumPartition(Strings,intk) {
7+
if (k ==9) {
8+
returns.length();
9+
}
10+
intpartitions =1;
11+
longpartitionValue =0;
12+
longdigit;
13+
for (inti =0;i <s.length();i++) {
14+
digit = (long)s.charAt(i) -'0';
15+
if (digit >k) {
16+
return -1;
17+
}
18+
partitionValue =partitionValue *10 +digit;
19+
if (partitionValue >k) {
20+
partitionValue =digit;
21+
partitions++;
22+
}
23+
}
24+
returnpartitions;
25+
}
26+
}

0 commit comments

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