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 9b79c85

Browse filesBrowse files
ThanhNITThanhNIT
authored
Added tasks 826, 827, 828, 829
1 parent ba90006 commit 9b79c85
Copy full SHA for 9b79c85

File tree

Expand file treeCollapse file tree

13 files changed

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

13 files changed

+437
-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
@@ -1299,6 +1299,7 @@ implementation 'com.github.javadev:leetcode-in-kotlin:1.10'
12991299

13001300
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
13011301
|-|-|-|-|-|-
1302+
| 0826 |[Most Profit Assigning Work](src/main/kotlin/g0801_0900/s0826_most_profit_assigning_work/Solution.kt)| Medium | Array, Sorting, Greedy, Binary_Search, Two_Pointers | 366 | 100.00
13021303
| 0436 |[Find Right Interval](src.save/main/kotlin/g0401_0500/s0436_find_right_interval/Solution.kt)| Medium | Array, Sorting, Binary_Search | 333 | 100.00
13031304

13041305
#### Day 12
@@ -1712,6 +1713,10 @@ implementation 'com.github.javadev:leetcode-in-kotlin:1.10'
17121713
| 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
17131714
| 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
17141715
| 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
1716+
| 0829 |[Consecutive Numbers Sum](src/main/kotlin/g0801_0900/s0829_consecutive_numbers_sum/Solution.kt)| Hard | Math, Enumeration | 151 | 100.00
1717+
| 0828 |[Count Unique Characters of All Substrings of a Given String](src/main/kotlin/g0801_0900/s0828_count_unique_characters_of_all_substrings_of_a_given_string/Solution.kt)| Hard | String, Hash_Table, Dynamic_Programming | 216 | 100.00
1718+
| 0827 |[Making A Large Island](src/main/kotlin/g0801_0900/s0827_making_a_large_island/Solution.kt)| Hard | Array, Depth_First_Search, Breadth_First_Search, Matrix, Union_Find | 985 | 100.00
1719+
| 0826 |[Most Profit Assigning Work](src/main/kotlin/g0801_0900/s0826_most_profit_assigning_work/Solution.kt)| Medium | Array, Sorting, Greedy, Binary_Search, Two_Pointers, Binary_Search_II_Day_11 | 366 | 100.00
17151720
| 0825 |[Friends Of Appropriate Ages](src/main/kotlin/g0801_0900/s0825_friends_of_appropriate_ages/Solution.kt)| Medium | Array, Sorting, Binary_Search, Two_Pointers | 278 | 100.00
17161721
| 0824 |[Goat Latin](src/main/kotlin/g0801_0900/s0824_goat_latin/Solution.kt)| Easy | String | 146 | 100.00
17171722
| 0823 |[Binary Trees With Factors](src/main/kotlin/g0801_0900/s0823_binary_trees_with_factors/Solution.kt)| Medium | Array, Hash_Table, Dynamic_Programming | 298 | 100.00

‎src/main/kotlin/g0801_0900/s0826_most_profit_assigning_work/Solution.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.s0826_most_profit_assigning_work
2+
3+
// #Medium #Array #Sorting #Greedy #Binary_Search #Two_Pointers #Binary_Search_II_Day_11
4+
// #2023_03_25_Time_366_ms_(100.00%)_Space_42.9_MB_(83.33%)
5+
6+
class Solution {
7+
fun maxProfitAssignment(difficulty: IntArray, profit: IntArray, worker: IntArray): Int {
8+
val n = 100000
9+
val maxProfit = IntArray(n)
10+
for (i in difficulty.indices) {
11+
maxProfit[difficulty[i]] = maxProfit[difficulty[i]].coerceAtLeast(profit[i])
12+
}
13+
for (i in 1 until n) {
14+
maxProfit[i] = maxProfit[i].coerceAtLeast(maxProfit[i - 1])
15+
}
16+
var sum = 0
17+
for (efficiency in worker) {
18+
sum += maxProfit[efficiency]
19+
}
20+
return sum
21+
}
22+
}

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

