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 00ce680

Browse filesBrowse files
ThanhNITThanhNIT
authored
Added tasks 887, 888, 889, 890, 891
1 parent 1e9c789 commit 00ce680
Copy full SHA for 00ce680

File tree

16 files changed

+499
-0
lines changed
Filter options

16 files changed

+499
-0
lines changed

‎README.md

Copy file name to clipboardExpand all lines: README.md
+5Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1725,6 +1725,11 @@ implementation 'com.github.javadev:leetcode-in-kotlin:1.11'
17251725
|------|----------------|-------------|-------------|----------|---------
17261726
| 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
17271727
| 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
1728+
| 0891 |[Sum of Subsequence Widths](src/main/kotlin/g0801_0900/s0891_sum_of_subsequence_widths/Solution.kt)| Hard | Array, Math, Sorting | 481 | 100.00
1729+
| 0890 |[Find and Replace Pattern](src/main/kotlin/g0801_0900/s0890_find_and_replace_pattern/Solution.kt)| Medium | Array, String, Hash_Table | 150 | 100.00
1730+
| 0889 |[Construct Binary Tree from Preorder and Postorder Traversal](src/main/kotlin/g0801_0900/s0889_construct_binary_tree_from_preorder_and_postorder_traversal/Solution.kt)| Medium | Array, Hash_Table, Tree, Binary_Tree, Divide_and_Conquer | 168 | 100.00
1731+
| 0888 |[Fair Candy Swap](src/main/kotlin/g0801_0900/s0888_fair_candy_swap/Solution.kt)| Easy | Array, Hash_Table, Sorting, Binary_Search | 318 | 100.00
1732+
| 0887 |[Super Egg Drop](src/main/kotlin/g0801_0900/s0887_super_egg_drop/Solution.kt)| Hard | Dynamic_Programming, Math, Binary_Search | 119 | 100.00
17281733
| 0886 |[Possible Bipartition](src/main/kotlin/g0801_0900/s0886_possible_bipartition/Solution.kt)| Medium | Depth_First_Search, Breadth_First_Search, Graph, Union_Find, Graph_Theory_I_Day_14_Graph_Theory | 397 | 100.00
17291734
| 0885 |[Spiral Matrix III](src/main/kotlin/g0801_0900/s0885_spiral_matrix_iii/Solution.kt)| Medium | Array, Matrix, Simulation | 265 | 100.00
17301735
| 0884 |[Uncommon Words from Two Sentences](src/main/kotlin/g0801_0900/s0884_uncommon_words_from_two_sentences/Solution.kt)| Easy | String, Hash_Table | 171 | 100.00

‎src/main/kotlin/g0801_0900/s0887_super_egg_drop/Solution.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.s0887_super_egg_drop
2+
3+
// #Hard #Dynamic_Programming #Math #Binary_Search
4+
// #2023_04_09_Time_119_ms_(100.00%)_Space_33_MB_(75.00%)
5+
6+
class Solution {
7+
fun superEggDrop(k: Int, n: Int): Int {
8+
val dp = IntArray(k + 1)
9+
var counter = 1
10+
while (true) {
11+
var temp = dp[0]
12+
for (i in 1 until dp.size) {
13+
val `val` = dp[i] + temp + 1
14+
temp = dp[i]
15+
dp[i] = `val`
16+
if (`val` >= n) {
17+
return counter
18+
}
19+
}
20+
counter += 1
21+
}
22+
}
23+
}

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

