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

Commit96d7792

Browse files
authored
Added tasks 2778-2784
1 parent31c4cde commit96d7792

File tree

15 files changed

+519
-0
lines changed

15 files changed

+519
-0
lines changed
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
packageg2701_2800.s2778_sum_of_squares_of_special_elements;
2+
3+
// #Easy #Array #Simulation #2023_09_21_Time_1_ms_(100.00%)_Space_42.8_MB_(94.54%)
4+
5+
publicclassSolution {
6+
publicintsumOfSquares(int[]nums) {
7+
intsum =0;
8+
for (inti =0;i <nums.length;i++) {
9+
if (nums.length % (i +1) ==0) {
10+
sum +=nums[i] *nums[i];
11+
}
12+
}
13+
returnsum;
14+
}
15+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2778\. Sum of Squares of Special Elements
2+
3+
Easy
4+
5+
You are given a**1-indexed** integer array`nums` of length`n`.
6+
7+
An element`nums[i]` of`nums` is called**special** if`i` divides`n`, i.e.`n % i == 0`.
8+
9+
Return_the**sum of the squares** of all**special** elements of_`nums`.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[1,2,3,4]
14+
15+
**Output:** 21
16+
17+
**Explanation:**
18+
19+
There are exactly 3 special elements in nums: nums[1] since 1 divides 4, nums[2] since 2 divides 4, and nums[4] since 4 divides 4.
20+
21+
Hence, the sum of the squares of all special elements of nums is nums[1]\* nums[1] + nums[2]\* nums[2] + nums[4]\* nums[4] = 1\* 1 + 2\* 2 + 4\* 4 = 21.
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[2,7,1,19,18,3]
26+
27+
**Output:** 63
28+
29+
**Explanation:**
30+
31+
There are exactly 4 special elements in nums: nums[1] since 1 divides 6, nums[2] since 2 divides 6, nums[3] since 3 divides 6, and nums[6] since 6 divides 6.
32+
33+
Hence, the sum of the squares of all special elements of nums is nums[1]\* nums[1] + nums[2]\* nums[2] + nums[3]\* nums[3] + nums[6]\* nums[6] = 2\* 2 + 7\* 7 + 1\* 1 + 3\* 3 = 63.
34+
35+
**Constraints:**
36+
37+
*`1 <= nums.length == n <= 50`
38+
*`1 <= nums[i] <= 50`
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
packageg2701_2800.s2779_maximum_beauty_of_an_array_after_applying_operation;
2+
3+
// #Medium #Array #Sorting #Binary_Search #Sliding_Window
4+
// #2023_09_21_Time_37_ms_(93.81%)_Space_58.5_MB_(50.34%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintmaximumBeauty(int[]nums,intk) {
10+
Arrays.sort(nums);
11+
inti =0;
12+
intn =nums.length;
13+
intj =0;
14+
while (j <n) {
15+
if (nums[j] -nums[i] >k *2) {
16+
i++;
17+
}
18+
j++;
19+
}
20+
returnj -i;
21+
}
22+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
2779\. Maximum Beauty of an Array After Applying Operation
2+
3+
Medium
4+
5+
You are given a**0-indexed** array`nums` and a**non-negative** integer`k`.
6+
7+
In one operation, you can do the following:
8+
9+
* Choose an index`i` that**hasn't been chosen before** from the range`[0, nums.length - 1]`.
10+
* Replace`nums[i]` with any integer from the range`[nums[i] - k, nums[i] + k]`.
11+
12+
The**beauty** of the array is the length of the longest subsequence consisting of equal elements.
13+
14+
Return_the**maximum** possible beauty of the array_`nums`_after applying the operation any number of times._
15+
16+
**Note** that you can apply the operation to each index**only once**.
17+
18+
A**subsequence** of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.
19+
20+
**Example 1:**
21+
22+
**Input:** nums =[4,6,1,2], k = 2
23+
24+
**Output:** 3
25+
26+
**Explanation:**
27+
28+
In this example, we apply the following operations:
29+
30+
- Choose index 1, replace it with 4 (from range[4,8]), nums =[4,4,1,2].
31+
32+
- Choose index 3, replace it with 4 (from range[0,4]), nums =[4,4,1,4].
33+
34+
After the applied operations, the beauty of the array nums is 3 (subsequence consisting of indices 0, 1, and 3).
35+
36+
It can be proven that 3 is the maximum possible length we can achieve.
37+
38+
**Example 2:**
39+
40+
**Input:** nums =[1,1,1,1], k = 10
41+
42+
**Output:** 4
43+
44+
**Explanation:**
45+
46+
In this example we don't have to apply any operations.
47+
48+
The beauty of the array nums is 4 (whole array).
49+
50+
**Constraints:**
51+
52+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
53+
* <code>0 <= nums[i], k <= 10<sup>5</sup></code>
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packageg2701_2800.s2780_minimum_index_of_a_valid_split;
2+
3+
// #Medium #Array #Hash_Table #Sorting #2023_09_21_Time_5_ms_(99.77%)_Space_61.4_MB_(8.22%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publicintminimumIndex(List<Integer>nums) {
9+
intn =nums.size();
10+
Integer[]numbers =newInteger[n];
11+
nums.toArray(numbers);
12+
intmajority = -1;
13+
intcount =0;
14+
for (intx :numbers) {
15+
if (count ==0) {
16+
majority =x;
17+
count =1;
18+
}elseif (x ==majority) {
19+
count++;
20+
}else {
21+
count--;
22+
}
23+
}
24+
intmajorityCount =0;
25+
for (intx :numbers) {
26+
if (x ==majority) {
27+
++majorityCount;
28+
}
29+
}
30+
intcount1 =0;
31+
intcount2 =majorityCount;
32+
intleft =0;
33+
intright =n;
34+
inti = -1;
35+
while (i <n -1) {
36+
++left;
37+
--right;
38+
i++;
39+
if (numbers[i] ==majority) {
40+
++count1;
41+
--count2;
42+
}
43+
if (count1 *2 >left &&count2 *2 >right) {
44+
returni;
45+
}
46+
}
47+
return -1;
48+
}
49+
}
Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
2780\. Minimum Index of a Valid Split
2+
3+
Medium
4+
5+
An element`x` of an integer array`arr` of length`m` is**dominant** if`freq(x) * 2 > m`, where`freq(x)` is the number of occurrences of`x` in`arr`. Note that this definition implies that`arr` can have**at most one** dominant element.
6+
7+
You are given a**0-indexed** integer array`nums` of length`n` with one dominant element.
8+
9+
You can split`nums` at an index`i` into two arrays`nums[0, ..., i]` and`nums[i + 1, ..., n - 1]`, but the split is only**valid** if:
10+
11+
*`0 <= i < n - 1`
12+
*`nums[0, ..., i]`, and`nums[i + 1, ..., n - 1]` have the same dominant element.
13+
14+
Here,`nums[i, ..., j]` denotes the subarray of`nums` starting at index`i` and ending at index`j`, both ends being inclusive. Particularly, if`j < i` then`nums[i, ..., j]` denotes an empty subarray.
15+
16+
Return_the**minimum** index of a**valid split**_. If no valid split exists, return`-1`.
17+
18+
**Example 1:**
19+
20+
**Input:** nums =[1,2,2,2]
21+
22+
**Output:** 2
23+
24+
**Explanation:**
25+
26+
We can split the array at index 2 to obtain arrays[1,2,2] and[2].
27+
28+
In array[1,2,2], element 2 is dominant since it occurs twice in the array and 2\* 2 > 3.
29+
30+
In array[2], element 2 is dominant since it occurs once in the array and 1\* 2 > 1.
31+
32+
Both[1,2,2] and[2] have the same dominant element as nums, so this is a valid split.
33+
34+
It can be shown that index 2 is the minimum index of a valid split.
35+
36+
**Example 2:**
37+
38+
**Input:** nums =[2,1,3,1,1,1,7,1,2,1]
39+
40+
**Output:** 4
41+
42+
**Explanation:**
43+
44+
We can split the array at index 4 to obtain arrays[2,1,3,1,1] and[1,7,1,2,1].
45+
46+
In array[2,1,3,1,1], element 1 is dominant since it occurs thrice in the array and 3\* 2 > 5.
47+
48+
In array[1,7,1,2,1], element 1 is dominant since it occurs thrice in the array and 3\* 2 > 5.
49+
50+
Both[2,1,3,1,1] and[1,7,1,2,1] have the same dominant element as nums, so this is a valid split.
51+
52+
It can be shown that index 4 is the minimum index of a valid split.
53+
54+
**Example 3:**
55+
56+
**Input:** nums =[3,3,3,3,7,2,2]
57+
58+
**Output:** -1
59+
60+
**Explanation:**
61+
62+
It can be shown that there is no valid split.
63+
64+
**Constraints:**
65+
66+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
67+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
68+
*`nums` has exactly one dominant element.
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packageg2701_2800.s2781_length_of_the_longest_valid_substring;
2+
3+
// #Hard #Array #String #Hash_Table #Sliding_Window
4+
// #2023_09_21_Time_137_ms_(75.23%)_Space_60.4_MB_(65.51%)
5+
6+
importjava.util.HashSet;
7+
importjava.util.List;
8+
importjava.util.Set;
9+
10+
publicclassSolution {
11+
publicintlongestValidSubstring(Stringword,List<String>forbidden) {
12+
Set<String>set =newHashSet<>();
13+
for (Strings :forbidden) {
14+
set.add(s);
15+
}
16+
intn =word.length();
17+
intans =0;
18+
inti =0;
19+
intj =0;
20+
while (j <n) {
21+
intk =j;
22+
while (k >j -10 &&k >=i) {
23+
if (set.contains(word.substring(k,j +1))) {
24+
i =k +1;
25+
break;
26+
}
27+
k--;
28+
}
29+
ans =Math.max(j -i +1,ans);
30+
j++;
31+
}
32+
returnans;
33+
}
34+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
2781\. Length of the Longest Valid Substring
2+
3+
Hard
4+
5+
You are given a string`word` and an array of strings`forbidden`.
6+
7+
A string is called**valid** if none of its substrings are present in`forbidden`.
8+
9+
Return_the length of the**longest valid substring** of the string_`word`.
10+
11+
A**substring** is a contiguous sequence of characters in a string, possibly empty.
12+
13+
**Example 1:**
14+
15+
**Input:** word = "cbaaaabc", forbidden =["aaa","cb"]
16+
17+
**Output:** 4
18+
19+
**Explanation:**
20+
21+
There are 9 valid substrings in word: "c", "b", "a", "ba", "aa", "bc", "baa", "aab", "ab", "abc"and "aabc". The length of the longest valid substring is 4.
22+
23+
It can be shown that all other substrings contain either "aaa" or "cb" as a substring.
24+
25+
**Example 2:**
26+
27+
**Input:** word = "leetcode", forbidden =["de","le","e"]
28+
29+
**Output:** 4
30+
31+
**Explanation:**
32+
33+
There are 11 valid substrings in word: "l", "t", "c", "o", "d", "tc", "co", "od", "tco", "cod", and "tcod". The length of the longest valid substring is 4.
34+
35+
It can be shown that all other substrings contain either "de", "le", or "e" as a substring.
36+
37+
**Constraints:**
38+
39+
* <code>1 <= word.length <= 10<sup>5</sup></code>
40+
*`word` consists only of lowercase English letters.
41+
* <code>1 <= forbidden.length <= 10<sup>5</sup></code>
42+
*`1 <= forbidden[i].length <= 10`
43+
*`forbidden[i]` consists only of lowercase English letters.
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2701_2800.s2784_check_if_array_is_good;
2+
3+
// #Easy #Array #Hash_Table #Sorting #2023_09_21_Time_1_ms_(99.49%)_Space_41.2_MB_(98.36%)
4+
5+
publicclassSolution {
6+
publicbooleanisGood(int[]nums) {
7+
intmax =Integer.MIN_VALUE;
8+
intsum =0;
9+
for (inti :nums) {
10+
if (i >max) {
11+
max =i;
12+
}
13+
sum +=i;
14+
}
15+
if (max !=nums.length -1) {
16+
returnfalse;
17+
}
18+
intnewSum =max * (max +1) /2 +max;
19+
if (sum !=newSum) {
20+
returnfalse;
21+
}
22+
intcount =0;
23+
for (inti :nums) {
24+
if (i ==max) {
25+
count++;
26+
}
27+
}
28+
returncount ==2;
29+
}
30+
}

0 commit comments

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