您现在的位置是:首页 >技术教程 >代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II网站首页技术教程

代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II

weixin_42474696 2023-05-28 16:00:02
简介代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


一、977.有序数组的平方

注意循环终止的条件:left<=right,因为left和right相等的时候,不应该退出循环,而是再进行一次,把这个数也要放在新数组中。

    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        int[] result = new int[nums.length];
        // for(int i = nums.length-1;i>=0;i--;){

        // }
        int r = nums.length-1;
        while(left<=right){
            if(nums[left]*nums[left]>nums[right]*nums[right]){
                result[r] = nums[left]*nums[left];
                r--;
                left++;
            }else{
                result[r] = nums[right]*nums[right];
                r--;
                right--;
            }
        }
        return result;
    }

11分钟

二、209.长度最小的子数组

思路:滑动窗口,如何移动窗口起始位置:动态移动。如何移动终止位置:for循环遍历(因为它要一点点循环到最后)
(一开始虽然想到了思路,但是用while遍历,比较混乱最后没写出来)

两个错误:

  1. while(sum>target),这里面有没有等号
  2. result = Math.min(result,right-left+1),维护result值的位置
  3. 没有判断子树和sum达不到target的情况

修改:

  1. 当子数组的和为目标时,应该要再算一次result的值,所以应该有等号
  2. 什么时候记录result的值?应该是在每次当子数组的和大于等于目标的时候才要记录,位置不要放到外面。
  3. 结尾增加判断
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int left = 0;
        int result = Integer.MAX_VALUE;
        for(int right =0;right<nums.length;right++ ){
            sum += nums[right];
            while(sum>=target){//?
                result = Math.min(result,right-left+1);//?
                sum -= nums[left];
                left++;

            }
            // result = Math.min(result,right-left+1);
        }
        return result == Integer.MAX_VALUE? 0: result;

    }

46分钟

三、59.螺旋矩阵II

分成四个回合,不断的循环存取数值

错误的点:

  1. 没有更新轮数。应该放到循环里面。
  2. for(y=0;y<=n-lun-2;y++)第一回合中,纵坐标y值不应该固定成0,因为第二轮的起始点就在1了,这点注意。
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int x=0;
        int y;
        int lun=0;//轮数
        int num = 1;
        for (lun = 0; lun < n/2; lun++) {
            for(y=lun;y<=n-lun-2;y++){
                result[lun][y]=num;
                num++;
            }
            for(x=lun;x<=n-lun-2;x++){
                result[x][y]=num;
                num++;
            }
            for(;y>=lun+1;y--){
                result[x][y]=num;
                num++;
            }
            for(;x>=lun+1;x--){
                result[x][y] = num;
                num++;
            }
        }
        if(n%2==1){
            result[n/2][n/2]=n*n;
        }
        return result;
    }

29分钟


四、27. 移除元素

同学美团面试考到了,重新复习一下

使用栈解决,有三种不匹配的情况,
1.左方向的括号多余
2. 右方向括号类型不匹配
3. 右方向的括号多余

错误之处

  1. char型的要用单引号,而不是双引号(低级错误)
if (chars[i]=="("||chars[i]=="["||chars[i]=="{")//双引号要改成单引号!
  1. 在removeLast之后,只是移除来r就以为没事了
  2. 最后没有增加对只有“(”的判断,要判断栈里是否为空
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        char[] chars = s.toCharArray();
        for(int i = 0;i<chars.length;i++){
            if (chars[i]=='('||chars[i]=='['||chars[i]=='{'){
                stack.add(chars[i]);
            } else if (!stack.isEmpty()&&chars[i]==')'){
                char r = stack.removeLast();
                if (r!='('){
                    return false;
                }
            } else if (!stack.isEmpty()&&chars[i]==']'){
                char r = stack.removeLast();
                if (r!='['){
                    return false;
                }
            } else if (!stack.isEmpty()&&chars[i]=='}'){
                char r = stack.removeLast();
                if (r!='{'){
                    return false;
                }
            } else {
                return false;
            }
        }
        return stack.isEmpty()?true:false;//?
    }

还有一种解法

    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        char[] chars = s.toCharArray();
        for(int i = 0;i<chars.length;i++){
            if (chars[i]=='('){
                stack.add(')');
            }else if (chars[i]=='['){
                stack.add(']');
            } else if (chars[i]=='{'){
                stack.add('}');
            //开始右括号了
            } else if (stack.isEmpty()||chars[i]!=stack.removeLast()){
                return false;
            }
        }
        return stack.isEmpty()?true:false;//?
    }```

29分钟

# 总结
提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文仅仅简单介绍了pandas的使用,而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。