公众号如何添加wordpress,seo引擎优化方案,珠海网站建设方案外包,南京外贸网站建设系统问题一#xff1a;给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -1。 输入 输出 nums [-1,0,3,5,9,12], target 9 4 …问题一给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 输入 输出 nums [-1,0,3,5,9,12], target 9 4 nums [-1,0,3,5,9,12], target 2 -1
问题类型二分
考察点二分查找的区间表示
右闭区间ri len(nums)-1
右闭区间的写法再遍历过程中lfri ,因为lf可以取到ri对应的值
右开区间(ri len(nums))
右开区间的写法再遍历过程中lfri ,因为lf不可以取到ri对应的值
实际上两个区间表示的元素个数都是一样的左区间都是闭区间处理方式一致。而右区间的不一致这将导致在分支判断过程中会出现不一致。
对于右闭区间nums[mid] target时ri需要更新此时明确nums[mid]是不会为target的所以ri mid -1。
对于右开区间nums[mid] target时ri需要更新此时ri属于开区间ri mid
或者换一种方式理解开区间天生比闭区间多1所以按照写法开区间等价于ri 1mid -1 也就是mid。
func search(nums []int, target int) int {lf,ri : 0,len(nums)-1mid: lf (ri-lf)/2for lf ri{mid lf (ri-lf)/2if nums[mid] target{ri mid -1}else if nums[mid] target{lf mid1}else {return mid}}return -1
}
func search(nums []int, target int) int {lf,ri : 0,len(nums)mid : 0for lf ri{mid lf (ri-lf)/2if nums[mid] target{ri mid}else if nums[mid] target{lf mid 1}else{return mid}}return -1
}
问题二: 给你一个数组 nums 和一个值 val你需要原地移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 输入 输出 nums [3,2,2,3], val 3 2nums [2,2] nums [0,1,2,2,3,0,4,2], val 2 5, nums [0,1,4,0,3]
问题类型双指针、暴力循环
考察点双指针的使用覆盖后向指针元素 有效 前向指针元素
思路1暴力
暴力也是一种双指针属于移动位置的双指针i用来判断当前元素是否为所需元素j元素控制数组进行腾挪。
不管怎样暴力必须要学会暴力是走路双指针就是跑步
思路2双指针1
追及问题同向先后双指针ri指针在前lf指针在后ri指针负责遍历全部数组如果遍历过程中遇到不是val的元素就赋值给lf并让lf如果是val就跳过lf不动。最后返回lf
思路3双指针2
相遇问题一个在起点一个在终点如果lf遇到val就把ri-1的值赋给lfri--否则lf
func removeElement(nums []int, val int) int {size : len(nums)for i:0;isize;i{if nums[i] val{for j: i1;jsize;j{nums[j-1] nums[j]}i--size--}}return size
}
func removeElement(nums []int, val int) int {lf : 0for ri:0;rilen(nums);ri{ // v 即if nums[ri] ! val {nums[lf] nums[ri]lf}}return lf
}
func removeElement(nums []int, val int) int {lf,ri : 0,len(nums)for lf ri {if nums[lf] val{nums[lf] nums[ri-1]ri--}else{lf }}return lf
}
