Week 10 @ 2025 算法周记【二分搜索】

By Bryan
  • In progress
    • 3 min

    二分搜索

    LC 704. Binary Search 二分查找

    https://leetcode.com/problems/binary-search/description/?show=1

    func search(nums []int, target int) int { L, R := 0, len(nums) for L < R { mid := L + (R - L) / 2 if nums[mid] == target { return mid } else if nums[mid] < target { L = mid + 1 } else { R = mid } } return -1 }

    LC 34. Find First and Last Position of Element in Sorted Array 在排序数组中找元素的第一个和最后一个位置

    https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/?show=1

    func searchRange(nums []int, target int) []int { LB := leftBound(nums, target) if LB == len(nums) || nums[LB] != target { return []int{-1, -1} } UB := leftBound(nums, target + 1) - 1 return []int{LB, UB} } func leftBound(nums []int, target int) int { L, R := 0, len(nums) for L < R { mid := L + (R - L) / 2 if nums[mid] < target { L = mid+1 } else { R = mid } } return R }

    LC 875. Koko Eating Bananas 爱吃香蕉的珂珂 

    https://leetcode.com/problems/koko-eating-bananas/description/

    func minEatingSpeed(piles []int, h int) int { L, R := 1, 1_000_000_001 for L < R { mid := L + (R-L)/2 if getCount(piles, mid) <= h { R = mid } else { L = mid + 1 } } return R } func getCount(piles []int, k int) int { c := 0 for _, x := range piles { c += x / k if x % k != 0 { c++ } } return c }

    LC 1011. Capacity To Ship Packages Within D Days 在 D 天内送达包裹的能力

    https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/

    func shipWithinDays(weights []int, days int) int { L, R := getInit(weights) for L < R { mid := L + (R - L) / 2 if getNeedDays(weights, mid) <= days { R = mid } else { L = mid + 1 } } return R } func getInit(arr []int) (L, R int) { L, R = 0, 1 for _, x := range arr { L = max(L, x) R += x } return } func getNeedDays(weights []int, cap int) (days int) { remain := 0 for _, w := range weights { if remain < w { remain = cap days++ } remain -= w } return }

    LC 410. Split Array Largest Sum 分割数组的最大值

    https://leetcode.com/problems/split-array-largest-sum/description/

    func splitArray(nums []int, k int) int { L, R := getInit(nums) for L < R { mid := L + (R - L) / 2 if getSplitsCount(nums, mid) <= k { R = mid } else { L = mid + 1 } } return R } func getInit(arr []int) (L, R int) { L, R = 0, 1 for _, x := range arr { L = max(L, x) R += x } return } func getSplitsCount(nums []int, maxGroupSum int) (c int) { remain := 0 for _, num := range nums { if remain < num { remain = maxGroupSum c++ } remain -= num } return }

    LC 566. Reshape the Matrix 重塑矩阵

    https://leetcode.com/problems/reshape-the-matrix/description/

    func matrixReshape(mat [][]int, r int, c int) [][]int { m, n := len(mat), len(mat[0]) if m * n != r * c { // invalid return mat } newMatrix := createMatrix(r, c) i, j := 0, 0 next := func() { j++ if j >= c { i++ j = 0 } } for _, row := range mat { for _, v := range row { newMatrix[i][j] = v next() } } return newMatrix } func createMatrix(m, n int) [][]int { mat := make([][]int, m) for i := range mat { mat[i] = make([]int, n) } return mat }

    转换坐标

    func matrixReshape(mat [][]int, r int, c int) [][]int { n := len(mat[0]) // 如果想成功 reshape，元素个数应该相同 if r*c != len(mat)*n { return mat } res := make([][]int, r) for i := range res { res[i] = make([]int, c) } for i := 0; i < len(mat)*n; i++ { set(&res, i, get(&mat, i, n)) } return res } // 通过一维坐标访问二维数组中的元素 func get(matrix *[][]int, index int, n int) int { // 计算二维中的横纵坐标 i := index / n j := index % n return (*matrix)[i][j] } // 通过一维坐标设置二维数组中的元素 func set(matrix *[][]int, index int, value int) { n := len((*matrix)[0]) // 计算二维中的横纵坐标 i := index / n j := index % n (*matrix)[i][j] = value }

    LC 74. Search a 2D Matrix 搜索二维矩阵

    https://leetcode.com/problems/search-a-2d-matrix/description/

    func searchMatrix(matrix [][]int, target int) bool { m, n := len(matrix), len(matrix[0]) getValueByIndex := func(index int) int { i := index / n j := index % n return matrix[i][j] } L, R := 0, m*n for L < R { mid := L + (R - L) / 2 midValue := getValueByIndex(mid) if midValue == target { return true } else if midValue < target { L = mid + 1 } else { R = mid } } return false }

    Related content