Copy file name to clipboard
+36Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
826\. Most Profit Assigning Work
2+
3+
Medium
4+
5+
You have `n` jobs and `m` workers. You are given three arrays: `difficulty`, `profit`, and `worker` where:
6+
7+
* `difficulty[i]` and `profit[i]` are the difficulty and the profit of the <code>i<sup>th</sup></code> job, and
8+
* `worker[j]` is the ability of <code>j<sup>th</sup></code> worker (i.e., the <code>j<sup>th</sup></code> worker can only complete a job with difficulty at most `worker[j]`).
9+
10+
Every worker can be assigned **at most one job**, but one job can be **completed multiple times**.
11+
12+
* For example, if three workers attempt the same job that pays `$1`, then the total profit will be `$3`. If a worker cannot complete any job, their profit is `$0`.
13+
14+
Return the maximum profit we can achieve after assigning the workers to the jobs.
15+
16+
**Example 1:**
17+
18+
**Input:** difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
19+
20+
**Output:** 100
21+
22+
**Explanation:** Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.
23+
24+
**Example 2:**
25+
26+
**Input:** difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
27+
28+
**Output:** 0
29+
30+
**Constraints:**
31+
32+
* `n == difficulty.length`
33+
* `n == profit.length`
34+
* `m == worker.length`
35+
* <code>1 <= n, m <= 10<sup>4</sup></code>
36+
* <code>1 <= difficulty[i], profit[i], worker[i] <= 10<sup>5</sup></code>

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

Copy file name to clipboard
+90Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
package g0801_0900.s0827_making_a_large_island
2+
3+
// #Hard #Array #Depth_First_Search #Breadth_First_Search #Matrix #Union_Find
4+
// #2023_03_25_Time_985_ms_(100.00%)_Space_92.1_MB_(33.33%)
5+
6+
class Solution {
7+
private lateinit var p: IntArray
8+
private lateinit var s: IntArray
9+
10+
private fun makeSet(x: Int, y: Int, rl: Int) {
11+
val a = x * rl + y
12+
p[a] = a
13+
s[a] = 1
14+
}
15+
16+
private fun comb(x1: Int, y1: Int, x2: Int, y2: Int, rl: Int) {
17+
var a = find(x1 * rl + y1)
18+
var b = find(x2 * rl + y2)
19+
if (a == b) {
20+
return
21+
}
22+
if (s[a] < s[b]) {
23+
val t = a
24+
a = b
25+
b = t
26+
}
27+
p[b] = a
28+
s[a] += s[b]
29+
}
30+
31+
private fun find(a: Int): Int {
32+
if (p[a] == a) {
33+
return a
34+
}
35+
p[a] = find(p[a])
36+
return p[a]
37+
}
38+
39+
fun largestIsland(grid: Array<IntArray>): Int {
40+
val rl = grid.size
41+
val cl = grid[0].size
42+
p = IntArray(rl * cl)
43+
s = IntArray(rl * cl)
44+
for (i in 0 until rl) {
45+
for (j in 0 until cl) {
46+
if (grid[i][j] == 0) {
47+
continue
48+
}
49+
makeSet(i, j, rl)
50+
if (i > 0 && grid[i - 1][j] == 1) {
51+
comb(i, j, i - 1, j, rl)
52+
}
53+
if (j > 0 && grid[i][j - 1] == 1) {
54+
comb(i, j, i, j - 1, rl)
55+
}
56+
}
57+
}
58+
var m = 0
59+
var t: Int
60+
val sz: HashMap<Int, Int> = HashMap()
61+
for (i in 0 until rl) {
62+
for (j in 0 until cl) {
63+
if (grid[i][j] == 0) {
64+
// find root, check if same and combine size
65+
t = 1
66+
if (i > 0 && grid[i - 1][j] == 1) {
67+
sz[find((i - 1) * rl + j)] = s[find((i - 1) * rl + j)]
68+
}
69+
if (j > 0 && grid[i][j - 1] == 1) {
70+
sz[find(i * rl + j - 1)] = s[find(i * rl + j - 1)]
71+
}
72+
if (i < rl - 1 && grid[i + 1][j] == 1) {
73+
sz[find((i + 1) * rl + j)] = s[find((i + 1) * rl + j)]
74+
}
75+
if (j < cl - 1 && grid[i][j + 1] == 1) {
76+
sz[find(i * rl + j + 1)] = s[find(i * rl + j + 1)]
77+
}
78+
for (`val` in sz.values) {
79+
t += `val`
80+
}
81+
m = m.coerceAtLeast(t)
82+
sz.clear()
83+
} else {
84+
m = m.coerceAtLeast(s[i * rl + j])
85+
}
86+
}
87+
}
88+
return m
89+
}
90+
}

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

