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 e13f8d2

Browse filesBrowse files
ThanhNITThanhNIT
authored
Added tasks 854, 855, 856, 857
1 parent b307084 commit e13f8d2
Copy full SHA for e13f8d2

File tree

13 files changed

+442
-0
lines changed
Filter options

13 files changed

+442
-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
| 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
17201720
| 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
17211721
| 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
1722+
| 0857 |[Score of Parentheses](src/main/kotlin/g0801_0900/s0857_minimum_cost_to_hire_k_workers/Solution.kt)| Hard | Array, Sorting, Greedy, Heap_Priority_Queue | 302 | 100.00
1723+
| 0856 |[Score of Parentheses](src/main/kotlin/g0801_0900/s0856_score_of_parentheses/Solution.kt)| Medium | String, Stack | 129 | 84.62
1724+
| 0855 |[Exam Room](src/main/kotlin/g0801_0900/s0855_exam_room/ExamRoom.kt)| Medium | Design, Ordered_Set | 644 | 83.33
1725+
| 0854 |[K-Similar Strings](src/main/kotlin/g0801_0900/s0854_k_similar_strings/Solution.kt)| Hard | String, Breadth_First_Search | 136 | 100.00
17221726
| 0853 |[Car Fleet](src/main/kotlin/g0801_0900/s0853_car_fleet/Solution.kt)| Medium | Array, Sorting, Stack, Monotonic_Stack | 757 | 85.29
17231727
| 0852 |[Peak Index in a Mountain Array](src/main/kotlin/g0801_0900/s0852_peak_index_in_a_mountain_array/Solution.kt)| Easy | Array, Binary_Search, Binary_Search_I_Day_2 | 433 | 94.29
17241728
| 0851 |[Loud and Rich](src/main/kotlin/g0801_0900/s0851_loud_and_rich/Solution.kt)| Medium | Array, Depth_First_Search, Graph, Topological_Sort | 347 | 100.00

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

Copy file name to clipboard
+54Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package g0801_0900.s0854_k_similar_strings
2+
3+
// #Hard #String #Breadth_First_Search #2023_03_31_Time_136_ms_(100.00%)_Space_33.6_MB_(100.00%)
4+
5+
class Solution {
6+
fun kSimilarity(a: String, b: String): Int {
7+
var ans = 0
8+
val achars = a.toCharArray()
9+
val bchars = b.toCharArray()
10+
ans += getAllPerfectMatches(achars, bchars)
11+
for (i in achars.indices) {
12+
if (achars[i] == bchars[i]) {
13+
continue
14+
}
15+
return ans + checkAllOptions(achars, bchars, i, b)
16+
}
17+
return ans
18+
}
19+
20+
private fun checkAllOptions(achars: CharArray, bchars: CharArray, i: Int, b: String): Int {
21+
var ans = Int.MAX_VALUE
22+
for (j in i + 1 until achars.size) {
23+
if (achars[j] == bchars[i] && achars[j] != bchars[j]) {
24+
swap(achars, i, j)
25+
ans = Math.min(ans, 1 + kSimilarity(String(achars), b))
26+
swap(achars, i, j)
27+
}
28+
}
29+
return ans
30+
}
31+
32+
private fun getAllPerfectMatches(achars: CharArray, bchars: CharArray): Int {
33+
var ans = 0
34+
for (i in achars.indices) {
35+
if (achars[i] == bchars[i]) {
36+
continue
37+
}
38+
for (j in i + 1 until achars.size) {
39+
if (achars[j] == bchars[i] && bchars[j] == achars[i]) {
40+
swap(achars, i, j)
41+
ans++
42+
break
43+
}
44+
}
45+
}
46+
return ans
47+
}
48+
49+
private fun swap(a: CharArray, i: Int, j: Int) {
50+
val temp = a[i]
51+
a[i] = a[j]
52+
a[j] = temp
53+
}
54+
}

‎src/main/kotlin/g0801_0900/s0854_k_similar_strings/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+
854\. K-Similar Strings
2+
3+
Hard
4+
5+
Strings `s1` and `s2` are `k`**\-similar** (for some non-negative integer `k`) if we can swap the positions of two letters in `s1` exactly `k` times so that the resulting string equals `s2`.
6+
7+
Given two anagrams `s1` and `s2`, return the smallest `k` for which `s1` and `s2` are `k`**\-similar**.
8+
9+
**Example 1:**
10+
11+
**Input:** s1 = "ab", s2 = "ba"
12+
13+
**Output:** 1
14+
15+
**Explanation:** The two string are 1-similar because we can use one swap to change s1 to s2: "ab" --> "ba".
16+
17+
**Example 2:**
18+
19+
**Input:** s1 = "abc", s2 = "bca"
20+
21+
**Output:** 2
22+
23+
**Explanation:** The two strings are 2-similar because we can use two swaps to change s1 to s2: "abc" --> "bac" --> "bca".
24+
25+
**Constraints:**
26+
27+
* `1 <= s1.length <= 20`
28+
* `s2.length == s1.length`
29+
* `s1` and `s2` contain only lowercase letters from the set `{'a', 'b', 'c', 'd', 'e', 'f'}`.
30+
* `s2` is an anagram of `s1`.

