首页 > 其他分享 >代码随想录day 02 双指针 滑动窗口 螺旋矩阵

代码随想录day 02 双指针 滑动窗口 螺旋矩阵

时间:2023-12-28 20:33:51浏览次数:34  
标签:02 窗口 矩阵 复杂度 随想录 算法 数组 day 指针

有序数组的平方题目如下:

如果是可以使用O(nlogn)或以上复杂度的算法,本题可以简单的先平方一遍,然后使用排序算法就可以了
但是要求使用O(n)复杂度的算法,那么我首先想到的是昨天的快慢指针类似的想法:
我想先平方一次数组,然后从中间开始排序,如下

但是运行之后发现从中间开始进行相邻元素的比较好像很难达到O(n)的复杂度,开始卡壳

看了题解思路发现我的解法正好相反,其实这个数组给的是一个有序的数组,那么他的平方最大值应该是在两边出现,那么
两个指针从两边向中间靠拢指针直接互相比较就可以获得有序数组了,而如果从中间比较,我们没办法知道最小值的具体位置,
而且随着数组的元素个数是奇数还是偶数也会发生一定的变化,更极端的,如果数组只有一个负数和一万个正数,那么最小值
将在左端出现而不是中间,大大增加了比较的难度,也就达不到O(n)的时间复杂度

对vector容器有点不熟悉,没有确定容量报了一下数组空间的问题

规范化初始vector后问题迎刃而解

寻找长度最小的子数组题目如下:

对于O(n)级别的算法 没什么思路 想到有点类似动态规划但又不太一样 只能先看看视频的思路讲解 再尝试

第一次尝试判断写了if 错了

应该是写成while 如果写的是if 那么满足条件窗口的右端就会继续划 窗口长度都不会改变
最小的窗口肯定找不到
个人解法如下:

其实后面一个for可以省去,只要赋值一个特别大的值,做完算法之后看看这个值有没有被修改就行了

螺旋矩阵题目:

螺旋矩阵完全没有接触过 没有一点思路

看了视频之后有点想太多 难点不在于算法而是边界的上的处理

这里我的解法统一使用offset来表示每圈的起始坐标

写的时候笨比了一下 直接while条件写成了 n /2 每圈还要--的 得再开个变量

标签:02,窗口,矩阵,复杂度,随想录,算法,数组,day,指针
From: https://www.cnblogs.com/mingtiao/p/17932469.html

相关文章

  • 软件开发者必读!2024年30大趋势提前曝光!
    软件是科技行业的基础。从智能手机到复杂的企业系统,软件是推动这些技术的核心。在探索数字时代的过程中,了解软件开发的趋势非常重要。人工智能、机器学习、物联网等技术的快速发展对软件开发行业产生了巨大影响。本文旨在通过30个数据汇总,帮助读者们初步了解2024年软件开发领域的新......
  • 2023-2024-1 20231329 《计算机基础与程序设计》第14周学习总结
    作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP这个作业要求在哪里2022-2023-1计算机基础与程序设计第14周作业(https://www.cnblogs.com/rocedu/p/9577842.html)这个作业的目标《C语言程......
  • 2023-2024 20231313《计算机基础与程序设计》第十四周学习总结
    2023-202420231313《计算机基础与程序设计》第十四周学习总结作业速达作业课程班级链接作业要求计算机基础与程序设计第十四周学习总结作业内容《C语言程序设计》第13章并完成云班课测试作业正文我的作业目录教材总结总结学习过程中的问题《C语言程......
  • 【eBPF-02】入门:基于 BCC 框架的程序进阶
    本文是eBPF系列的第二篇文章,我们来学习eBPFBCC框架的进阶用法,对上一篇文章中的代码进行升级,动态输出进程运行时的参数情况。主要内容包括:通过kprobe挂载内核事件的eBPF程序要如何编写?通过tracepoint挂载内核事件的eBPF程序要如何编写?eBPF的程序事件类型有哪些......
  • Day1
    Markdown学习标题三级标题###+空格+文字文字**+文字粗体*+文字斜体+文字删除图片超链接[2323](百度一下,你就知道(baidu.com))列表1.+空格或无序列表-+空格表格|姓名|性别|姓名性别代码```public......
  • 重磅发布|博睿数据2023年度精选案例集—— IT运维之光
    当前,数字经济已经成为全球经济增长的重要引擎。随着新技术的飞速发展,企业数字化转型机遇不断涌现,而稳定、安全、可靠的IT运维环境是实现数字化转型的关键。在此背景下,AIOps智能运维正成为企业高效管控种类繁多数量庞大的物理设备、精准定位故障信息、实时防护网络攻击、快速迭代需......
  • 2024跨年微信背景图
    ......
  • Diffie-Hellman Key Agreement Protocol 安全漏洞 (CVE-2002-20001)【原理扫描】
    Diffie-HellmanKeyAgreementProtocol是一种密钥协商协议。它最初在Diffie和Hellman关于公钥密码学的开创性论文中有所描述。该密钥协商协议允许Alice和Bob交换公钥值,并根据这些值和他们自己对应的私钥的知识,安全地计算共享密钥K,从而实现进一步的安全通信。仅知道交换......
  • JavaWeb - Day13 - 事务管理、AOP(基础、进阶、案例)
    01.事务管理-事务回顾-spring事务管理1.1事务回顾在数据库阶段我们已学习过事务了,我们讲到:事务是一组操作的集合,它是一个不可分割的工作单位。事务会把所有的操作作为一个整体,一起向数据库提交或者是撤销操作请求。所以这组操作要么同时成功,要么同时失败。怎么样来控制这组......
  • 世微 AP2402 DC-DC降压恒流驱动IC 刹车灯 半亮 高亮瀑闪线路图
    产品描述AP2402是一款PWM工作模式,高效率、外围简单、内置功率管,适用于5-100V输入的高精度降压LED恒流驱动芯片。输出功率可达15W,电流1.5A。AP2402可实现三段功能切换,通过MODE1/2/3切换三种功能模式:全亮,半亮,爆闪,全亮/半亮/爆闪循环模式。AP2402工作频率固定在150KHZ左......