1.LeetCode977有序数组的平方题目链接
- 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
- 示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100] - 示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121] - 分析:粗略想法是找到第一个大于0的位置,然后分别用左右指针往左右遍历,比较大小再加入新数组里,就是实现的时候各种情况都要考虑,写的好像比较冗余,代码如下(java):
点击查看代码
public class Solution {
public int[] sortedSquares(int[] nums) {
int[] result=new int[nums.length];
int j=0;
for(int i=0;i<nums.length;i++){
if(nums[i]<=0){
j++;
}
}
//-3 -2 -1 0 1 2 3
//
int left=j-1;
int right=j;
if(left<0){
for(int i=0;i<nums.length;i++){
result[i]=nums[i]*nums[i];
}
}else if(right>=nums.length){
j=0;
for(int i=nums.length-1;i>=0;i--){
result[j]=nums[i]*nums[i];
j++;
}
}else{
j=0;
while (left>=0||right<nums.length){
if(left<0){
result[j]=nums[right]*nums[right];
right++;
}else if(right>=nums.length){
result[j]=nums[left]*nums[left];
left--;
}else if((nums[left]*nums[left])<(nums[right]*nums[right])){
result[j]=nums[left]*nums[left];
left--;
}else {
result[j]=nums[right]*nums[right];
right++;
}
j++;
}
}
return result;
}
}
- 看完卡哥的视频讲解表示有被自己笑到,想到了双指针,结果没想到从两边取,所以多了那么多的判断是否越界,哈哈哈,练习卡哥双指针法代码如下:
点击查看代码
public class Solution {
public int[] sortedSquares(int[] nums) {
int left=0;
int right=nums.length-1;
int[] result=new int[nums.length];
int i=nums.length-1;
while (left<=right){
if(nums[left]*nums[left]>nums[right]*nums[right]){
result[i]=nums[left]*nums[left];
left++;
}else{
result[i]=nums[right]*nums[right];
right--;
}
i--;
}
return result;
}
}
2.LeetCode209长度最小的子数组题目链接
- 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0
- 示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。 - 示例 2:
输入:target = 4, nums = [1,4,4]
输出:1 - 示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0 - 分析:题目要找长度最小的>=target的连续子数组,那么可以先找到这个数组中最大的元素所在位置,然后设置左右指针往左右遍历,对了,可以定义一个变量记录target-当前元素后剩余的值,该变量值小于0时停止遍历。
- 结果:写完了没AC,看那个用例的情况我的代码没有考虑到。
- 看视频和文章后,有点脑子懂了手没懂的感觉,暴力破解如下(为了练习,未AC,超时了):
点击查看代码
public class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result=100000;
int tmp=0;
int subLength = 0;
for(int i=0;i<nums.length;i++){
tmp=0;
for(int j=i;j<nums.length;j++){
tmp+=nums[j];
if(tmp>=target){
subLength=j-i+1;
if(subLength<result){
result=subLength;
}
}
}
}
if(result==100000){
result=0;
}
return result;
}
}
- 滑动窗口根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n),代码如下:
点击查看代码
public class Solution {
/**
* 窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
*
* 窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。
*
* 窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。
* @param target
* @param nums
* @return
*/
public int minSubArrayLen(int target, int[] nums) {
int i=0;
int sum=0;
int result=1000000;
int subLength=0;
for(int j=0;j<nums.length;j++){
sum+=nums[j];
while (sum>=target){
subLength=j-i+1;
sum=sum-nums[i];
i++;
if(subLength<result){
result=subLength;
}
}
}
if(result==1000000){
result=0;
}
return result;
}
}
3.LeetCode59螺旋矩阵II 题目链接
-
给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
-
示例 1:
输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]] -
示例 2:
输入:n = 1
输出:[[1]] -
分析:分析了好一会儿,感觉那个螺旋的时候是更新(n,n-1,n-1,n-2,n-2,...,2,2,1,1)个数,不知道有没有用,emmmm...还是不会
-
需要看看视频和文章!
-
总结:今天脑子有点跟不上,找到不足点,很有收获,之后还是多学习呀~
二分法:循环不变量原则,记住左闭右闭及左闭右开实现;
双指针:快慢指针,相向双指针;
滑动窗口:窗口内元素和大于等于目标值时,缩减窗口大小,窗口起始位置右移。
螺旋矩阵:循环不变量原则,还没看实现,暂时先不总结,白天再单独总结一篇,它值得!