Cấu trúc dữ liệu với Kotlin: Thực hành Leetcode (P1)
Trong bài viết này chúng ta sẽ thực hiện giải các bài tập Leetcode level easy, medium liên quan đến chủ đề Array, String. Đây là các dạng cấu trúc dữ liệu rất thường được sử dụng trong quá trình phát triển ứng dụng Android. Bạn hãy học thật kỹ nhé!
Array, String
Longest Common Prefix
https://leetcode.com/problems/longest-common-prefix/description/
LeetCode Practice
fun longestCommonPrefix(strs: List<String>): String {
if (strs.isEmpty()) return ""
if (strs.size == 1) return strs[0]
val firstStr = strs[0]
var ret = ""
for (i in firstStr.indices) {
var fullMatched = true
for (j in 1 until strs.size) {
if (strs[j].length <= i || strs[j][i] != firstStr[i]) {
fullMatched = false
break
}
}
if (fullMatched) {
ret += firstStr[i]
} else {
break
}
}
return ret
}Merge Sorted Array
https://leetcode.com/problems/merge-sorted-array/description
LeetCode Practice
fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
var i = n + m - 1
var i1 = m - 1
var i2 = n - 1
while (i1 >= 0 && i2 >= 0) {
if (nums1[i1] < nums2[i2]) {
nums1[i] = nums2[i2]
i2--
} else {
nums1[i] = nums1[i1]
i1--
}
i--
}
while (i2 >= 0) {
nums1[i2] = nums2[i2]
i2--
}
println(nums1.toList())
}Best Time To Buy Sell Stock II
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
LeetCode Practice
fun maxProfit(prices: IntArray): Int {
if (prices.size < 2) return 0
var buyPrice = prices[0]
var state = 0 // 0 is idle, 1 is holding
var profit = 0
for (i in 1 until prices.size) {
if (state == 0) {
if (buyPrice < prices[i]) {
state = 1
} else {
buyPrice = prices[i]
}
} else {
if (prices[i] < prices[i - 1]) {
profit += (prices[i - 1] - buyPrice)
buyPrice = prices[i]
state = 0
}
}
}
if (state == 1) {
profit += (prices.last() - buyPrice)
}
return profit
}
