草庐IT

有序数组的平方&长度最小的子数组&螺旋矩阵Ⅱ

neverlate 2023-03-28 原文

一、有序数组的平方

977.有序数组的平方 leetcode链接

1.方法概述

  • 双"指针"解法：因为数组本来是有序的，平方后可能出现的两端大数值大的情况。所以从数组两端开始遍历，谁大就将值赋给新建数组reslut的末端位置index。然后当两端相遇，停止遍历。

2.具体实现

Java实现版本

点击查看代码 
class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int[] arr = new int[nums.length];
        int index = arr.length - 1;

        while(left <= right){
            if(nums[left]*nums[left] > nums[right]*nums[right]){
                arr[index--] = nums[left]*nums[left++];
            }else{
                arr[index--] = nums[right]*nums[right--];
            }
        }
        return arr;
    }
}

3.要点总结

  • 关键点在于数组本来就是有序的，数组元素平方后最大值只可能出现在两端，可能是最右端元素的平方值，也可能是最左端负数的平方值，不可能在中间。
  • index代表的是新建数组result的末端位置，当赋完一次值时需要执行--操作。左端下标left是在赋值完后进行++操作，右端下标right则是执行--操作。这里 nums[left]*nums[left++]； 是在nums[left]*nums[left]；赋值操作完成后left才开始++，同理 nums[right]*nums[right--]；也是在nums[right]*nums[right]再--。当然也可以写成：arr[index--] = nums[left]*nums[left];left++;和arr[index--] = nums[right]*nums[right]; right--;

二、长度最小的子数组

209.最小长度的子数组 leetcode链接

1.方法概述

  • 滑动窗口的思想，当窗口的左边界位置start到窗口右边界位置end的和sum >=目标值target时，这就是最大窗口。然后想象这个最大窗口在一格一格的滑动，当该窗口滑动到数组最右端时，再通过比较和sum与目标值target的大小来判断是否能缩小该窗口的大小，最终返回窗口即为长度最小的连续子数组。

2.具体实现

Java实现版本

