Leetcode刷题笔记2:数组基础2

导语

leetcode刷题笔记记录,本篇博客记录数组基础1部分的题目,主要题目包括:

  • 977.有序数组的平方 ,
  • 209.长度最小的子数组 ,
  • 59.螺旋矩阵II

知识点

滑动窗口

所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。一般需要用到双指针来进行求解。

模拟

模拟并不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。 需要对边界值和循环过程进行仔细的考虑。

Leetcode 977 有序数组的平方

题目描述

给你一个按 非递减顺序 排序的整数数组 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]

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶:

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

解法

可以使用双指针,从两边往中间走,这样会得到一个从大到小排列的数组,返回结果时只需要倒置一下就可以了。

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        left, right = 0, len(nums) - 1
        ans_l = []
        while left <= right:
            if abs(nums[left]) >= abs(nums[right]):
                ans_l.append(nums[left] ** 2)
                left += 1
            else:
                ans_l.append(nums[right] ** 2)
                right -= 1
        return ans_l[::-1]

同时,也可以令双指针从中间开始(即从正负数分界处开始),为此,需要先找到正负数的分界线,代码如下:

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 寻找分割点
        cut = -1
        for num in nums:
            if num < 0:
                cut += 1
            else:
                break
        # 这样cut右边都是非负数,左边都是负数
        left, right = cut, cut + 1
        ans_l = []
        while left>= 0 or right <= len(nums)-1:
            if left < 0:
                ans_l.append(nums[right] ** 2)
                right += 1
            elif right > len(nums) - 1:
                ans_l.append(nums[left] ** 2)
                left -= 1
            elif -nums[left] <= nums[right]:
                ans_l.append(nums[left] ** 2)
                left -= 1
            else:
                ans_l.append(nums[right] ** 2)
                right += 1

        return ans_l

Leetcode 209 长度最小的子数组

题目描述

给定一个含有 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

提示:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

解法

最简单的解法为暴力解法,但Leetcode上已经提示,Python的暴力解法一定会超时,所以这里使用滑动窗口来解决这个问题。

暴力解法中一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,那么滑动窗口如何用一个for循环来完成这个操作呢。

一个最关键的问题在于如果用一个for循环,那么应该表示滑动窗口的起始位置,还是终止位置?如果只用一个for循环来表示滑动窗口的起始位置,那么如何遍历剩下的终止位置?此时难免再次陷入暴力解法的怪圈。所以 只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。

滑动窗口解法

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        start, ans = 0, 0
        min_length = len(nums) + 1
        for end in range(len(nums)):
            ans += nums[end]
            while ans >= target:
                min_length = min(end-start+1, min_length)
                ans -= nums[start]
                start += 1
            
        return min_length if min_length <= len(nums) else 0

Leetcode 59 螺旋矩阵II

题目描述

给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1:

输入: n = 3
输出: [[1,2,3],[8,9,4],[7,6,5]]

示例 2:

输入: n = 1
输出: [[1]]

提示:

  • 1 <= n <= 20

解法

这个题目的过程就是模拟,需要考虑好边界值条件,一个解题的关键是处理好区间选取,为了代码统一和边界值统一考虑,应选取左开右闭的区间,即每一行列都只考虑起始位置点,而不考虑终止位置点。

