Week 4 @ 2025 算法周记【差分数组 + 双指针数组 + 复习】

/**
 * @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
}

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
}

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
}

func transpose(matrix [][]int) [][]int {
    m, n := len(matrix), len(matrix[0])
    result := make([][]int, n)
    for i := range result {
        result[i] = make([]int, m)
    }

    for i := range matrix {
        for j, v := range matrix[i] {
            result[j][i] = v
        }
    }

    return result
}

func longestCommonPrefix(strs []string) string {
    p := 0
    
outer:
    for {
        for _, str := range strs {
            if p >= len(str) {
                break outer
            }

            if str[:p+1] != strs[0][:p+1] {
                break outer
            }
         }

         p++
    }

    return strs[0][:p]
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    h := newHeap(len(lists))
    for _, l := range lists {
        if l != nil {
            heap.Push(h, l)
        }
    }

    dummy := &ListNode{}
    head := dummy

    for h.Len() != 0 {
        top := heap.Pop(h).(*ListNode)

        head.Next = top
        head = head.Next

        if top.Next != nil {
            heap.Push(h, top.Next)
            top.Next = nil
        }
    }

    return dummy.Next
}

type Heap []*ListNode

func newHeap(cap int) *Heap {
    h := make(Heap, 0, cap)
    return &h
}

func (h Heap) Len() int {
    return len(h)
}

func (h Heap) Less(i, j int) bool {
    return h[i].Val < h[j].Val
}

func (h Heap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *Heap) Push(x any) {
    *h = append(*h, x.(*ListNode))
}

func (h *Heap) Pop() any {
    l := len(*h)
    v := (*h)[l-1]
    *h = (*h)[:l-1]
    return v
}

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)

    // 二分：满足 count(mid) >= k 的最小值
    L, R := matrix[0][0], matrix[n-1][n-1]

    for L < R {
        mid := L + (R - L) / 2

        if count(matrix, mid) >= k {
            R = mid
        } else {
            L = mid + 1
        }
    }

    return L
}

// 返回 <=x 的元素数量 - O(n)
func count(matrix [][]int, x int) (c int) {
    n := len(matrix)

    i, j := 0, n-1

    for i < n && j >= 0 {
        if matrix[i][j] <= x {
            c += j+1
            i++
        } else {
            j--
        }
    }

    return c
}