/
Week 4 @ 2025 算法周记【差分数组 + 双指针数组 + 复习】
In progress
Week 4 @ 2025 算法周记【差分数组 + 双指针数组 + 复习】
- Bryan
Owned by Bryan
差分数组
LC 370. Range Addition 范围加法 [Premium]
Range Addition - LeetCode LintCode 炼码 - 更高效的学习体验！
/**
* @param length: the length of the array
* @param updates: update operations
* @return: the modified array after all k operations were executed
*/
func GetModifiedArray(length int, updates [][]int) []int {
diff := make([]int, length)
for _, update := range updates {
startIndex, endIndex, inc := update[0], update[1], update[2]
diff[startIndex] += inc
if endIndex+1 < length {
diff[endIndex+1] -= inc
}
}
result := make([]int, length)
result[0] = diff[0]
for i := 1; i < length; i++ {
result[i] = result[i-1] + diff[i]
}
return result
}LC 1109. Corporate Flight Bookings 航班预订统计
Corporate Flight Bookings - LeetCode
func corpFlightBookings(bookings [][]int, n int) []int {
diff := make([]int, n)
for _, booking := range bookings {
first, last, seats := booking[0], booking[1], booking[2]
// NOTE: first & last is 1-based
diff[first-1] += seats
if last < n {
diff[last] -= seats
}
}
result := make([]int, n)
result[0] = diff[0]
for i := 1; i < n; i++ {
result[i] = result[i-1] + diff[i]
}
return result
}LC 1094. Car Pooling 拼车
func carPooling(trips [][]int, capacity int) bool {
diffCar := make([]int, 1005)
for _, trip := range trips {
numPassengers, from, to := trip[0], trip[1], trip[2]
diffCar[from] += numPassengers
diffCar[to] -= numPassengers
current := 0
for _, d := range diffCar {
current += d
if current > capacity {
return false
}
}
}
return true
}双指针数组
LC 867. Transpose Matrix 转置矩阵
LC 14. Longest Common Prefix 最长公共前缀
Longest Common Prefix - LeetCode
复习
LC 23. Merge k Sorted Lists 合并 K 个有序链表
Merge k Sorted Lists - LeetCode
LC 378. Kth Smallest Element in a Sorted Matrix 有序矩阵中第 K 小的元素
Kth Smallest Element in a Sorted Matrix - LeetCode
合并 k 个有序列表 / 堆（只利用了单向递增）
略
二分
, multiple selections available,