/
Week 4 @ 2025 算法周记【差分数组 + 双指针数组 + 复习】
In progress
Week 4 @ 2025 算法周记【差分数组 + 双指针数组 + 复习】
- Bryan
Owned by Bryan
差分数组
LC 370. Range Addition 范围加法 [Premium]
https://leetcode.com/problems/range-addition/ https://www.lintcode.com/problem/903/
/**
* @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 航班预订统计
https://leetcode.com/problems/corporate-flight-bookings/description/
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 拼车
https://leetcode.com/problems/car-pooling/description/
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 转置矩阵
https://leetcode.com/problems/transpose-matrix/
LC 14. Longest Common Prefix 最长公共前缀
https://leetcode.com/problems/longest-common-prefix/description/
复习
LC 23. Merge k Sorted Lists 合并 K 个有序链表
https://leetcode.com/problems/merge-k-sorted-lists/
LC 378. Kth Smallest Element in a Sorted Matrix 有序矩阵中第 K 小的元素
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/
合并 k 个有序列表 / 堆（只利用了单向递增）
略
二分
, multiple selections available,