day02 有序数组平方、长度最小的子数组、螺旋矩阵II

题目链接：leetcode977-有序数组平方，leetcode209-长度最小的子数组, leetcode59-螺旋矩阵II

有序数组平方

解题思路：双指针法，left, right
1）创建一个等长的新数组
2）left从左到右扫描数组，right从右向左扫描数组
3）分别对left和right进行平方，并对平方的结果进行比较，谁大谁放入新数组(从新数组尾部开始存放，因为原始数组是从小到大排序的，如果存在负数，则left执行的val的平方值可能会大于right指向的平方值)
时间复杂度: O(n)
空间复杂度: O(1): 除了存储答案的数组以外，只需要维护常量空间

Go

func sortedSquares(nums []int) []int {numsLen := len(nums)left, right := 0, numsLen-1// 创建新数组ans := make([]int, numsLen)ansIdx := numsLen - 1for left <= right {lS, rS := nums[left]*nums[left], nums[right]*nums[right]if lS >= rS {ans[ansIdx] = lSleft++} else {ans[ansIdx] = rSright--}ansIdx--}return ans
}

Rust

	pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {let (mut left, mut right) = (0usize, nums.len() - 1);let mut ans = vec![0;nums.len()];let mut ans_idx = right;while left <= right {let (l_s, r_s) = (nums[left] * nums[left], nums[right] * nums[right]);// 之所以使用l_s >= r_s, 是为了避免 right-=1(right为0时会报错)// 如：[0, 1, 2, 3], right最小也只是为0， 此时(left=right=0)if l_s >= r_s {ans[ans_idx] = l_s;left += 1;} else {ans[ans_idx] = r_s;right -= 1;}// ans_idx是usize类型if ans_idx == 0 {break}ans_idx -=1;}ans}

长度最小的子数组

解题思路：滑动窗口，双指针: l,r
1） 找到sum>=target的连续子数组，确保[l, r]范围内的val的sum>=target, r-l+1即为sum>=target的连续子数组的长度
2）移动l, 在满足sum >= target的前提下，缩小[l, r]的范围，持续移动l, 求最小的r-l+1
时间复杂度: O(n)
空间复杂度: O(1)

Go

func minSubArrayLen(target int, nums []int) int {l, r, numsLen := 0, 0, len(nums)minLen := numsLen + 1 // 设置初始长度为最大长度sum := 0for ; r < numsLen; r++ {sum += nums[r]for sum >= target {curLen := r - l + 1if curLen < minLen {minLen = curLen}// 缩小[l, r]的范围sum -= nums[l]l++}}// minLen等于numsLen+1说明没有发生任何变化，即没有找到minLenif minLen == numsLen+1 {return 0}return minLen
}

Rust

	pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {// 给min_len一个默认大小let (mut l, mut min_len,mut sum)  = (0usize, nums.len()+1, 0);for r in 0..nums.len() {sum += nums[r];// 在满足sum >= target的前提下，缩小[l, r]的范围while sum >= target {let cur_len = r - l + 1;if cur_len < min_len {min_len = cur_len;}// 移动lsum -= nums[l];l += 1;}}// min_len 等于默认值，说明min_len没有发生变化，说明没有找到最小连续子数组if min_len == nums.len() + 1 {return 0;}min_len as i32}

螺旋矩阵II

解题思路：模拟题，画图思考

Go

func generateMatrix(n int) [][]int {// cycleNum: 要转的圈数// lineNo: 行号// columnNo: 列号// layerNo: 当前层数cycleNum, lineNo, columnNo, layerNo := n/2, 0, 0, 1// 初始化矩阵matrix := make([][]int, n)for i := 0; i < n; i++ {matrix[i] = make([]int, n)}// 计数器，每经过一个格子进行累加counter := 1for i := 0; i < cycleNum; i++ {// 左-->右，行不变，列累加for columnNo < n-layerNo {matrix[lineNo][columnNo] = countercounter++columnNo++}// 上--->下，列不变，行累加for lineNo < n-layerNo {matrix[lineNo][columnNo] = countercounter++lineNo++}// 右--->左, 行不变，列减小for columnNo >= layerNo {matrix[lineNo][columnNo] = countercounter++columnNo--}// 下--->上，列不变，行减小for lineNo >= layerNo {matrix[lineNo][columnNo] = countercounter++lineNo--}// 此时lineNo和columnNo都等于layerNum-1layerNo++lineNo++columnNo++}// 如果n为奇数，则最中心会空出来，即matrix[n/2][n/2]=n^2if n&1 == 1 {matrix[n/2][n/2] = n * n}return matrix
}

Rust

pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {// cycle_num: 要转的圈数// line_no：行的标号// column_no: 列的标号// layer_no: 当前在第几层let n_usize = n as usize;let (cycle_num, mut layer_no) = (n/2, 1usize);let (mut line_no, mut column_no) = (0usize, 0usize);// 累加器let mut counter = 1;// 初始化矩阵let mut matrix = vec![vec![0;n as usize];n as usize];for i in 0..cycle_num {// 左--->右，行不变，列累加while column_no < n_usize - layer_no {matrix[line_no][column_no] = counter;counter += 1;column_no += 1;}// 上--->下，列不变，行累加while line_no < n_usize - layer_no {matrix[line_no][column_no] = counter;counter += 1;line_no += 1;}// 右--->左，行不变，列减小while column_no >= layer_no {matrix[line_no][column_no] = counter;counter += 1;column_no -= 1;}// 下--->上，列不变，行减小while line_no >= layer_no {matrix[line_no][column_no] = counter;counter += 1;line_no -= 1;}// 此时 line_no和column_no都为 layer_no-1// 等待进入下一层layer_no += 1;line_no += 1;column_no += 1;}if n & 1 == 1 {matrix[n_usize >> 1][n_usize >> 1] = n * n;}matrix}