leetcode解题思路分析(九十九)853 - 859 题

2024-09-05 04:48

本文主要是介绍leetcode解题思路分析(九十九)853 - 859 题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  1. 车队
    N 辆车沿着一条车道驶向位于 target 英里之外的共同目的地。每辆车 i 以恒定的速度 speed[i] (英里/小时),从初始位置 position[i] (英里) 沿车道驶向目的地。一辆车永远不会超过前面的另一辆车,但它可以追上去,并与前车以相同的速度紧接着行驶。此时,我们会忽略这两辆车之间的距离,也就是说,它们被假定处于相同的位置。车队 是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意,一辆车也可以是一个车队。即便一辆车在目的地才赶上了一个车队,它们仍然会被视作是同一个车队。会有多少车队到达目的地?

按起始位置逆向排序,然后计算每辆车单独驶向终点需要的时间,如果出现反差说明一定追得上。

class Solution {
public:int carFleet(int target, vector<int>& position, vector<int>& speed) {int n=position.size();vector<double>time(n);for(int i=0;i<n;i++){time[i]=(double)(target-position[i])/speed[i];}unordered_map<int,double>pos2time;for(int i=0;i<n;i++){pos2time[position[i]]=time[i];}sort(position.begin(),position.end());int ans=n;for(int i=n-2;i>=0;i--){double &preTime=pos2time[position[i]];double &curTime=pos2time[position[i+1]];if(curTime>=preTime){ans--;preTime=curTime;}}return ans;}
};
  1. 相似度为K的字符串
    如果可以通过将 A 中的两个小写字母精确地交换位置 K 次得到与 B 相等的字符串,我们称字符串 A 和 B 的相似度为 K(K 为非负整数)。给定两个字母异位词 A 和 B ,返回 A 和 B 的相似度 K 的最小值。
class Solution {
public:int kSimilarity(string s1, string s2) {int n=s1.size();unordered_map<string,int>vis1,vis2;queue<string>que1,que2;que1.push(s1);que2.push(s2);vis1[s1]=0;vis2[s2]=0;while(!que1.empty()&&!que2.empty()){if(que1.size()<que2.size()){for(int sz=que1.size();sz>0;sz--){string tmp=que1.front();que1.pop();for(int i=0;i<n;i++){if(tmp[i]==s2[i])continue;for(int j=i+1;j<n;j++){if(tmp[j]==s2[j])continue;if(tmp[j]!=s2[i])continue;if(tmp[i]==tmp[j])continue; string nex=tmp;swap(nex[i],nex[j]);if(vis1.count(nex))continue;if(vis2.count(nex))return vis1[tmp]+vis2[nex]+1;que1.push(nex);vis1[nex]=vis1[tmp]+1;}break;}}}else {for(int sz=que2.size();sz>0;sz--){string tmp=que2.front();que2.pop();for(int i=0;i<n;i++){if(tmp[i]==s1[i])continue;for(int j=i+1;j<n;j++){if(tmp[j]==s1[j])continue;if(tmp[j]!=s1[i])continue;if(tmp[i]==tmp[j])continue;string nex=tmp;swap(nex[i],nex[j]);if(vis2.count(nex))continue;if(vis1.count(nex))return vis2[tmp]+vis1[nex]+1;que2.push(nex);vis2[nex]=vis2[tmp]+1;}break;}}}}return 0;}
};
  1. 考场就座
    在考场里,一排有 N 个座位,分别编号为 0, 1, 2, …, N-1 。当学生进入考场后,他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位,他会坐在编号最小的座位上。(另外,如果考场里没有人,那么学生就坐在 0 号座位上。)返回 ExamRoom(int N) 类,它有两个公开的函数:其中,函数 ExamRoom.seat() 会返回一个 int (整型数据),代表学生坐的位置;函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave§ 时都保证有学生坐在座位 p 上。

找中点