‎src/main/kotlin/g0801_0900/s0855_exam_room/ExamRoom.kt

Copy file name to clipboard
+84Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package g0801_0900.s0855_exam_room
2+
3+
// #Medium #Design #Ordered_Set #2023_03_31_Time_644_ms_(83.33%)_Space_40.4_MB_(100.00%)
4+
5+
import java.util.Objects
6+
7+
class ExamRoom() {
8+
private class Node(var `val`: Int, map: MutableMap<Int?, Node>) {
9+
var pre: Node? = null
10+
var next: Node? = null
11+
12+
init {
13+
map[`val`] = this
14+
}
15+
16+
fun insert(left: Node?): Int {
17+
val right = left!!.next
18+
left.next = this
19+
right!!.pre = this
20+
next = right
21+
pre = left
22+
return `val`
23+
}
24+
25+
fun delete() {
26+
val left = pre
27+
val right = next
28+
left!!.next = right
29+
right!!.pre = left
30+
}
31+
}
32+
33+
private val map: MutableMap<Int?, Node> = HashMap()
34+
private val head = Node(-1, map)
35+
private val tail = Node(-1, map)
36+
private var n = 0
37+
38+
init {
39+
head.next = tail
40+
tail.pre = head
41+
}
42+
43+
constructor(n: Int) : this() {
44+
this.n = n
45+
}
46+
47+
fun seat(): Int {
48+
val right = n - 1 - tail.pre!!.`val`
49+
val left = head.next!!.`val`
50+
var max = 0
51+
var maxAt = -1
52+
var maxAtLeft: Node? = null
53+
var cur = tail.pre
54+
while (cur !== head && cur!!.pre !== head) {
55+
val pre = cur!!.pre
56+
val at = (cur.`val` + pre!!.`val`) / 2
57+
val distance = at - pre.`val`
58+
if (distance >= max) {
59+
maxAtLeft = pre
60+
max = distance
61+
maxAt = at
62+
}
63+
cur = cur.pre
64+
}
65+
if (head.next === tail || left >= max && left >= right) {
66+
return Node(0, map).insert(head)
67+
}
68+
return if (right > max) {
69+
Node(n - 1, map).insert(tail.pre)
70+
} else Node(maxAt, map).insert(Objects.requireNonNull(maxAtLeft))
71+
}
72+
73+
fun leave(p: Int) {
74+
map[p]!!.delete()
75+
map.remove(p)
76+
}
77+
}
78+
79+
/*
80+
* Your ExamRoom object will be instantiated and called as such:
81+
* var obj = ExamRoom(n)
82+
* var param_1 = obj.seat()
83+
* obj.leave(p)
84+
*/

‎src/main/kotlin/g0801_0900/s0855_exam_room/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+
855\. Exam Room
2+
3+
Medium
4+
5+
There is an exam room with `n` seats in a single row labeled from `0` to `n - 1`.
6+
7+
When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number `0`.
8+
9+
Design a class that simulates the mentioned exam room.
10+
11+
Implement the `ExamRoom` class:
12+
13+
* `ExamRoom(int n)` Initializes the object of the exam room with the number of the seats `n`.
14+
* `int seat()` Returns the label of the seat at which the next student will set.
15+
* `void leave(int p)` Indicates that the student sitting at seat `p` will leave the room. It is guaranteed that there will be a student sitting at seat `p`.
16+
17+
**Example 1:**
18+
19+
**Input** ["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"] [[10], [], [], [], [], [4], []]
20+
21+
**Output:** [null, 0, 9, 4, 2, null, 5]
22+
23+
**Explanation:**
24+
25+
ExamRoom examRoom = new ExamRoom(10);
26+
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
27+
examRoom.seat(); // return 9, the student sits at the last seat number 9.
28+
examRoom.seat(); // return 4, the student sits at the last seat number 4.
29+
examRoom.seat(); // return 2, the student sits at the last seat number 2.
30+
examRoom.leave(4);
31+
examRoom.seat(); // return 5, the student sits at the last seat number 5.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= n <= 10<sup>9</sup></code>
36+
* It is guaranteed that there is a student sitting at seat `p`.
37+
* At most <code>10<sup>4</sup></code> calls will be made to `seat` and `leave`.

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

