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

复试 || 就业day09(2024.01.04)算法篇

文章目录

  • 前言
  • 验证外星语词典
  • 在长度 2N 的数组中找出重复 N 次的元素
  • 找到小镇的法官
  • 查找共用字符
  • 数组的相对排序
  • 分发饼干
  • 分发糖果
  • 区间选点(AcWing)
  • 最大不相交区间数量(AcWing)
  • 无重叠区间
  • 关于重写小于号

前言

💫你好,我是辰chen,本文旨在准备考研复试或就业
💫文章题目大多来自于 leetcode,当然也可能来自洛谷或其他刷题平台
💫欢迎大家的关注,我的博客主要关注于考研408以及AIoT的内容
🌟 仅给出C++版代码

以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新),欢迎大家的关注:

💥ACM-ICPC算法汇总【基础篇】
💥ACM-ICPC算法汇总【提高篇】
💥AIoT(人工智能+物联网)
💥考研
💥CSP认证考试历年题解

验证外星语词典


题目链接:验证外星语词典

C++版AC代码:

class Solution {
public:bool isAlienSorted(vector<string>& words, string order) {unordered_map<char, char> m;// 注意这里相当于重新映射成 a b c d e f g ...for (int i = 0; i < order.size(); i ++ ) m[order[i]] = (char)(i + 'a'); int n = words.size();vector<string> tmp, exch;for (int i = 0; i < n; i ++ ) {string word = words[i], numstr;for (int j = 0; j < word.size(); j ++ ) numstr += m[word[j]];    // 将原字符串映射为按照外星语字典序映射的字符串,即可排序tmp.push_back(numstr), exch.push_back(numstr);  // 分别存到tmp(要排序),exch(对比串)中}sort(tmp.begin(), tmp.end());    // 对tmp进行排序bool flag = true;for (int i = 0; i < n; i ++ ) if (tmp[i] != exch[i]) {     // 有变化即不是按照新字典序有序排列flag = false;break;}return flag;}
};

在长度 2N 的数组中找出重复 N 次的元素


题目链接:在长度 2N 的数组中找出重复 N 次的元素

C++版AC代码:

class Solution {
public:int repeatedNTimes(vector<int>& nums) {unordered_map<int, int> m;int res;for (int i = 0; i < nums.size(); i ++ ) {m[nums[i]] ++;if (m[nums[i]] >= 2) { // 因为有n+1个不同的值,所以当一个元素出现2次的时候就是目标值res = nums[i];break;}}return res;}
};

找到小镇的法官


题目链接:找到小镇的法官

C++版AC代码:

class Solution {
public:int findJudge(int n, vector<vector<int>>& trust) {if (trust.empty() && n == 1) return 1;int judge = -1;unordered_map<int, int> m1;unordered_map<int, bool> m2;for (int i = 0; i < trust.size(); i ++ ) {int fs = trust[i][0], sd = trust[i][1];m1[sd] ++, m2[fs] = false;      // 信任sd的人数+1, fs不可能是法官}for (auto i = m1.begin(); i != m1.end(); i ++ ) {int guy = i -> first, num = i -> second;if ((num == n - 1) && !m2.count(guy)) {judge = guy;break;}}return judge;}
};

查找共用字符


题目链接:查找共用字符

C++版AC代码:

class Solution {
public:vector<string> commonChars(vector<string>& words) {unordered_map<char, int> m;     // 用来记录共用字符,一开始把words[0]存进去for (int i = 0; i < words[0].size(); i ++ ) m[words[0][i]] ++;for (int i = 0; i < words.size(); i ++ ) {string word = words[i];unordered_map<char, int> tmp;         // 存储当前字符串的信息,用来和m做对比for (int j = 0; j < word.size(); j ++ ) tmp[word[j]] ++;for (auto j = m.begin(); j != m.end(); j ++ ) {char s = j -> first;int cnt = j -> second;if (!tmp.count(s)) m[s] = 0;     // tmp中没有这个字符,即不是共用字符,删掉else m[s] = min(cnt, tmp[s]);    // 如果是共用字符则取出现次数为两个串中的最小值}}vector<string> res;for (auto i = m.begin(); i != m.end(); i ++ ) {int cnt = i -> second;while (cnt -- ) res.push_back(string(1, i -> first));// string(1, c) : 把字符c变成字符串格式}return res;}
};

数组的相对排序


题目链接:数组的相对排序

C++版AC代码:

class Solution {
public:vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {unordered_map<int, int> m;for (int i = 0; i < arr1.size(); i ++ ) m[arr1[i]] ++; vector<int> res, tmp; for (int i = 0; i < arr2.size(); i ++ ) {auto it = m.find(arr2[i]);int k = it -> second;while (k -- ) res.push_back(arr2[i]);   // 按照arr2中的顺序把arr1中的元素存入resit -> second = 0;                       // 标记成已经存储好}for (auto i = m.begin(); i != m.end(); i ++ ) {  // 把arr2中没有的元素暂存到tmp中int k = i -> second;while (k -- ) tmp.push_back(i -> first);}sort(tmp.begin(), tmp.end());       // arr2中没有的元素排序for (int i = 0; i < tmp.size(); i ++ ) res.push_back(tmp[i]);return res;}
};

分发饼干


题目链接:分发饼干

C++版AC代码:

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end()), sort(s.begin(), s.end());int res = 0;for (int i = 0, j = 0; i < g.size() && j < s.size(); j ++ ) if (g[i] <= s[j]) i ++, res ++;return res;}
};

分发糖果


题目链接:分发糖果

C++版AC代码:

class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();vector<int> v(n, 1);         // 开一个长度为n的vector并附初值为1for (int i = 1; i < n; i ++ )     // 从头往后遍历if (ratings[i] > ratings[i - 1]) // 右边比左边大就让右边+1v[i] = v[i - 1] + 1;for (int i = n - 1; i > 0; i -- ) if (ratings[i] < ratings[i - 1])  // 左边比右边大且左边的糖果数≤右边的糖果数就更新+1v[i - 1] = max(v[i - 1], v[i] + 1);return accumulate(v.begin(), v.end(), 0);}
};

区间选点(AcWing)


题目链接:区间选点(AcWing)

C++版AC代码:

#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;struct St{int l, r;bool operator < (const St w) const {      // 按照右端点进行排序return r < w.r;}
}st[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i ++ ) {int l, r;cin >> l >> r;st[i] = {l, r};}sort(st, st + n);int ed = -1e9 - 1, res = 0;for (int i = 0; i < n; i ++ ) {if (st[i].l > ed) {      // 新区间的左端点大于当前区间的右端点,证明这是一个新的区间res ++;              // 区间数 + 1ed = st[i].r;        // 更新为新的右端点}}cout << res;return 0;
}

最大不相交区间数量(AcWing)


题目链接:最大不相交区间数量(AcWing)

C++版AC代码:

同上

#include <iostream>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 100010;struct St {int l, r;bool operator < (const St w) const {return r < w.r;}
}st[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i ++ ) {int l, r;cin >> l >> r;st[i] = {l, r};}sort(st, st + n);int res = 0, ed = -1e9 - 1;for (int i = 0; i < n; i ++ ) if (st[i].l > ed) {res ++;ed = st[i].r;}cout << res;return 0;
}

无重叠区间


题目链接:无重叠区间

C++版AC代码:

class Solution {
public:// 问题等价于求最多的无重叠区间// 贪心思路:按照右端点进行排序,想要最多的无重叠区域,就是在不重叠的时候选择最小的右端点static bool cmp(const vector<int> &a, const vector<int> &b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);int res = 0, r = -5 * 1e4 - 1;for (int i = 0; i < intervals.size(); i ++ ) {int st = intervals[i][0], ed = intervals[i][1];if (st >= r) {    // 根据例子所述,区间是不包含两个端点的,所以相等的时候也需要更新res ++;r = ed;}}return intervals.size() - res;}
};

关于重写小于号

定义结构体的写法:

struct St {int l, r;bool operator < (const St w) const {return r < w.r;}
}st[N];// 调用无需传入第三个参数:
sort(st, st + n);

关于外部定义的写法:

static bool cmp(const vector<int> &a, const vector<int> &b) {return a[1] < b[1];
}// 调用需要传入第三个参数:
sort(intervals.begin    (), intervals.end(), cmp);

相关文章:

复试 || 就业day09(2024.01.04)算法篇

文章目录 前言验证外星语词典在长度 2N 的数组中找出重复 N 次的元素找到小镇的法官查找共用字符数组的相对排序分发饼干分发糖果区间选点(AcWing)最大不相交区间数量(AcWing)无重叠区间关于重写小于号 前言 &#x1f4ab;你好&#xff0c;我是辰chen&#xff0c;本文旨在准备考…...

Win10电脑关闭OneDrive自动同步的方法

在Win10电脑操作过程中&#xff0c;用户想要关闭OneDrive的自动同步功能&#xff0c;但不知道具体要怎么操作&#xff1f;首先用户需要打开OneDrive&#xff0c;然后点击关闭默认情况下将文档保存到OneDrive选项保存&#xff0c;最后关闭在这台电脑上同步设置保存就好了。接下来…...

linux(centos)相关

文件架构&#xff1a; bin--binary--二进制命令&#xff0c;可直接执行 sbin systembin系统二进制命令&#xff0c;超级管理员 lib 库目录 类似dll文件 lib64 64位系统相关的库文件 usr 用户文件 boot 引导分区的文件&#xff0c;链接&#xff0c;系统启动等 dev device设备目录…...

外贸网站显示不安全警告怎么办?消除网站不安全警告超全指南

外贸网站显示不安全警告怎么办&#xff1f;当用户访问你的网站&#xff0c;而您的网站没有部署SSL证书实现HTTPS加密时&#xff0c;网站就会显示不安全警告&#xff0c;这种警告&#xff0c;不仅有可能阻止用户继续浏览网站&#xff0c;影响网站声誉&#xff0c;还有可能影响网…...

Java:HeapMemory和DirectMemory配置与使用介绍

目录 一、Heap内存 1、查看Heap内存配置的最大值 2、配置Heap内存最大值的方式 3、配置Heap内存最小值的方式 4、查看已使用Heap内存的方式 5、查看未使用Heap内存的方式 二、Direct内存 1、查看Direct内存配置的最大值 2、配置Direct内存最大值的方式 3、获取Direct…...

记 -bash: docker-compose: command not found 的问题解决

docker-compose: command not found 错误表明系统无法找到 docker-compose 命令。这可能是因为 docker-compose 并未正确安装&#xff0c;或者其可执行文件的路径未包含在系统的 PATH 变量中。 以下是我遇到时解决方法&#xff1a; 确保 Docker 和 Docker Compose 已安装&…...

分享10篇优秀论文,涉及图神经网络、大模型优化、表格分析

引言 第38届AAAI人工智能年度会议将于2024年2月在加拿大温哥华举行。今天给大家分享十篇AAAI2024论文&#xff0c;主要涉及图神经网络&#xff0c;大模型幻觉、中文书法文字生成、表格数据分析、KGs错误检测、多模态Prompt、思维图生成等。 论文获取方式&#xff0c;回复&am…...

Ubuntu 24.04 Preview 版安装 libtinfo5

Ubuntu 24.04 Preview 版安装 libtinfo5 0. 背景1. 安装 libtinfo52. 安装 cuda 0. 背景 Ubuntu 24.04 Preview 版安装 Cuda 时报确实 libtinfo5 的错误。 1. 安装 libtinfo5 wget http://archive.ubuntu.com/ubuntu/pool/universe/n/ncurses/libtinfo5_6.4-2_amd64.deb dpk…...

Spring AOP<一>简介与基础使用

spring AOP 基础定义 含义使用切面组织多个Advice,Advice放在切面中定义。也就是说是定义通知的自定义类。自定义的AOP类Aspect连接点方法调用&#xff0c;异常抛出可以增强的点JoinPoint &#xff1a;也就是**被增强的方法的总称&#xff0c;可以获取具体方法的信息&#xff…...

react ant tree节点没有children也会显示展开框 节点有children却不显示展开框

1.背景 最近处理树状结构时遇到了一个诡异问题&#xff0c;后端返回了组织树&#xff0c;组织树里面可能有组织&#xff0c;也可能有用户&#xff0c;很奇怪的是所有用户都会显示展开图标&#xff0c;而组织有些会显示展开图标&#xff0c;有些不会显示 2.分析 一开始找到了用…...

【Linux】进程查看|fork函数|进程状态

&#x1f984; 个人主页——&#x1f390;开着拖拉机回家_Linux,大数据运维-CSDN博客 &#x1f390;✨&#x1f341; &#x1fa81;&#x1f341;&#x1fa81;&#x1f341;&#x1fa81;&#x1f341;&#x1fa81;&#x1f341; &#x1fa81;&#x1f341;&#x1fa81;&am…...

LeetCode第98题 - 有效的括号

题目 解答 方案一 class Solution {public boolean isValidBST(TreeNode root) {if (root null) {return true;}if (root.left null && root.right null) {return true;}if (root.left ! null && root.left.val > root.val) {return false;}if (root.…...

Nacos学习思维导图

一、服务注册 参考文档&#xff1a;http://www.bryh.cn/a/118936.html https://blog.csdn.net/Saintmm/article/details/121981184 二、服务续约 参考文档&#xff1a;http://www.bryh.cn/a/118936.html https://blog.csdn.net/Saintmm/article/details/121981184 三、服务…...

新视野英语课本复盘1

the triumpth of years of hard work 多年的辛勤付出的胜利 get by on very little sleep 靠很少的睡眠勉强维持生活或工作 pursue new passions 追求新的热爱之事 reap the benefits of this opportunity 收获这个机会带来的益处 you will not only emerge as a more broadly …...

Sentinel整合OpenFeign

1、配置文件 feign:sentinel:enabled: true 2、 编写一个工厂类 import com.cart.cartservice.client.ItemClient; import com.cart.cartservice.entity.Item; import lombok.extern.slf4j.Slf4j; import org.springframework.cloud.openfeign.FallbackFactory; import org.sp…...

PyTorch实战:基于Seq2seq模型处理机器翻译任务(模型预测)

文章目录 引言数据预处理加载字典对象en2id和zh2id文本分词 加载训练好的Seq2Seq模型模型预测完整代码结束语 引言 随着全球化的深入&#xff0c;翻译需求日益增长。传统的人工翻译方式虽然质量高&#xff0c;但效率低&#xff0c;成本高。机器翻译的出现&#xff0c;为解决这…...

stm32学习总结:5、Proteus8+STM32CubeMX+MDK仿真串口并使用串口打印日志(注意重定向printf到串口打印的问题)

stm32学习总结&#xff1a;5、Proteus8STM32CubeMXMDK仿真串口并使用串口打印日志&#xff08;注意重定向printf到串口打印的问题&#xff09; 文章目录 stm32学习总结&#xff1a;5、Proteus8STM32CubeMXMDK仿真串口并使用串口打印日志&#xff08;注意重定向printf到串口打印…...

SAFe大规模敏捷企业级实训

课程简介 SAFe – Scaled Agile Framework是目前全球运用最广泛的大规模敏捷框架&#xff0c;也是成长最快、最被认可、最有价值的规模化敏捷框架&#xff0c;目前全球SAFe认证专业人士已达80万人&#xff0c;福布斯100强的70%都在实施SAFe。本课程是一个2天的 SAFe权威培训课…...

中医电子处方系统,西医个体诊所门诊卫生室病历记录查询软件教程

中医电子处方系统&#xff0c;西医个体诊所门诊卫生室病历记录查询软件教程 一、软件程序问答 1、电子处方软件如何快速开单&#xff1f; 如下图&#xff0c;软件以 佳易王诊所电子处方管理系统V17.1版本为例说明 在开电子处方的时候可以按单个药品开&#xff0c;也可以直…...

搞定ESD(八):静电放电之原理图设计

文章目录 一、防护对象识别方法1.1 根据应用手册识别防护对象1.2 根据端口信号类型识别防护对象1.3 根据信号类型识别防护对象二、电路级ESD防护设计2.1 静电尖峰脉冲电压钳位设计(ESD器件并联)2.1.1 高速差分信号ESD防护设计2.1.2 低速信号ESD防护设计2.2 静电放电电流限制设…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...