一、前言
今天是参加 卡哥算法训练营的第二天, 任务如下所示
网络异常，图片无法展示
|
二、1640. 能否连接形成数组
题目描述
网络异常，图片无法展示
|
思路分析
这道题也做过好几遍了, 这次竟然一次通过
这题也是左右遍历双指针的思路, 需要注意的是数组元素可能为负数
代码展示
public int[] sortedSquares(int[] nums) { int left = 0, right = nums.length - 1, n = nums.length - 1; int[] result = new int[nums.length]; while(left <= right){ int leftNum = nums[left] * nums[left]; int rightNum = nums[right] * nums[right]; if (leftNum >= rightNum){ left++; result[n] = leftNum; }else{ right--; result[n] = rightNum; } n--; } return result; } 复制代码
提交结果
网络异常，图片无法展示
|
补充
结果上来看内存使用过多, 发现自己在每次循环的时候都会去创建两个对象去存储 nums[left] 和 nums[right]的平方值, 那么我直接把它的创建提出去, 内存消耗唰的一下就降下来了
网络异常，图片无法展示
|
三、 209. 长度最小的子数组
题目描述
网络异常，图片无法展示
|
思路分析
依旧是双指针玩法
right一直前进， 如果 nums[left]到 nums[right]的和大于等于 target的话就移动 left前进，继续判断
注意可能数组 nums所有元素和加起来都小于 target， 所以先使 num = Integer.MAX_VALUE , 最后判断一下
代码展示
class Solution { public int minSubArrayLen(int target, int[] nums) { int result = Integer.MAX_VALUE; int left = 0, right = 0,num = 0; for (; right < nums.length; right++) { num += nums[right]; while(num >= target){ result = Math.min(result, right - left + 1); num -= nums[left]; left++; } } return result == Integer.MAX_VALUE ? 0 : result; } } 复制代码
提交结果
网络异常，图片无法展示
|
总结
又是一道几个月之前做过的题目，再一次做的时候细节还是没有把控好， 后面要注意
四、 59. 螺旋矩阵 II
题目描述
网络异常，图片无法展示
|
思路分析
这道题麻了，只记得大概，边界还总控制不好
首先可以确定我们的返回值， 因为是 int[n][n]的， 其次我们可以判断出来他是一圈一圈的进行赋值
然后要把控好这个边界的问题
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
最后根据以上分析写出下面的代码
代码展示
class Solution { // 创建返回值 int[][] res = new int[n][n]; // 定义当前是第几圈 int loopNum = 0; // 动态，指定下标使用 int i = 0,j = 0; // 开始的元素下标定位和当前值 int start = 0, count = 1; // 一共有 n/2 圈， 每次赋值一圈元素 while(loopNum++ < n / 2){ // 行赋值 for (i = start; i < n - loopNum;i++){ res[start][i] = count++; } // 列赋值 for(j = start; j < n - loopNum; j++){ res[j][i] = count++; } // 行~ for (; i >= loopNum ; i--){ res[j][i] = count++; } // 列~ for(; j >= loopNum ; j--){ res[j][start] = count++; } // 下标增加 start++; } // 可能有最中间元素未赋值， 进行判断 if (n % 2 == 1){ res[start][start] = count; } return res; } 复制代码
提交结果
网络异常，图片无法展示
|
总结
这个是真的麻爪了， 在模拟顺时针化矩阵的时候总是出错，最后还是看了题解才把控好这个边界的问题
五、每日一题 1640. 能否连接形成数组
题目描述
网络异常，图片无法展示
|
思路分析
里面需要注意的就是不允许 对每个数组 pieces[i] 中的整数重新排序。这个最开始忘记了, 走了很多弯路
代码分析:
- 先去获取 pieces里面每个数组的首位元素, 因为题中有说值不重复, 那么直接放入 map中就可以了
- 然后就是去遍历判断是否相等, 这里需要注意的是 i++ 这个条件不要放在最外层循环, 容易跳过, 也吃了个亏
代码展示
class Solution { public boolean canFormArray(int[] arr, int[][] pieces) { Map<Integer, int[]> map = new HashMap<>(); for (int[] piece : pieces) { map.put(piece[0], piece); } for (int i = 0; i < arr.length;) { if (!map.containsKey(arr[i])){ return false; } int[] ints = map.get(arr[i]); for (int j = 0; j < ints.length; j++,i++) { if (ints[j] != arr[i]){ return false; } } } return true; } } 复制代码
提交结果
网络异常，图片无法展示
|
总结
老问题, 能放到外面定义的对象就尽量放到循环外面, 要不然就是纯纯增加内存消耗
网络异常，图片无法展示
|
