|
题目链接：977. 有序数组的平方 - 力扣（LeetCode）
思路： 本题中因为我们是返回每个数字的平方组成的以递增顺序排序的新数组。因此，每个元素的正负在此刻并不重要，我首先对每个元素进行了取绝对值，然后对取绝对值后的数组进行排序，最终返回每个元素进行平方后的数组就完成了这道问题。
存在问题： 由于太久没写排序了，竟然是只能磕磕绊绊的写出一个冒泡排序，在这里先写下对于冒泡排序的一些感悟吧：
冒泡时应当注意对于第二层的处理是否会造成栈溢出，同时要想好，这一趟冒泡是将什么元素置于什么位置（也就是最大/最小的元素在此趟中确定）然后根据此确立第二个for循环的书写方式
本题中排序最好的方式应当是分组后进行快排，这样做的时间复杂度仅有O(n)，而使用冒泡排序显然落了下乘，但个人实力不足也只能做到这种地步了
代码如下：
public class Solution {
public int[] sortedSquares(int[] nums) {
for(int i = 0; i < nums.length;i++){
if(nums[i] < 0){
nums[i] *= -1;
}
}
for(int i = 0; i < nums.length;i++){
for(int j = 0;j <nums.length - i - 1;j++){
if(nums[j] > nums[j+1]){
int temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
}
}
}
for(int i = 0; i < nums.length;i++){
nums[i] *= nums[i];
}
return nums;
}
}
具体代码如下：
public class Solution {
public int[] sortedSquares(int[] nums) {
int leftIndex,rightIndex;
leftIndex = 0;
rightIndex = nums.length-1;
int[] result = new int[nums.length];
int k = nums.length-1;
while(k>=0){
if(nums[leftIndex] * nums[leftIndex] < nums[rightIndex] * nums[rightIndex]){
result[k--] = nums[rightIndex] * nums[rightIndex];
rightIndex--;
}
else{
result[k--] = nums[leftIndex] * nums[leftIndex];
leftIndex++;
}
}
return result;
}
}
总结：
对于左右两侧分布极值的问题，使用相向左右指针对此类问题进行处理是一个不错的选择。
题目链接：209. 长度最小的子数组 - 力扣（LeetCode）
初始想法： 本来看到这道题是并没有什么思路的，能想到的就是通过暴力解法，通过双层for循环，统计每一次的从起点位置开始到终止位置大于target为止的距离，并得出其中的最小值，最终返回此值，其时间复杂度为O(n^2)
随即观看了代码随想录的相关解题视频，给出了一个时间复杂度仅有O(n)的解法：滑动窗口
具体的ac代码如下：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int MAX = 100004;
int begin = 0;
int result = MAX;
boolean exist = false;
for(int j = 0; j < nums.length;j++){
sum+=nums[j];
while(sum >= target){
exist = true;
result = Math.min(result,(j - begin+1));
sum-=nums[begin];
begin++;
}
}
if(exist)
return result;
else return 0;
}
}
总结：
这道题实际上还是对于双指针的利用，通过双指针能够很好的对于区间内的元素进行判断，在数组的相关处理中应当多想到使用双指针对问题进行处理。
题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）
思路：刚看到是真的毫无头绪，完全不知道应该从哪里开始，于是看了代码随想录中的解析
-
本题依旧用到在二分查找中的循环不变量原则，即在转圈时一定要遵守好区间的左闭右开/左闭右闭，这样才能在动态中写好代码 左闭右开如下图： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MibO9rMq-1667010047410)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/3d230d70-c63f-4a16-b5aa-e3b88662d5c4/Untitled.png)] -
直接使用模拟，人工的模拟好矩阵的填充过程，并处理好其中的特殊情况就能较好的完成这一道习题
做好以上几点基本就可以写出一个漂亮的ac代码，
代码如下:
class Solution{
public int[][] generateMatrix(int n) {
int matrix[][] = new int[n][n];
int offset= 1;
int startx = 0;
int starty = 0;
int mid = n / 2;
int fill = 1;
int times = 0;
while(times++ < n/2){
int i = starty;
int j = startx;
for(;j < n - offset;j++){
matrix[i][j] = fill++;
}
for(;i < n - offset;i++){
matrix[i][j] = fill++;
}
for(;j > startx;j--){
matrix[i][j] = fill++;
}
for(;i > starty;i--){
matrix[i][j] = fill++;
}
startx++;
starty++;
offset++;
}
if(n % 2 == 1){
matrix[mid][mid] = fill;
}
return matrix;
}
}
数组总结
数组由于其内存空间连续的特性，想要修改其中的内容是一件非常简单的事情。而与之相对的，要从数组中删除一个元素就不是一件容易的事情了，我们只能使用覆盖的方式来删除原位置上的元素，而通常情况下我们都需要将删除后方的元素进行逐个向前移动，这就会产生一个O(n)的时间复杂度。
当然，在对数组进行处理的过程中，若是不限制空间复杂度，使用一个新的数组来保存显然是更优的处理方式，比如之前所做过的
题目链接：977. 有序数组的平方 - 力扣（LeetCode）
就是一个很好的例子。
当然，若是不允许有额外的内存开销，通过双指针（快慢指针、相向指针）对问题进行处理也是一个好的思路，如这两天内所完成的
题目链接：209. 长度最小的子数组 - 力扣（LeetCode）
题目链接：977. 有序数组的平方 - 力扣（LeetCode）
题目链接：27. 移除元素 - 力扣（LeetCode）
都是对此类问题的优秀处理
由于数组在内存上是连续存放的，其可类比为一个近似于区间的概念，那么我们在对于区间的处理上一定要遵循好循环不变量的原则，处理问题一定要想好相关的区间是 左闭右开 还是左闭右闭的问题。
两天中就基本完成了目标中的数组相关问题，希望接下来的日子里同样能够不懈怠，继续努力
|