刷题日记:面试经典 150 题 DAY3

刷题日记:面试经典 150 题 DAY3

  • 274. H 指数
  • 238. 除自身以外数组的乘积
  • 380. O(1) 时间插入、删除和获取随机元素
  • 134. 加油站
  • 135. 分发糖果

274. H 指数

原题链接 274. H 指数

重要的是都明白H指数到底是是个啥。注意到如果将引用数从大到小排序,则对于下标i有 引用数 ≥ c i t a t i o n [ i ] 的论文有 i + 1 篇 引用数\geq citation[i]的论文有i+1篇 引用数citation[i]的论文有i+1,注意到此时引用数递减而文章数量递增,所求H指数就是求一个交点。

class Solution {
public:int hIndex(vector<int>& citations) {sort(citations.begin(), citations.end(),greater<int>());int i;for(i = 0;i<citations.size() && citations[i]>=(i+1);i++);return i;}
};

其实时间复杂度为 O ( N ) O(N) O(N)的算法更加符合直觉。我们创建一个新的数组count来记录,count[i]中存储引用数为i的文章有几篇,这里面重要的一步是将引用数大于等于n的篇数存储到count[n] 之中,这是因为对于本题来说,h指数不可能大于n,所以大于n篇数的分别计数就没有意义(该思想经常出现)

class Solution {
public:int hIndex(vector<int>& citations) {int n = citations.size();int count[n+1];memset(count,0,sizeof(count));for(int cite:citations) {if(cite >= n) {count[n]++;} else {count[cite]++;}}int sum = 0,i = 0;for(i = n; i>=0;i--) {sum += count[i];if(sum >= i) {break;}}return i;}
};

238. 除自身以外数组的乘积

原题链接 238. 除自身以外数组的乘积

题很简单,只需要注意到要处理0,可以分类讨论

  • 不存在0,则只需要算出整体乘积,然后除以当前数字
  • 存在一个0,则除了这个0外剩下位置都是0,该位置是所有其它数乘积
  • 存在两个及以上0,则全是0
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int count_0 = 0;int len = nums.size();int total = 1;for(int num:nums) {if(num == 0) count_0++;else total*=num;}vector<int> result(len,0);if(count_0 >= 2) {return result;}if(count_0 == 1) {for(int i = 0;i < len;i++) {if(nums[i] == 0) {result[i] = total;}}return result;}for(int i = 0;i < len;i++) {result[i] = total/nums[i];}return result;}
};

380. O(1) 时间插入、删除和获取随机元素

原题链接 380. O(1) 时间插入、删除和获取随机元素

数据结构设计题,之前没试过这类题,自己做想到要用哈希(废话),但是感觉脑子不够用,遂去狠狠的学习了【宫水三叶】数据结构运用题

class RandomizedSet {
private:unordered_map<int,int> hashmap;int nums[200010];int idx;
public:RandomizedSet() {srand((unsigned)time(NULL));idx = -1;}bool insert(int val) {if(hashmap.count(val) > 0) {return false;}nums[++idx]  = val;hashmap[val] = idx;return true;}bool remove(int val) {if(hashmap.count(val) == 0) {return false;}int tail = nums[idx];int rm_idx = hashmap[val];swap(nums[rm_idx],nums[idx]);hashmap.erase(val);if(val != tail) hashmap[tail] = rm_idx;idx--;return true;}int getRandom() {int random_i = rand() % (idx+1);return nums[random_i];}
};/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet* obj = new RandomizedSet();* bool param_1 = obj->insert(val);* bool param_2 = obj->remove(val);* int param_3 = obj->getRandom();*/

结构:

  • 一个定长数组用于存储元素,维护一个idx,表示在数组的[0...idx]中存储着元素
  • 一个哈希表,存储键值对(val,idx),即元素和其所在的下标

插入

  • 直接向哈希表和数组的末尾插入

删除

  • 对哈希表的操作:直接删除其键值对
  • 对数组的操作:将要删除的量交换到最后,然后让idx减去1(经常用到),此时需要再更新哈希表。将key为原数组尾的值改成交换后的下标

134. 加油站

原题链接 134. 加油站

朴素的想法是,我只需要模拟开车的过程,并一个一个尝试哪一个加油站可以作为起点就可以。但是这个方法复杂度有 O ( N 2 ) O(N^2) O(N2)
能在 O ( N ) O(N) O(N)内做出来的方法基于以下重要观察:

  • 如果从 i i i出发能到达 j j j而无法到达 j + 1 j+1 j+1,则从任何的 k ∈ [ i , j ] k \in[i,j] k[i,j]出发都不可能到达 j + 1 j+1 j+1,也就是任何的 k ∈ [ i , j ] k \in [i,j] k[i,j]都不可能作为起点,所以我们直接从 j + 1 j+1 j+1开始检查即可
    • 这是因为到达 k k k时汽车至少有非负的汽油,一定不低于从 k k k出发的汽油

