代码随想录算法训练营第二天| 977 有序数组平方 209 长度最小子数组 59 螺旋矩阵

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