Copy file name to clipboard
+29Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package g0801_0900.s0856_score_of_parentheses
2+
3+
// #Medium #String #Stack #2023_03_31_Time_129_ms_(84.62%)_Space_34_MB_(46.15%)
4+
5+
import java.util.Deque
6+
import java.util.LinkedList
7+
8+
class Solution {
9+
fun scoreOfParentheses(s: String): Int {
10+
val stack: Deque<Int> = LinkedList()
11+
for (element in s) {
12+
if (element == '(') {
13+
stack.push(-1)
14+
} else {
15+
var curr = 0
16+
while (stack.peek() != -1) {
17+
curr += stack.pop()
18+
}
19+
stack.pop()
20+
stack.push(if (curr == 0) 1 else curr * 2)
21+
}
22+
}
23+
var score = 0
24+
while (!stack.isEmpty()) {
25+
score += stack.pop()
26+
}
27+
return score
28+
}
29+
}

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

Copy file name to clipboard
+35Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
856\. Score of Parentheses
2+
3+
Medium
4+
5+
Given a balanced parentheses string `s`, return _the **score** of the string_.
6+
7+
The **score** of a balanced parentheses string is based on the following rule:
8+
9+
* `"()"` has score `1`.
10+
* `AB` has score `A + B`, where `A` and `B` are balanced parentheses strings.
11+
* `(A)` has score `2 * A`, where `A` is a balanced parentheses string.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "()"
16+
17+
**Output:** 1
18+
19+
**Example 2:**
20+
21+
**Input:** s = "(())"
22+
23+
**Output:** 2
24+
25+
**Example 3:**
26+
27+
**Input:** s = "()()"
28+
29+
**Output:** 2
30+
31+
**Constraints:**
32+
33+
* `2 <= s.length <= 50`
34+
* `s` consists of only `'('` and `')'`.
35+
* `s` is a balanced parentheses string.

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

Copy file name to clipboard
+43Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package g0801_0900.s0857_minimum_cost_to_hire_k_workers
2+
3+
// #Hard #Array #Sorting #Greedy #Heap_Priority_Queue
4+
// #2023_03_31_Time_302_ms_(100.00%)_Space_39.4_MB_(100.00%)
5+
6+
import java.util.PriorityQueue
7+
8+
class Solution {
9+
fun mincostToHireWorkers(quality: IntArray, wage: IntArray, k: Int): Double {
10+
val n = quality.size
11+
val workers = arrayOfNulls<Worker>(n)
12+
for (i in 0 until n) {
13+
workers[i] = Worker(wage[i], quality[i])
14+
}
15+
workers.sortBy { it!!.ratio() }
16+
val maxHeap = PriorityQueue { a: Int?, b: Int? ->
17+
Integer.compare(
18+
b!!, a!!
19+
)
20+
}
21+
var sumQuality = 0
22+
var result = Double.MAX_VALUE
23+
for (i in 0 until n) {
24+
val worker = workers[i]
25+
sumQuality += worker!!.quality
26+
maxHeap.add(worker.quality)
27+
if (maxHeap.size > k) {
28+
sumQuality -= maxHeap.remove()!!
29+
}
30+
val groupRatio = worker.ratio()
31+
if (maxHeap.size == k) {
32+
result = Math.min(sumQuality * groupRatio, result)
33+
}
34+
}
35+
return result
36+
}
37+
38+
internal class Worker(var wage: Int, var quality: Int) {
39+
fun ratio(): Double {
40+
return wage.toDouble() / quality
41+
}
42+
}
43+
}

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

Copy file name to clipboard
+35Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
856\. Score of Parentheses
2+
3+
Medium
4+
5+
Given a balanced parentheses string `s`, return _the **score** of the string_.
6+
7+
The **score** of a balanced parentheses string is based on the following rule:
8+
9+
* `"()"` has score `1`.
10+
* `AB` has score `A + B`, where `A` and `B` are balanced parentheses strings.
11+
* `(A)` has score `2 * A`, where `A` is a balanced parentheses string.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "()"
16+
17+
**Output:** 1
18+
19+
**Example 2:**
20+
21+
**Input:** s = "(())"
22+
23+
**Output:** 2
24+
25+
**Example 3:**
26+
27+
**Input:** s = "()()"
28+
29+
**Output:** 2
30+
31+
**Constraints:**
32+
33+
* `2 <= s.length <= 50`
34+
* `s` consists of only `'('` and `')'`.
35+
* `s` is a balanced parentheses string.

‎src/test/kotlin/g0801_0900/s0854_k_similar_strings/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.s0854_k_similar_strings
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 kSimilarity() {
10+
assertThat(Solution().kSimilarity("ab", "ba"), equalTo(1))
11+
}
12+
13+
@Test
14+
fun kSimilarity2() {
15+
assertThat(Solution().kSimilarity("abc", "bca"), equalTo(2))
16+
}
17+
}

0 commit comments

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