所以我们能在每个元素至多被遍历两遍内获得答案

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int len = gas.size();int i = 0;while(i < len) {int cargas = 0;int cnt;for(cnt = 0;cnt < len;cnt++) {int j = (i+cnt)%len;cargas += gas[j]-cost[j];if(cargas < 0) {break;}}if(cnt == len) {return i;} else {i += cnt+1;}}return -1;}
};

135. 分发糖果

原题链接 135. 分发糖果

第一遍做想到一个比较符合直觉的想法:考虑两种打分的分布,分别是:递增,递减

在这里插入图片描述

这样分糖果的策略很简单,就是在单调列中,这个孩子是打分第几低,我就给他几个糖果
实际打分的分布可以看作是多个递增递减列的组合

在这里插入图片描述

此时仅需要考虑中间那个孩子需要多少糖果即可,很简单能想到应该是max(left,right)
最后写成代码:

class Solution {
public:int candy(vector<int>& ratings) {int len = ratings.size();vector<int> uplift(len,0);vector<int> downlift(len,0);int cd = 0;for(int i = 1;i < len;i++){if(ratings[i]>ratings[i-1]) {cd++;} else  {cd = 0;}uplift[i] = cd;}cd = 0;for(int i = len-2;i >= 0;i--){if(ratings[i]>ratings[i+1]) {cd++;} else {cd = 0;}downlift[i] = cd;}cd = len;for(int i = 0;i < len;i++){cd += max(uplift[i],downlift[i]);}return cd;}
};

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

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

相关文章

windows环境下Grafana+loki+promtail入门级部署日志系统,收集Springboot(Slf4j+logback)项目日志

&#x1f339;作者主页&#xff1a;青花锁 &#x1f339;简介&#xff1a;Java领域优质创作者&#x1f3c6;、Java微服务架构公号作者&#x1f604; &#x1f339;简历模板、学习资料、面试题库、技术互助 &#x1f339;文末获取联系方式 &#x1f4dd; 往期热门专栏回顾 专栏…

【开发工具】GIF 录屏工具推荐 ( GIF123 - 推荐使用 | GifCam | LICEcap )

文章目录 一、GIF 录屏工具推荐1、GIF123 ( 推荐使用 )2、GifCam3、LICEcap 本博客中介绍的 3 款 GIF 录屏工具下载地址 : https://download.csdn.net/download/han1202012/88905642 也可以到对应的官网独立下载 : GIF123 : https://gif123.aardio.com/ ;GifCam : https://bl…

【JavaEE】_Spring MVC 项目传参问题

目录 1. 传递单个参数 1.1 关于参数名的问题 2. 传递多个参数 2.1 关于参数顺序的问题 2.2 关于基本类型与包装类的问题 3. 使用对象传参 4. 后端参数重命名问题 4.1 关于RequestPara注解 1. 传递单个参数 现创建Spring MVC项目&#xff0c;.java文件内容如下&#xff…

探索数字未来:DApp钱包Defi引领新纪元

​小编介绍&#xff1a;10年专注商业模式设计及软件开发&#xff0c;擅长企业生态商业模式&#xff0c;商业零售会员增长裂变模式策划、商业闭环模式设计及方案落地&#xff1b;扶持10余个电商平台做到营收过千万&#xff0c;数百个平台达到百万会员&#xff0c;欢迎咨询。 随…

99.qt qml-单例程序实现

在之前讲过: 58.qt quick-qml系统托盘实现https://nuoqian.blog.csdn.net/article/details/121855993 由于,该示例只是简单讲解了系统托盘实现,并没有实现单例程序,所以多次打开后就会出现多个exe出现的可能,本章出一章QML单例程序实现, 多次打开始终只显示出第一个打开…

深入分析Android运行时环境ART:原理、特点与优化策略

摘要 随着移动互联网的快速发展&#xff0c;智能手机的性能和功能日益强大&#xff0c;其中Android操作系统因其开放性和灵活性而占据主导地位。Android运行时环境&#xff08;ART&#xff09;作为执行应用程序代码的关键组件&#xff0c;在系统性能和用户体验方面起着至关重要…

【探索AI】十二 深度学习之第2周:深度神经网络(一)深度神经网络的结构与设计

第2周&#xff1a;深度神经网络 将从以下几个部分开始学习&#xff0c;第1周的概述有需要详细讲解的的同学自行百度&#xff1b; 深度神经网络的结构与设计 深度学习的参数初始化策略 过拟合与正则化技术 批标准化与Dropout 实践&#xff1a;使用深度学习框架构建简单的深度神…

Topaz Video AI:一键提升视频品质,智能重塑影像魅力 mac/win版

