704.二分查找
Loading Question... - 力扣（LeetCode）
给定一个 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 中因此返回 -11. 左闭右闭
whileleft <= right)要使用 <= ，因为left == right是有意义的，所以使用 <=if (nums[middle] > target) right要赋值为 middle - 1，因为当前这个nums[middle]一定不是 target，那么接下来要查找的左区间结束下标位置就是 middle - 1
// 时间复杂度 O(logn)
// 空间复杂福 O(1)
func BinarySearch(nums []int, target int) int {
// 定义左右区间
left := 0
right := len(nums) - 1
// 左闭右闭
for left <= right {
// 防止溢出,等同于 left + right / 2
middle := left + (right-left)/2
if nums[middle] > target {
// 如果中间值大于目标值,更新右区间
right = middle - 1
} else if nums[middle] < target {
// 如果中间值小于目标值,小于左区间
left = middle + 1
} else {
// 如果等于,直接返回下标
return middle
}
}
return -1
}2. 左闭右开
while (left < right)，这里用 < , 因为 left == right 在区间 [ left, right ) 是没有意义的if (nums[middle] > target)right 更新为 middle，因为当前 nums [ middle ] 不等于 target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为 middle，即：下一个查询区间不会去比较 nums[ middle ]
// 时间复杂度 O(logn)
// 空间复杂福 O(1)
func BinarySearch2(nums []int, target int) int {
left := 0
right := len(nums)
// 左闭右开
for left < right {
middle := left + (right-left) / 2
if nums[middle] > target {
right = middle
} else if nums[middle] < target {
left = middle + 1
} else {
return middle
}
}
return -1
}27.移除元素
Loading Question... - 力扣（LeetCode）
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
# 示例
1. 给定 nums = [ 3, 2, 2, 3 ], val = 3, 函数应该返回新的长度2, 并且 nums 中的前两个元素均为2。
2. 你不需要考虑数组中超出新长度后面的元素。
# 示例2:
1. 给定 nums = [ 0, 1, 2, 2, 3, 0, 4, 2 ], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 41. 暴力破解
这个算法就是数组底层删除元素的实现原理 , 只不过底层使用双指针实现的 , 时间复杂度为 O(n)
数组元素其实并没有删除 , 只是被全部移到最后了 , 然后修改数组长度
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
func RemoveElement(arr []int, values int) int {
lenght := len(arr)
for i := 0; i < lenght; i++ {
if values == arr[i] {
// 将所有元素向前移动一位
for j := i + 1; j < lenght; j++ {
arr[j-1] = arr[j]
}
// 每个元素向前移动后,原本是 i 的元素也会向前
i--
// 因为移除(覆盖)了一个元素,所以length-1
lenght--
}
}
return lenght
}
2. 双指针法
slowIndex:慢指针寻找新数组的元素 ，新数组就是不含有目标元素的数组FastIndex:快指针指向更新新数组下标的位置
// 时间复杂度：O(n)
// 空间复杂度：O(1)
func RemoveElement2(arr []int, value int) int {
// 定义慢指针:新数组的与元素
slowIndex := 0
for FastIndex := 0; FastIndex < len(arr); FastIndex++ {
// 如果快指针指向的元素 != 要删除的元素,那么就是最后要组成的元素,也就是新数组
if arr[FastIndex] != value {
// 把快指针执行的元素赋给更新新数字下标的位置
arr[slowIndex] = arr[FastIndex]
slowIndex++
}
}
//切片,从 0 开始切到 slowIndex , 不包含5
arr = arr[:slowIndex]
fmt.Println(arr)
return slowIndex
}
3. 相向双指针法
left : 指向更新后的元素
right : 指向要删除的元素
func RemoveElement(nums []int, val int) int {
// left指向更新后的元素
left := 0
// right指向要删除的元素
right := len(nums) - 1
for left <= right {
// 不断寻找左侧的val和右侧的非val 找到时交换位置 目的是将val全覆盖掉
for left <= right && nums[left] != val {
left++
}
for left <= right && nums[right] == val {
right--
}
//各自找到后开始覆盖 覆盖后继续寻找
if left < right {
nums[left] = nums[right]
left++
right--
}
}
fmt.Println(nums)
return left
}977 有序数组的平方
977. Squares of a Sorted Array - 力扣（LeetCode）
给你一个按非递减顺序排序的整数数组nums , 返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]1. 暴力破解
平方之后排序
func SortedSquares(nums []int) []int {
for i := 0; i < len(nums); i++ {
nums[i] *= nums[i]
}
// 使用 sort.Ints比较
sort.Ints(nums)
// 使用 sort 比较器比较
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
return nums
}2. 双指针法
func SortedSquares(nums []int) []int {
// 分别只指向切片首位和末尾,结果集末尾
i := 0
j := len(nums) - 1
resultIndex := len(nums) - 1
// 结果集切片
result := make([]int, len(nums))
for i <= j {
//计算左右两边的平方
lsquare := nums[i] * nums[i]
rsquare := nums[j] * nums[j]
if rsquare > lsquare {
result[resultIndex] = rsquare
j--
} else {
result[resultIndex] = lsquare
i++
}
resultIndex--
}
return result
}要注意 else 这里 , 不能写
else if rsquare < lsquare, 否则无法退出循环
209.长度最小的子数组
给定一个含有
n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于
target的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。
# 示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
# 示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
# 示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：01. 暴力破解
两个 for 循环不断遍历 , 寻找子数组
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
func MinSubArrayLen(target int, nums []int) int {
// 最后返回的最小子数组,先等于最大值
result := len(nums) + 1
if len(nums) == 0 {
return 0
}
for i := 0; i < len(nums); i++ {
num := 0
for j := i; j < len(nums); j++ {
num += nums[j]
if num >= target {
// 判断哪个子数组最小
// j-i+1 为当前子数组长度
if result > j-i+1 {
result = j - i + 1
// 因为当前循环成功找到了子数组长度,并且修改了result,所以break跳过本次循环
break
}
}
}
}
// 如果result还是原来的值,说明没有被赋值,也就说明没有找打子数组
if result == len(nums) + 1 {
return 0
}
return result
}2. 滑动窗口
// MinSubArrayLen 滑动窗口
func MinSubArrayLen(target int, nums []int) int {
// 最后返回的最小子数组,首先需要让它等于最大值
result := len(nums) + 1
// 子数组之和
sum := 0
// 指向滑动窗口起始位置
i := 0
// j 指向尾部位置
for j := 0; j < len(nums); j++ {
sum += nums[j]
for sum >= target {
// 修改最小子数组的值
if result > j-i+1 {
result = j - i + 1
}
// 修改滑动窗口初始位置
sum -= nums[i]
i++
}
}
// 如果result没有发送改变
if result == len(nums)+1 {
return 0
}
return result
}59.螺旋矩阵
func GenerateMatrix(n int) [][]int {
// 四个边界值
top, bottom := 0, n-1
left, right := 0, n-1
// 要填的数据,从1开始
num := 1
// n * n 的矩阵能填的所有数据
All := n * n
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, n)
}
for num <= All {
//左边
for i := left; i <= right; i++ {
res[top][i] = num
num++
}
// 顶边要换到内层
top++
for i := top; i <= bottom; i++ {
res[i][right] = num
num++
}
// 右边要换到内层
right--
for i := right; i >= left; i-- {
res[bottom][i] = num
num++
}
// 底层要换到内层
bottom--
for i := bottom; i >= top; i-- {
res[i][left] = num
num++
}
// 左边换到内层
left++
}
return res
}
评论区