Copy file name to clipboard
+44Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
887\. Super Egg Drop
2+
3+
Hard
4+
5+
You are given `k` identical eggs and you have access to a building with `n` floors labeled from `1` to `n`.
6+
7+
You know that there exists a floor `f` where `0 <= f <= n` such that any egg dropped at a floor **higher** than `f` will **break**, and any egg dropped **at or below** floor `f` will **not break**.
8+
9+
Each move, you may take an unbroken egg and drop it from any floor `x` (where `1 <= x <= n`). If the egg breaks, you can no longer use it. However, if the egg does not break, you may **reuse** it in future moves.
10+
11+
Return _the **minimum number of moves** that you need to determine **with certainty** what the value of_ `f` is.
12+
13+
**Example 1:**
14+
15+
**Input:** k = 1, n = 2
16+
17+
**Output:** 2
18+
19+
**Explanation:**
20+
21+
Drop the egg from floor 1. If it breaks, we know that f = 0.
22+
23+
Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
24+
25+
If it does not break, then we know f = 2.
26+
27+
Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
28+
29+
**Example 2:**
30+
31+
**Input:** k = 2, n = 6
32+
33+
**Output:** 3
34+
35+
**Example 3:**
36+
37+
**Input:** k = 3, n = 14
38+
39+
**Output:** 4
40+
41+
**Constraints:**
42+
43+
* `1 <= k <= 100`
44+
* <code>1 <= n <= 10<sup>4</sup></code>

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

Copy file name to clipboard
+31Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package g0801_0900.s0888_fair_candy_swap
2+
3+
// #Easy #Array #Hash_Table #Sorting #Binary_Search
4+
// #2023_04_09_Time_318_ms_(100.00%)_Space_39_MB_(100.00%)
5+
6+
class Solution {
7+
fun fairCandySwap(aliceSizes: IntArray, bobSizes: IntArray): IntArray {
8+
var aSum = 0
9+
var bSum = 0
10+
val ans = IntArray(2)
11+
for (bar in aliceSizes) {
12+
aSum += bar
13+
}
14+
for (bar in bobSizes) {
15+
bSum += bar
16+
}
17+
val diff: Int = aSum - bSum
18+
val set: HashSet<Int> = HashSet()
19+
for (bar in aliceSizes) {
20+
set.add(bar)
21+
}
22+
for (bar in bobSizes) {
23+
if (set.contains(bar + diff / 2)) {
24+
ans[0] = bar + diff / 2
25+
ans[1] = bar
26+
break
27+
}
28+
}
29+
return ans
30+
}
31+
}

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

Copy file name to clipboard
+34Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
888\. Fair Candy Swap
2+
3+
Easy
4+
5+
Alice and Bob have a different total number of candies. You are given two integer arrays `aliceSizes` and `bobSizes` where `aliceSizes[i]` is the number of candies of the <code>i<sup>th</sup></code> box of candy that Alice has and `bobSizes[j]` is the number of candies of the <code>j<sup>th</sup></code> box of candy that Bob has.
6+
7+
Since they are friends, they would like to exchange one candy box each so that after the exchange, they both have the same total amount of candy. The total amount of candy a person has is the sum of the number of candies in each box they have.
8+
9+
Return a_n integer array_ `answer` _where_ `answer[0]` _is the number of candies in the box that Alice must exchange, and_ `answer[1]` _is the number of candies in the box that Bob must exchange_. If there are multiple answers, you may **return any** one of them. It is guaranteed that at least one answer exists.
10+
11+
**Example 1:**
12+
13+
**Input:** aliceSizes = [1,1], bobSizes = [2,2]
14+
15+
**Output:** [1,2]
16+
17+
**Example 2:**
18+
19+
**Input:** aliceSizes = [1,2], bobSizes = [2,3]
20+
21+
**Output:** [1,2]
22+
23+
**Example 3:**
24+
25+
**Input:** aliceSizes = [2], bobSizes = [1,3]
26+
27+
**Output:** [2,3]
28+
29+
**Constraints:**
30+
31+
* <code>1 <= aliceSizes.length, bobSizes.length <= 10<sup>4</sup></code>
32+
* <code>1 <= aliceSizes[i], bobSizes[j] <= 10<sup>5</sup></code>
33+
* Alice and Bob have a different total number of candies.
34+
* There will be at least one valid answer for the given input.

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