Copy file name to clipboard
+40Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
827\. Making A Large Island
2+
3+
Hard
4+
5+
You are given an `n x n` binary matrix `grid`. You are allowed to change **at most one** `0` to be `1`.
6+
7+
Return _the size of the largest **island** in_ `grid` _after applying this operation_.
8+
9+
An **island** is a 4-directionally connected group of `1`s.
10+
11+
**Example 1:**
12+
13+
**Input:** grid = [[1,0],[0,1]]
14+
15+
**Output:** 3
16+
17+
**Explanation:** Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
18+
19+
**Example 2:**
20+
21+
**Input:** grid = [[1,1],[1,0]]
22+
23+
**Output:** 4
24+
25+
**Explanation:** Change the 0 to 1 and make the island bigger, only one island with area = 4.
26+
27+
**Example 3:**
28+
29+
**Input:** grid = [[1,1],[1,1]]
30+
31+
**Output:** 4
32+
33+
**Explanation:** Can't change any 0 to 1, only one island with area = 4.
34+
35+
**Constraints:**
36+
37+
* `n == grid.length`
38+
* `n == grid[i].length`
39+
* `1 <= n <= 500`
40+
* `grid[i][j]` is either `0` or `1`.

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

Copy file name to clipboard
+49Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package g0801_0900.s0828_count_unique_characters_of_all_substrings_of_a_given_string
2+
3+
// #Hard #String #Hash_Table #Dynamic_Programming
4+
// #2023_03_25_Time_216_ms_(100.00%)_Space_37.1_MB_(50.00%)
5+
6+
import java.util.Arrays
7+
8+
class Solution {
9+
fun uniqueLetterString(s: String): Int {
10+
// Store last index of a character.
11+
val lastCharIdx = IntArray(26)
12+
// Store last to last index of a character.
13+
// Eg. For ABA - lastCharIdx = 2, prevLastCharIdx = 0.
14+
val prevLastCharIdx = IntArray(26)
15+
Arrays.fill(lastCharIdx, -1)
16+
Arrays.fill(prevLastCharIdx, -1)
17+
val len = s.length
18+
val dp = IntArray(len)
19+
var account = 1
20+
dp[0] = 1
21+
lastCharIdx[s[0].code - 'A'.code] = 0
22+
prevLastCharIdx[s[0].code - 'A'.code] = 0
23+
for (i in 1 until len) {
24+
val ch = s[i]
25+
val chIdx = ch.code - 'A'.code
26+
val lastSeenIdx = lastCharIdx[chIdx]
27+
val prevLastIdx = prevLastCharIdx[chIdx]
28+
dp[i] = dp[i - 1] + 1
29+
if (lastSeenIdx == -1) {
30+
dp[i] += i
31+
} else {
32+
// Add count for curr index from index of last char appearance.
33+
dp[i] += i - lastSeenIdx - 1
34+
if (prevLastIdx == lastSeenIdx) {
35+
// if last char idx is the only appearance of the char from left so far,
36+
// substrings that overlap [0, lastSeenIdx] will need count to be discounted, as
37+
// current char will cause duplication.
38+
dp[i] -= lastSeenIdx + 1
39+
} else {
40+
dp[i] -= lastSeenIdx - prevLastIdx
41+
}
42+
}
43+
prevLastCharIdx[chIdx] = lastSeenIdx
44+
lastCharIdx[chIdx] = i
45+
account += dp[i]
46+
}
47+
return account
48+
}
49+
}

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

