TalkGo算法之美第四期

使用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
}

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



func checkFunc(piles []int, speed, H int) bool {
	needDays := 0
	for _, value := range piles {
		needDays+=value/speed // 每天吃speed个
		if value%speed>0{needDays++} // 不够整除算一天
	}
	
	return needDays<=H
}



func minEatingSpeed(piles []int, H int) int {
	best := -1
	left, right := 1, int(10e9)
	for left<= right {
		mid := (right+left)>>1
		if checkFunc(piles, mid, H) { // 可以吃完
			best, right = mid, mid-1
		} else {
			left = mid+1
		}
	}
	return best
}