Topaz Video AI是一款革命性的视频智能处理软件&#xff0c;它利用先进的机器学习和人工智能技术&#xff0c;为视频创作者提供了前所未有的视频增强和修复功能。无论您是专业视频编辑师、摄影师&#xff0c;还是热爱视频创作的爱好者&#xff0c;Topaz Video AI都能帮助您轻松…

Mamba与MoE架构强强联合,Mamba-MoE高效提升LLM计算效率和可扩展性

论文题目&#xff1a; MoE-Mamba: Efficient Selective State Space Models with Mixture of Experts 论文链接&#xff1a; https://arxiv.org/abs/2401.04081 代码仓库&#xff1a; GitHub - llm-random/llm-random 作为大型语言模型&#xff08;LLM&#xff09;基础架构的后…

数字化转型导师鹏:政府数字化转型政务服务类案例研究

政府数字化转型政务服务类案例研究 课程背景&#xff1a; 很多地方政府存在以下问题&#xff1a; 不清楚标杆省政府数字化转型的政务服务类成功案例 不清楚地级市政府数字化转型的政务服务类成功案例 不清楚县区级政府数字化转型的政务服务类成功案例 课程特色&#x…

【查找算法】二分查找

一&#xff1a;二分查找 1.1 基本概念 二分查找也称折半查找&#xff08;Binary Search&#xff09;&#xff0c;它是一种效率较高的查找方法。但是&#xff0c;折半查找要求线性表必须采用顺序存储结构&#xff0c;而且表中元素按关键字有序排列。 1.2 原理 查找的目标数据元…

MySQL 8.0.35 企业版安装和启用TDE插件keyring_encrypted_file

本文主要记录MySQL企业版TDE插件keyring_encrypted_file的安装和使用。 TDE说明 TDE( Transparent Data Encryption,透明数据加密) 指的是无需修改应用就可以实现数据的加解密&#xff0c;在数据写磁盘的时候加密&#xff0c;读的时候自动解密。加密后其他人即使能够访问数据库…

Progressive Widening

下面的解释来源于论文《Monte Carlo Tree Search With Iteratively Refining State Abstractions》&#xff0c;因为这篇论文的重点不是Progressive Widening&#xff0c;所以就不全文学习了&#xff0c;只摘抄其中关于Progressive Widening的部分。 Progressive Widening&…

蓝牙耳机和笔记本电脑配对连接上了,播放设备里没有显示蓝牙耳机这个设备,选不了输出设备

环境&#xff1a; WIN10 杂牌蓝牙耳机6s 问题描述&#xff1a; 蓝牙耳机和笔记本电脑配对连接上了&#xff0c;播放设备里没有显示蓝牙耳机这个设备&#xff0c;选不了输出设备 解决方案&#xff1a; 1.打开设备和打印机&#xff0c;找到这个设备 2.选中这个设备&#…

Nacos配置管理

Nacos除了可以做注册中心&#xff0c;同样可以做配置管理来使用。 统一配置管理 当微服务部署的实例越来越多&#xff0c;达到数十、数百时&#xff0c;逐个修改微服务配置就会让人抓狂&#xff0c;而且很容易出错。我们需要一种统一配置管理方案&#xff0c;可以集中管理所有…

5.测试教程 - 进阶篇

文章目录 1.按测试对像划分1.1**界面测试**1.2**可靠性测试**1.3**容错性测试**1.4**文档测试**1.5**兼容性测试**1.6**易用性测试**1.7**安装卸载测试**1.8**安全测试**1.9**性能测试**1.10**内存泄漏测试** 2.按是否查看代码划分2.1黑盒测试(Black-box Testing)2.2白盒测试(W…

Scratch 第十六课-弹珠台游戏

第十六课-弹珠台游戏 大家好&#xff0c;今天我们一起做一款弹珠台scratch游戏&#xff0c;我们也可以叫它弹球游戏&#xff01;这款游戏在刚出来的时候非常火爆。小朋友们要认真学习下&#xff01; 这节课的学习目标 物体碰撞如何处理转向问题。复习键盘对角色的控制方式。…

软件开发人员从0到1实现物联网项目:技术调研

前言 春节返乡之际&#xff0c;发现老家县城竟然开了近十家棋牌室。巧的是朋友也有意涉足&#xff0c;便咨询我自助棋牌室的软件投入成本。作为程序员的我&#xff0c;在思考了自助棋牌室背后的技术需求后&#xff0c;嗅到了一丝丝商机&#xff1a;何不自己开发一个自助棋牌室…

YOLOV9训练集制作+Train+Val记录

一、YOLO数据集格式分布 在YOLO中&#xff0c;数据集的分布如图&#xff0c;在dataset文件夹下有imags&#xff08;图片&#xff09;和labels&#xff08;标签&#xff09;。在images和labels文件夹下又分别存放三个文件夹&#xff0c;分别对应测试集、训练集、验证集&#xff…