Copy file name to clipboard
+42Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
828\. Count Unique Characters of All Substrings of a Given String
2+
3+
Hard
4+
5+
Let's define a function `countUniqueChars(s)` that returns the number of unique characters on `s`.
6+
7+
* For example, calling `countUniqueChars(s)` if `s = "LEETCODE"` then `"L"`, `"T"`, `"C"`, `"O"`, `"D"` are the unique characters since they appear only once in `s`, therefore `countUniqueChars(s) = 5`.
8+
9+
Given a string `s`, return the sum of `countUniqueChars(t)` where `t` is a substring of `s`. The test cases are generated such that the answer fits in a 32-bit integer.
10+
11+
Notice that some substrings can be repeated so in this case you have to count the repeated ones too.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "ABC"
16+
17+
**Output:** 10
18+
19+
**Explanation:** All possible substrings are: "A","B","C","AB","BC" and "ABC".
20+
21+
Every substring is composed with only unique letters.
22+
23+
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
24+
25+
**Example 2:**
26+
27+
**Input:** s = "ABA"
28+
29+
**Output:** 8
30+
31+
**Explanation:** The same as example 1, except `countUniqueChars`("ABA") = 1.
32+
33+
**Example 3:**
34+
35+
**Input:** s = "LEETCODE"
36+
37+
**Output:** 92
38+
39+
**Constraints:**
40+
41+
* <code>1 <= s.length <= 10<sup>5</sup></code>
42+
* `s` consists of uppercase English letters only.

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

Copy file name to clipboard
+25Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package g0801_0900.s0829_consecutive_numbers_sum
2+
3+
// #Hard #Math #Enumeration #2023_03_25_Time_151_ms_(100.00%)_Space_33.6_MB_(100.00%)
4+
5+
class Solution {
6+
fun consecutiveNumbersSum(n: Int): Int {
7+
var ans = 0
8+
var i = 1
9+
while (i * i <= n) {
10+
if (n % i > 0) {
11+
i++
12+
continue
13+
}
14+
val j = n / i
15+
if (i % 2 == 1) {
16+
ans++
17+
}
18+
if (j != i && j % 2 == 1) {
19+
ans++
20+
}
21+
i++
22+
}
23+
return ans
24+
}
25+
}

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

Copy file name to clipboard
+33Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
829\. Consecutive Numbers Sum
2+
3+
Hard
4+
5+
Given an integer `n`, return _the number of ways you can write_ `n` _as the sum of consecutive positive integers._
6+
7+
**Example 1:**
8+
9+
**Input:** n = 5
10+
11+
**Output:** 2
12+
13+
**Explanation:** 5 = 2 + 3
14+
15+
**Example 2:**
16+
17+
**Input:** n = 9
18+
19+
**Output:** 3
20+
21+
**Explanation:** 9 = 4 + 5 = 2 + 3 + 4
22+
23+
**Example 3:**
24+
25+
**Input:** n = 15
26+
27+
**Output:** 4
28+
29+
**Explanation:** 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
30+
31+
**Constraints:**
32+
33+
* <code>1 <= n <= 10<sup>9</sup></code>

‎src/test/kotlin/g0801_0900/s0826_most_profit_assigning_work/SolutionTest.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.s0826_most_profit_assigning_work
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 maxProfitAssignment() {
10+
assertThat(
11+
Solution()
12+
.maxProfitAssignment(
13+
intArrayOf(2, 4, 6, 8, 10),
14+
intArrayOf(10, 20, 30, 40, 50),
15+
intArrayOf(4, 5, 6, 7)
16+
),
17+
equalTo(100)
18+
)
19+
}
20+
21+
@Test
22+
fun maxProfitAssignment2() {
23+
assertThat(
24+
Solution()
25+
.maxProfitAssignment(intArrayOf(85, 47, 57), intArrayOf(24, 66, 99), intArrayOf(40, 25, 25)),
26+
equalTo(0)
27+
)
28+
}
29+
}

0 commit comments

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