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 7793194

Browse filesBrowse files
ThanhNITThanhNIT
authored
Added tasks 862, 863, 865, 866
1 parent 2f9d469 commit 7793194
Copy full SHA for 7793194

File tree

13 files changed

+489
-0
lines changed
Filter options

13 files changed

+489
-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,7 +1719,11 @@ 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+
| 0866 |[Prime Palindrome](src/main/kotlin/g0801_0900/s0866_prime_palindrome/Solution.kt)| Medium | Math | 143 | 100.00
1723+
| 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
17221724
| 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
1725+
| 0863 |[All Nodes Distance K in Binary Tree](src/main/kotlin/g0801_0900/s0863_all_nodes_distance_k_in_binary_tree/Solution.kt)| Medium | Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree | 147 | 95.83
1726+
| 0862 |[Shortest Subarray with Sum at Least K](src/main/kotlin/g0801_0900/s0862_shortest_subarray_with_sum_at_least_k/Solution.kt)| Hard | Array, Binary_Search, Heap_Priority_Queue, Prefix_Sum, Sliding_Window, Queue, Monotonic_Queue | 563 | 84.62
17231727
| 0861 |[Score After Flipping Matrix](src/main/kotlin/g0801_0900/s0861_score_after_flipping_matrix/Solution.kt)| Medium | Array, Greedy, Matrix, Bit_Manipulation | 135 | 71.43
17241728
| 0860 |[Lemonade Change](src/main/kotlin/g0801_0900/s0860_lemonade_change/Solution.kt)| Easy | Array, Greedy, Programming_Skills_II_Day_17 | 413 | 86.96
17251729
| 0859 |[Buddy Strings](src/main/kotlin/g0801_0900/s0859_buddy_strings/Solution.kt)| Easy | String, Hash_Table | 149 | 91.01

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

Copy file name to clipboard
+34Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package g0801_0900.s0862_shortest_subarray_with_sum_at_least_k
2+
3+
// #Hard #Array #Binary_Search #Heap_Priority_Queue #Prefix_Sum #Sliding_Window #Queue
4+
// #Monotonic_Queue #2023_04_04_Time_563_ms_(84.62%)_Space_51.6_MB_(38.46%)
5+
6+
import java.util.Deque
7+
import java.util.LinkedList
8+
9+
class Solution {
10+
internal class Pair(var index: Int, var value: Long)
11+
12+
fun shortestSubarray(nums: IntArray, k: Int): Int {
13+
val n = nums.size
14+
val dq: Deque<Pair> = LinkedList()
15+
var ans = Int.MAX_VALUE
16+
var sum: Long = 0
17+
for (i in 0 until n) {
18+
sum += nums[i].toLong()
19+
// Keep dq in incrementing order
20+
while (!dq.isEmpty() && sum <= dq.peekLast().value) dq.removeLast()
21+
// Add current sum and index
22+
dq.add(Pair(i, sum))
23+
// Calculate your answer here
24+
if (sum >= k) ans = Math.min(ans, i + 1)
25+
26+
// Check if Contraction is possible or not
27+
while (!dq.isEmpty() && sum - dq.peekFirst().value >= k) {
28+
ans = ans.coerceAtMost(i - dq.peekFirst().index)
29+
dq.removeFirst()
30+
}
31+
}
32+
return if (ans == Int.MAX_VALUE) -1 else ans
33+
}
34+
}

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

Copy file name to clipboard
+31Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
862\. Shortest Subarray with Sum at Least K
2+
3+
Hard
4+
5+
Given an integer array `nums` and an integer `k`, return _the length of the shortest non-empty **subarray** of_ `nums` _with a sum of at least_ `k`. If there is no such **subarray**, return `-1`.
6+
7+
A **subarray** is a **contiguous** part of an array.
8+
9+
**Example 1:**
10+
11+
**Input:** nums = [1], k = 1
12+
13+
**Output:** 1
14+
15+
**Example 2:**
16+
17+
**Input:** nums = [1,2], k = 4
18+
19+
**Output:** -1
20+
21+
**Example 3:**
22+
23+
**Input:** nums = [2,-1,2], k = 3
24+
25+
**Output:** 3
26+
27+
**Constraints:**
28+
29+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
30+
* <code>-10<sup>5</sup> <= nums[i] <= 10<sup>5</sup></code>
31+
* <code>1 <= k <= 10<sup>9</sup></code>

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

