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

Commitcaba152

Browse files
authored
Added tasks 2790-2800
1 parent36317d8 commitcaba152

File tree

15 files changed

+542
-0
lines changed

15 files changed

+542
-0
lines changed
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2701_2800.s2790_maximum_number_of_groups_with_increasing_length;
2+
3+
// #Hard #Array #Math #Sorting #Greedy #Binary_Search
4+
// #2023_09_14_Time_14_ms_(99.59%)_Space_55.6_MB_(52.28%)
5+
6+
importjava.util.Arrays;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
publicintmaxIncreasingGroups(List<Integer>usageLimits) {
11+
intn =usageLimits.size();
12+
longtotal =0;
13+
longk =0;
14+
int[]count =newint[n +1];
15+
Arrays.fill(count,0);
16+
for (inta :usageLimits) {
17+
intlocalA = (int)Math.min(a, (double)n);
18+
count[localA]++;
19+
}
20+
for (inti =0;i <=n;i++) {
21+
for (intj =0;j <count[i];j++) {
22+
total +=i;
23+
if (total >= (k +1) * (k +2) /2) {
24+
k++;
25+
}
26+
}
27+
}
28+
return (int)k;
29+
}
30+
}
Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
2790\. Maximum Number of Groups With Increasing Length
2+
3+
Hard
4+
5+
You are given a**0-indexed** array`usageLimits` of length`n`.
6+
7+
Your task is to create**groups** using numbers from`0` to`n - 1`, ensuring that each number,`i`, is used no more than`usageLimits[i]` times in total**across all groups**. You must also satisfy the following conditions:
8+
9+
* Each group must consist of**distinct** numbers, meaning that no duplicate numbers are allowed within a single group.
10+
* Each group (except the first one) must have a length**strictly greater** than the previous group.
11+
12+
Return_an integer denoting the**maximum** number of groups you can create while satisfying these conditions._
13+
14+
**Example 1:**
15+
16+
**Input:**`usageLimits` =[1,2,5]
17+
18+
**Output:** 3
19+
20+
**Explanation:**
21+
22+
In this example, we can use 0 at most once, 1 at most twice, and 2 at most five times.
23+
24+
One way of creating the maximum number of groups while satisfying the conditions is:
25+
26+
Group 1 contains the number[2].
27+
28+
Group 2 contains the numbers[1,2].
29+
30+
Group 3 contains the numbers[0,1,2].
31+
32+
It can be shown that the maximum number of groups is 3.
33+
34+
So, the output is 3.
35+
36+
**Example 2:**
37+
38+
**Input:**`usageLimits` =[2,1,2]
39+
40+
**Output:** 2
41+
42+
**Explanation:**
43+
44+
In this example, we can use 0 at most twice, 1 at most once, and 2 at most twice.
45+
46+
One way of creating the maximum number of groups while satisfying the conditions is:
47+
48+
Group 1 contains the number[0].
49+
50+
Group 2 contains the numbers[1,2].
51+
52+
It can be shown that the maximum number of groups is 2.
53+
54+
So, the output is 2.
55+
56+
**Example 3:**
57+
58+
**Input:**`usageLimits` =[1,1]
59+
60+
**Output:** 1
61+
62+
**Explanation:**
63+
64+
In this example, we can use both 0 and 1 at most once.
65+
66+
One way of creating the maximum number of groups while satisfying the conditions is:
67+
68+
Group 1 contains the number[0].
69+
70+
It can be shown that the maximum number of groups is 1.
71+
72+
So, the output is 1.
73+
74+
**Constraints:**
75+
76+
* <code>1 <= usageLimits.length <= 10<sup>5</sup></code>
77+
* <code>1 <= usageLimits[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+
packageg2701_2800.s2791_count_paths_that_can_form_a_palindrome_in_a_tree;
2+
3+
// #Hard #Dynamic_Programming #Depth_First_Search #Tree #Bit_Manipulation #Bitmask
4+
// #2023_09_14_Time_97_ms_(99.78%)_Space_59_MB_(81.43%)
5+
6+
importjava.util.Arrays;
7+
importjava.util.HashMap;
8+
importjava.util.List;
9+
importjava.util.Map;
10+
11+
publicclassSolution {
12+
privateintgetMap(List<Integer>parent,Strings,int[]dp,intidx) {
13+
if (dp[idx] <0) {
14+
dp[idx] =0;
15+
dp[idx] =getMap(parent,s,dp,parent.get(idx)) ^ (1 << (s.charAt(idx) -'a'));
16+
}
17+
returndp[idx];
18+
}
19+
20+
publiclongcountPalindromePaths(List<Integer>parent,Strings) {
21+
intn =parent.size();
22+
int[]dp =newint[n];
23+
longans =0;
24+
Map<Integer,Integer>mapCount =newHashMap<>();
25+
Arrays.fill(dp, -1);
26+
dp[0] =0;
27+
for (inti =0;i <n;i++) {
28+
intcurrMap =getMap(parent,s,dp,i);
29+
intevenCount =mapCount.getOrDefault(currMap,0);
30+
mapCount.put(currMap,evenCount +1);
31+
}
32+
for (Map.Entry<Integer,Integer>entry :mapCount.entrySet()) {
33+
intvalue =entry.getValue();
34+
ans += (long)value * (value -1) /2;
35+
for (inti =0;i <=25;i++) {
36+
intbase =1 <<i;
37+
if ((entry.getKey() &base) >0 &&mapCount.containsKey(entry.getKey() ^base)) {
38+
ans += (long)value *mapCount.get(entry.getKey() ^base);
39+
}
40+
}
41+
}
42+
returnans;
43+
}
44+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
2791\. Count Paths That Can Form a Palindrome in a Tree
2+
3+
Hard
4+
5+
You are given a**tree** (i.e. a connected, undirected graph that has no cycles)**rooted** at node`0` consisting of`n` nodes numbered from`0` to`n - 1`. The tree is represented by a**0-indexed** array`parent` of size`n`, where`parent[i]` is the parent of node`i`. Since node`0` is the root,`parent[0] == -1`.
6+
7+
You are also given a string`s` of length`n`, where`s[i]` is the character assigned to the edge between`i` and`parent[i]`.`s[0]` can be ignored.
8+
9+
Return_the number of pairs of nodes_`(u, v)`_such that_`u < v`_and the characters assigned to edges on the path from_`u`_to_`v`_can be**rearranged** to form a**palindrome**_.
10+
11+
A string is a**palindrome** when it reads the same backwards as forwards.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2023/07/15/treedrawio-8drawio.png)
16+
17+
**Input:** parent =[-1,0,0,1,1,2], s = "acaabc"
18+
19+
**Output:** 8
20+
21+
**Explanation:**
22+
23+
The valid pairs are:
24+
25+
- All the pairs (0,1), (0,2), (1,3), (1,4) and (2,5) result in one character which is always a palindrome.
26+
27+
- The pair (2,3) result in the string "aca" which is a palindrome.
28+
29+
- The pair (1,5) result in the string "cac" which is a palindrome.
30+
31+
- The pair (3,5) result in the string "acac" which can be rearranged into the palindrome "acca".
32+
33+
**Example 2:**
34+
35+
**Input:** parent =[-1,0,0,0,0], s = "aaaaa"
36+
37+
**Output:** 10
38+
39+
**Explanation:** Any pair of nodes (u,v) where u < v is valid.
40+
41+
**Constraints:**
42+
43+
*`n == parent.length == s.length`
44+
* <code>1 <= n <= 10<sup>5</sup></code>
45+
*`0 <= parent[i] <= n - 1` for all`i >= 1`
46+
*`parent[0] == -1`
47+
*`parent` represents a valid tree.
48+
*`s` consists of only lowercase English letters.
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
packageg2701_2800.s2798_number_of_employees_who_met_the_target;
2+
3+
// #Easy #Array #Enumeration #2023_09_14_Time_0_ms_(100.00%)_Space_40.6_MB_(98.10%)
4+
5+
publicclassSolution {
6+
publicintnumberOfEmployeesWhoMetTarget(int[]hours,inttarget) {
7+
intcount =0;
8+
for (inti :hours) {
9+
if (i >=target) {
10+
count++;
11+
}
12+
}
13+
returncount;
14+
}
15+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
2798\. Number of Employees Who Met the Target
2+
3+
Easy
4+
5+
There are`n` employees in a company, numbered from`0` to`n - 1`. Each employee`i` has worked for`hours[i]` hours in the company.
6+
7+
The company requires each employee to work for**at least**`target` hours.
8+
9+
You are given a**0-indexed** array of non-negative integers`hours` of length`n` and a non-negative integer`target`.
10+
11+
Return_the integer denoting the number of employees who worked at least_`target`_hours_.
12+
13+
**Example 1:**
14+
15+
**Input:** hours =[0,1,2,3,4], target = 2
16+
17+
**Output:** 3
18+
19+
**Explanation:**
20+
21+
The company wants each employee to work for at least 2 hours.
22+
23+
- Employee 0 worked for 0 hours and didn't meet the target.
24+
25+
- Employee 1 worked for 1 hours and didn't meet the target.
26+
27+
- Employee 2 worked for 2 hours and met the target.
28+
29+
- Employee 3 worked for 3 hours and met the target.
30+
31+
- Employee 4 worked for 4 hours and met the target.
32+
33+
There are 3 employees who met the target.
34+
35+
**Example 2:**
36+
37+
**Input:** hours =[5,1,4,2,2], target = 6
38+
39+
**Output:** 0
40+
41+
**Explanation:**
42+
43+
The company wants each employee to work for at least 6 hours.
44+
45+
There are 0 employees who met the target.
46+
47+
**Constraints:**
48+
49+
*`1 <= n == hours.length <= 50`
50+
* <code>0 <= hours[i], target <= 10<sup>5</sup></code>
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
packageg2701_2800.s2799_count_complete_subarrays_in_an_array;
2+
3+
// #Medium #Array #Hash_Table #Sliding_Window #2023_09_14_Time_3_ms_(99.82%)_Space_44_MB_(32.27%)
4+
5+
publicclassSolution {
6+
publicintcountCompleteSubarrays(int[]nums) {
7+
intn =nums.length;
8+
int[]map =newint[2001];
9+
intlast =0;
10+
for (inti =0;i <n; ++i) {
11+
map[nums[i]]++;
12+
if (map[nums[i]] ==1) {
13+
last =i;
14+
}
15+
}
16+
map =newint[2001];
17+
for (inti =0;i <=last; ++i) {
18+
map[nums[i]]++;
19+
}
20+
intans =0;
21+
for (inti =0;i <n; ++i) {
22+
ans +=n -last;
23+
map[nums[i]]--;
24+
if (map[nums[i]] ==0) {
25+
intpossLast =0;
26+
for (intj =last +1;j <n &&map[nums[i]] ==0; ++j) {
27+
map[nums[j]]++;
28+
possLast =j;
29+
}
30+
if (map[nums[i]] >0) {
31+
last =possLast;
32+
}else {
33+
break;
34+
}
35+
}
36+
}
37+
returnans;
38+
}
39+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
2799\. Count Complete Subarrays in an Array
2+
3+
Medium
4+
5+
You are given an array`nums` consisting of**positive** integers.
6+
7+
We call a subarray of an array**complete** if the following condition is satisfied:
8+
9+
* The number of**distinct** elements in the subarray is equal to the number of distinct elements in the whole array.
10+
11+
Return_the number of**complete** subarrays_.
12+
13+
A**subarray** is a contiguous non-empty part of an array.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[1,3,1,2,2]
18+
19+
**Output:** 4
20+
21+
**Explanation:** The complete subarrays are the following:[1,3,1,2],[1,3,1,2,2],[3,1,2] and[3,1,2,2].
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[5,5,5,5]
26+
27+
**Output:** 10
28+
29+
**Explanation:** The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.
30+
31+
**Constraints:**
32+
33+
*`1 <= nums.length <= 1000`
34+
*`1 <= nums[i] <= 2000`

0 commit comments

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