977 有序数组平方
func sortedSquares(nums []int) []int {
// 思路,最简单,先平方,再排序
for idx, num := range nums{
nums[idx] = num * num
}
// 插排思想,维护两个列表,将无序列表元素插入到有序列表合适位置
for i := 1; i < len(nums); i++ { // 此处nums[:i]即我们维护的有序列表
temp := nums[i] // 暂时存放要插入的元素
for j := 0; j < i; j++ {
if nums[j]>nums[i] {// 前面元素小于后面元素,不符合倒叙
// 将有序列表整体平移
for x := i; x > j; x-- {
nums[x] = nums[x-1]
}
nums[j] = temp // 将移出来的空位补充为nums[i] 元素
}
}
}
return nums
}
时间 平方操作n + 插入排序 n^2 = n^2 空间 两步操作都在原数组内部进行 所以 1
func sortedSquares(nums []int) []int {
// 思路2 双指针,双端指针向中间移动的方法
length := len(nums)
var newli = make([]int, length)
left, right := 0, length - 1
for left <= right { // 此处取整 是因为 我是左闭右臂区间
sqrtl, sqrtr := nums[left] * nums[left],nums[right] * nums[right]
if sqrtl <= sqrtr { // 取更大的元素,放入到新切片的最后段
newli[length-1] = sqrtr
right-- // 右指针已经放入新切片,可以移动
}else{
newli[length-1] = sqrtl
left++
}
length-- // 新切片指针往前移动一位
}
return newli
}
时间 往左和往右共遍历n次,所以n 空间 新切片长度n 所以n
209 长度最小子数组
// 题目真他妈坑,错略的看我还以为是非连续的子数组,但是时间上后面的变量说明是连续的,为什么不他妈的直接在题目上说连续
func minSubArrayLen(target int, nums []int) int {
// 思路: 分而治之,查询所有子数组, 然后判断子和是否等于val
if sum(nums) < target {
return 0
}
// 如何查询子数组,答案是双指针变种,滑动窗口
var min = len(nums)
for left := 0; left < len(nums); left++{
// 先右指针(快指针)往右侧滑动,滑动到底部之后,左侧才开始滑动一次
for right := left; right < len(nums); right++ {
if sum(nums[left: right+1]) >= target{
if right+1-left < min {
min = right+1-left
}
}
}
}
return min
}
func sum(slice []int) int {
var sum int
for _, val := range slice {
sum += val
}
return sum
}
时间 n*n 空间 1
绷不住了,暴力破解现在会超时了
func minSubArrayLen(target int, nums []int) int {
// 思路: 分而治之,查询所有子数组, 然后判断子和是否等于val
if sum(nums) < target {
return 0
}
// 真滑动窗口, 原理: right是窗口的末端,我们每次计算之前的窗口的和,如果和大于tar, 那么缩小窗口,即起始位置后移一位,直到大于为止
var min, sum, left = len(nums), 0, 0
for right:=0; right<len(nums); right++{
sum += nums[right]
for (sum >= target) { // 窗口区间和大于 tar 左指针右移动,操~~ 这里写成了if然我扣半天
// 更新最小值
if right + 1 - left < min {
min = right + 1 - left
}
sum -= nums[left]
left++
}
}
return min
}
时间 最坏情况是 [2,3,4,5], 1 外层走一次,内层走一次,所以n 空间 1
59 螺旋矩阵
func generateMatrix(n int) [][]int {
// 思考,本质上n*n正方形,所以需要转n/2(偶数) 或者n/2+1(奇数)圈,原理就是每次遍历一圈,边长-2,所以要减去多少个2,就要多少圈,所以是n/2
startx, starty := 0,0 // x y 轴坐标
offset, count := 1, 0 // 边界条件,坐标值
var li [][]int
for i:=0; i<n; i++ {
// 初始化多为切片
li = append(li, make([]int, n)) // append会帮助我初始化外层切片,make初始化内层切片
}
for i:=0; i<n/2; i++{
// 转圈的结构代码
// 第一条边, 左闭右开
var x, y int
for y=starty; y<n-offset; y++{
count++
li[startx][y] = count
}
// 第二条边
for x=startx; x<n-offset; x++{
count++
li[x][y] = count // const x = n-offset
}
// 三
for y=n-offset; y>offset-1; y--{
count++
li[x][y] = count // const y = n-offset
}
// 四
for x=n-offset; x>offset-1; x--{
count++
li[x][y] = count
}
// 此处的三个变量都可以简化为 i+1 或者 i+2
startx++
starty++
offset++
}
if n%2 == 1 { // 奇数边最后一个元素放到中间
count++
li[n/2][n/2] = count
}
return li
}
时间 初始化矩阵n*make n = n^2 + (4*(n-1)+4*(n-3) + ...) 等差数列求和 n^2 == n^2 空间 多维矩阵n^2
标签:977,right,nums,int,sum,随想录,++,数组,left
From: https://www.cnblogs.com/zhougongjin55/p/18309355