Cấu trúc dữ liệu với Kotlin: Leetcode (P2)
Tiếp nối chuỗi các bài về kiến thức Cấu trúc dữ liệu & Giải thuật trong ngôn ngữ Kotlin chúng ta đến với các bài tập về LinkedList, Stack, Queue nhé!
LinkedList, Stack, Queue
Remove Duplicates from Sorted List
Link LeetCode: https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/
class ListNode(var `val`: Int, var next: ListNode? = null)
fun deleteDuplicates(head: ListNode?): ListNode? {
if (head == null) {
return null
}
val dummyNode = ListNode(0)
dummyNode.next = head
var currentNode = head
var prevNode = dummyNode
while (currentNode != null) {
if (currentNode.next != null && currentNode.`val` == currentNode.next!!.`val`) {
while (currentNode?.next != null && currentNode?.`val` == currentNode?.next!!.`val`) {
currentNode = currentNode.next
}
prevNode.next = currentNode
}
prevNode = prevNode.next!!
currentNode = currentNode?.next
}
return dummyNode.next
}Hướng dẫn giải bài Remove Duplicated from Sorted List bằng Kotlin – Android Mastery
Number of Students Unable to Eat Lunch
Link LeetCode: https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/description
fun countStudents(students: IntArray, sandwiches: IntArray): Int {
val studentsDeque = ArrayDeque<Int>()
val sandwichesDeque = ArrayDeque<Int>()
// Convert the arrays to deques
for (student in students) {
studentsDeque.addLast(student)
}
for (sandwich in sandwiches) {
sandwichesDeque.addLast(sandwich)
}
var count = 0
while (studentsDeque.isNotEmpty()) {
if (studentsDeque.first() == sandwichesDeque.first()) {
studentsDeque.removeFirst()
sandwichesDeque.removeFirst()
count = 0
} else {
count++
studentsDeque.addLast(studentsDeque.removeFirst())
}
if (count == studentsDeque.size) {
return count
}
}
return 0
}Hướng dẫn giải Number of Students Unable to Earn Lunch bằng Kotlin DeQueue
Set, Map
Roman to Integer
Link LeetCode: https://leetcode.com/problems/roman-to-integer/description/
fun romanToInt(s: String): Int {
val m = hashMapOf(
"I" to 1,
"IV" to 4,
"V" to 5,
"IX" to 9,
"X" to 10,
"XL" to 40,
"L" to 50,
"XC" to 90,
"C" to 100,
"CD" to 400,
"D" to 500,
"CM" to 900,
"M" to 1000
)
var res = 0
var i = 0
while (i < s.length) {
val a = if (i < s.length - 1) s.substring(i, i + 2) else ""
val b = s[i].toString()
if (m.containsKey(a)) {
res += m[a]!!
i += 2
} else {
res += m[b]!!
i++
}
}
return res
}Hướng dẫn giải bài tập Roman to Integer bằng ngôn ngữ Kotlin – Android Mastery
Ransom Note
Link LeetCode: https://leetcode.com/problems/ransom-note/description/
fun canConstruct(ransomNote: String, magazine: String): Boolean {
val count = IntArray(26)
for (ch in magazine) {
count[ch - 'a']++
}
for (ch in ransomNote) {
val value = ch - 'a'
if (count[value] <= 0) return false
count[value]--
}
return true
}Hướng dẫn giải Ransom Note sử dụng ngôn ngữ Kotlin – Android Mastery
Find All Numbers Disappeared in an Array
LeetCode Link: https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/
fun findDisappearedNumbers(nums: IntArray): List<Int> {
val list = mutableListOf<Int>()
var idx: Int
for (i in nums.indices) {
idx = if (nums[i] < 0) nums[i] * -1 - 1 else nums[i] - 1
if (nums[idx] > 0) {
nums[idx] = -nums[idx]
}
}
for (i in nums.indices) {
if (nums[i] > 0) {
list.add(i + 1)
}
}
return list
}Hướng dẫn giải bài tập Find All Numbers Disappeared in an Array – Android Mastery
Subarray Sum Equals K
LeetCode Link: https://leetcode.com/problems/subarray-sum-equals-k/description/
fun subarraySum(nums: IntArray, k: Int): Int {
val map = HashMap<Int, Int>()
map[0] = 1
var count = 0
var sum = 0
for (num in nums) {
sum += num
count += map[sum-k] ?: 0
map[sum] = (map[sum] ?: 0) + 1
}
return count
}Hướng dẫn giải bài tập Sub Array Sum Equals K bằng ngôn ngữ Kotlin – Android Mastery
Trên đây là các hướng dẫn giải của mình cho một số bài tập LeetCode đơn giản ứng dụng những cấu trúc dữ liệu thường dùng nhất của ngôn ngữ lập trình Kotlin. Nếu các bạn có nhu cầu tìm hiểu sâu hơn, hiểu rõ ràng hơn về các phương pháp tiếp cận đề bài, phân tích và giải thì có thể tham khảo qua khóa học Android Mastery của mình nhé. Trong khóa học này mình sẽ đi giải thích tường tận mọi kiến thức cho một người học lập trình Android từ tay mơ Kotlin đến Master Android Development.
Chúc các bạn sớm thành công với mục tiêu học tập!