代码如下:

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        matrix = [[0] * n for j in range(n)]
        cnt = 1
        offset = 1
        start_x, start_y =0, 0
        loop = n // 2
        
        while loop:
            for j in range( start_y, n - offset ):
                matrix[start_x][j] = cnt
                cnt += 1
            for i in range( start_x, n - offset ):
                matrix[i][n-offset] = cnt
                cnt += 1
            for j in range( n - offset, start_y, -1):
                matrix[n-offset][j] = cnt
                cnt += 1
            for i in range( n - offset, start_x, -1):
                matrix[i][start_y] = cnt
                cnt += 1
            start_x += 1
            start_y += 1
            offset += 1
            loop -= 1

        if n%2 == 1:
            matrix[n//2][n//2] = n * n 

        return matrix

参考

  • 代码随想录
  • 题解

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/633959.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

(二)vForm 动态表单设计器之下拉、选择

系列文章目录 &#xff08;一&#xff09;vForm 动态表单设计器之使用 目录 系列文章目录 前言 一、后端需提供接口 二、组件配置 总结 前言 动态表单下拉、选择等组件&#xff0c;大概率要使用数据库中的数据&#xff0c;那么vForm如何拿到数据库中的数据呢&#xff1f;跟随…

Xed编辑器开发第二期:使用Rust从0到1写一个文本编辑器

第三篇 这部分接着处理用户退出命令以及一些其他新功能&#xff1b; 3.1 使用CtrlQ退出 modifiers: event::KeyModifiers::CONTROL,使用CONTROL替换之前的NONE值即可&#xff1b; 3.2 重构键盘输入 让我们重构我们的代码&#xff0c;以便我们有一个用于低级按键读取的函数&…

php部分特性漏洞学习

php部分函数漏洞学习 简单总结一些我遇到的ctf中的php的一些函数或特性的漏洞&#xff0c;我刷题还是太少了&#xff0c;所以很多例子来自ctfshow&#xff0c;以后遇到相关赛题再更新 1.MD5和其他hash 弱类型比较 php中&#xff0c;有两中判断相等的符号&#xff0c;和&…

flutter使用dbus插件时,在终端无法使用“dart-dbus”命令

不用flutter的人&#xff0c;可能都不会找到这儿&#xff0c;遇到这个问题&#xff0c;所以这里默认flutter已经装过了&#xff0c;且对flutter如何使用插件也有所了解了。 由于我在项目中用到了dbus插件&#xff0c;用法如图所示&#xff0c;我需要使用这条命令来生成一个sou…

前端javascript包管理,npm升级用pnpm

一 pnpm 介绍 pnpm&#xff08;Package Manager&#xff09;是一个快速、节省磁盘空间的 JavaScript 包管理器&#xff0c;它是 Node.js 生态系统中 npm 的一个替代品。pnpm 解决了传统包管理工具在处理依赖时的一些痛点&#xff0c;特别是关于存储空间使用和依赖地狱的问题。…

vite vue-cli 之vue3安装Vue devtools调试工具

一.vite的官方配置-vite-plugin-vue-devtools vite.config.js import { fileURLToPath, URL } from node:urlimport vue from vitejs/plugin-vue import vueJsx from vitejs/plugin-vue-jsx import { defineConfig } from vite import VueDevTools from vite-plugin-vue-devt…

Android JetPack ViewModel

一、什么是ViewModel&#xff1f; Android ViewModel在我们使用MVVM开发模式时会经常用到&#xff0c;对我来说就是好用&#xff0c;好维护。 它相对于MVC模式&#xff0c; 一来可以减少Activity层的代码&#xff0c;可以把一些业务逻辑和对数据的交互到ViewModel层去&#…

Excel模板计算得出表格看板

背景 表格看板及导出&#xff0c;单元格时间年是根据筛选器时间变化的 较往年和往年是计算单元格 思路 1.通过excel模板来把数据填入excel再数据清洗得到数据返回前端 2.数据填充&#xff0c;通过行列作为key 列如&#xff1a;key整体20241月&#xff0c;根据key匹配数据填…

计算机操作系统总结(1)

1操作系统的概念&#xff08;定义&#xff09;功能和目标 (1)什么是操作系统&#xff1f; &#xff08;2&#xff09;操作系统的功能和目标—作为系统资源的管理者 &#xff08;3&#xff09;操作系统的功能和目标—向上层提供方便易用的服务 &#xff08;4&#xff09;操作系…

中银基金软件开发工程师春招群面记录

本文介绍2024届春招中&#xff0c;中国银行下属中银基金管理有限公司的软件开发工程师岗位1场面试的基本情况、提问问题等。 2024年04月投递了中国银行的共计4个部门或单位&#xff0c;包括中银基金管理有限公司的软件开发工程师岗位&#xff0c;暂时不清楚所在部门。目前完成了…

平均分配问题

将dwd_phone_shop这六行数据按照1 3 5,2 4 6的排序分为两组,与dwd_phone_base连接,分别与为其中1 3 5 为shop_Id为1的那一组 2 4 6 为shop_Id为2 的那一组 取余法 开窗函数法

南加州大学字节提出MagicPose,提供逼真的人类视频生成,实现生动的运动和面部表情传输,以及不需要任何微调的一致的野外零镜头生成。

MagicPose可以精确地生成外观一致的结果&#xff0c;而原始的文本到图像模型(如Stable Diffusion和ControlNet)很难准确地保持主体身份信息。 此外&#xff0c;MagicPose模块可以被视为原始文本到图像模型的扩展/插件&#xff0c;而无需修改其预训练的权重。 相关链接 论文链…

javaSwing飞机订票系统

摘要 Java swing实现的飞机票预定系统&#xff0c;系统数据库原本采用的是Oracle&#xff0c;我又改了一个mysql版本的&#xff0c;所以这套系统有两个版本&#xff0c;一个是mysql数据库版的&#xff0c;一个是Oracle数据库版 一&#xff0e; 已经完成的功能 &#xff1a; …

Linux基础命令[27]-gpasswd

文章目录 1. gpasswd 命令说明2. gpasswd 命令语法3. gpasswd 命令示例3.1 不加参数3.2 -a&#xff08;将用户加入组&#xff09;3.3 -d&#xff08;从组中删除用户&#xff09;3.4 -r&#xff08;删除组密码&#xff09;3.5 -M&#xff08;多个用户一起加入组&#xff09;3.6 …

excel里如何将数据分组转置?

这个表格怎样转换为下表&#xff1f;按照国家来分组&#xff0c;把不同年份对应的不同序列值进行转置&#xff1f;&#xff1f; 这演示用数据透视表就完成这个数据转换。 1.创建数据透视表 选中数据中任意单元格&#xff0c;点击插入选项卡&#xff0c;数据透视表&#xff0c;…

C++设计模式|结构型 适配器模式

1.什么是适配器模式&#xff1f; 可以将⼀个类的接⼝转换成客户希望的另⼀个接⼝&#xff0c;主要⽬的是 充当两个不同接⼝之间的桥梁&#xff0c;使得原本接⼝不兼容的类能够⼀起⼯作。 2. 适配器模式的组成 &#xff08;1&#xff09;接口类&#xff0c;给客户端调用&…

vue打包部署到springboot,通过tomcat运行

tomcat默认端口 8080springboot端口 9132vue 端口 9131 框架 项目是基于SpringBootVue前后端分离的仓库管理系统 后端&#xff1a;SpringBoot MybatisPlus前端&#xff1a;Node.js Vue element-ui数据库&#xff1a;mysql 一. 打包Vue项目 cmd中输入命令 npm run build 后…

PHP在线制作表白网源码

PHP在线制作表白网源码&#xff0c;送女友个惊喜吧&#xff0c;无数据库&#xff0c;上传就能用&#xff0c;后台/admin&#xff0c;账号密码都是admin 百度网盘&#xff1a;https://pan.baidu.com/s/1rbD2_8IsP9UPLK-cdgEXfA?pwdre59

前端绘制流程节点数据

根据数据结构和节点的层级、子节点id&#xff0c;前端自己绘制节点位置和关联关系、指向、已完成节点等 <template><div><div>通过后端节点和层级&#xff0c;绘制出节点以及关联关系等</div><div class"container" ref"container&…

本地centos7+docker+ollama+gpu部署

1、一台有 NVIDIA GPU 驱动的机器 2、Docker CE安装 # 删除旧版本的 Docker&#xff08;如果存在&#xff09; sudo yum remove -y docker docker-common docker-selinux docker-engine # 安装必要的软件包&#xff1a; sudo yum install -y yum-utils device-mapper-persiste…