Week 10 @ 2025 算法周记【二分搜索】
- 1 二分搜索
- 1.1 LC 704. Binary Search 二分查找
- 1.2 LC 34. Find First and Last Position of Element in Sorted Array 在排序数组中找元素的第一个和最后一个位置
- 1.3 LC 875. Koko Eating Bananas 爱吃香蕉的珂珂
- 1.4 LC 1011. Capacity To Ship Packages Within D Days 在 D 天内送达包裹的能力
- 1.5 LC 410. Split Array Largest Sum 分割数组的最大值
- 1.6 LC 566. Reshape the Matrix 重塑矩阵
- 1.7 LC 74. Search a 2D Matrix 搜索二维矩阵
二分搜索
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 在排序数组中找元素的第一个和最后一个位置
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
}
, multiple selections available,