数组
977. 有序数组的平方
看完题目的第一想法
根据题意直接每个元素求平方,然后排个序,提交。时间复杂度O(\(nlogn\))。
func sortedSquares(nums []int) []int {
for i, num := range nums{
nums[i] = num*num
}
sort.Ints(nums)
return nums
}
进阶
因为题目进阶部分要求时间复杂度O(\(n\)),再结合题目中的非递减顺序排序的数组,当数组的元素为负数时,它的平方可能为最大值,即有序数组元素的平方的最大值一定在数组的左端点或者右端点。可以使用双指针来求解。
func sortedSquares(nums []int) []int {
n := len(nums)
rlt := make([]int, n)
for left, right := 0, n-1; left <= right; {
n = n - 1
if s := nums[left] * nums[left]; s > nums[right]*nums[right] {
rlt[n] = s
left++
} else {
rlt[n] = nums[right] * nums[right]
right--
}
}
return rlt
}
今日收获
暴力题解很容易完成,双指针对特定的数组题目有奇效。
209. 长度最小的子数组
看完题目的第一想法
求长度最小的子数组,通过两层for循环不断的寻找符合条件的子数组,时间复杂度O(\(n^2\)), 愉快的撸代码很遗憾的是超时啦。
func minSubArrayLen(target int, nums []int) int {
rlt := math.MaxInt32
for i := range nums {
sum := 0
for j := i; j < len(nums); j++ {
sum += nums[j]
if sum >= target {
rlt = min(rlt, j-i+1)
break
}
}
}
if rlt == math.MaxInt32 {
return 0
}
return rlt
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
进阶
使用双循环遍历时外层循环确认起始位置,内层循环确认终点位置,那么可以使用滑动窗口的方式(使用两个指针,一个指针扩大窗口的范围,一个指针缩小窗口的范围,使其满足最小的子数组)去掉一层循环。
func minSubArrayLen(target int, nums []int) int {
rlt := math.MaxInt32
sum := 0
for i, j := 0, 0; j < len(nums); j++ {
sum += nums[j]
for sum >= target {
rlt = min(rlt, j-i+1)
sum -= nums[i]
i++
}
}
if rlt == math.MaxInt32 {
return 0
}
return rlt
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
今日收获
使用滑动窗口时:
- 窗口表示的就是 >= target的长度最小的子数组
- 窗口的起始位置如何移动:当窗口的大小大于target,就需要缩小窗口,对应代码中
i++
- 窗口的终止位置如何移动:窗口的终止位置就是for循环的索引
59. 螺旋矩阵 II
看完题目的第一想法
做过【54.螺旋矩阵】,直接开始模拟。 在模拟的过程中始终保持左闭右开的遍历顺序。
func generateMatrix(n int) [][]int {
startX, startY := 0, 0
// 计数
count := 1
offset := 1
rlt := make([][]int, n)
for i := range rlt {
rlt[i] = make([]int, n)
}
for loop := n / 2; loop > 0; loop-- {
i, j := startX, startY
// 上行,从左到右
for ; j < n-offset; j++ {
rlt[i][j] = count
count++
}
// 右列,从上到下
for ; i < n-offset; i++ {
rlt[i][j] = count
count++
}
// 下行, 从右到左
for ; j > startY; j-- {
rlt[i][j] = count
count++
}
// 左列,从下到上
for ; i > startX; i-- {
rlt[i][j] = count
count++
}
// 遍历完一圈 起始坐标需要改变
startX++
startY++
// 每一圈的遍历长度也随之缩减
offset++
}
if n%2 == 1 {
rlt[n/2][n/2] = count
}
return rlt
}
今日收获
遍历时,需要保持同一种区间风格,注意的是当n为奇数时需要单独给最中间的值赋值。题的难度不大,写代码时需要仔细。
标签:return,nums,int,练习,++,算法,数组,rlt From: https://www.cnblogs.com/neilliu/p/16720812.html