Leetcode刷题笔记9

1. 两数之和

1. 两数之和 - 力扣(LeetCode)

解法一:暴力枚举

没什么好说的,直接使用两个for循环,i从第一个元素开始,j从第二个元素开始遍历并寻找

时间复杂度:O(N^2)

空间复杂度:O(1)

代码:C++

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for(int i=0; i<n; i++){for(int j=i+1; j<n; j++){if(nums[i]+nums[j]==target){return {i,j};}}}return {};}};

 解法二:哈希表 - 空间换时间

哈希表是一种用于高效地存储和查找数据的数据结构。它基于哈希函数将键映射到表中的位置,通常称为桶。

例如:

nums = [2, 7, 11, 15]target = 9

第一次迭代

  • i = 0nums[i] = 2
  • 查找 target - nums[i] = 9 - 2 = 7 在哈希表中不存在。
  • 2 和索引 0 存入哈希表:hmap[2] = 0

第二次迭代

  • i = 1nums[i] = 7
  • 查找 target - nums[i] = 9 - 7 = 2 在哈希表中存在,索引为 0
  • 找到目标值,返回索引 [0, 1]

通过使用额外的空间(哈希表),将时间复杂度从暴力解法的 O(n^2) 降低到 O(n)

时间复杂度:O(N)

空间复杂度:O(N)

代码:C++

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hmap; // 定义一个哈希表for (int i = 0; i < nums.size(); ++i) { // 遍历数组中的每一个元素auto it = hmap.find(target - nums[i]); // 在哈希表中查找是否存在使得和为 target 的元素if (it != hmap.end()) { // 如果找到return {it->second, i}; // 返回对应的索引}hmap[nums[i]] = i; // 将当前元素及其索引存入哈希表}return {};}};

9. 回文数

9. 回文数 - 力扣(LeetCode)

判断一个整数是否是回文数的核心思路是:将该整数的一半反转,然后与原整数的另一半进行比较。如果两部分相等,那么这个整数就是回文数。

解法一:暴力解法

  • 将整数转换为字符串。
  • 反转字符串。
  • 检查原字符串和反转后的字符串是否相等。
bool isPalindrome(int x) {if (x < 0) return false;std::string str = std::to_string(x);std::string rev_str = std::string(str.rbegin(), str.rend());return str == rev_str;
}

缺点:

  • 空间复杂度高:需要额外的空间来存储字符串和反转后的字符串。
  • 效率较低:字符串操作和反转可能会比较耗时。

优化:因为回文数是前后对应的,所以只需要反转一半的数字就可以知道它是不是回文数

解法二:优化

首先排除里面带0的组合,比如x<0,或者x以0结尾但不等于0

然后反转数字的一半:

  • x 大于 revertedNumber 时,进入循环。
  • 在每次循环中,将 x 的最后一位数字加到 revertedNumber 的末尾。
  • 然后将 x 去掉最后一位数字(通过整除 10)

 最后判断:

  • x 的长度是偶数时,x 应该等于 revertedNumber
  • x 的长度是奇数时,revertedNumber 会多一位,因此我们可以通过 revertedNumber / 10 去掉中间的数字再比较。
  • 最终,如果 x 等于 revertedNumberx 等于 revertedNumber 去掉最后一位的结果,那么 x 是回文数,返回 true;否则返回 false

代码:C++