class ExamRoom {int n;set<int> s;
public:ExamRoom(int N) : n(N){}int seat() {// 没有人的时候直接坐第一个位置if (s.empty()){s.insert(0);return 0;}int res = 0;// 上一个点的位置int pre = -1;// 当前最大距离int maxDist = 0;for (int cur : s){// 取相邻结点的中点位置int dist = (cur - pre) >> 1;if (dist > maxDist){res = pre == -1 ? 0 : pre + dist;maxDist = dist;}pre = cur;}// 考虑最后一个位置的特殊情况if (n - 1 - pre > maxDist){res = n - 1;}s.insert(res);return res;}// 离开就是删除,而无需重排void leave(int p) {s.erase(p);}
};
/*** Your ExamRoom object will be instantiated and called as such:* ExamRoom* obj = new ExamRoom(n);* int param_1 = obj->seat();* obj->leave(p);*/
  1. 括号的分数
    给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:
    () 得 1 分。
    AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。
    (A) 得 2 * A 分,其中 A 是平衡括号字符串。

很容易想到用栈解决问题,但是实际上,只有 () 会对字符串 S 贡献实质的分数,其它的括号只会将分数乘二或者将分数累加。因此,我们可以找到每一个 () 对应的深度 x,那么答案就是 2^x 的累加和。虑到乘法内加法可以拆分出来先乘后加,因此可以统计深度然后逐个求乘法,最终累加即可。

class Solution {
public:int scoreOfParentheses(string s) {int ret = 0, deep = 0;for (int i = 0; i < s.size(); ++i){if (s[i] == '('){deep++;}else{deep--;if (s[i - 1] == '('){ret += 1 << deep;}}}return ret;}
};
  1. 雇佣K名工人的最低成本
    有 N 名工人。 第 i 名工人的工作质量为 quality[i] ,其最低期望工资为 wage[i] 。现在我们想雇佣 K 名工人组成一个工资组。在雇佣 一组 K 名工人时,我们必须按照下述规则向他们支付工资:对工资组中的每名工人,应当按其工作质量与同组其他工人的工作质量的比例来支付工资。工资组中的每名工人至少应当得到他们的最低期望工资。返回组成一个满足上述条件的工资组至少需要多少钱。

定义一个“价值”,表示工人最低期望工资与工作质量之比。如果一名工人的价值为 R,当他恰好拿到最低期望工资时,如果所有价值高于 R 的工人都无法拿到最低期望工资,而所有价值低于 R 的工人都拿得比最低期望工资多。因此,我们可以按照这些工人的价值,对他们进行升序排序。在前 i 名工人中选择 K 个工作质量最低的。我们可以使用一个大根堆来实时维护 K 个最小值。

class Solution {
public:double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {int n = quality.size();// first是性价比,越小越好, second是质量vector<pair<double, int>> workers(n);for (int i = 0; i < n; ++i){workers[i] = {(double)(wage[i])/quality[i], quality[i]};}sort(workers.begin(), workers.end());double res = LONG_MAX;// 质量总和int sum = 0;// 大顶堆的队列,质量大即使性价比高也会比移除priority_queue<int> q;for (auto& worker : workers){if (q.size() < k){q.push(worker.second);sum += worker.second;} if (q.size() == k) {// 当前单位价格是由当前性价比最差的来决定的,所以直接乘以就可以res = min(res, worker.first * sum);// 移除元素还需要删除质量本身sum -= q.top();q.pop();}}return res;}
};  
  1. 镜面反射
    有一个特殊的正方形房间,每面墙上都有一面镜子。除西南角以外,每个角落都放有一个接受器,编号为 0, 1,以及 2。正方形房间的墙壁长度为 p,一束激光从西南角射出,首先会与东墙相遇,入射点到接收器 0 的距离为 q 。返回光线最先遇到的接收器的编号(保证光线最终会遇到一个接收器)。

光的反射,可以理解为光直射到了镜像面,即我们让光不变,而是扩展空间为很多个镜面,这样只要看光的直线延长线上啥时候能撞到一个角即可

class Solution {
public:int mirrorReflection(int p, int q) {// 只要确保分子分母不都是偶数就行了while((q&1) == 0 && (p&1) == 0){q >>= 1;p >>= 1;}// p 为偶数if((p&1) == 0)return 2;// q 为偶数if((q&1) == 0)return 0;// p, q 都是奇数return 1;}
};
  1. 亲密字符串
    给你两个字符串 s 和 goal ,只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果,就返回 true ;否则返回 false 。交换字母的定义是:取两个下标 i 和 j (下标从 0 开始)且满足 i != j ,接着交换 s[i] 和 s[j] 处的字符。例如,在 “abcd” 中交换下标 0 和下标 2 的元素可以生成 “cbad” 。

遍历即可

class Solution {
public:bool buddyStrings(string s, string goal) {int cnt = 0;if (s.size() != goal.size()) return false;int diff1 = -1; // 第一次不同的位置int diff2 = -1; // 第二次不同的位置int chars[26];memset(chars, 0, sizeof(chars));bool valid_no_diff = false;for (int i = 0; i < s.size(); i++) {if (s[i] != goal[i]) {cnt++;if (cnt > 2) return false;if (cnt == 1) diff1 = i;if (cnt == 2) diff2 = i;}chars[s[i]-'a']++;if (chars[s[i] - 'a'] >= 2) valid_no_diff = true;}if (cnt == 0 && valid_no_diff) return true; // 两个串一摸一样,需要有两个以上相同字母出现if (cnt == 2 && s[diff1] == goal[diff2] && s[diff2] == goal[diff1]) return true; // 两个串有两个位置不同,需要正好可以互换return false;}
};

这篇关于leetcode解题思路分析(九十九)853 - 859 题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137991

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者

MOLE 2.5 分析分子通道和孔隙

软件介绍 生物大分子通道和孔隙在生物学中发挥着重要作用,例如在分子识别和酶底物特异性方面。 我们介绍了一种名为 MOLE 2.5 的高级软件工具,该工具旨在分析分子通道和孔隙。 与其他可用软件工具的基准测试表明,MOLE 2.5 相比更快、更强大、功能更丰富。作为一项新功能,MOLE 2.5 可以估算已识别通道的物理化学性质。 软件下载 https://pan.quark.cn/s/57

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

衡石分析平台使用手册-单机安装及启动

单机安装及启动​ 本文讲述如何在单机环境下进行 HENGSHI SENSE 安装的操作过程。 在安装前请确认网络环境,如果是隔离环境,无法连接互联网时,请先按照 离线环境安装依赖的指导进行依赖包的安装,然后按照本文的指导继续操作。如果网络环境可以连接互联网,请直接按照本文的指导进行安装。 准备工作​ 请参考安装环境文档准备安装环境。 配置用户与安装目录。 在操作前请检查您是否有 sud

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &