TalkGo算法之美第四期

第四期来啦。本期主题是很常见的二分查找,也是一个很重要的数据结构。二分查找简单点说就是从有序的序列中通过不断的二分缩小查找范围,最终查找到我们想要的目标数据。

本期为期一个月(春节休息一周),每周一三五早上八点半左右更新。

第一周

周一: 704. 二分查找

先掌握最基本的最原始的二分查找吧

周三: 34. 在排序数组中查找元素的第一个和最后一个位置

如果存在重复元素,该怎么找到重复元素的最左和最右值?

周五: 74. 搜索二维矩阵

把数组换成矩阵呢?看看自己是不是真的活学活用二分

第二周

周一: 162. 寻找峰值

上周的二分算法适用于一个有序数组,对于无序数组竟然也可以使用二分,那二分的判断条件怎么定?

周三: 875. 爱吃香蕉的珂珂

给定数组并非有序,但查找判定条件有序,所以可以二分。

周五: 1011. 在 D 天内送达包裹的能力

还是有人不能灵活使用二分,那就再来一道和上一题类似的吧

第三周

周一: 1300. 转变数组后最接近目标值的数组和

Tips:双重二分

周三: 1631. 最小体力消耗路径

一题多解的好题,很值得一做。

周五: 1712. 将数组分成三个子数组的方案数

最后一题,来道hrad吧

参考资料

使用golang自带的二分搜索(可以直接看源码实现)

func search(nums []int, target int) int {
	// index:=  sort.Search(len(nums), func(i int) bool { return nums[i] >= target })
	index:= sort.SearchInts(nums,target)
	if index >= len(nums) || nums[index] !=target{
		return -1
	}
	return index
}
2赞

打卡,704. 二分查找

虽然简单,二分还是要注重写对细节,没能一次性写完通过,改了一小下

class Solution {
   public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) {
            return -1;
        }
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;  // 注意 mid - 1
            } else if (nums[mid] < target) {
                left = mid + 1;  // 注意 mid + 1
            } else {
                return mid;
            }
        }
        return -1;
    }
};

也可以二分法做

func search(nums []int, target int) int {
	idx := sort.SearchInts(nums, target)
	if idx >= len(nums) || nums[idx] != target {
		return -1
	}
	return idx
}

之前用过好多次 go 标准库的 binary_search 操作,今天写了下还是忘了,其实后来一看标准库实现是一个 “升序 lower_bound 操作” 。。。

利用二分查找进行滑窗内元素的更新

周三: 34. 在排序数组中查找元素的第一个和最后一个位置

直接使用库函数

func searchRange(nums []int, target int) []int {
	left := sort.SearchInts(nums, target) // 查询最左边比>= target的数。
	if left == len(nums) || nums[left]!=target { // 有可能不等需要判断
		return []int{-1,-1}
	}
	right := sort.SearchInts(nums, target+1) // 查询target最右边的右边一个位置。
	return []int{left,right-1} // 这里要减1
}
1赞

[ 在排序数组中查找元素的第一个和最后一个位置](力扣)

// 我是抄楼上的
func searchRange(nums []int, target int) []int {
	idx := sort.SearchInts(nums, target)
	if idx >= len(nums) || nums[idx] != target {
		return []int{-1, -1}
	}
	return []int{idx, sort.SearchInts(nums, target+1) - 1}
}

二分加滑窗解决

// 力扣
// 由于二分专题就用二分法来求解吧
// 实际上矩阵大小 100 * 100 完全没有必要用二分

func searchMatrix(matrix [][]int, target int) bool {
	n, m := len(matrix), len(matrix[0])
	if matrix[n-1][m-1] < target || matrix[0][0] > target {
		return false
	}
	row := sort.Search(n, func(idx int) bool {
		return matrix[idx][0] >= target
	})
	if row < n && matrix[row][0] == target {
		return true
	}
	row--
	col := sort.SearchInts(matrix[row], target)
	if col >= m || matrix[row][col] != target {
		return false
	}
	return true
}

周五: 74. 搜索二维矩阵

/*
将二维矩阵看成是一维的 arr = append(matrix[0], matrix[1]... matrix[n-1]
相互转化工式:matrix[i][j] = arr[i*m+j]
arr[x] = matrix[x/m][x%m]
 */
func searchMatrix(matrix [][]int, target int) bool {
	n,m := len(matrix) ,len(matrix[0])
	ind := sort.Search(n*m, func(x int) bool {
		row, col := x/m, x%m
		return matrix[row][col]>=target
	})

	return ind<n*m &&  matrix[ind/m][ind%m]==target
}
1赞

[34] 在排序数组中查找元素的第一个和最后一个位置

转换题目,求区间 [target, target+1) 的下标

class Solution {
   public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lowerBound(nums, target);
        int right = lowerBound(nums, target + 1) - 1;
        if (right < nums.size() && nums[right] == target) {
            return {left, right};
        }
        return {-1, -1};
    }

    // 求小于等于 target 的左下标
    int lowerBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                right = mid - 1;  // 还是一步一步缩短范围
            }
        }
        return left;
    }
};

[74] 搜索二维矩阵

参考上面 [LightningBilly] 同学的题解

/*
将 n * m 二维矩阵看成是一维的 arr = [ matrix[0], matrix[1]... matrix[n-1] ]
相互转化工式:matrix[i][j] = arr[i * m + j]
arr[x] = matrix[x / m][x % m]
 */