Copy file name to clipboard
+66Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package g0801_0900.s0889_construct_binary_tree_from_preorder_and_postorder_traversal
2+
3+
// #Medium #Array #Hash_Table #Tree #Binary_Tree #Divide_and_Conquer
4+
// #2023_04_09_Time_168_ms_(100.00%)_Space_35.5_MB_(75.00%)
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+
fun constructFromPrePost(preorder: IntArray, postorder: IntArray): TreeNode? {
20+
return if (preorder.isEmpty() || preorder.size != postorder.size) {
21+
null
22+
} else buildTree(preorder, 0, preorder.size - 1, postorder, 0, postorder.size - 1)
23+
}
24+
25+
private fun buildTree(
26+
preorder: IntArray,
27+
preStart: Int,
28+
preEnd: Int,
29+
postorder: IntArray,
30+
postStart: Int,
31+
postEnd: Int
32+
): TreeNode? {
33+
if (preStart > preEnd || postStart > postEnd) {
34+
return null
35+
}
36+
val data = preorder[preStart]
37+
val root = TreeNode(data)
38+
if (preStart == preEnd) {
39+
return root
40+
}
41+
var offset = postStart
42+
while (offset <= preEnd) {
43+
if (postorder[offset] == preorder[preStart + 1]) {
44+
break
45+
}
46+
offset++
47+
}
48+
root.left = buildTree(
49+
preorder,
50+
preStart + 1,
51+
preStart + offset - postStart + 1,
52+
postorder,
53+
postStart,
54+
offset
55+
)
56+
root.right = buildTree(
57+
preorder,
58+
preStart + offset - postStart + 2,
59+
preEnd,
60+
postorder,
61+
offset + 1,
62+
postEnd - 1
63+
)
64+
return root
65+
}
66+
}

