当前位置: 首页 > news >正文

算法刷题 week2

目录

  • week2
  • 1. 二维数组中的查找
        • 题目
        • 题解
          • (单调性扫描) O(n+m)
  • 2.替换空格
        • 题目
        • 题解
          • (线性扫描) O(n)
          • (双指针扫描) O(n)
  • 3.从尾到头打印链表
        • 题目
        • 题解
          • (遍历链表) O(n)

week2

1. 二维数组中的查找

题目

在这里插入图片描述

题解

(单调性扫描) O(n+m)

核心在于发现每个子矩阵右上角的数的性质:

  • 如下图所示,x左边的数都小于等于x,x下边的数都大于等于x。

在这里插入图片描述

因此我们可以从整个矩阵的右上角开始枚举,假设当前枚举的数是 x:

  • 如果 x 等于target,则说明我们找到了目标值,返回true;
  • 如果 x 小于target,则 x 左边的数一定都小于target,我们可以直接排除当前一整行的数;
  • 如果 x 大于target,则 x 下边的数一定都大于target,我们可以直接排除当前一整列的数;

排除一整行就是让枚举的点的横坐标加一,排除一整列就是让纵坐标减一。
当我们排除完整个矩阵后仍没有找到目标值时,就说明目标值不存在,返回false。

时间复杂度分析

每一步会排除一行或者一列,矩阵一共有 n 行,m 列,所以最多会进行n+m 步。所以时间复杂度是 O(n+m)。

class Solution {
public:bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {if (array.empty() || array[0].empty()) return false;int i = 0, j = array[0].size() - 1;  // j 初始为右上角的位置while (i < array.size() && j >= 0) {if (array[i][j] == target) return true;if (array[i][j] > target) --j;  // 锁定当前行,排除当前列else ++i;  // 排除当前行,往下搜索}return false;}
};

2.替换空格

题目

在这里插入图片描述

题解

(线性扫描) O(n)

这个题在C++里比较好做,我们可以从前往后枚举原字符串:

  • 如果遇到空格,则在string类型的答案中添加 "%20"
  • 如果遇到其他字符,则直接将它添加在答案中;

但在C语言中,我们没有string这种好用的模板,需要自己malloc出char数组来存储答案。
此时我们就需要分成三步来做:

  1. 遍历一遍原字符串,计算出答案的最终长度;
  2. malloc出该长度的char数组;
  3. 再遍历一遍原字符串,计算出最终的答案数组;

时间复杂度分析

原字符串只会被遍历常数次,所以总时间复杂度是 O(n)。

class Solution {
public:string replaceSpaces(string &str) {string res;for (auto x : str)if (x == ' ')res += "%20";else res += x;return res;}
};
(双指针扫描) O(n)

在部分编程语言中,我们可以动态地将原数组长度扩大,此时我们就可以使用双指针算法,来降低空间的使用:

