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

Commitc36c225

Browse files
authored
Added tasks 440-443.
1 parent11d5ecc commitc36c225

File tree

12 files changed

+358
-0
lines changed

12 files changed

+358
-0
lines changed
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
packageg0401_0500.s0440_k_th_smallest_in_lexicographical_order;
2+
3+
// #Hard #Trie
4+
5+
publicclassSolution {
6+
publicintfindKthNumber(intn,intk) {
7+
intcurr =1;
8+
k =k -1;
9+
while (k >0) {
10+
intsteps =calSteps(n,curr,curr +1L);
11+
if (steps <=k) {
12+
curr +=1;
13+
k -=steps;
14+
}else {
15+
curr *=10;
16+
k -=1;
17+
}
18+
}
19+
returncurr;
20+
}
21+
22+
// use long in case of overflow
23+
privateintcalSteps(intn,longn1,longn2) {
24+
longsteps =0;
25+
while (n1 <=n) {
26+
steps +=Math.min(n +1L,n2) -n1;
27+
n1 *=10;
28+
n2 *=10;
29+
}
30+
return (int)steps;
31+
}
32+
}
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
440\. K-th Smallest in Lexicographical Order
2+
3+
Hard
4+
5+
Given two integers`n` and`k`, return_the_ <code>k<sup>th</sup></code>_lexicographically smallest integer in the range_`[1, n]`.
6+
7+
**Example 1:**
8+
9+
**Input:** n = 13, k = 2
10+
11+
**Output:** 10
12+
13+
**Explanation:** The lexicographical order is\[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9\], so the second smallest number is 10.
14+
15+
**Example 2:**
16+
17+
**Input:** n = 1, k = 1
18+
19+
**Output:** 1
20+
21+
**Constraints:**
22+
23+
* <code>1 <= k <= n <= 10<sup>9</sup></code>
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
packageg0401_0500.s0441_arranging_coins;
2+
3+
// #Easy #Math #Binary_Search
4+
5+
publicclassSolution {
6+
publicintarrangeCoins(intn) {
7+
if (n <0) {
8+
thrownewIllegalArgumentException(
9+
"Input Number is invalid. Only positive numbers are allowed");
10+
}
11+
if (n <=1) {
12+
returnn;
13+
}
14+
if (n <=3) {
15+
returnn ==3 ?2 :1;
16+
}
17+
// Binary Search space will start from 2 to n/2.
18+
longstart =2;
19+
longend =n /2;
20+
while (start <=end) {
21+
longmid =start + (end -start) /2;
22+
longcoinsFilled =mid * (mid +1) /2;
23+
if (coinsFilled ==n) {
24+
return (int)mid;
25+
}
26+
if (coinsFilled <n) {
27+
start =mid +1;
28+
}else {
29+
end =mid -1;
30+
}
31+
}
32+
// Since at this point start > end, start will start pointing to a value greater
33+
// than the desired result. We will return end as it will point to the correct
34+
// int value.
35+
return (int)end;
36+
}
37+
}
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
441\. Arranging Coins
2+
3+
Easy
4+
5+
You have`n` coins and you want to build a staircase with these coins. The staircase consists of`k` rows where the <code>i<sup>th</sup></code> row has exactly`i` coins. The last row of the staircase**may be** incomplete.
6+
7+
Given the integer`n`, return_the number of**complete rows** of the staircase you will build_.
8+
9+
**Example 1:**
10+
11+
![](https://assets.leetcode.com/uploads/2021/04/09/arrangecoins1-grid.jpg)
12+
13+
**Input:** n = 5
14+
15+
**Output:** 2
16+
17+
**Explanation:** Because the 3<sup>rd</sup> row is incomplete, we return 2.
18+
19+
**Example 2:**
20+
21+
![](https://assets.leetcode.com/uploads/2021/04/09/arrangecoins2-grid.jpg)
22+
23+
**Input:** n = 8
24+
25+
**Output:** 3
26+
27+
**Explanation:** Because the 4<sup>th</sup> row is incomplete, we return 3.
28+
29+
**Constraints:**
30+
31+
* <code>1 <= n <= 2<sup>31</sup> - 1</code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg0401_0500.s0442_find_all_duplicates_in_an_array;
2+
3+
// #Medium #Array #Hash_Table
4+
5+
importjava.util.ArrayList;
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publicList<Integer>findDuplicates(int[]nums) {
10+
intnum =nums.length;
11+
int[]count =newint[num];
12+
List<Integer>list =newArrayList<>();
13+
for (inti =0;i <num;i++) {
14+
// count number of times each number appears
15+
count[nums[i] -1] +=1;
16+
}
17+
for (inti =0;i <num;i++) {
18+
// if count of num is 2 add pos to list
19+
if (count[i] ==2) {
20+
list.add(i +1);
21+
}
22+
}
23+
returnlist;
24+
}
25+
}
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
441\. Arranging Coins
2+
3+
Easy
4+
5+
You have`n` coins and you want to build a staircase with these coins. The staircase consists of`k` rows where the <code>i<sup>th</sup></code> row has exactly`i` coins. The last row of the staircase**may be** incomplete.
6+
7+
Given the integer`n`, return_the number of**complete rows** of the staircase you will build_.
8+
9+
**Example 1:**
10+
11+
![](https://assets.leetcode.com/uploads/2021/04/09/arrangecoins1-grid.jpg)
12+
13+
**Input:** n = 5
14+
15+
**Output:** 2
16+
17+
**Explanation:** Because the 3<sup>rd</sup> row is incomplete, we return 2.
18+
19+
**Example 2:**
20+
21+
![](https://assets.leetcode.com/uploads/2021/04/09/arrangecoins2-grid.jpg)
22+
23+
**Input:** n = 8
24+
25+
**Output:** 3
26+
27+
**Explanation:** Because the 4<sup>th</sup> row is incomplete, we return 3.
28+
29+
**Constraints:**
30+
31+
* <code>1 <= n <= 2<sup>31</sup> - 1</code>
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg0401_0500.s0443_string_compression;
2+
3+
// #Medium #String #Two_Pointers
4+
5+
publicclassSolution {
6+
/** This is breaking the rules, it's not in-place. */
7+
publicintcompress(char[]chars) {
8+
if (chars ==null ||chars.length ==0) {
9+
return0;
10+
}
11+
StringBuildersb =newStringBuilder();
12+
intcount =1;
13+
charprev =chars[0];
14+
for (inti =1;i <chars.length;i++) {
15+
if (chars[i] ==prev) {
16+
count++;
17+
}else {
18+
if (count >1) {
19+
sb.append(prev);
20+
sb.append(count);
21+
}elseif (count ==1) {
22+
sb.append(prev);
23+
}
24+
prev =chars[i];
25+
count =1;
26+
}
27+
}
28+
sb.append(prev);
29+
if (count >1) {
30+
sb.append(count);
31+
}
32+
inti =0;
33+
for (charc :sb.toString().toCharArray()) {
34+
chars[i++] =c;
35+
}
36+
returnsb.length();
37+
}
38+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
443\. String Compression
2+
3+
Medium
4+
5+
Given an array of characters`chars`, compress it using the following algorithm:
6+
7+
Begin with an empty string`s`. For each group of**consecutive repeating characters** in`chars`:
8+
9+
* If the group's length is`1`, append the character to`s`.
10+
* Otherwise, append the character followed by the group's length.
11+
12+
The compressed string`s`**should not be returned separately**, but instead, be stored**in the input character array`chars`**. Note that group lengths that are`10` or longer will be split into multiple characters in`chars`.
13+
14+
After you are done**modifying the input array**, return_the new length of the array_.
15+
16+
You must write an algorithm that uses only constant extra space.
17+
18+
**Example 1:**
19+
20+
**Input:** chars =\["a","a","b","b","c","c","c"\]
21+
22+
**Output:** Return 6, and the first 6 characters of the input array should be:\["a","2","b","2","c","3"\]
23+
24+
**Explanation:** The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
25+
26+
**Example 2:**
27+
28+
**Input:** chars =\["a"\]
29+
30+
**Output:** Return 1, and the first character of the input array should be:\["a"\]
31+
32+
**Explanation:** The only group is "a", which remains uncompressed since it's a single character.
33+
34+
**Example 3:**
35+
36+
**Input:** chars =\["a","b","b","b","b","b","b","b","b","b","b","b","b"\]
37+
38+
**Output:** Return 4, and the first 4 characters of the input array should be:\["a","b","1","2"\].
39+
40+
**Explanation:** The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".
41+
42+
**Example 4:**
43+
44+
**Input:** chars =\["a","a","a","b","b","a","a"\]
45+
46+
**Output:** Return 6, and the first 6 characters of the input array should be:\["a","3","b","2","a","2"\].
47+
48+
**Explanation:** The groups are "aaa", "bb", and "aa". This compresses to "a3b2a2". Note that each group is independent even if two groups have the same character.
49+
50+
**Constraints:**
51+
52+
*`1 <= chars.length <= 2000`
53+
*`chars[i]` is a lowercase English letter, uppercase English letter, digit, or symbol.
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg0401_0500.s0440_k_th_smallest_in_lexicographical_order;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidfindKthNumber() {
11+
assertThat(newSolution().findKthNumber(13,2),equalTo(10));
12+
}
13+
14+
@Test
15+
voidfindKthNumber2() {
16+
assertThat(newSolution().findKthNumber(1,1),equalTo(1));
17+
}
18+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg0401_0500.s0441_arranging_coins;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidfindKthNumber() {
11+
assertThat(newSolution().arrangeCoins(5),equalTo(2));
12+
}
13+
14+
@Test
15+
voidarrangeCoins2() {
16+
assertThat(newSolution().arrangeCoins(8),equalTo(3));
17+
}
18+
}
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
packageg0401_0500.s0442_find_all_duplicates_in_an_array;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importjava.util.Arrays;
7+
importorg.junit.jupiter.api.Test;
8+
9+
classSolutionTest {
10+
@Test
11+
voidfindDuplicates() {
12+
assertThat(
13+
newSolution().findDuplicates(newint[] {4,3,2,7,8,2,3,1}),
14+
equalTo(Arrays.asList(2,3)));
15+
}
16+
17+
@Test
18+
voidfindDuplicates2() {
19+
assertThat(newSolution().findDuplicates(newint[] {1,1,2}),equalTo(Arrays.asList(1)));
20+
}
21+
}
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
packageg0401_0500.s0443_string_compression;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidcompress() {
11+
assertThat(
12+
newSolution().compress(newchar[] {'a','a','b','b','c','c','c'}),
13+
equalTo(6));
14+
}
15+
16+
@Test
17+
voidcompress2() {
18+
assertThat(newSolution().compress(newchar[] {'a'}),equalTo(1));
19+
}
20+
21+
@Test
22+
voidcompress3() {
23+
assertThat(
24+
newSolution()
25+
.compress(
26+
newchar[] {
27+
'a','b','b','b','b','b','b','b','b','b','b','b','b'
28+
}),
29+
equalTo(4));
30+
}
31+
}

0 commit comments

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