leetcode

2023/2/17

704

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例1:
输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     
示例2:
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1   
提示：

你可以假设 nums 中的所有元素是不重复的。

n 将在 [1, 10000]之间。

nums 的每个元素都将在 [-9999, 9999]之间。

解答：
func search(nums []int, target int) int {
 var left int = 0
 var right int = len(nums)

 for left < right{
    middle := left + (right - left)/2
    if nums[middle] == target {
        return middle
    }else if nums[middle] > target{
        right = middle
    }else{
        left = middle + 1
    }
 } 
 return -1
}

2023/2/18

35:

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

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

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 为 无重复元素 的升序排列数组

-104 <= target <= 104

解答：
func searchInsert(nums []int, target int) int {
    left := 0
     right := len(nums)-1

    for left <= right {
         middle := left + (right - left)/2
        if nums[middle] == target {
            return middle 
        }else if nums[middle] > target {
            right =  middle - 1
        }else {
            left = middle + 1
        }
    }
    return right + 1
}

2023/2/19

34:

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

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

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

解答：

func searchRange(nums []int, target int) []int {
 leftBorder := getLeft(nums,target)
 rightBorder := getRight(nums,target)

 // 情况一
 if leftBorder == -2 || rightBorder == -2 {
     return []int{-1,-1}
 }
 // 情况二
 if rightBorder - leftBorder > 1 {
     return []int{leftBorder + 1,rightBorder - 1}
 }
 // 情况三
 return []int{-1,-1}

}

func getLeft (nums []int,target int)int {
 left,right := 0, len(nums)-1
 border := -2
 for left <= right {
     middle := left + ((right - left)>>1)
     if nums[middle] >= target {
         right = middle - 1
         border = right
     }else {
         left = middle + 1
     }
 }
 return border
}

func getRight (nums []int,target int)int {
 left,right := 0, len(nums)-1
 border := -2
 for left <= right {
     middle := left + ((right - left)>>1)
     if nums[middle] > target {
         right = middle - 1
     }else {
         left = middle + 1
         border = left
     }
 }
 return border
}

2023/2/20

53:

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

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

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

解答：

func search(nums []int, target int) int {
    left_index := left_bound(nums,target)
    if left_index == -1 {
        return 0
    }
    right_index := right_bound(nums,target)
    return right_index - left_index + 1

}
func left_bound(nums []int,target int)int{
    left := 0
    right := len(nums)-1
    for left <= right {
        middle := left + ((right - left) >> 1)
        if nums[middle] < target {
            left = middle + 1
        }else if nums[middle] > target {
            right = middle - 1
        }else {
            right = middle - 1
        }
    }
    if left >= len(nums) || nums[left] != target {
        return -1
    }
    return left
}
func right_bound(nums []int,target int)int{
    left := 0
    right := len(nums)-1
    for left <= right {
        middle := left + ((right - left) >> 1)
        if nums[middle] < target {
            left = middle + 1
        }else if nums[middle] > target {
            right = middle - 1
        }else {
            left = middle + 1
        }
    }
    if left < 0 || nums[right] != target {
        return -1
    }
    return right
}

2023/2/21

303:

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象

int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
提示：

1 <= nums.length <= 104

-105 <= nums[i] <= 105

0 <= i <= j < nums.length

最多调用 104 次 sumRange 方法

解答：
//前缀和
type NumArray struct {
    sums []int
}
func Constructor(nums []int) NumArray {
    sums := make([]int,len(nums)+1)
    for i, v := range nums{
        sums[i+1] = sums[i] + v
    }
    return NumArray{sums}
}
func (this *NumArray) SumRange(left int, right int) int {
    return this.sums[right+1] - this.sums[left]
}
/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.SumRange(left,right);
 */