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

Commitbd08265

Browse files
authored
Added tasks 2529, 2530, 2531, 2532, 2535
1 parentd4b31ad commitbd08265

File tree

16 files changed

+565
-0
lines changed

16 files changed

+565
-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+
| 2535 |[Difference Between Element Sum and Digit Sum of an Array](src/main/java/g2501_2600/s2535_difference_between_element_sum_and_digit_sum_of_an_array/Solution.java)| Easy | Array, Math | 3 | 77.42
1852+
| 2532 |[Time to Cross a Bridge](src/main/java/g2501_2600/s2532_time_to_cross_a_bridge/Solution.java)| Hard | Array, Heap_Priority_Queue, Simulation | 67 | 72.50
1853+
| 2531 |[Make Number of Distinct Characters Equal](src/main/java/g2501_2600/s2531_make_number_of_distinct_characters_equal/Solution.java)| Medium | String, Hash_Table, Counting | 7 | 100.00
1854+
| 2530 |[Maximal Score After Applying K Operations](src/main/java/g2501_2600/s2530_maximal_score_after_applying_k_operations/Solution.java)| Medium | Array, Greedy, Heap_Priority_Queue | 168 | 67.97
1855+
| 2529 |[Maximum Count of Positive Integer and Negative Integer](src/main/java/g2501_2600/s2529_maximum_count_of_positive_integer_and_negative_integer/Solution.java)| Easy | Array, Binary_Search, Counting | 0 | 100.00
18511856
| 2528 |[Maximize the Minimum Powered City](src/main/java/g2501_2600/s2528_maximize_the_minimum_powered_city/Solution.java)| Hard | Array, Greedy, Binary_Search, Prefix_Sum, Sliding_Window, Queue | 51 | 77.59
18521857
| 2527 |[Find Xor-Beauty of Array](src/main/java/g2501_2600/s2527_find_xor_beauty_of_array/Solution.java)| Medium | Array, Math, Bit_Manipulation | 1 | 100.00
18531858
| 2526 |[Find Consecutive Integers from a Data Stream](src/main/java/g2501_2600/s2526_find_consecutive_integers_from_a_data_stream/DataStream.java)| Medium | Hash_Table, Design, Counting, Queue, Data_Stream | 32 | 94.65
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg2501_2600.s2529_maximum_count_of_positive_integer_and_negative_integer;
2+
3+
// #Easy #Array #Binary_Search #Counting #2023_04_20_Time_0_ms_(100.00%)_Space_42.4_MB_(77.96%)
4+
5+
publicclassSolution {
6+
publicintmaximumCount(int[]nums) {
7+
intplus =0;
8+
intminus =0;
9+
for (intnum :nums) {
10+
if (num >0) {
11+
plus++;
12+
}
13+
if (num <0) {
14+
minus++;
15+
}
16+
}
17+
returnMath.max(plus,minus);
18+
}
19+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2529\. Maximum Count of Positive Integer and Negative Integer
2+
3+
Easy
4+
5+
Given an array`nums` sorted in**non-decreasing** order, return_the maximum between the number of positive integers and the number of negative integers._
6+
7+
* In other words, if the number of positive integers in`nums` is`pos` and the number of negative integers is`neg`, then return the maximum of`pos` and`neg`.
8+
9+
**Note** that`0` is neither positive nor negative.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[-2,-1,-1,1,2,3]
14+
15+
**Output:** 3
16+
17+
**Explanation:** There are 3 positive integers and 3 negative integers. The maximum count among them is 3.
18+
19+
**Example 2:**
20+
21+
**Input:** nums =[-3,-2,-1,0,0,1,2]
22+
23+
**Output:** 3
24+
25+
**Explanation:** There are 2 positive integers and 3 negative integers. The maximum count among them is 3.
26+
27+
**Example 3:**
28+
29+
**Input:** nums =[5,20,66,1314]
30+
31+
**Output:** 4
32+
33+
**Explanation:** There are 4 positive integers and 0 negative integers. The maximum count among them is 4.
34+
35+
**Constraints:**
36+
37+
*`1 <= nums.length <= 2000`
38+
*`-2000 <= nums[i] <= 2000`
39+
*`nums` is sorted in a**non-decreasing order**.
40+
41+
**Follow up:** Can you solve the problem in`O(log(n))` time complexity?
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2501_2600.s2530_maximal_score_after_applying_k_operations;
2+
3+
// #Medium #Array #Greedy #Heap_Priority_Queue #2023_04_20_Time_168_ms_(67.97%)_Space_60_MB_(30.08%)
4+
5+
importjava.util.Arrays;
6+
importjava.util.Collections;
7+
importjava.util.PriorityQueue;
8+
9+
publicclassSolution {
10+
publiclongmaxKelements(int[]nums,intk) {
11+
PriorityQueue<Integer>p =newPriorityQueue<>(Collections.reverseOrder());
12+
Arrays.sort(nums);
13+
for (inti =0;i <nums.length;i++) {
14+
p.add(nums[nums.length -i -1]);
15+
}
16+
longscore =0;
17+
while (k !=0) {
18+
intv1 =p.poll();
19+
score +=v1;
20+
intv2 = (int)Math.ceil((double)v1 /3);
21+
p.add(v2);
22+
k--;
23+
}
24+
returnscore;
25+
}
26+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
2530\. Maximal Score After Applying K Operations
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` and an integer`k`. You have a**starting score** of`0`.
6+
7+
In one**operation**:
8+
9+
1. choose an index`i` such that`0 <= i < nums.length`,
10+
2. increase your**score** by`nums[i]`, and
11+
3. replace`nums[i]` with`ceil(nums[i] / 3)`.
12+
13+
Return_the maximum possible**score** you can attain after applying**exactly**_`k`_operations_.
14+
15+
The ceiling function`ceil(val)` is the least integer greater than or equal to`val`.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[10,10,10,10,10], k = 5
20+
21+
**Output:** 50
22+
23+
**Explanation:** Apply the operation to each array element exactly once. The final score is 10 + 10 + 10 + 10 + 10 = 50.
24+
25+
**Example 2:**
26+
27+
**Input:** nums =[1,10,3,3,3], k = 3
28+
29+
**Output:** 17
30+
31+
**Explanation:** You can do the following operations:
32+
33+
Operation 1: Select i = 1, so nums becomes[1,**<ins>4</ins>**,3,3,3]. Your score increases by 10.
34+
35+
Operation 2: Select i = 1, so nums becomes[1,**<ins>2</ins>**,3,3,3]. Your score increases by 4.
36+
37+
Operation 3: Select i = 2, so nums becomes[1,1,<ins>**1**</ins>,3,3]. Your score increases by 3.
38+
39+
The final score is 10 + 4 + 3 = 17.
40+
41+
**Constraints:**
42+
43+
* <code>1 <= nums.length, k <= 10<sup>5</sup></code>
44+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
packageg2501_2600.s2531_make_number_of_distinct_characters_equal;
2+
3+
// #Medium #String #Hash_Table #Counting #2023_04_20_Time_7_ms_(100.00%)_Space_43_MB_(96.82%)
4+
5+
@SuppressWarnings("java:S135")
6+
publicclassSolution {
7+
publicbooleanisItPossible(Stringword1,Stringword2) {
8+
int[]count1 =count(word1);
9+
int[]count2 =count(word2);
10+
intd =count1[26] -count2[26];
11+
int[]zip1 =zip(count1,count2);
12+
int[]zip2 =zip(count2,count1);
13+
for (inti =0;i <26;i++) {
14+
intd1 =zip1[i];
15+
if (d1 == -1) {
16+
continue;
17+
}
18+
for (intj =0;j <26;j++) {
19+
intd2 =zip2[j];
20+
if (d2 == -1) {
21+
continue;
22+
}
23+
if (i ==j) {
24+
if (d ==0) {
25+
returntrue;
26+
}
27+
continue;
28+
}
29+
if (d -d1 +d2 ==0) {
30+
returntrue;
31+
}
32+
}
33+
}
34+
returnfalse;
35+
}
36+
37+
privateint[]zip(int[]c1,int[]c2) {
38+
int[]zip =newint[26];
39+
for (inti =0;i <26;i++) {
40+
intd =0;
41+
if (c1[i] ==0) {
42+
d = -1;
43+
}else {
44+
if (c2[i] ==0) {
45+
d++;
46+
}
47+
if (c1[i] ==1) {
48+
d++;
49+
}
50+
}
51+
zip[i] =d;
52+
}
53+
returnzip;
54+
}
55+
56+
privateint[]count(Stringword) {
57+
int[]count =newint[27];
58+
intlen =word.length();
59+
for (inti =0;i <len;i++) {
60+
count[word.charAt(i) -'a']++;
61+
}
62+
for (inti =0;i <26;i++) {
63+
if (count[i] >0) {
64+
count[26]++;
65+
}
66+
}
67+
returncount;
68+
}
69+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2531\. Make Number of Distinct Characters Equal
2+
3+
Medium
4+
5+
You are given two**0-indexed** strings`word1` and`word2`.
6+
7+
A**move** consists of choosing two indices`i` and`j` such that`0 <= i < word1.length` and`0 <= j < word2.length` and swapping`word1[i]` with`word2[j]`.
8+
9+
Return`true`_if it is possible to get the number of distinct characters in_`word1`_and_`word2`_to be equal with**exactly one** move._ Return`false`_otherwise_.
10+
11+
**Example 1:**
12+
13+
**Input:** word1 = "ac", word2 = "b"
14+
15+
**Output:** false
16+
17+
**Explanation:** Any pair of swaps would yield two distinct characters in the first string, and one in the second string.
18+
19+
**Example 2:**
20+
21+
**Input:** word1 = "abcc", word2 = "aab"
22+
23+
**Output:** true
24+
25+
**Explanation:** We swap index 2 of the first string with index 0 of the second string. The resulting strings are word1 = "abac" and word2 = "cab", which both have 3 distinct characters.
26+
27+
**Example 3:**
28+
29+
**Input:** word1 = "abcde", word2 = "fghij"
30+
31+
**Output:** true
32+
33+
**Explanation:** Both resulting strings will have 5 distinct characters, regardless of which indices we swap.
34+
35+
**Constraints:**
36+
37+
* <code>1 <= word1.length, word2.length <= 10<sup>5</sup></code>
38+
*`word1` and`word2` consist of only lowercase English letters.
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
packageg2501_2600.s2532_time_to_cross_a_bridge;
2+
3+
// #Hard #Array #Heap_Priority_Queue #Simulation
4+
// #2023_04_20_Time_67_ms_(72.50%)_Space_50.4_MB_(15.00%)
5+
6+
importjava.util.Comparator;
7+
importjava.util.PriorityQueue;
8+
9+
publicclassSolution {
10+
publicintfindCrossingTime(intn,intk,int[][]time) {
11+
// create 2 PQ
12+
PriorityQueue<int[]>leftBridgePQ =
13+
newPriorityQueue<>((a,b) -> (a[1] ==b[1] ?b[0] -a[0] :b[1] -a[1]));
14+
PriorityQueue<int[]>rightBridgePQ =
15+
newPriorityQueue<>((a,b) -> (a[1] ==b[1] ?b[0] -a[0] :b[1] -a[1]));
16+
PriorityQueue<int[]>leftWHPQ =newPriorityQueue<>(Comparator.comparingInt(a ->a[1]));
17+
PriorityQueue<int[]>rightWHPQ =newPriorityQueue<>(Comparator.comparingInt(a ->a[1]));
18+
for (inti =0;i <k;i++) {
19+
inteffciency =time[i][0] +time[i][2];
20+
leftBridgePQ.offer(newint[] {i,effciency});
21+
}
22+
intduration =0;
23+
while (n >0 || !rightBridgePQ.isEmpty() || !rightWHPQ.isEmpty()) {
24+
while (!leftWHPQ.isEmpty() &&leftWHPQ.peek()[1] <=duration) {
25+
intid =leftWHPQ.poll()[0];
26+
inte =time[id][0] +time[id][2];
27+
leftBridgePQ.offer(newint[] {id,e});
28+
}
29+
while (!rightWHPQ.isEmpty() &&rightWHPQ.peek()[1] <=duration) {
30+
intid =rightWHPQ.poll()[0];
31+
inte =time[id][0] +time[id][2];
32+
rightBridgePQ.offer(newint[] {id,e});
33+
}
34+
if (!rightBridgePQ.isEmpty()) {
35+
intid =rightBridgePQ.poll()[0];
36+
duration +=time[id][2];
37+
leftWHPQ.offer(newint[] {id,duration +time[id][3]});
38+
}elseif (!leftBridgePQ.isEmpty() &&n >0) {
39+
intid =leftBridgePQ.poll()[0];
40+
duration +=time[id][0];
41+
rightWHPQ.offer(newint[] {id,duration +time[id][1]});
42+
--n;
43+
}else {
44+
// update duration
45+
intleft =Integer.MAX_VALUE;
46+
if (!leftWHPQ.isEmpty() &&n >0) {
47+
left =leftWHPQ.peek()[1];
48+
}
49+
intright =Integer.MAX_VALUE;
50+
if (!rightWHPQ.isEmpty()) {
51+
right =rightWHPQ.peek()[1];
52+
}
53+
duration =Math.min(left,right);
54+
}
55+
}
56+
returnduration;
57+
}
58+
}

0 commit comments

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