‎src/main/kotlin/g0801_0900/s0889_construct_binary_tree_from_preorder_and_postorder_traversal/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+
889\. Construct Binary Tree from Preorder and Postorder Traversal
2+
3+
Medium
4+
5+
Given two integer arrays, `preorder` and `postorder` where `preorder` is the preorder traversal of a binary tree of **distinct** values and `postorder` is the postorder traversal of the same tree, reconstruct and return _the binary tree_.
6+
7+
If there exist multiple answers, you can **return any** of them.
8+
9+
**Example 1:**
10+
11+
![](https://assets.leetcode.com/uploads/2021/07/24/lc-prepost.jpg)
12+
13+
**Input:** preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
14+
15+
**Output:** [1,2,3,4,5,6,7]
16+
17+
**Example 2:**
18+
19+
**Input:** preorder = [1], postorder = [1]
20+
21+
**Output:** [1]
22+
23+
**Constraints:**
24+
25+
* `1 <= preorder.length <= 30`
26+
* `1 <= preorder[i] <= preorder.length`
27+
* All the values of `preorder` are **unique**.
28+
* `postorder.length == preorder.length`
29+
* `1 <= postorder[i] <= postorder.length`
30+
* All the values of `postorder` are **unique**.
31+
* It is guaranteed that `preorder` and `postorder` are the preorder traversal and postorder traversal of the same binary tree.

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

Copy file name to clipboard
+45Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package g0801_0900.s0890_find_and_replace_pattern
2+
3+
// #Medium #Array #String #Hash_Table #2023_04_10_Time_150_ms_(100.00%)_Space_35.9_MB_(11.11%)
4+
5+
import java.util.Collections
6+
7+
class Solution {
8+
fun findAndReplacePattern(words: Array<String>, pattern: String): List<String> {
9+
val finalans: MutableList<String> = ArrayList()
10+
if (pattern.length == 1) {
11+
Collections.addAll(finalans, *words)
12+
return finalans
13+
}
14+
for (word in words) {
15+
val check = CharArray(26)
16+
check.fill('1')
17+
val ans: HashMap<Char, Char> = HashMap()
18+
for (j in word.indices) {
19+
val pat = pattern[j]
20+
val wor = word[j]
21+
if (ans.containsKey(pat)) {
22+
if (ans[pat] == wor) {
23+
if (j == word.length - 1) {
24+
finalans.add(word)
25+
}
26+
} else {
27+
break
28+
}
29+
} else {
30+
if (j == word.length - 1 && check[wor.code - 'a'.code] == '1') {
31+
finalans.add(word)
32+
}
33+
if (check[wor.code - 'a'.code] != '1' && check[wor.code - 'a'.code] != pat) {
34+
break
35+
}
36+
if (check[wor.code - 'a'.code] == '1') {
37+
ans[pat] = wor
38+
check[wor.code - 'a'.code] = pat
39+
}
40+
}
41+
}
42+
}
43+
return finalans
44+
}
45+
}

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

Copy file name to clipboard
+30Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
890\. Find and Replace Pattern
2+
3+
Medium
4+
5+
Given a list of strings `words` and a string `pattern`, return _a list of_ `words[i]` _that match_ `pattern`. You may return the answer in **any order**.
6+
7+
A word matches the pattern if there exists a permutation of letters `p` so that after replacing every letter `x` in the pattern with `p(x)`, we get the desired word.
8+
9+
Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.
10+
11+
**Example 1:**
12+
13+
**Input:** words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
14+
15+
**Output:** ["mee","aqq"]
16+
17+
**Explanation:** "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. "ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to the same letter.
18+
19+
**Example 2:**
20+
21+
**Input:** words = ["a","b","c"], pattern = "a"
22+
23+
**Output:** ["a","b","c"]
24+
25+
**Constraints:**
26+
27+
* `1 <= pattern.length <= 20`
28+
* `1 <= words.length <= 50`
29+
* `words[i].length == pattern.length`
30+
* `pattern` and `words[i]` are lowercase English letters.

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

Copy file name to clipboard
+45Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package g0801_0900.s0891_sum_of_subsequence_widths
2+
3+
// #Hard #Array #Math #Sorting #2023_04_10_Time_481_ms_(100.00%)_Space_48.5_MB_(100.00%)
4+
5+
class Solution {
6+
// 1-6 (number of elements in between 1 and 6) = (6-1-1) = 4
7+
// length of sub seq 2 -> 4C0 3 -> 4C1 ; 4 -> 4c2 ; 5 -> 4C3 6 -> 4C4 4c0 + 4c1 + 4c2 + 4c3 +
8+
// 4c4 1+4+6+4+1=16
9+
// 1-5 3c0 + 3c1 + 3c2 + 3c3 = 8
10+
// 1-4 2c0 + 2c1 2c2 = 4
11+
// 1-3 1c0 + 1c1 = 2
12+
// 1-2 1c0 = 1
13+
/*
14+
16+8+4+2+1(for 1 as min) 8+4+2+1(for 2 as min) 4+2+1(for 3 as min) 2+1(for 4 as min) 1(for 5 as min)
15+
-1*nums[0]*31 + nums[1]*1 + nums[2]*2 + nums[3]*4 + nums[4]*8 + nums[5]*16
16+
-1*nums[1]*15 + nums[2]*1 +nums[3]*2 + nums[4]*4 + nums[5]*8
17+
-1*nums[2]*7 + nums[3]*1 + nums[4]*2 + nums[5]*4
18+
-1*nums[3]*3 + nums[4]*1 + nums[5]*2
19+
-1*nums[4]*1 + nums[5]*1
20+
21+
-nums[0]*31 + -nums[1]*15 - nums[2]*7 - nums[3]*3 - nums[4]*1
22+
nums[1]*1 + nums[2]*3 + nums[3]*7 + nums[4]*15 + nums[5]*31
23+
24+
(-1)*nums[0]*(pow[6-1-0]-1) + (-1)*nums[1]*(pow[6-1-1]-1) + (-1)*nums[2]*(pow[6-1-2]-1)
25+
... (-1)* nums[5]*(pow[6-1-5]-1)
26+
+ nums[1]*(pow[1]-1) + nums[2]*(pow[2]-1) + .... + nums[5]*(pow[5]-1)
27+
28+
(-1)*A[i]*(pow[l-1-i]-1) + A[i]*(pow[i]-1)
29+
*/
30+
fun sumSubseqWidths(nums: IntArray): Int {
31+
val mod = 1000000007
32+
nums.sort()
33+
val l = nums.size
34+
val pow = LongArray(l)
35+
pow[0] = 1
36+
for (i in 1 until l) {
37+
pow[i] = pow[i - 1] * 2 % mod
38+
}
39+
var res: Long = 0
40+
for (i in 0 until l) {
41+
res = (res + -1 * nums[i] * (pow[l - 1 - i] - 1) + nums[i] * (pow[i] - 1)) % mod
42+
}
43+
return res.toInt()
44+
}
45+
}

0 commit comments

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