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] <= 104nums已按 非递减顺序 排序
进阶:
- 请你设计时间复杂度为
O(n)的算法解决本问题
解法
可以使用双指针,从两边往中间走,这样会得到一个从大到小排列的数组,返回结果时只需要倒置一下就可以了。
class Solution(object):def sortedSquares(self, nums):""":type nums: List[int]:rtype: List[int]"""left, right = 0, len(nums) - 1ans_l = []while left <= right:if abs(nums[left]) >= abs(nums[right]):ans_l.append(nums[left] ** 2)left += 1else:ans_l.append(nums[right] ** 2)right -= 1return ans_l[::-1]
同时,也可以令双指针从中间开始(即从正负数分界处开始),为此,需要先找到正负数的分界线,代码如下:
class Solution(object):def sortedSquares(self, nums):""":type nums: List[int]:rtype: List[int]"""# 寻找分割点cut = -1for num in nums:if num < 0:cut += 1else:break# 这样cut右边都是非负数,左边都是负数left, right = cut, cut + 1ans_l = []while left>= 0 or right <= len(nums)-1:if left < 0:ans_l.append(nums[right] ** 2)right += 1elif right > len(nums) - 1:ans_l.append(nums[left] ** 2)left -= 1elif -nums[left] <= nums[right]:ans_l.append(nums[left] ** 2)left -= 1else:ans_l.append(nums[right] ** 2)right += 1return 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 <= 1091 <= nums.length <= 1051 <= 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, 0min_length = len(nums) + 1for end in range(len(nums)):ans += nums[end]while ans >= target:min_length = min(end-start+1, min_length)ans -= nums[start]start += 1return 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 = 1offset = 1start_x, start_y =0, 0loop = n // 2while loop:for j in range( start_y, n - offset ):matrix[start_x][j] = cntcnt += 1for i in range( start_x, n - offset ):matrix[i][n-offset] = cntcnt += 1for j in range( n - offset, start_y, -1):matrix[n-offset][j] = cntcnt += 1for i in range( n - offset, start_x, -1):matrix[i][start_y] = cntcnt += 1start_x += 1start_y += 1offset += 1loop -= 1if n%2 == 1:matrix[n//2][n//2] = n * n return matrix
参考
- 代码随想录
- 题解
相关文章:
Leetcode刷题笔记2:数组基础2
导语 leetcode刷题笔记记录,本篇博客记录数组基础1部分的题目,主要题目包括: 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II 知识点 滑动窗口 所谓滑动窗口,就是不断的调节子序列的起始位…...
整理好了!2024年最常见 20 道 Redis面试题(八)
上一篇地址:整理好了!2024年最常见 20 道 Redis面试题(七)-CSDN博客 十五、Redis 的性能调优有哪些方法? Redis的性能调优是一个多方面的工作,涉及到硬件、配置、代码层面的优化等多个方面。以下是一些常…...
【STM32项目】基于stm32智能鱼缸控制系统的设计与实现(完整工程资料源码)
实物演示效果 基于stm32智能鱼缸控制系统的设计与实现 目录: 实物演示效果 目录: 一、 绪论...
深入理解 Mysql 分层架构:从存储引擎到查询优化器的内部机制解析
一、基础架构 1.连接器 1.会先连接到这个数据库上,这时候接待你的就是连接器。连接器负责跟客户端建立连接、获取权限、维持和管理连接 2.用户密码连接成功之后,会从权限表中拿出你的权限,后续操作权限都依赖于此时拿出的权限,这就意味着当链…...
Java筑基(三)
Java筑基(三) 一、final概念1、案例1:采用继承:2、案例2:final修饰的类不可以被继承:3、案例3:final修饰的类不能有子类,但是可以有父类4、final修饰构造方法5、final修饰普通方法6、…...
Zoho Campaigns邮件营销怎么发邮件?
Zoho Campaigns,作为业界领先的邮件营销平台,以其强大的功能、用户友好的界面以及深度的分析能力,为企业提供了一站式的邮件营销解决方案,助力企业高效地触达目标受众,构建并巩固庞大的客户基础。云衔科技为企业提供Zo…...
Qt 界面上字体自适应控件大小 - 随控件缩放
Qt 界面上字体自适应控件大小 - 随控件缩放 引言一、设计思路二、进阶版大致思路三、参考链接 引言 Qt控件自适应字体大小可以用adjustSize()函数,但字体自适应控件大小并没有现成的函数可调. - 本文实现了按钮上的字体随按钮大小变化而变化 (如上图所示) - 其他控件…...
【Python】 使用SMOTE解决数据不平衡问题
原谅把你带走的雨天 在渐渐模糊的窗前 每个人最后都要说再见 原谅被你带走的永远 微笑着容易过一天 也许是我已经 老了一点 那些日子你会不会舍不得 思念就像关不紧的门 空气里有幸福的灰尘 否则为何闭上眼睛的时候 又全都想起了 谁都别说 让我一个人躲一躲 你的承诺 我竟然没怀…...
Redis第18讲——Redis和Redission实现延迟消息
即使不是做电商业务的同学,也一定知道订单超时关闭这种业务场景,这个场景大致就是用户下单后,如果在一定时间内未支付(比如15分钟、半小时),那么系统就会把这笔订单给关闭掉。这个功能实现的方式有很多种&a…...
返回枚举类给前端
1. 前言 在实际开发过程中,前端的下拉框或者单选按钮的内容通常的需要和后端匹配的,故一般会由后端将下拉框的内容或单选框的内容传给前端,而这些内容在后端一般是由枚举类存储的,如果后端直接返回枚举类,返回结果将会…...
A. Maximize?
time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output You are given an integer x𝑥. Your task is to find any integer y𝑦 (1≤y<x)(1≤𝑦<𝑥) su…...
RBAC 动态权限
文章目录 前言一、RBAC(Role-Based Access Control,基于角色的访问控制)二、Java实现RBAC 权限的大概思路1. 添加依赖2. 配置MyBatis-Plus和数据源1. 添加依赖2. 实体类与Mapper接口UserMapper.java 3. 配置MyBatis-Plus4. 自定义UserDetails…...
c语言:模拟strlen(三种方法)最全版本
1.计数的方法 #include <stdio.h> #include <assert.h> int my_strlen(const char * str)//const的使用优化 {int count0;assert(str)while(*str){count;str;}return count; } 2.用指针的方法(指针-指针) #include <stdio.h> #incl…...
线性模型--普通最小二乘法
线性模型 一、模型介绍二、用于回归的线性模型2.1 线性回归(普通最小二乘法) 一、模型介绍 线性模型是在实践中广泛使用的一类模型,该模型利用输入特征的线性函数进行预测。 二、用于回归的线性模型 以下代码可以在一维wave数据集上学习参…...
移动云以深度融合之服务,令“大”智慧贯穿云端
移动云助力大模型,开拓创新领未来。 云计算——AI模型的推动器。 当前人工智能技术发展的现状和趋势,以及中国在人工智能领域的发展策略和成就。确实,以 ChatGPT 为代表的大型语言模型在自然语言处理、文本生成、对话系统等领域取得了显著的…...
簡述vue常用指令
Vue.js 提供了许多内置指令,这些指令用于在模板中添加特殊功能。以下是一些 Vue 的常用内置指令的简要说明: v-text: 更新元素的 textContent。示例:<span v-text"message"></span> v-html: 更…...
【建议收藏】用AI快速生成一个网页(名侦探柯南~灰原哀主题网页),适合大学生web期末大作业
下面是提供给AI的提示词和AI给出的代码以及成果展示 1、生成一个网页导航栏,宽度为1300px,高度为60px。导航区域在导航栏最右侧不超出导航栏,高60px,宽度500px,里面是5个导航菜单项横向排列,每个宽度100px&…...
用c++用4个凸函数(觉得啥好用用啥)去测试adam,rmsprop,adagrad算法的性能(谁先找到最优点)
为了测试 Adam、RMSProp 和 Adagrad 算法的性能,你可以使用四个凸函数进行实验。以下是一些常用的凸函数示例: Rosenbrock 函数: Booth 函数: Himmelblau 函数: Beale 函数: 你可以选择其中一个或多…...
AJAX初级
AJAX的概念: 使用浏览器的 XMLHttpRequest 对象 与服务器通信 浏览器网页中,使用 AJAX技术(XHR对象)发起获取省份列表数据的请求,服务器代码响应准备好的省份列表数据给前端,前端拿到数据数组以后…...
重载大于号运算符,比较复数大小
本题目要求编写代码的功能为: 输入两个复数(变量名自拟),比较复数模的大小,复数实部与虚部都是整数 要求输入时输入4个整数,分别代表复数1的实部、虚部,复数2的实部虚部 输入格式: 在同一行中输…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
