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

Commitb2560be

Browse files
authored
Added tasks 2667-2673
1 parent900221b commitb2560be

File tree

15 files changed

+495
-0
lines changed

15 files changed

+495
-0
lines changed
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
2667\. Create Hello World Function
2+
3+
Easy
4+
5+
Write a function`createHelloWorld`. It should return a new function that always returns`"Hello World"`.
6+
7+
**Example 1:**
8+
9+
**Input:** args =[]
10+
11+
**Output:** "Hello World"
12+
13+
**Explanation:**
14+
15+
const f = createHelloWorld();
16+
f(); // "Hello World"
17+
18+
The function returned by createHelloWorld should always return "Hello World".
19+
20+
**Example 2:**
21+
22+
**Input:** args =[{},null,42]
23+
24+
**Output:** "Hello World"
25+
26+
**Explanation:**
27+
28+
const f = createHelloWorld();
29+
f({}, null, 42); // "Hello World"
30+
31+
Any arguments could be passed to the function but it should still always return "Hello World".
32+
33+
**Constraints:**
34+
35+
*`0 <= args.length <= 10`
Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
// #Easy #2023_09_10_Time_45_ms_(94.20%)_Space_43.6_MB_(9.97%)
2+
3+
constcreateHelloWorld=()=>()=>"Hello World";
4+
5+
/*
6+
* const f = createHelloWorld();
7+
* f(); // "Hello World"
8+
*/
9+
10+
export{createHelloWorld}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2601_2700.s2670_find_the_distinct_difference_array;
2+
3+
// #Easy #Array #Hash_Table #2023_09_10_Time_5_ms_(92.12%)_Space_44.5_MB_(66.07%)
4+
5+
importjava.util.HashSet;
6+
7+
publicclassSolution {
8+
publicint[]distinctDifferenceArray(int[]nums) {
9+
intn =nums.length;
10+
HashSet<Integer>prefixSet =newHashSet<>();
11+
HashSet<Integer>suffixSet =newHashSet<>();
12+
int[]preList =newint[n];
13+
int[]sufList =newint[n];
14+
int[]ans =newint[n];
15+
for (inti =0;i <nums.length;i++) {
16+
prefixSet.add(nums[i]);
17+
suffixSet.add(nums[n -1 -i]);
18+
preList[i] =prefixSet.size();
19+
sufList[n -1 -i] =suffixSet.size();
20+
}
21+
for (inti =0;i <nums.length;i++) {
22+
if (i ==nums.length -1) {
23+
ans[i] =preList[i];
24+
}else {
25+
ans[i] =preList[i] -sufList[i +1];
26+
}
27+
}
28+
returnans;
29+
}
30+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2670\. Find the Distinct Difference Array
2+
3+
Easy
4+
5+
You are given a**0-indexed** array`nums` of length`n`.
6+
7+
The**distinct difference** array of`nums` is an array`diff` of length`n` such that`diff[i]` is equal to the number of distinct elements in the suffix`nums[i + 1, ..., n - 1]`**subtracted from** the number of distinct elements in the prefix`nums[0, ..., i]`.
8+
9+
Return_the**distinct difference** array of_`nums`.
10+
11+
Note that`nums[i, ..., j]` denotes the subarray of`nums` starting at index`i` and ending at index`j` inclusive. Particularly, if`i > j` then`nums[i, ..., j]` denotes an empty subarray.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[1,2,3,4,5]
16+
17+
**Output:**[-3,-1,1,3,5]
18+
19+
**Explanation:**
20+
21+
For index i = 0, there is 1 element in the prefix and 4 distinct elements in the suffix. Thus, diff[0] = 1 - 4 = -3.
22+
23+
For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 - 3 = -1.
24+
25+
For index i = 2, there are 3 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 3 - 2 = 1.
26+
27+
For index i = 3, there are 4 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 4 - 1 = 3.
28+
29+
For index i = 4, there are 5 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 5 - 0 = 5.
30+
31+
**Example 2:**
32+
33+
**Input:** nums =[3,2,3,4,2]
34+
35+
**Output:**[-2,-1,0,2,3]
36+
37+
**Explanation:**
38+
39+
For index i = 0, there is 1 element in the prefix and 3 distinct elements in the suffix. Thus, diff[0] = 1 - 3 = -2.
40+
41+
For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 - 3 = -1.
42+
43+
For index i = 2, there are 2 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 2 - 2 = 0.
44+
45+
For index i = 3, there are 3 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 3 - 1 = 2.
46+
47+
For index i = 4, there are 3 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 3 - 0 = 3.
48+
49+
**Constraints:**
50+
51+
*`1 <= n == nums.length <= 50`
52+
*`1 <= nums[i] <= 50`
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
packageg2601_2700.s2671_frequency_tracker;
2+
3+
// #Medium #Hash_Table #Design #2023_09_10_Time_31_ms_(83.08%)_Space_111.8_MB_(59.70%)
4+
5+
importjava.util.HashMap;
6+
importjava.util.Map;
7+
8+
publicclassFrequencyTracker {
9+
privatefinalMap<Integer,Integer>numCount;
10+
privatefinalMap<Integer,Integer>frequencies;
11+
12+
publicFrequencyTracker() {
13+
numCount =newHashMap<>();
14+
frequencies =newHashMap<>();
15+
}
16+
17+
publicvoidadd(intnumber) {
18+
intnewCount =numCount.merge(number,1,Integer::sum);
19+
frequencies.merge(newCount,1,Integer::sum);
20+
if (newCount >1) {
21+
frequencies.merge(newCount -1, -1,Integer::sum);
22+
}
23+
}
24+
25+
publicvoiddeleteOne(intnumber) {
26+
IntegercurrentVal =numCount.get(number);
27+
if (currentVal !=null &&currentVal >0) {
28+
intnewCount =numCount.merge(number, -1,Integer::sum);
29+
frequencies.merge(newCount,1,Integer::sum);
30+
frequencies.merge(newCount +1, -1,Integer::sum);
31+
}
32+
}
33+
34+
publicbooleanhasFrequency(intfrequency) {
35+
Integerexisting =frequencies.get(frequency);
36+
returnexisting !=null &&existing >0;
37+
}
38+
}
39+
40+
/*
41+
* Your FrequencyTracker object will be instantiated and called as such:
42+
* FrequencyTracker obj = new FrequencyTracker();
43+
* obj.add(number);
44+
* obj.deleteOne(number);
45+
* boolean param_3 = obj.hasFrequency(frequency);
46+
*/
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
2671\. Frequency Tracker
2+
3+
Medium
4+
5+
Design a data structure that keeps track of the values in it and answers some queries regarding their frequencies.
6+
7+
Implement the`FrequencyTracker` class.
8+
9+
*`FrequencyTracker()`: Initializes the`FrequencyTracker` object with an empty array initially.
10+
*`void add(int number)`: Adds`number` to the data structure.
11+
*`void deleteOne(int number)`: Deletes**one** occurrence of`number` from the data structure. The data structure**may not contain**`number`, and in this case nothing is deleted.
12+
*`bool hasFrequency(int frequency)`: Returns`true` if there is a number in the data structure that occurs`frequency` number of times, otherwise, it returns`false`.
13+
14+
**Example 1:**
15+
16+
**Input**["FrequencyTracker", "add", "add", "hasFrequency"][[],[3],[3],[2]]
17+
18+
**Output:**[null, null, null, true]
19+
20+
**Explanation:**
21+
22+
FrequencyTracker frequencyTracker = new FrequencyTracker();
23+
frequencyTracker.add(3); // The data structure now contains [3]
24+
frequencyTracker.add(3); // The data structure now contains [3, 3]
25+
frequencyTracker.hasFrequency(2); // Returns true, because 3 occurs twice
26+
27+
**Example 2:**
28+
29+
**Input**["FrequencyTracker", "add", "deleteOne", "hasFrequency"][[],[1],[1],[1]]
30+
31+
**Output:**[null, null, null, false]
32+
33+
**Explanation:**
34+
35+
FrequencyTracker frequencyTracker = new FrequencyTracker();
36+
frequencyTracker.add(1); // The data structure now contains [1]
37+
frequencyTracker.deleteOne(1); // The data structure becomes empty []
38+
frequencyTracker.hasFrequency(1); // Returns false, because the data structure is empty
39+
40+
**Example 3:**
41+
42+
**Input**["FrequencyTracker", "hasFrequency", "add", "hasFrequency"][[],[2],[3],[1]]
43+
44+
**Output:**[null, false, null, true]
45+
46+
**Explanation:**
47+
48+
FrequencyTracker frequencyTracker = new FrequencyTracker();
49+
frequencyTracker.hasFrequency(2); // Returns false, because the data structure is empty
50+
frequencyTracker.add(3); // The data structure now contains [3]
51+
frequencyTracker.hasFrequency(1); // Returns true, because 3 occurs once
52+
53+
**Constraints:**
54+
55+
* <code>1 <= number <= 10<sup>5</sup></code>
56+
* <code>1 <= frequency <= 10<sup>5</sup></code>
57+
* At most, <code>2 * 10<sup>5</sup></code> calls will be made to`add`,`deleteOne`, and`hasFrequency` in**total**.
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
packageg2601_2700.s2672_number_of_adjacent_elements_with_the_same_color;
2+
3+
// #Medium #Array #2023_09_10_Time_4_ms_(100.00%)_Space_96_MB_(23.28%)
4+
5+
publicclassSolution {
6+
publicint[]colorTheArray(intn,int[][]q) {
7+
if (n ==1) {
8+
returnnewint[q.length];
9+
}
10+
int[]ans =newint[q.length];
11+
int[]color =newint[n];
12+
intcnt =0;
13+
for (inti =0;i <q.length;i++) {
14+
intind =q[i][0];
15+
intassColor =q[i][1];
16+
17+
intleftColor =0;
18+
intrytColor =0;
19+
20+
if (ind -1 >=0) {
21+
leftColor =color[ind -1];
22+
}
23+
if (ind +1 <n) {
24+
rytColor =color[ind +1];
25+
}
26+
if (color[ind] !=0 &&leftColor ==color[ind]) {
27+
cnt--;
28+
}
29+
if (color[ind] !=0 &&rytColor ==color[ind]) {
30+
cnt--;
31+
}
32+
color[ind] =assColor;
33+
if (color[ind] !=0 &&leftColor ==color[ind]) {
34+
cnt++;
35+
}
36+
if (color[ind] !=0 &&rytColor ==color[ind]) {
37+
cnt++;
38+
}
39+
ans[i] =cnt;
40+
}
41+
returnans;
42+
}
43+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
2672\. Number of Adjacent Elements With the Same Color
2+
3+
Medium
4+
5+
There is a**0-indexed** array`nums` of length`n`. Initially, all elements are**uncolored** (has a value of`0`).
6+
7+
You are given a 2D integer array`queries` where <code>queries[i] =[index<sub>i</sub>, color<sub>i</sub>]</code>.
8+
9+
For each query, you color the index <code>index<sub>i</sub></code> with the color <code>color<sub>i</sub></code> in the array`nums`.
10+
11+
Return_an array_`answer`_of the same length as_`queries`_where_`answer[i]`_is the number of adjacent elements with the same color**after** the_ <code>i<sup>th</sup></code>_query_.
12+
13+
More formally,`answer[i]` is the number of indices`j`, such that`0 <= j < n - 1` and`nums[j] == nums[j + 1]` and`nums[j] != 0` after the <code>i<sup>th</sup></code> query.
14+
15+
**Example 1:**
16+
17+
**Input:** n = 4, queries =[[0,2],[1,2],[3,1],[1,1],[2,1]]
18+
19+
**Output:**[0,1,1,0,2]
20+
21+
**Explanation:** Initially array nums =[0,0,0,0], where 0 denotes uncolored elements of the array.
22+
- After the 1<sup>st</sup> query nums =[2,0,0,0]. The count of adjacent elements with the same color is 0.
23+
- After the 2<sup>nd</sup> query nums =[2,2,0,0]. The count of adjacent elements with the same color is 1.
24+
- After the 3<sup>rd</sup> query nums =[2,2,0,1]. The count of adjacent elements with the same color is 1.
25+
- After the 4<sup>th</sup> query nums =[2,1,0,1]. The count of adjacent elements with the same color is 0.
26+
- After the 5<sup>th</sup> query nums =[2,1,1,1]. The count of adjacent elements with the same color is 2.
27+
28+
**Example 2:**
29+
30+
**Input:** n = 1, queries =[[0,100000]]
31+
32+
**Output:**[0]
33+
34+
**Explanation:** Initially array nums =[0], where 0 denotes uncolored elements of the array.
35+
- After the 1<sup>st</sup> query nums =[100000]. The count of adjacent elements with the same color is 0.
36+
37+
**Constraints:**
38+
39+
* <code>1 <= n <= 10<sup>5</sup></code>
40+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
41+
*`queries[i].length == 2`
42+
* <code>0 <= index<sub>i</sub> <= n - 1</code>
43+
* <code>1 <= color<sub>i</sub> <= 10<sup>5</sup></code>
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg2601_2700.s2673_make_costs_of_paths_equal_in_a_binary_tree;
2+
3+
// #Medium #Array #Dynamic_Programming #Greedy #Tree #Binary_Tree
4+
// #2023_09_10_Time_4_ms_(96.98%)_Space_55.3_MB_(45.28%)
5+
6+
publicclassSolution {
7+
publicintminIncrements(intn,int[]cost) {
8+
intlast =n /2 -1;
9+
intres =0;
10+
for (inti =last;i >=0;i--) {
11+
intabs =cost[2 *i +1] -cost[2 *i +2];
12+
if (abs <0) {
13+
abs *= -1;
14+
}
15+
cost[i] +=Math.max(cost[2 *i +1],cost[2 *i +2]);
16+
res +=abs;
17+
}
18+
returnres;
19+
}
20+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2673\. Make Costs of Paths Equal in a Binary Tree
2+
3+
Medium
4+
5+
You are given an integer`n` representing the number of nodes in a**perfect binary tree** consisting of nodes numbered from`1` to`n`. The root of the tree is node`1` and each node`i` in the tree has two children where the left child is the node`2 * i` and the right child is`2 * i + 1`.
6+
7+
Each node in the tree also has a**cost** represented by a given**0-indexed** integer array`cost` of size`n` where`cost[i]` is the cost of node`i + 1`. You are allowed to**increment** the cost of**any** node by`1`**any** number of times.
8+
9+
Return_the**minimum** number of increments you need to make the cost of paths from the root to each**leaf** node equal_.
10+
11+
**Note**:
12+
13+
* A**perfect binary tree** is a tree where each node, except the leaf nodes, has exactly 2 children.
14+
* The**cost of a path** is the sum of costs of nodes in the path.
15+
16+
**Example 1:**
17+
18+
![](https://assets.leetcode.com/uploads/2023/04/04/binaryytreeedrawio-4.png)
19+
20+
**Input:** n = 7, cost =[1,5,2,2,3,3,1]
21+
22+
**Output:** 6
23+
24+
**Explanation:** We can do the following increments:
25+
- Increase the cost of node 4 one time.
26+
- Increase the cost of node 3 three times.
27+
- Increase the cost of node 7 two times.
28+
29+
Each path from the root to a leaf will have a total cost of 9.
30+
31+
The total increments we did is 1 + 3 + 2 = 6.
32+
It can be shown that this is the minimum answer we can achieve.
33+
34+
**Example 2:**
35+
36+
![](https://assets.leetcode.com/uploads/2023/04/04/binaryytreee2drawio.png)
37+
38+
**Input:** n = 3, cost =[5,3,3]
39+
40+
**Output:** 0
41+
42+
**Explanation:** The two paths already have equal total costs, so no increments are needed.
43+
44+
**Constraints:**
45+
46+
* <code>3 <= n <= 10<sup>5</sup></code>
47+
*`n + 1` is a power of`2`
48+
*`cost.length == n`
49+
* <code>1 <= cost[i] <= 10<sup>4</sup></code>

0 commit comments

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