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
Appearance settings

Commit d429aba

Browse filesBrowse files
ThanhNITThanhNIT
authored
Added tasks 867, 868, 869, 870
1 parent 7793194 commit d429aba
Copy full SHA for d429aba

File tree

Expand file treeCollapse file tree

13 files changed

+331
-0
lines changed
Filter options
Expand file treeCollapse file tree

13 files changed

+331
-0
lines changed

‎README.md

Copy file name to clipboardExpand all lines: README.md
+4Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1719,6 +1719,10 @@ implementation 'com.github.javadev:leetcode-in-kotlin:1.11'
17191719
|------|----------------|-------------|-------------|----------|---------
17201720
| 1143 |[Longest Common Subsequence](src/main/kotlin/g1101_1200/s1143_longest_common_subsequence/Solution.kt)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Algorithm_II_Day_17_Dynamic_Programming, Dynamic_Programming_I_Day_19, Udemy_Dynamic_Programming | 307 | 38.36
17211721
| 0994 |[Rotting Oranges](src/main/kotlin/g0901_1000/s0994_rotting_oranges/Solution.kt)| Medium | Array, Breadth_First_Search, Matrix, Algorithm_I_Day_9_Breadth_First_Search_Depth_First_Search, Level_2_Day_10_Graph/BFS/DFS | 308 | 57.93
1722+
| 0870 |[Advantage Shuffle](src/main/kotlin/g0801_0900/s0870_advantage_shuffle/Solution.kt)| Medium | Array, Sorting, Greedy | 698 | 100.00
1723+
| 0869 |[Reordered Power of 2](src/main/kotlin/g0801_0900/s0869_reordered_power_of_2/Solution.kt)| Medium | Math, Sorting, Counting, Enumeration | 145 | 87.50
1724+
| 0868 |[Binary Gap](src/main/kotlin/g0801_0900/s0868_binary_gap/Solution.kt)| Easy | Bit_Manipulation | 142 | 100.00
1725+
| 0867 |[Transpose Matrix](src/main/kotlin/g0801_0900/s0867_transpose_matrix/Solution.kt)| Easy | Array, Matrix, Simulation | 201 | 100.00
17221726
| 0866 |[Prime Palindrome](src/main/kotlin/g0801_0900/s0866_prime_palindrome/Solution.kt)| Medium | Math | 143 | 100.00
17231727
| 0865 |[Smallest Subtree with all the Deepest Nodes](src/main/kotlin/g0801_0900/s0865_smallest_subtree_with_all_the_deepest_nodes/Solution.kt)| Medium | Hash_Table, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree | 147 | 100.00
17241728
| 0864 |[Shortest Path to Get All Keys](src/main/kotlin/g0801_0900/s0864_shortest_path_to_get_all_keys/Solution.kt)| Hard | Breadth_First_Search, Bit_Manipulation | 176 | 100.00

‎src/main/kotlin/g0801_0900/s0867_transpose_matrix/Solution.kt

Copy file name to clipboard
+27Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package g0801_0900.s0867_transpose_matrix
2+
3+
// #Easy #Array #Matrix #Simulation #2023_04_05_Time_201_ms_(100.00%)_Space_38.4_MB_(8.70%)
4+
5+
class Solution {
6+
fun transpose(input: Array<IntArray>): Array<IntArray> {
7+
val output = Array(input[0].size) {
8+
IntArray(
9+
input.size
10+
)
11+
}
12+
var i = 0
13+
var b = 0
14+
while (i < input.size) {
15+
var j = 0
16+
var a = 0
17+
while (j < input[0].size) {
18+
output[a][b] = input[i][j]
19+
j++
20+
a++
21+
}
22+
i++
23+
b++
24+
}
25+
return output
26+
}
27+
}

‎src/main/kotlin/g0801_0900/s0867_transpose_matrix/readme.md