class Solution {
public:bool isPalindrome(int x) {// 如果 x 小于 0,或者 x 是以 0 结尾但不等于 0,那么 x 不是回文数。// 负数肯定不是回文数,因为它们的倒序数不是负数。// 以 0 结尾的数(但不是 0 本身)也不是回文数,因为倒序会多出一个 0。if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}// 定义变量 revertedNumber 来存储反转后的数字int revertedNumber = 0;// 当 x 大于 revertedNumber 时继续循环while (x > revertedNumber) {//在每次循环中,将 x 的最后一位数字加到 revertedNumber 的末尾。//然后将 x 去掉最后一位数字(通过整除 10)。revertedNumber = revertedNumber * 10 + x % 10;// 去掉 x 的最后一位数字x /= 10;}// 当 x 的长度是偶数时,x 应该等于 revertedNumber。// 当 x 的长度是奇数时,revertedNumber 会多一位,因此我们可以通过 revertedNumber / 10 去掉中间的数字再比较。// 最终,如果 x 等于 revertedNumber 或 x 等于 revertedNumber 去掉最后一位的结果,那么 x 是回文数,返回 true;否则返回 false。return x == revertedNumber || x == revertedNumber / 10;}
};

DP34 【模板】前缀和

【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

从a1开始访问的,所以数组大小得是n+1

例子:
arr: [1,4,7,2,5,8,3,6,9]

i:   [1,2,3,4,5,6,7,8,9]

解法一:暴力解法 -> 模拟

时间复杂度:O(N*q) -> 有多少次查询就要遍历数组多少次(q次查询)
超时

解法二:前缀和 -> 快速求出数组中某一个连续区间的和

时间复杂度:O(q) + O(N)

第一步:预处理出来一个前缀和数组(dp)
arr: [1,4,7,2,5,8,3,6,9]

dp:  [1,5,12,14,19,27,30,36,45]

i:   [1,2,3,4,5,6,7,8,9]

dp[i]:表示[1,i]区间内所有元素的和
比如dp[3]表示原始数组1+4+7

dp[i] = dp[i-1] + arr[i]


第二步:使用前缀和数组

想求出l到r之间的和时可以直接减去就行:
[l,r] = dp[r] - dp[l-1]

dp:  [1,5,12,14,19,27,30,36,45]
               l          r

细节问题:为什么下标要从1开始计数?
比如如果想算[0,2],那l就要访问-1,-1这个位置访问不了,所以要处理边界问题

从1开始就可以处理边界情况
比如算[1,2] -> dp[2] - dp[0],可以把dp[0] = 0

代码:C++

#include <iostream>
#include <vector>
using namespace std;int main() 
{// 1. 读入数据int n, q;cin >> n >> q;vector<int> arr(n+1);for(int i = 1; i <= n; i++) cin >> arr[i];// 2. 预处理出来一个前缀和数组vector<long long> dp(n+1); // 防止溢出for(int i = 1; i <= n; i++) dp[i] = dp[i-1] + arr[i];// 3.使用前缀和数组int l = 0, r = 0;while(q--){cin >> l >> r;cout << dp[r] - dp[l-1] << endl;}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

4_机械臂位姿求逆理论及代码计算

1、aubo arcs sdk poseInverse 使用例子 auto cur_pose rpc_cli->getRobotInterface(robot_name)->getRobotState()->getTcpPose();// 2.288083 0.035207 1.550335auto pose_inv rpc_cli->getMath()->poseInverse(cur_pose);//结果&#xff1a;0.118611 -0.57…

blender

通用设置&#xff1a; 仅显示/取消隐藏&#xff1a;数字键盘/ 移动视角&#xff1a;shift鼠标中键 Blender如何给场景添加参考图片-百度经验 (baidu.com) 进入编辑模式&#xff1a;Tab 编辑模式&#xff1a;点-线-面 两个视图 法向显示&#xff1a;就能变成恶心的蓝红色 显…

自动驾驶---Perception之视觉点云雷达点云

1 前言 在自动驾驶领域&#xff0c;点云技术的发展历程可以追溯到自动驾驶技术的早期阶段&#xff0c;特别是在环境感知和地图构建方面。 在自动驾驶技术的早期技术研究中&#xff0c;视觉点云和和雷达点云都有出现。20世纪60年代&#xff0c;美国MIT的Roberts从2D图像中提取3D…

解锁ChatGPT:从GPT-2实践入手解密ChatGPT

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三连支…

LabVIEW开发实验室超导体电流特性测试系统

本系统旨在为学校实验室提供一个基于LabVIEW的超导体电流特性测试平台&#xff0c;通过精确测量超导体在不同温度和电流条件下的电学特性&#xff0c;帮助学生和研究人员深入理解超导体的物理性质。本文将从背景、目标、工作原理、使用方法、操作流程和注意事项等方面详细介绍该…

现代x86汇编-环境安装

今天端午节&#xff0c;独自在家&#xff0c;翻阅了张银奎老师编写的《现代x86汇编语言程序设计》一书&#xff0c;前言部分说明书中示例代码都是用微软visual C工具编写并使用微软宏汇编&#xff08;著名的MASM&#xff09;编译的&#xff0c;好久没有用微软vc了&#xff0c;假…

【UML用户指南】-13-对高级结构建模-包

目录 1、名称 2、元素 3、可见性 4、引入与引出 用包把建模元素安排成可作为一个组来处理的较大组块。可以控制这些元素的可见性&#xff0c;使一些元素在包外是可见的&#xff0c;而另一些元素要隐藏在包内。也可以用包表示系统体系结构的不同视图。 狗窝并不复杂&#x…

排序题+贪心

排序力扣题 一&#xff1a;合并区间 56. 合并区间 方法一&#xff1a;先排序再合并 如图&#xff0c;把区间按照起点从小到达排序&#xff0c;如果起点相同那么按照终点小的优先排序 然后每次记录一个区间&#xff0c;访问下一个区间&#xff1a; 如果下一个区间的起点<前…

Hexo+Github搭建个人博客教程

hexo官网&#xff1a;https://hexo.io/zh-cn/ butterfly 主题设置&#xff1a;https://butterfly.js.org/ GitHub地址&#xff1a;https://github.com/jerryc127/hexo-theme-butterfly 基础命令 初始化博客命令&#xff1a;hexo init “文件名” 开启本地服务&#xff08;本…

支付交易——在线支付系统基本概念

摘要 本文聚集于实战&#xff0c;只讲解最实用的知识点&#xff0c;至于支付起源、在线支付发展历程等科普知识&#xff0c;感兴趣的读者可参考其它优秀的支付类书籍或网络上其它优秀的文章。本章内容对大部分专业概念进行了极致简化&#xff0c;以便更好地帮助读者入门。实际…

XSS(跨站脚本攻击)

1.什么是xss XSS全称&#xff08;Cross Site Scripting&#xff09;跨站脚本攻击&#xff0c;为了避免和CSS层叠样式表名称冲突&#xff0c;所以改为了 XSS&#xff0c;是最常见的Web应用程序安全漏洞之一,XSS是指攻击者在网页中嵌入客户端脚本&#xff0c;通常是JavaScript编写…

Word中插入Mathtype右编号,调整公式与编号的位置

当你已经将mathtype内置于word后&#xff0c;可以使用右编号快速插入公式 但是往往会出现公式和编号出现的位置或之间的距离不合适 比如我在双栏下插入公式&#xff0c;会发现插入的公式与编号是适用于单栏的 解决办法&#xff1a; 开始->样式->MTDisplayLquation -&g…

【Python Cookbook】S02E04 文本模式的匹配和查找 match()、search()、findall() 以及 捕获组和 + 的含义

目录 问题解决方案讨论 问题 本文讨论一些按照特定的文本模式进行的查找和匹配。 解决方案 如果想要匹配的只是简单文字&#xff0c;通常我们使用一些内置的基本字符串方法即可&#xff0c;如&#xff1a;str.find()&#xff0c;str.startwith()&#xff0c;str.endswith() …

电脑存储设备,固态硬盘介绍,usb接口

简介 存储设备分为两大类主存和辅存&#xff0c;另外还有专门提供存储服务的网络存储 主存储器 随机存取存储器&#xff08;RAM, Random Access Memory&#xff09; 特点&#xff1a;高速、易失性存储器&#xff0c;断电后数据丢失。用途&#xff1a;临时存储正在使用的数据…

【Oracle生产运维】数据库服务器负载过高异常排查处理

说明 在Oracle数据库运维工作中&#xff0c;经常会遇到Oracle数据库服务器平均负载&#xff08;load average&#xff09;突然异常升高&#xff0c;如果放任不管&#xff0c;严重的情况下会出现数据库宕机、服务器重启等重大故障。因此&#xff0c;当发现数据库服务器平均负载…

log4j日志打印导致OOM问题

一、背景 某天压测&#xff0c;QPS压到一定值后机器就开始重启&#xff0c;出现OOM&#xff0c;好在线上机器配置了启动参数-XX:HeapDumpOnOutOfMemoryError -XX:HeapDumpPath/**/**heapdump.hprof。将dump文件下载到本地&#xff0c;打开Java sdk bin目录下的jvisualvm工具&a…

事业单位——被逆袭篇

目录 一、结果 二、考试 三、时间 四、复习 五、总结 一、结果 图1&#xff1a;2024年浙江广播电视集团下属浙江省中波发射管理中心公开招聘笔面试结果 准考证号笔试面试总成绩排名备注107016070.866.48310702416555.44107134390.871.681入围107146869.869.08210715406454.…

电影推荐系统的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;用户管理&#xff0c;免费电影管理&#xff0c;付费电影管理&#xff0c;电影论坛管理 前台账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;付费电影&#x…

Java:111-SpringMVC的底层原理(中篇)

这里续写上一章博客&#xff08;110章博客&#xff09;&#xff1a; 现在我们来学习一下高级的技术&#xff0c;前面的mvc知识&#xff0c;我们基本可以在67章博客及其后面相关的博客可以学习到&#xff0c;现在开始学习精髓&#xff1a; Spring MVC 高级技术&#xff1a; …

Spring Boot 项目启动时在 prepareContext 阶段做了哪些事?

概览 如果你对Spring Boot 启动流程还不甚了解&#xff0c;可阅读《Spring Boot 启动流程详解》这篇文章。如果你已了解&#xff0c;那就让我们直接看看prepareContext() 源码。 private void prepareContext(ConfigurableApplicationContext context, ConfigurableEnvironme…