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

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

时间:2024-07-18 16:30:31浏览次数:17  
标签:977 right nums int sum 随想录 ++ 数组 left

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

相关文章

  • 代码随想录算法训练营第42期 第二天 | LeetCode977. 有序数组的平方、209. 长度最小的
    一、977.有序数组的平方学习链接:有序数组的平方状态:暴力解法与双指针都做出来了时间复杂度:暴力解法O()    双指针解法 O()细节之处:暴力解法1       双指针解法1  暴力解法classSolution{publicint[]sortedSquares(int[]nums){......
  • 「代码随想录算法训练营」第十四天 | 二叉树 part4
    513.找树左下角的值题目链接:https://leetcode.cn/problems/find-bottom-left-tree-value/题目难度:中等文章讲解:https://programmercarl.com/0513.找树左下角的值.html视频讲解:https://www.bilibili.com/video/BV1424y1Z7pn题目状态:有点思路,但未通过,最后在ChatGPT的帮助下理......
  • 代码随想录算法训练营第27天 | 回溯3:93.复原IP地址、78.子集、90.子集II
    代码随想录算法训练营第27天|回溯3:93.复原IP地址、78.子集、90.子集II93.复原IP地址https://leetcode.cn/problems/restore-ip-addresses/submissions/547344868/代码随想录https://programmercarl.com/0093.复原IP地址.html#算法公开课78.子集https://leetcode.cn/probl......
  • DAY2 数组part02
     今日任务977.有序数组的平方,209.长度最小的子数组,59.螺旋矩阵II,总结977.有序数组的平方题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/文章讲解:https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%......
  • 代码随想录算法训练营第16天|LeetCode112路径总和LeetCode113路径总和iiLeetCode106.
    代码随想录算法训练营Day16代码随想录算法训练营第16天|LeetCode112路径总和LeetCode113路径总和iiLeetCode106.从中序与后序遍历序列构造二叉树LeetCode105.从前序与中序遍历序列构造二叉树目录代码随想录算法训练营前言LeetCode112路径总和,LeetCode113路径......
  • 代码随想录算法训练营第 15 天 |LeetCode110平衡二叉树 LeetCode257二叉树的所有路径
    代码随想录算法训练营Day15代码随想录算法训练营第15天|LeetCode110平衡二叉树LeetCode257二叉树的所有路径LeetCode404左叶子之和LeetCode222完全二叉树节点之和目录代码随想录算法训练营前言LeetCode110平衡二叉树LeetCode257二叉树的所有路径LeetCode404左......
  • 代码随想录算法训练营第28天 | 回溯4:491.递增子序列、46.全排列、47.全排列 II
    代码随想录算法训练营第28天|回溯4:491.递增子序列、46.全排列、47.全排列II491.递增子序列https://leetcode.cn/problems/non-decreasing-subsequences/代码随想录https://programmercarl.com/0491.递增子序列.html#算法公开课46.全排列https://leetcode.cn/problems/pe......
  • 前端开发数组去重方法
    使用原生JavaScript方法1. filter() 方法配合 indexOf()constuniqueArray=array.filter((item,index,self)=>{returnself.indexOf(item)===index;});该方法利用 filter() 遍历数组,对于每个元素,通过 indexOf() 查找其在原数组中的第一个索引。如果当前......
  • 双栈:数组实现
    双栈:数组实现结构描述:#include<iostream>#include<cstdlib>#defineMAX100usingnamespacestd;typedefintDataType;classDoubleStack{public:DataType*A;//两个栈的栈顶intTP;intTB;//建立一个空栈voidInit();//判空、......
  • 栈:数组实现
    栈:数组实现结构描述:#defineMAX100typedefintDataType;classSeqStack{public:DataType*A;intTop;voidInit();voidPush(DataTypeX);voidPop();DataTypeGetTop();voidMakeEmpty();boolIsEmpty();boolIsFull()......