class Solution {
   public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return false;
        }
        int n = matrix.size();
        int m = matrix[0].size();
        int left = 0, right = n * m - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midVal = matrix[mid / m][mid % m];
            if (midVal < target) {
                left = mid + 1;
            } else if (midVal > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

周一

func search(nums []int, target int) int {
  left, rigth := 0, len(nums)-1
  for left < rigth {
  	mid := (left+rigth)>>1
  	if nums[mid] >= target {
  		rigth = mid
  	}else {
  		left = mid+1
  	}
  }
  if nums[left] == target {
  	return left
  }
  return -1
}

周三

func searchRange(nums []int, target int) []int {
	res := []int{-1,-1}
	left, rigth := 0, len(nums)-1
	for left < rigth {
		mid := (left+rigth) >> 1
		if nums[mid] >= target {
			rigth = mid
		}else {
			left = mid+1
		}
	}
	if nums[left] == target {
		res[0] = left
	}

	left, rigth = 0, len(nums)-1
	for left < rigth {
		mid := (left+rigth+1) >> 1
		if nums[mid] <= target {
			left = mid
		}else {
			rigth = mid-1
		}
	}
	if nums[rigth] == target {
		res[1] = rigth
	}

	return res
}

周一: 162. 寻找峰值


func findPeakElement(nums []int) int {
	low, high := 0, len(nums)-1
	best := -1 // 默认无解,也可以根据需要置其他特殊值
	for low <= high {
		mid := low + (high-low)/2

		if mid == 0 {
			if mid+1 == len(nums) ||  nums[mid] > nums[mid+1] {
				best = mid
				break
			} 
			best, low = mid+1, mid+1
		} else if mid == len(nums)-1 {
			if nums[mid-1] < nums[mid] {
				best = mid
				break
			}
			best, high = mid-1, mid-1
		} else if nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1] {
			best = mid
			break
		} else if nums[mid-1] < nums[mid] {
			best, low = mid, mid+1
		} else if nums[mid-1] > nums[mid] {
			best, high = mid-1, mid-1
		}

	}
	return best
}
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int i,l=nums.size();
        for(i=0;i<l;i++)
        {
            if(i && nums[i-1]>=nums[i])continue;
            if(i<l-1 && nums[i]<=nums[i+1])continue;
            return i;
        }
        
        return 0;
    }
};

常规二分做法:

func findPeakElement(nums []int) int {
	low :=0
	high := len(nums)
	for low < high {
		middle := (low + high)/2
		if middle >0 && nums[middle] > nums[middle-1]{
			low = middle+1
		}else {
			high = middle
		}
	}
    if low ==0{
        return low
    }
	return low-1
}

提升:三分做法,三分法可以用来查找凸函数的最大(小)值。详见wiki

func findPeakElement(nums []int) int {
	low :=0
	high := len(nums)
	for  high-low>1 {
		lmid := (low + high)/2
		rmid := (lmid + high)/2  // 对右侧区间取半
		if nums[lmid] >= nums[rmid]{
			high = rmid
		}else {
			low = lmid
		}
	}
    if high == len(nums) || nums[low] > nums[high]{ //由于本题存在假设边界不是完全的凸(凹)函数,需要做额外的判断
        return low
    }
	return high
}

// 二分法

//func findPeakElement(nums []int) int {
//	l, r := 0, len(nums)-1
//	for l < r {
//		mid := l + (r-l)/2
//		if mid + 1 < len(nums) && nums[mid+1] > nums[mid] {
//			l = mid + 1
//		} else {
//			r = mid
//		}
//	}
//	return l
//}

992. K 个不同整数的子数组

难度困难231收藏分享切换为英文接收动态反馈

给定一个正整数数组 A,如果 A 的某个子数组中不同整数的个数恰好为 K,则称 A 的这个连续、不一定独立的子数组为好子数组

(例如,[1,2,3,1,2] 中有 3 个不同的整数:12,以及 3。)

返回 A好子数组的数目。

思路

  • 先求包含k个不同字符的最长区间
  • 然后求固定右边界,包含k个不同字符的子数组个数

go

/*
 * @Description:
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-09 17:58:29
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-09 21:49:00
 * @FilePath: /992subarraysWithKDistinct/992.go
 */
package leetcode

/*
类似 求和为特定value的子数组个数;滑窗加hash

*/
func subarraysWithKDistinct(A []int, K int) int {
	res := 0
	cntMap := make(map[int]int, 0)

	//其实这一步可以省略 也不影响最终的结果
	for i := 0; i < K; i++ {
		cntMap[A[i]]++
	}
	// 左闭 右闭 区间 [left, right]
	left := 0
	right := K - 1
	for left <= right {
		if len(cntMap) <= K {
			if len(cntMap) == K {
				res += help(A, left, right, cntMap, K)
			}
			if right+1 == len(A) {
				return res
			}
			//向右移动
			right++
			cntMap[A[right]]++
		} else if len(cntMap) > K {
			cntMap[A[left]]--
			if cntMap[A[left]] == 0 {
				delete(cntMap, A[left])
			}
			left++
		}
	}

	return res
}

// 计算以right为结尾的满足条件的子数组有多少个
func help(A []int, left, right int, cntMap map[int]int, K int) int {
	tmpMap := make(map[int]int, 0) //记录移除的个数,这样就不会改变原有的cntMap

	cnt := 0
	for left <= right {
		cnt++
		//移动left
		tmpMap[A[left]]++
		if tmpMap[A[left]] == cntMap[A[left]] {
			break
		}

		left++
	}

	return cnt
}