69. x的平方根


题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4 输出: 2 示例 2:

输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。

解题思路

根据 n^2 >= x 将 [0,n] 区间分成两部分 [n^2<=x] 和 [n^2>x] ,目标结果在所选性质的左边区间,所以使用模板2

代码

func mySqrt(x int) int {
    l,r:=0,x
    for l<r {
        mid:=(l+r+1)/2
        if mid*mid >x{
            r=mid-1
        }else{
            l=mid
        }
    }
    return l
}

35. 搜索插入位置


题目描述

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5 输出: 2 示例 2:

输入: [1,3,5,6], 2 输出: 1 示例 3:

输入: [1,3,5,6], 7 输出: 4 示例 4:

输入: [1,3,5,6], 0 输出: 0

解题思路

根据 nums[i]<target 将区间 [0,n]区间分成两部分{i | nums[i]<target} 和 {i | nums[i]>=target},目标值在所选性质的右边区间,选用模板1

代码

func searchInsert(nums []int, target int) int {
  // r 为最后一个能选到的位置
    l,r:=0,len(nums)
    for l<r{
        mid:=(l+r)/2
        if nums[mid]<target{
            l=mid+1
        }else{
            r=mid
        }
    }
    return l
}

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


题目描述

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2:

输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]

解题思路

  • 选用 nums[i]<target 可以查到模板值出现的第一个位置,分成{i | nums[i]<target} 和 {i | nums[i] >=target},使用模板1
  • 选用 nums[i]>target 可以查到目标值出现的最后一个位置,分成{i | nums[i]<=target} 和 {i | nums[i] >target},使用模板2

代码

func searchRange(nums []int, target int) []int {
    res:=make([]int,2)
    res[0]=-1
    res[1]=-1
  // 数据为空,可以返回了
    if len(nums)==0{
        return res
    }
    l,r:=0,len(nums)-1
    mid:=0
    for l<r{
        mid=(l+r)/2
        if nums[mid]<target{
            l=mid+1
        }else{
            r=mid
        }
    }
  // 没找到第一次出现的位置,说明该数字没出现过,可以返回了
    if nums[l]!=target{
        return res
    }
    res[0]=l
    l,r=0,len(nums)-1
    for l<r{
        mid=(l+r+1)/2
        if nums[mid]>target{
            r=mid-1
        }else{
            l=mid
        }
    }
    res[1]=l
    return res
}

74. 搜索二维矩阵


题目描述

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 示例 1:

输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true 示例 2:

输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false

解题思路

将二维矩阵看作是有序的一维数组,转化成简单的二分搜索,使用 < 性质划分,目标在右边,故使用模板1

代码

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix)==0 || len(matrix[0])==0{
        return false
    }
    m,n:=len(matrix),len(matrix[0])
    l,r:=0,m*n-1
    for l<r{
        mid:=(l+r)/2
        x,y:=toXY(mid,n)
        if matrix[x][y]<target{
            l=mid+1
        }else{
            r=mid
        }
    }
    x,y:=toXY(l,n)
    return matrix[x][y]==target
}

// i => [0,m*n-1]
func toXY(i,n int)(x ,y int){
    x= i/n
    y= i%n
    return
}

153. 寻找旋转排序数组中的最小值


题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2] 输出: 1 示例 2:

输入: [4,5,6,7,0,1,2] 输出: 0

解题思路

  • 可以想象成一段上升的线段,从中间截断,然后将左侧的平移到右侧
  • 寻找一个性质,可以将数组分成两部分,这里选择:将数组最后一个元素记为 last,根据 > last 分成两部分
  • 目标结果在性质右边,选用模板1

代码

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

33. 搜索旋转排序数组


题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4 示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1

解题思路

  • 寻找旋转点,参考 leetcode 153
  • 旋转目标值所在的区间进行二分查找

代码