Copy file name to clipboard
+29Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
867\. Transpose Matrix
2+
3+
Easy
4+
5+
Given a 2D integer array `matrix`, return _the **transpose** of_ `matrix`.
6+
7+
The **transpose** of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices.
8+
9+
![](https://assets.leetcode.com/uploads/2021/02/10/hint_transpose.png)
10+
11+
**Example 1:**
12+
13+
**Input:** matrix = [[1,2,3],[4,5,6],[7,8,9]]
14+
15+
**Output:** [[1,4,7],[2,5,8],[3,6,9]]
16+
17+
**Example 2:**
18+
19+
**Input:** matrix = [[1,2,3],[4,5,6]]
20+
21+
**Output:** [[1,4],[2,5],[3,6]]
22+
23+
**Constraints:**
24+
25+
* `m == matrix.length`
26+
* `n == matrix[i].length`
27+
* `1 <= m, n <= 1000`
28+
* <code>1 <= m * n <= 10<sup>5</sup></code>
29+
* <code>-10<sup>9</sup> <= matrix[i][j] <= 10<sup>9</sup></code>

‎src/main/kotlin/g0801_0900/s0868_binary_gap/Solution.kt

Copy file name to clipboard
+24Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package g0801_0900.s0868_binary_gap
2+
3+
// #Easy #Bit_Manipulation #2023_04_05_Time_142_ms_(100.00%)_Space_33.8_MB_(50.00%)
4+
5+
@Suppress("NAME_SHADOWING")
6+
class Solution {
7+
fun binaryGap(n: Int): Int {
8+
var n = n
9+
var max = 0
10+
var pos = 0
11+
var lastPos = -1
12+
while (n != 0) {
13+
pos++
14+
if (n and 1 == 1) {
15+
if (lastPos != -1) {
16+
max = max.coerceAtLeast(pos - lastPos)
17+
}
18+
lastPos = pos
19+
}
20+
n = n shr 1
21+
}
22+
return max
23+
}
24+
}

‎src/main/kotlin/g0801_0900/s0868_binary_gap/readme.md

Copy file name to clipboard
+43Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
868\. Binary Gap
2+
3+
Easy
4+
5+
Given a positive integer `n`, find and return _the **longest distance** between any two **adjacent**_ `1`_'s in the binary representation of_ `n`_. If there are no two adjacent_ `1`_'s, return_ `0`_._
6+
7+
Two `1`'s are **adjacent** if there are only `0`'s separating them (possibly no `0`'s). The **distance** between two `1`'s is the absolute difference between their bit positions. For example, the two `1`'s in `"1001"` have a distance of 3.
8+
9+
**Example 1:**
10+
11+
**Input:** n = 22
12+
13+
**Output:** 2
14+
15+
**Explanation:** 22 in binary is "10110".
16+
17+
The first adjacent pair of 1's is "10110" with a distance of 2.
18+
19+
The second adjacent pair of 1's is "10110" with a distance of 1.
20+
21+
The answer is the largest of these two distances, which is 2.
22+
23+
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.
24+
25+
**Example 2:**
26+
27+
**Input:** n = 8
28+
29+
**Output:** 0
30+
31+
**Explanation:** 8 in binary is "1000". There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.
32+
33+
**Example 3:**
34+
35+
**Input:** n = 5
36+
37+
**Output:** 2
38+
39+
**Explanation:** 5 in binary is "101".
40+
41+
**Constraints:**
42+
43+
* <code>1 <= n <= 10<sup>9</sup></code>

‎src/main/kotlin/g0801_0900/s0869_reordered_power_of_2/Solution.kt

Copy file name to clipboard
+35Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package g0801_0900.s0869_reordered_power_of_2
2+
3+
// #Medium #Math #Sorting #Counting #Enumeration
4+
// #2023_04_05_Time_145_ms_(87.50%)_Space_35.5_MB_(50.00%)
5+
6+
import kotlin.math.pow
7+
8+
class Solution {
9+
fun reorderedPowerOf2(n: Int): Boolean {
10+
var i = 0
11+
while (2.0.pow(i.toDouble()) < n.toLong() * 10) {
12+
if (isValid(2.0.pow(i++.toDouble()).toInt().toString(), n.toString())) {
13+
return true
14+
}
15+
}
16+
return false
17+
}
18+
19+
private fun isValid(a: String, b: String): Boolean {
20+
val m: MutableMap<Char, Int> = HashMap()
21+
val mTwo: MutableMap<Char, Int> = HashMap()
22+
for (c in a.toCharArray()) {
23+
m[c] = if (m.containsKey(c)) m[c]!! + 1 else 1
24+
}
25+
for (c in b.toCharArray()) {
26+
mTwo[c] = if (mTwo.containsKey(c)) mTwo[c]!! + 1 else 1
27+
}
28+
for (entry in mTwo.entries.iterator()) {
29+
if (!m.containsKey(entry.key) || entry.value != m[entry.key]) {
30+
return false
31+
}
32+
}
33+
return a[0] != '0' && m.size == mTwo.size
34+
}
35+
}

‎src/main/kotlin/g0801_0900/s0869_reordered_power_of_2/readme.md

Copy file name to clipboard
+23Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
869\. Reordered Power of 2
2+
3+
Medium
4+
5+
You are given an integer `n`. We reorder the digits in any order (including the original order) such that the leading digit is not zero.
6+
7+
Return `true` _if and only if we can do this so that the resulting number is a power of two_.
8+
9+
**Example 1:**
10+
11+
**Input:** n = 1
12+
13+
**Output:** true
14+
15+
**Example 2:**
16+
17+
**Input:** n = 10
18+
19+
**Output:** false
20+
21+
**Constraints:**
22+
23+
* <code>1 <= n <= 10<sup>9</sup></code>

‎src/main/kotlin/g0801_0900/s0870_advantage_shuffle/Solution.kt

Copy file name to clipboard
+35Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package g0801_0900.s0870_advantage_shuffle
2+
3+
// #Medium #Array #Sorting #Greedy #2023_04_05_Time_698_ms_(100.00%)_Space_51.1_MB_(100.00%)
4+
5+
import java.util.Arrays
6+
import java.util.PriorityQueue
7+
8+
class Solution {
9+
fun advantageCount(nums1: IntArray, nums2: IntArray): IntArray {
10+
val n = nums1.size
11+
Arrays.sort(nums1)
12+
val maxpq = PriorityQueue { pair1: IntArray, pair2: IntArray ->
13+
pair2[1] - pair1[1]
14+
}
15+
for (i in 0 until n) {
16+
maxpq.offer(intArrayOf(i, nums2[i]))
17+
}
18+
var left = 0
19+
var right = n - 1
20+
val res = IntArray(n)
21+
while (!maxpq.isEmpty()) {
22+
val pair = maxpq.poll()
23+
val i = pair[0]
24+
val `val` = pair[1]
25+
if (nums1[right] > `val`) {
26+
res[i] = nums1[right]
27+
right--
28+
} else {
29+
res[i] = nums1[left]
30+
left++
31+
}
32+
}
33+
return res
34+
}
35+
}

‎src/main/kotlin/g0801_0900/s0870_advantage_shuffle/readme.md

Copy file name to clipboard
+25Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
870\. Advantage Shuffle
2+
3+
Medium
4+
5+
You are given two integer arrays `nums1` and `nums2` both of the same length. The **advantage** of `nums1` with respect to `nums2` is the number of indices `i` for which `nums1[i] > nums2[i]`.
6+
7+
Return _any permutation of_ `nums1` _that maximizes its **advantage** with respect to_ `nums2`.
8+
9+
**Example 1:**
10+
11+
**Input:** nums1 = [2,7,11,15], nums2 = [1,10,4,11]
12+
13+
**Output:** [2,11,7,15]
14+
15+
**Example 2:**
16+
17+
**Input:** nums1 = [12,24,8,32], nums2 = [13,25,32,11]
18+
19+
**Output:** [24,32,8,12]
20+
21+
**Constraints:**
22+
23+
* <code>1 <= nums1.length <= 10<sup>5</sup></code>
24+
* `nums2.length == nums1.length`
25+
* <code>0 <= nums1[i], nums2[i] <= 10<sup>9</sup></code>

‎src/test/kotlin/g0801_0900/s0867_transpose_matrix/SolutionTest.kt

Copy file name to clipboard
+23Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package g0801_0900.s0867_transpose_matrix
2+
3+
import org.hamcrest.CoreMatchers.equalTo
4+
import org.hamcrest.MatcherAssert.assertThat
5+
import org.junit.jupiter.api.Test
6+
7+
internal class SolutionTest {
8+
@Test
9+
fun transpose() {
10+
assertThat(
11+
Solution().transpose(arrayOf(intArrayOf(1, 2, 3), intArrayOf(4, 5, 6), intArrayOf(7, 8, 9))),
12+
equalTo(arrayOf(intArrayOf(1, 4, 7), intArrayOf(2, 5, 8), intArrayOf(3, 6, 9)))
13+
)
14+
}
15+
16+
@Test
17+
fun transpose2() {
18+
assertThat(
19+
Solution().transpose(arrayOf(intArrayOf(1, 2, 3), intArrayOf(4, 5, 6))),
20+
equalTo(arrayOf(intArrayOf(1, 4), intArrayOf(2, 5), intArrayOf(3, 6)))
21+
)
22+
}
23+
}

‎src/test/kotlin/g0801_0900/s0868_binary_gap/SolutionTest.kt

Copy file name to clipboard
+22Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package g0801_0900.s0868_binary_gap
2+
3+
import org.hamcrest.CoreMatchers.equalTo
4+
import org.hamcrest.MatcherAssert.assertThat
5+
import org.junit.jupiter.api.Test
6+
7+
internal class SolutionTest {
8+
@Test
9+
fun binaryGap() {
10+
assertThat(Solution().binaryGap(22), equalTo(2))
11+
}
12+
13+
@Test
14+
fun binaryGap2() {
15+
assertThat(Solution().binaryGap(8), equalTo(0))
16+
}
17+
18+
@Test
19+
fun binaryGap3() {
20+
assertThat(Solution().binaryGap(5), equalTo(2))
21+
}
22+
}

‎src/test/kotlin/g0801_0900/s0869_reordered_power_of_2/SolutionTest.kt

Copy file name to clipboard
+17Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package g0801_0900.s0869_reordered_power_of_2
2+
3+
import org.hamcrest.CoreMatchers.equalTo
4+
import org.hamcrest.MatcherAssert.assertThat
5+
import org.junit.jupiter.api.Test
6+
7+
internal class SolutionTest {
8+
@Test
9+
fun reorderedPowerOf2() {
10+
assertThat(Solution().reorderedPowerOf2(1), equalTo(true))
11+
}
12+
13+
@Test
14+
fun reorderedPowerOf22() {
15+
assertThat(Solution().reorderedPowerOf2(10), equalTo(false))
16+
}
17+
}

‎src/test/kotlin/g0801_0900/s0870_advantage_shuffle/SolutionTest.kt

Copy file name to clipboard
+24Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package g0801_0900.s0870_advantage_shuffle
2+
3+
import org.hamcrest.CoreMatchers.equalTo
4+
import org.hamcrest.MatcherAssert.assertThat
5+
import org.junit.jupiter.api.Test
6+
7+
internal class SolutionTest {
8+
@Test
9+
fun advantageCount() {
10+
assertThat(
11+
Solution().advantageCount(intArrayOf(2, 7, 11, 15), intArrayOf(1, 10, 4, 11)),
12+
equalTo(intArrayOf(2, 11, 7, 15))
13+
)
14+
}
15+
16+
@Test
17+
fun advantageCount2() {
18+
assertThat(
19+
Solution()
20+
.advantageCount(intArrayOf(12, 24, 8, 32), intArrayOf(13, 25, 32, 11)),
21+
equalTo(intArrayOf(24, 32, 8, 12))
22+
)
23+
}
24+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.