Copy file name to clipboard
+58Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package g0801_0900.s0863_all_nodes_distance_k_in_binary_tree
2+
3+
// #Medium #Depth_First_Search #Breadth_First_Search #Tree #Binary_Tree
4+
// #2023_04_04_Time_147_ms_(95.83%)_Space_35.2_MB_(95.83%)
5+
6+
import com_github_leetcode.TreeNode
7+
8+
/*
9+
* Definition for a binary tree node.
10+
* class TreeNode(var `val`: Int = 0) {
11+
* var left: TreeNode? = null
12+
* var right: TreeNode? = null
13+
* }
14+
*/
15+
class Solution {
16+
private fun kFar(root: TreeNode?, k: Int, visited: TreeNode?, ls: MutableList<Int>) {
17+
if (root == null || k < 0 || root === visited) {
18+
return
19+
}
20+
if (k == 0) {
21+
ls.add(root.`val`)
22+
return
23+
}
24+
kFar(root.left, k - 1, visited, ls)
25+
kFar(root.right, k - 1, visited, ls)
26+
}
27+
28+
fun distanceK(root: TreeNode?, target: TreeNode?, k: Int): List<Int> {
29+
val ls: MutableList<Int> = ArrayList()
30+
if (k == 0) {
31+
ls.add(target!!.`val`)
32+
return ls
33+
}
34+
nodeToRoot(root, target!!, k, ls)
35+
return ls
36+
}
37+
38+
private fun nodeToRoot(root: TreeNode?, target: TreeNode, k: Int, ls: MutableList<Int>): Int {
39+
if (root == null) {
40+
return -1
41+
}
42+
if (root.`val` == target.`val`) {
43+
kFar(root, k, null, ls)
44+
return 1
45+
}
46+
val ld = nodeToRoot(root.left, target, k, ls)
47+
if (ld != -1) {
48+
kFar(root, k - ld, root.left, ls)
49+
return ld + 1
50+
}
51+
val rd = nodeToRoot(root.right, target, k, ls)
52+
if (rd != -1) {
53+
kFar(root, k - rd, root.right, ls)
54+
return rd + 1
55+
}
56+
return -1
57+
}
58+
}