点击查看代码 
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int start = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for(int end = 0;end < nums.length;end++){
            sum += nums[end];
            while(sum >= target){
                int len = end - start + 1;
                result = Math.min(result,len);
                sum -= nums[start++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

3.要点总结

  • 本题的时间复杂度要求为O(n)，用暴力解法两个for循环来不断寻找符合条件的子序列的时间复杂度O(n²)不满足题目要求，所以还是需要考虑双指针的思想，也就是本题的滑动窗口思想。
  • 本题的关键之处在于，窗口的起始位置和结束位置的设定和以及如何变动。如果for循环中的用窗口的起始位置start来索引，那么剩下的终止边界位置无法遍历。所以for循环中用窗口的结束位置end索引用来表示窗口的右边界位置并且用来遍历元素。如果当前窗口的和值sum >= 目标值target，则起始位置start就需要向后移动，也就是缩小最大窗口的过程，然后变更sum值。再来判断和值sum是否 >=目标值target，然后就是使用while循环来循环判断只要和值sum >= 目标值target，起始位置start就要移动。
  • 然后就是最小连续子序列的长度变更和返回。长度len就是窗口的起始位置start和结束位置end的差值，因为是数组长度所以还需要+1。result本来定义int类型数组的最大值，也就是最坏情况下为所有元素和值sum才等于目标值target。所以只需把result和len取小赋值给result就是最小的滑动窗口大小，也就是长度最小的连续子数组数组长度。如果没有满足的则返回0。

三、螺旋矩形Ⅱ

59.螺旋矩阵 II leetcode链接

1.方法概述

  • 在控制是左闭右开的循环不变量原则下，按顺时针方向，从上端的从左至右-1处依次填充元素，再是从右端从上至下-1处依次填充元素，再是从下端从右至左-1处依次填充元素，最后是从左端从下至上-1处依次填充元素。然后依次一圈一圈的放入，当循环圈数 > n/2 时停止。如果是填充元素是基数的情况下进行单独赋值。

2.具体实现

Java实现版本

点击查看代码 
class Solution {
    public int[][] generateMatrix(int n) {
        int loop = 0;
        int[][] arr = new int[n][n];
        int start = 0;
        int count = 1;
        int i,j;

        while(loop++ < n/2){
            for(j = start; j< n-loop;j++){
                arr[start][j] = count++;
            }

            for(i = start;i< n-loop;i++){
                arr[i][j] = count++;
            }

            for(;j >= loop;j--){
                arr[i][j] = count++;
            }

            for(;i >= loop;i--){
                arr[i][j] = count++;
            }
            start++;
        }
        if(n % 2 == 1){
            arr[start][start] = count;
        }
        return arr;
    }
}

3.要点总结

  • 关于循环多少loop圈，通过示例观察不难发现，图形为n✖n的矩阵，则填充圈数为n/2，则循环填充的次数也为loop圈。每进一次while循环loop++一次，再判断是否 < n/2。如果大于则不进入循环。
  • 关于填充的规则，矩形有四边，按照二维数组从上到下，从左到右分别定义为i下标和j下标。从上边从左端第一个元素开始，每次转角的元素交给下一边来填充，这样就不会导致填充混乱。从矩形上侧，第一层i是不变的即为定义的start初始值即可，j也是从start定义的初始值开始循环遍历，因为每个转角的元素值都交给下一侧的循环进行填充，所j < n - loop，将arr[start][j] = count++;。从矩形右侧从上往下，j的已近为最右侧边界下标，所以j不变，i从start初始值开始for循环遍历，将arr[i][j] = count++;。然后从矩形的下侧，从右往左，i是不变的，j的初值就是上次循环后的j值，然后j--，当j >= loop时停止循环，因为第一圈loop此时还等于1，此时j的最小值必须保证是1才能确保转角元素没有被赋值给数组arr，然后将arr[i][j]=count++;。从矩形左侧从下至上，j是不变的，当i >= loop时停止循环，然后i--，最后将 arr[i][j] = count++;。然后关键的一步是loop需要while循环处++。
  • 关于基数中心点的，因为start的值也跟着填充循环发生改变，所以最后的中心点就可以将arr[start][start] = count;即可。

仅供个人参考，欢迎批评指正！

amp有序strongemcode算法与数据结构

有关有序数组的平方&长度最小的子数组&螺旋矩阵Ⅱ的更多相关文章

  1. ruby-on-rails - unicode 字符串的长度 - 2

    在我的Rails(2.3，Ruby1.8.7)应用程序中，我需要将字符串截断到一定长度。该字符串是unicode，在控制台中运行测试时，例如'א'.length，我意识到返回了双倍长度。我想要一个与编码无关的长度，以便对unicode字符串或latin1编码字符串进行相同的截断。我已经了解了Ruby的大部分unicode资料，但仍然有些一头雾水。应该如何解决这个问题？ 最佳答案 Rails有一个返回多字节字符的mb_chars方法。试试unicode_string.mb_chars.slice(0,50)

  2. ruby-on-rails - rails : "missing partial" when calling 'render' in RSpec test - 2

    我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身，new.html.erb，有代码:当我运行rspec时，它失败了:1)messages/new.html.erbshou

  3. ruby-on-rails - 由于 "wkhtmltopdf"，PDFKIT 显然无法正常工作 - 2

    我在从html页面生成PDF时遇到问题。我正在使用PDFkit。在安装它的过程中，我注意到我需要wkhtmltopdf。所以我也安装了它。我做了PDFkit的文档所说的一切......现在我在尝试加载PDF时遇到了这个错误。这里是错误:commandfailed:"/usr/local/bin/wkhtmltopdf""--margin-right""0.75in""--page-size""Letter""--margin-top""0.75in""--margin-bottom""0.75in""--encoding""UTF-8""--margin-left""0.75in""-

  4. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

    我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

  5. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  6. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  7. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  8. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  9. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  10. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

随机推荐