  1. 首先遍历一遍原数组,求出最终答案的长度length;
  2. 将原数组resize成length大小;
  3. 使用两个指针,指针i指向原字符串的末尾,指针j指向length的位置;
  4. 两个指针分别从后往前遍历,如果str[i] == ' ',则指针j的位置上依次填充'0', '2', '%',这样倒着看就是"%20";如果str[i] != ' ',则指针j的位置上填充该字符即可。

由于i之前的字符串,在变换之后,长度一定不小于原字符串,所以遍历过程中一定有i <= j,这样可以保证str[j]不会覆盖还未遍历过的str[i],从而答案是正确的。

时间复杂度分析

原字符串只会被遍历常数次,所以总时间复杂度是 O(n)。

class Solution {
public:string replaceSpaces(string &str) {int len = 0;for (auto c : str)if (c == ' ') len += 3;else len++;//str.size() 字符串中有几个字符,大小就为几    //定义两个指针,字符串的长度和实际下标位置差1int i = str.size() - 1, j = len - 1;  str.resize(len);  //调整字符串大小while (i >= 0) {if (str[i] == ' ') {str[j--] = '0';str[j--] = '2';str[j--] = '%';}else str[j--] = str[i];i--;}return str;}
};

3.从尾到头打印链表

题目

在这里插入图片描述

题解

(遍历链表) O(n)

单链表只能从前往后遍历,不能从后往前遍历。

因此我们先从前往后遍历一遍输入的链表,将结果记录在答案数组中。
最后再将得到的数组逆序即可。

语法补充:

begin
语法:iterator begin();
解释:begin()函数返回一个迭代器,指向字符串的第一个元素.

end
语法:iterator end();
解释:end()函数返回一个迭代器,指向字符串的末尾(最后一个字符的下一个位置).

rbegin
语法:const reverse_iterator rbegin();
解释:rbegin()返回一个逆向迭代器,指向字符串的最后一个字符。

rend
语法:const reverse_iterator rend();
解释:rend()函数返回一个逆向迭代器,指向字符串的开头(第一个字符的前一个位置)。

在这里插入图片描述

时间复杂度分析
链表和答案数组仅被遍历了常数次,所以总时间复杂度是 O(n)。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vector<int> printListReversingly(ListNode* head) {vector<int> res;while (head) {res.push_back(head->val);head = head->next;}return vector<int>(res.rbegin(), res.rend()); //反向迭代器}
};

相关文章:

算法刷题 week2

目录 week21. 二维数组中的查找题目题解(单调性扫描) O(nm) 2.替换空格题目题解(线性扫描) O(n)(双指针扫描) O(n) 3.从尾到头打印链表题目题解(遍历链表) O(n) week2 1. 二维数组中的查找 题目 题解 (单调性扫描) O(nm) 核心在于发现每个子矩阵右上角的数的性质&#xff1…...

子网的划分

强化计算机网络发现王道没有这一块的内容&#xff0c;导致做题稀里糊涂。于是个人调研补充。 子网划分是将一个大型IP网络划分成更小的子网&#xff0c;以实现更有效的网络管理和资源分配。 原因&#xff1a; 提高网络性能&#xff1a;子网划分可以减少广播域的大小&#xff…...

Docker安装与卸载

Docker安装与卸载 安装 yum install -y yum-utils \device-mapper-persistent-data \lvm2 --skip-broken更新本地镜像源 打开终端或 SSH 连接到 Rocky Linux 的服务器。 进入 /etc/yum.repos.d/ 目录&#xff0c;该目录包含 Rocky Linux 的 yum 配置文件。 cd /etc/yum.repo…...

【Davinci开发】:开发过程问题记录及总结

开发过程问题总结 1、SWC访问系统OS Timer返回值异常a、代码发现,RTE接口为未连接状态b、连接后,仍然有问题,单步调试,发现没有访问权限当新平台基于之前平台的代码而延续开发时(应用代码相同,但是芯片已经更换),记录开发过程中遇所到的问题,单步调试,逐一排查。 1、…...

数据结构——排序算法——冒泡排序

冒泡排序1 void swap(vector<int> arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}void bubbleSort1(vector<int> arr) {for (int i 0; i < arr.size() - 1; i){for (int j 0; j < arr.size() - 1 - i; j){if (arr[j] > arr[j 1…...

vscode使用

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 例如&#xff1a;…...

python经典百题之求前!的和

题目&#xff1a;求12!3!…20!的和 方法一&#xff1a; 使用for循环和阶乘函数计算每项的值&#xff0c;再将每项的值累加起来。 def factorial(n):if n 0:return 1else:return n * factorial(n-1)sum 0 for i in range(1, 21):sum factorial(i) * iprint(sum)优点&#…...

C语言入门Day_22 初识指针

目录 前言&#xff1a; 1.内存地址 2.指针的定义 3.指针的使用 4.易错点 5.思维导图 前言&#xff1a; 之前我们学过变量可以用来存储数据&#xff0c;就像一个盒子里面可以放不同的球一样。 这是一个方便大家理解专业概念的比喻。 在计算机世界里面&#xff0c;数据实…...

【面试必刷TOP101】删除链表的倒数第n个节点 两个链表的第一个公共结点

目录 题目&#xff1a;删除链表的倒数第n个节点_牛客题霸_牛客网 (nowcoder.com) 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com) …...

手刻 Deep Learning -第壹章 -PyTorch教学-激励函数与感知机入门(上)

一、前言 本文接续前篇教学 Pytorch 与线性回归 &#xff0c;本文着重在 Activation Function &#xff08; 中文称 激励函数 &#xff09;&#xff0c;我们会介绍激励函数 &#xff08;也有人称 激活函数&#xff1f; 激发函数&#xff1f; &#xff09; 为什么会有用&#xf…...

物理内存分配

目录 内核物理内存分配接口 内存分配行为&#xff08;物理上&#xff09; 内存分配的行为操作 内存 三个水位线 水线计算 水位线影响内存分配行为 内存分配核心__alloc_pages 释放页 1、内核物理内存分配接口 struct page *alloc_pages(gfp_t gfp, unsigned int ord…...

RFID产线自动化升级改造管理方案

应用背景 在现代制造业中&#xff0c;产线管理是实现高效生产和优质产品的关键环节&#xff0c;产线管理涉及到生产过程的监控、物料管理、工艺控制、质量追溯等多个方面&#xff0c;有效的产线管理可以提高生产效率、降低成本、改善产品质量&#xff0c;并满足市场需求的变化…...

全量数据采集:不同网站的方法与挑战

简介 在当今数字化时代中&#xff0c;有数据就能方便我们做出很多决策。数据的获取与分析已经成为学术研究、商业分析、战略决策以及个人好奇心的关键驱动力。本文将分享不同网站的全量数据采集方法&#xff0c;以及在这一过程中可能会遇到的挑战。 部分全量采集方法 1. 撞店…...

Redis——渐进式遍历和数据库管理命令

介绍 如果使用keys * 这样的操作&#xff0c;将Redis中所有的key都获取到&#xff0c;由于Redis是单线程工作&#xff0c;这个操作本身又要消耗很多时间&#xff0c;那么就会导致Redis服务器阻塞&#xff0c;后续的操作无法正常执行 而渐进式遍历&#xff0c;通过多次执行遍历…...

如何打造可视化警务巡防通信解决方案

近年来&#xff0c;科学技术飞速发展&#xff0c;给予了犯罪分子可乘之机。当面临专业化的犯罪分子、高科技的犯罪手段&#xff0c;传统警务模式似乎不能满足警方打击犯罪的需要&#xff0c;因此当今公安工作迫切需要构建智能化、系统化、信息化的警务通信管理模式。 警务人员…...

ATF(TF-A) SPMC威胁模型-安全检测与评估

安全之安全(security)博客目录导读 ATF(TF-A) 威胁模型汇总 目录 一、简介 二、评估目标 1、数据流图 三、威胁分析 1、信任边界 2、资产 3、威胁代理 4、威胁类型 5、威胁评估 5.1 端点在直接请求/响应调用中模拟发送方或接收方FF-A ID 5.2 篡改端点和SPMC之间的…...

BIO AIO NIO 的区别

BIO AIO NIO 是 Java 中用于 I/O 操作的三种不同的编程模型。它们的区别在于它们执行I/O 操作的方式和效率。在讲 BIO,NIO,AIO 之前先来回顾一下这样几个概念&#xff1a;同步与异步&#xff0c;阻塞与非阻塞。 同步与异步 同步&#xff1a;同步就是发起一个调用后&#xff…...

大数据学习1.1-Centos8网络配置

1.查看虚拟网卡 2.配置网络信息 打勾处取消 记住箭头的数字 3.修改 网络连接 4.进入虚拟网络 5.进入属性 6.修改IPv4 5.将iIP和DNS进行修改 6.配置网络信息-进入修改网络配置文件 # 进入root用户 su root # 进入网络配置文件 cd /etc/sysconfig/network-scripts/ # 修改网络配…...

在Android studio 创建Flutter项目运行出现问题总结

在Android studio 中配置Flutter出现的问题 A problem occurred configuring root project ‘android’出现这个问题。解决办法 首先找到flutter配置的位置 在D:\xxx\flutter\packages\flutter_tools\gradle位置中的flutter.gradle buildscript { repositories { googl…...

Ceph入门到精通-ceph对于长文件名如何处理

RADOS object with short name 上一篇博文&#xff0c;我们将介绍了对象相关的数据结构ghobject_t&#xff0c;以及对象在底层文件系统存储的文件名&#xff0c;以及如何从文件名对应到 ghobject_t对象。 映射关系如下图所示&#xff1a; 这里面有一个漏洞&#xff0c;即obje…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...