微网站免费建设平台,厦门建设与管理局官网,html怎么做网站版块,excel做网站二维码1.前言
最近准备开始刷算法题了#xff0c;搜了很多相关的帖子#xff0c;下面三个很不错#xff0c;
计算机视觉秋招准备过程看这个#xff1a;计算机视觉算法工程师-秋招面经 - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/399813916
复习深度学习相关…1.前言
最近准备开始刷算法题了搜了很多相关的帖子下面三个很不错
计算机视觉秋招准备过程看这个计算机视觉算法工程师-秋招面经 - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/399813916
复习深度学习相关知识看深度学习500问
深度学习500问(github.com)https://github.com/scutan90/DeepLearning-500-questions刷题看这个
算法模板最科学的刷题方式最快速的刷题路径你值得拥有~ (github.com)https://github.com/greyireland/algorithm-pattern准备每天学习一点刷几道题后面将会持续更新。
2.基础算法篇-二分搜索
2.1二分搜索模板
给一个有序数组和目标值找第一次/最后一次/任何一次出现的索引如果没有出现返回-1
模板四点要素 1、初始化start0、endlen-1 2、循环退出条件start 1 end 3、比较中点和目标值A[mid] 、 、 target 4、判断最后两个元素是否符合A[start]、A[end] ? target
时间复杂度 O(logn)使用场景一般是有序数组的查找
模板 模板分析 二分查找 - LeetBook - 力扣LeetCode全球极客挚爱的技术成长平台 如果是最简单的二分搜索不需要找第一个、最后一个位置、或者是没有重复元素可以使用模板#1代码更简洁
其他情况用模板#3
2.2常见题目
1给定一个包含 n 个整数的排序数组找出给定目标值 target 的起始和结束位置。 如果目标值不在数组中则返回[-1, -1]
思路核心点就是找第一个 target 的索引和最后一个 target 的索引所以用两次二分搜索分别找第一次和最后一次的位置
func searchRange (A []int, target int) []int {if len(A) 0 {return []int{-1, -1}}result : make([]int, 2)start : 0end : len(A) - 1for start1 end {mid : start (end-start)/2if A[mid] target {end mid} else if A[mid] target {start mid} else {// 如果相等应该继续向左找就能找到第一个目标值的位置end mid}}// 搜索左边的索引if A[start] target {result[0] start} else if A[end] target {result[0] end} else {result[0] -1result[1] -1return result}start 0end len(A) - 1for start1 end {mid : start (end-start)/2if A[mid] target {end mid} else if A[mid] target {start mid} else {// 如果相等应该继续向右找就能找到最后一个目标值的位置start mid}}// 搜索右边的索引if A[end] target {result[1] end} else if A[start] target {result[1] start} else {result[0] -1result[1] -1return result}return result
}
2给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
func searchInsert(nums []int, target int) int {// 思路找到第一个 target 的元素位置start : 0end : len(nums) - 1for start1 end {mid : start (end-start)/2if nums[mid] target {// 标记开始位置start mid} else if nums[mid] target {end mid} else {start mid}}if nums[start] target {return start} else if nums[end] target {return end} else if nums[end] target { // 目标值比所有值都大return end 1}return 0
}
3编写一个高效的算法来判断 m x n 矩阵中是否存在一个目标值。该矩阵具有如下特性 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。
func searchMatrix(matrix [][]int, target int) bool {// 思路将2纬数组转为1维数组 进行二分搜索if len(matrix) 0 || len(matrix[0]) 0 {return false}row : len(matrix)col : len(matrix[0])start : 0end : row*col - 1for start1 end {mid : start (end-start)/2// 获取2纬数组对应值val : matrix[mid/col][mid%col]if val target {end mid} else if val target {start mid} else {return true}}if matrix[start/col][start%col] target || matrix[end/col][end%col] target{return true}return false
}
4假设你有 n 个版本 [1, 2, ..., n]你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
func firstBadVersion(n int) int {// 思路二分搜索start : 0end : nfor start1 end {mid : start (end - start)/2if isBadVersion(mid) {end mid} else if isBadVersion(mid) false {start mid}}if isBadVersion(start) {return start}return end
} 5假设按照升序排序的数组在预先未知的某个点上进行了旋转( 例如数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。
func findMin(nums []int) int {// 思路/ / 最后一个值作为target然后往左移动最后比较start、end的值if len(nums) 0 {return -1}start : 0end : len(nums) - 1for start1 end {mid : start (end-start)/2// 最后一个元素值为targetif nums[mid] nums[end] {end mid} else {start mid}}if nums[start] nums[end] {return nums[end]}return nums[start]
}
6假设按照升序排序的数组在预先未知的某个点上进行了旋转 ( 例如数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。(包含重复元素)
func findMin(nums []int) int {// 思路跳过重复元素mid值和end值比较分为两种情况进行处理if len(nums) 0 {return -1}start : 0end : len(nums) - 1for start1 end {// 去除重复元素for start end nums[end] nums[end-1] {end--}for start end nums[start] nums[start1] {start}mid : start (end-start)/2// 中间元素和最后一个元素比较判断中间点落在左边上升区还是右边上升区if nums[mid] nums[end] {end mid} else {start mid}}if nums[start] nums[end] {return nums[end]}return nums[start]
}
7假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值如果数组中存在这个目标值则返回它的索引否则返回 -1 。 你可以假设数组中不存在重复的元素。
func search(nums []int, target int) int {// 思路/ / 两条上升直线四种情况判断if len(nums) 0 {return -1}start : 0end : len(nums) - 1for start1 end {mid : start (end-start)/2// 相等直接返回if nums[mid] target {return mid}// 判断在那个区间可能分为四种情况if nums[start] nums[mid] {if nums[start] target target nums[mid] {end mid} else {start mid}} else if nums[end] nums[mid] {if nums[end] target nums[mid] target {start mid} else {end mid}}}if nums[start] target {return start} else if nums[end] target {return end}return -1
}
8假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true否则返回 false。(包含重复元素)
func search(nums []int, target int) bool {// 思路/ / 两条上升直线四种情况判断并且处理重复数字if len(nums) 0 {return false}start : 0end : len(nums) - 1for start1 end {// 处理重复数字for start end nums[start] nums[start1] {start}for start end nums[end] nums[end-1] {end--}mid : start (end-start)/2// 相等直接返回if nums[mid] target {return true}// 判断在那个区间可能分为四种情况if nums[start] nums[mid] {if nums[start] target target nums[mid] {end mid} else {start mid}} else if nums[end] nums[mid] {if nums[end] target nums[mid] target {start mid} else {end mid}}}if nums[start] target || nums[end] target {return true}return false
}
3.leedcode实战
3.1 第35题
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。
class Solution(object):def searchInsert(self, nums, target)::type nums: List[int]:type target: int:rtype: intresult 0mid 0start 0end len(nums) - 1while start 1 end:mid start (end - start)/2if nums[mid] target:result midreturn resultelif nums[mid] target:start midelif nums[mid] target:end midif nums[start] target:result startelif nums[end] target:result endelif nums[start] target:result startelif nums[start] target and nums[end] target:result endelif nums[end] target:result end 1return result 3.2第74题
给你一个满足下述两条属性的 m x n 整数矩阵
每行中的整数从左到右按非递减顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target 如果 target 在矩阵中返回 true 否则返回 false 。
class Solution(object):def searchMatrix(self, matrix, target)::type matrix: List[List[int]]:type target: int:rtype: boolrow len(matrix)col len(matrix[0])start 0end row * col - 1result Falsewhile start 1 end:mid start (end - start)/2if matrix[mid / col][mid % col] target:result Truereturn resultelif matrix[mid / col][mid % col] target:end midelif matrix[mid / col][mid % col] target:start midif matrix[start / col][start % col] target or matrix[end / col][end % col] target:result Trueelse:result Falsereturn result 3.3第34题
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
心得第一次没写出来想的是先去除掉重复的部分。正确的做法应该是在nums[mid]target部分下文章startmid就是向后找结束位置endmid就是向前找起始位置。
class Solution(object):def searchRange(self, nums, target)::type nums: List[int]:type target: int:rtype: List[int]if len(nums) 0:return [-1, -1]elif len(nums) 1 :if nums[0] target:return [0, 0]else:return [-1, -1]start 0end len(nums) - 1result [-1, -1]while start 1 end:mid start (end - start)/2if nums[mid] target:end midelif nums[mid] target:start midelse:end midif nums[start] target:result[0] startelif nums[end] target:result[0] endelse:result[0] -1result[1] -1return resultstart 0end len(nums) - 1while start 1 end:mid start (end - start)/2if nums[mid] target:end midelif nums[mid] target:start midelse:start midif nums[end] target:result[1] endelif nums[start] target:result[1] startelse:result[0] -1result[1] -1return resultreturn result 3.4第33题
整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
心得花了半小时没做出来一开始想着先用nums[mid]与target来做判断发现行不通然后尝试两条上升的直线划区域做想法没错但是陷入了误区。正确方法是两条上升的直线然后利用start一定会移动到mid和end一定会移动到mid的条件来判断。 定理一只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。 定理二判断顺序区间还是乱序区间只需要对比 left 和 right 是否是顺序对即可left right顺序区间否则乱序区间。 定理三每次二分都会至少存在一个顺序区间。感谢Gifted VVilburgiX补充 通过不断的用Mid二分根据定理二将整个数组划分成顺序区间和乱序区间然后利用定理一判断target是否在顺序区间如果在顺序区间下次循环就直接取顺序区间如果不在那么下次循环就取乱序区间。 class Solution(object):def search(self, nums, target)::type nums: List[int]:type target: int:rtype: intif len(nums) 0:return -1start 0end len(nums) - 1result 0while start 1 end:mid start (end - start)/2if nums[mid] target:return midif nums[start] nums[mid]:# 说明左半边是有序的if target nums[mid] and target nums[start]:end midelse:start midelif nums[end] nums[mid]:# 说明右半边是有序的if target nums[mid] and target nums[end]:# 用来确定目标是否在这一区域决定保留哪边。start midelse:end midif nums[start]target:result startelif nums[end]target:result endelse:result -1return result
3.5第153题
已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 旋转 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到
若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [0,1,2,4,5,6,7]
注意数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
心得第一次提交失败没有考虑到顺序数组的情况所以加了一个if语句判断是否是顺序的。
class Solution(object):def findMin(self, nums)::type nums: List[int]:rtype: intif len(nums) 1:return nums[0]start 0end len(nums) - 1while start 1 end:mid start (end - start)/2if nums[start] nums[end]:if nums[start] nums[mid]:start midelif nums[mid] nums[end]:end midelse:return nums[0]if nums[start] nums[end]:return nums[end]else:return nums[start]