func search(nums []int, target int) int {
    if len(nums)==0{
        return -1
    }
    l,r:=0,len(nums)-1
    p:=spinPoint(nums)
    res:=-1
    if target>=nums[p] && target <=nums[r]{
        res=bsearch(nums,p,r,target)
    }else{
        res=bsearch(nums,l,p-1,target)
    }
    return res
}
// 获取旋转点
func spinPoint(nums []int)int{
    l,r:=0,len(nums)-1
    last:=nums[r]
    for l<r{
        mid:=(l+r)/2
        if nums[mid] > last{
            l=mid+1
        }else{
            r=mid
        }
    }
    return l
}
// 普通二分查找
func bsearch(nums []int,l,r,target int)int{
    if l>r || l<0 || r<0{
        return -1
    }
    for l<r{
        mid:=(l+r)/2
        if nums[mid]<target{
            l=mid+1
        }else{
            r=mid
        }
    }
    if nums[l]!=target{
        return -1
    }
    return l
}

278. 第一个错误版本

题目描述

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5,并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。

解题思路

  • 按照版本是否错误这一性质划分数组,选用模板1
  • 本题要考察的实际上是 mid=(l+r)/2 会溢出,改写为 mid=l + (r-l)/2 即可

代码

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l=1,r=n;
        while(l<r){
            int mid=l+(r-l)/2;
            if(!isBadVersion(mid)){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return l;
    }
};

162. 寻找峰值

题目描述

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = [1,2,3,1] 输出: 2 解释: 3 是峰值元素,你的函数应该返回其索引 2。 示例 2:

输入: nums = [1,2,1,3,5,6,4] 输出: 1 或 5 解释: 你的函数可以返回索引 1,其峰值元素为 2; 或者返回索引 5, 其峰值元素为 6。 说明:

你的解法应该是 O(logN) 时间复杂度的。

解题思路

  • 根据 nums[i-1] < nums[i] < nums[i+1] ,即递增性质,将数组分成两部分
  • 目标值处于峰值,也就是在该性质的右边,选择模板1
  • 说明: 本题可能有多个峰值,返回其中一个即可

代码

func findPeakElement(nums []int) int {
    if len(nums)==0{
        return -1
    }
    if len(nums)==1{
        return 0
    }
    l,r:=0,len(nums)-1
    for l<r{
        mid:=(l+r)/2
        // nums[i-1] < nums[i] < nums[i+1]  说明还处于递增状态      
        if isGreat(nums,mid,mid-1) && isGreat(nums,mid+1,mid){
            l=mid+1
        }else{
            r=mid
        }

    }
    return l
}

// if nums[i1] > nums[i2] return true else return false
func isGreat(nums []int,i1,i2 int)bool{
    if i2<0{
        return true
    }
    if i1>len(nums)-1{
        return false
    }
    return nums[i1]>nums[i2]
}

275. H指数

题目描述

给定一位研究者论文被引用次数的数组(被引用次数是非负整数),数组已经按照升序排列。编写一个方法,计算出研究者的 h 指数。

h 指数的定义: “h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (N 篇论文中)至多有 h 篇论文分别被引用了至少 h 次。(其余的 N - h 篇论文每篇被引用次数不多于 h 次。)”

示例:

输入: citations = [0,1,3,5,6] 输出: 3 解释: 给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。 由于研究者有 3 篇论文每篇至少被引用了 3 次,其余两篇论文每篇被引用不多于 3 次,所以她的 h 指数是 3。

解题思路

  • 题目花里胡哨地引入了H指数概念,关键还是要找到一个性质划分数组
  • 根据论文被引用次数<达标篇数来划分数组,目标值在性质右边,选用模板1
  • Ps: 如果最终的目标被引用次数为0,则返回0

代码

func hIndex(citations []int) int {
    if len(citations)==0{
        return 0
    }
    lens:=len(citations)
    l,r:=0,lens-1
    for l<r{
        mid:=(l+r)/2
        if citations[mid] < (lens-mid){
            l=mid+1
        }else{
            r=mid
        }
    }
    if citations[l]!=0{
        return lens-l
    }
    return 0   
}