文章目录
977.有序数组的平方
题目描述:给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
解题思路
因为是有序数组,返回一个数组类型,思路就是new一个新的数组将平方后的数字赋值在新数组中,同时要判断平方后数字的大小。关键点就在于对于平方后数字的判断,要求时间复杂度为O(n),所以只是用一个for循环。
因为原数组是非递减排列的,所以使用双指针指向数组的首尾来判断两个数的大小,最大值只会在两边出现。
遇到的问题及解决方案
1.新数组是有序的,新数组也要定义一个指针k指向数组的最终位置,因为比较左右两个值之后最大的值要从新数组终止位置开始插入。我刚开始没有定义指针k。
2.在比较之后赋值给新数组后i和j两个指针要各自自增和自减,但每次赋值后新数组的指针k要减一。
209.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
解题思路
使用滑动窗口的方法解决,在滑动窗口中不断更新sum的值。
遇到的问题及解决方案
1.在定义时要定义滑动窗口的长度以及一个int32类型最大的值用来作比较。
2.当sum>=target时,应该用while循环判断并更新,我是用了if。
3.end++应该在判断完sum之后再更新。
public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int n=nums.Length;
int start=0,end=0;
int sum=0;
int ans=int.MaxValue;
while(end<n)
{
sum+=nums[end];
while(sum>=target)
{
ans=Math.Min(ans,end-start+1);
sum-=nums[start];
start++;
}
end++;
}
return ans==int.MaxValue?0:ans;
}
}
59.螺旋矩阵II
给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
解题思路
模拟顺时针画矩阵的过程:
填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上
拐角处让给新的一条边来继续画,这也是坚持了每条边左闭右开的原则。
遇到的问题及解决方案
1.要先创建一个nxn的二维数组,每个位置都赋值为0。
//赋值语句
int[][] arr = new int[n][];//定义二维数组的第一维是n
for(int i = 0; i < n; i++)//通过循环为每个一维数组分配大小为n的空间。最终得到一个n x n的二维数组
arr[i] = new int[n];
2.while循环条件的判断就是元素数量temp<n*n,要定义一个temp=1来赋值矩阵中的元素,在写代码的时候没有想到这一点。
3.在赋值的时候要定义两个变量start=0和end=n-1记录边界,外圈赋值完相应的值要进行变化。
4.最后要判断n是奇数的话,最中间的一个元素要单独赋值。
总结
**关于滑动窗口:**双指针和滑动窗口有什么区别,感觉双指针也是不断缩小的窗口。这道题,我想用两头取值的双指针,结果错了?
因为两头指针走完相当于最多只把整个数组遍历一遍,会漏掉很多情况。滑动窗口实际上是双层遍历的优化版本,而双指针其实只有一层遍历,只不过是从头尾开始遍历的。
滑动窗口的原理是右边先开始走,然后直到窗口内值的总和大于target,此时就开始缩圈,缩圈是为了找到最小值,只要此时总和还大于target,我就一直缩小,缩小到小于target为止在这过程中不断更新最小的长度值,然后右边继续走,如此反复,直到右边碰到边界。这样就保证了可以考虑到最小的情况。
**关于螺旋矩阵:**offset的意义在于 结束一圈后 起始位置向后移 结束位置向前移。可以画和n=4或者n=5的矩阵,会比较好理解。offset就是由于要去更向内的一圈,内圈元素更少的地方循环,所以循环的次数变少了