‎src/main/kotlin/g0801_0900/s0863_all_nodes_distance_k_in_binary_tree/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+
863\. All Nodes Distance K in Binary Tree
2+
3+
Medium
4+
5+
Given the `root` of a binary tree, the value of a target node `target`, and an integer `k`, return _an array of the values of all nodes that have a distance_ `k` _from the target node._
6+
7+
You can return the answer in **any order**.
8+
9+
**Example 1:**
10+
11+
![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/28/sketch0.png)
12+
13+
**Input:** root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
14+
15+
**Output:** [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
16+
17+
**Example 2:**
18+
19+
**Input:** root = [1], target = 1, k = 3
20+
21+
**Output:** []
22+
23+
**Constraints:**
24+
25+
* The number of nodes in the tree is in the range `[1, 500]`.
26+
* `0 <= Node.val <= 500`
27+
* All the values `Node.val` are **unique**.
28+
* `target` is the value of one of the nodes in the tree.
29+
* `0 <= k <= 1000`

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

Copy file name to clipboard
+63Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package g0801_0900.s0865_smallest_subtree_with_all_the_deepest_nodes
2+
3+
// #Medium #Hash_Table #Depth_First_Search #Breadth_First_Search #Tree #Binary_Tree
4+
// #2023_04_04_Time_147_ms_(100.00%)_Space_35.1_MB_(55.56%)
5+
6+
import com_github_leetcode.TreeNode
7+
8+
/*
9+
* Example:
10+
* var ti = TreeNode(5)
11+
* var v = ti.`val`
12+
* Definition for a binary tree node.
13+
* class TreeNode(var `val`: Int) {
14+
* var left: TreeNode? = null
15+
* var right: TreeNode? = null
16+
* }
17+
*/
18+
class Solution {
19+
private var deepLevel = 0
20+
private var left: TreeNode? = null
21+
private var right: TreeNode? = null
22+
23+
fun subtreeWithAllDeepest(root: TreeNode?): TreeNode? {
24+
if (root == null || root.left == null && root.right == null) {
25+
return root
26+
}
27+
deep(root, 0)
28+
return if (right == null) {
29+
left
30+
} else {
31+
lca(root, left!!.`val`, right!!.`val`)
32+
}
33+
}
34+
35+
private fun lca(root: TreeNode?, left: Int, right: Int): TreeNode? {
36+
if (root == null) {
37+
return null
38+
}
39+
if (root.`val` == left || root.`val` == right) {
40+
return root
41+
}
42+
val leftLca: TreeNode? = lca(root.left, left, right)
43+
val rightLca: TreeNode? = lca(root.right, left, right)
44+
return if (leftLca != null && rightLca != null) {
45+
root
46+
} else leftLca ?: rightLca
47+
}
48+
49+
private fun deep(root: TreeNode?, level: Int) {
50+
if (root == null) {
51+
return
52+
}
53+
if (deepLevel < level) {
54+
deepLevel = level
55+
left = root
56+
right = null
57+
} else if (deepLevel == level) {
58+
right = root
59+
}
60+
deep(root.left, level + 1)
61+
deep(root.right, level + 1)
62+
}
63+
}

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

Copy file name to clipboard
+51Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
865\. Smallest Subtree with all the Deepest Nodes
2+
3+
Medium
4+
5+
Given the `root` of a binary tree, the depth of each node is **the shortest distance to the root**.
6+
7+
Return _the smallest subtree_ such that it contains **all the deepest nodes** in the original tree.
8+
9+
A node is called **the deepest** if it has the largest depth possible among any node in the entire tree.
10+
11+
The **subtree** of a node is a tree consisting of that node, plus the set of all descendants of that node.
12+
13+
**Example 1:**
14+
15+
![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/01/sketch1.png)
16+
17+
**Input:** root = [3,5,1,6,2,0,8,null,null,7,4]
18+
19+
**Output:** [2,7,4]
20+
21+
**Explanation:**
22+
23+
We return the node with value 2, colored in yellow in the diagram.
24+
25+
The nodes coloured in blue are the deepest nodes of the tree.
26+
27+
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.
28+
29+
**Example 2:**
30+
31+
**Input:** root = [1]
32+
33+
**Output:** [1]
34+
35+
**Explanation:** The root is the deepest node in the tree.
36+
37+
**Example 3:**
38+
39+
**Input:** root = [0,1,3,null,2]
40+
41+
**Output:** [2]
42+
43+
**Explanation:** The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.
44+
45+
**Constraints:**
46+
47+
* The number of nodes in the tree will be in the range `[1, 500]`.
48+
* `0 <= Node.val <= 500`
49+
* The values of the nodes in the tree are **unique**.
50+
51+
**Note:** This question is the same as 1123: [https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/](https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/)

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

Copy file name to clipboard
+58Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package g0801_0900.s0866_prime_palindrome
2+
3+
// #Medium #Math #2023_04_04_Time_143_ms_(100.00%)_Space_33.4_MB_(100.00%)
4+
5+
import kotlin.math.sqrt
6+
7+
@Suppress("NAME_SHADOWING")
8+
class Solution {
9+
private fun isPrime(n: Int): Boolean {
10+
if (n % 2 == 0) {
11+
return n == 2
12+
}
13+
var i = 3
14+
val s = sqrt(n.toDouble()).toInt()
15+
while (i <= s) {
16+
if (n % i == 0) {
17+
return false
18+
}
19+
i += 2
20+
}
21+
return true
22+
}
23+
24+
private fun next(num: Int): Int {
25+
val s = (num + 1).toString().toCharArray()
26+
var i = 0
27+
val n = s.size
28+
while (i < n shr 1) {
29+
while (s[i] != s[n - 1 - i]) {
30+
increment(s, n - 1 - i)
31+
}
32+
i++
33+
}
34+
return String(s).toInt()
35+
}
36+
37+
private fun increment(s: CharArray, i: Int) {
38+
var i = i
39+
while (s[i] == '9') {
40+
s[i--] = '0'
41+
}
42+
s[i]++
43+
}
44+
45+
fun primePalindrome(n: Int): Int {
46+
if (n <= 2) {
47+
return 2
48+
}
49+
var p = next(n - 1)
50+
while (!isPrime(p)) {
51+
if (p in 10000000..99999999) {
52+
p = 100000000
53+
}
54+
p = next(p)
55+
}
56+
return p
57+
}
58+
}

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

Copy file name to clipboard
+37Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
866\. Prime Palindrome
2+
3+
Medium
4+
5+
Given an integer n, return _the smallest **prime palindrome** greater than or equal to_ `n`.
6+
7+
An integer is **prime** if it has exactly two divisors: `1` and itself. Note that `1` is not a prime number.
8+
9+
* For example, `2`, `3`, `5`, `7`, `11`, and `13` are all primes.
10+
11+
An integer is a **palindrome** if it reads the same from left to right as it does from right to left.
12+
13+
* For example, `101` and `12321` are palindromes.
14+
15+
The test cases are generated so that the answer always exists and is in the range <code>[2, 2 * 10<sup>8</sup>]</code>.
16+
17+
**Example 1:**
18+
19+
**Input:** n = 6
20+
21+
**Output:** 7
22+
23+
**Example 2:**
24+
25+
**Input:** n = 8
26+
27+
**Output:** 11
28+
29+
**Example 3:**
30+
31+
**Input:** n = 13
32+
33+
**Output:** 101
34+
35+
**Constraints:**
36+
37+
* <code>1 <= n <= 10<sup>8</sup></code>

0 commit comments

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