leetcode解题思路分析（九十九）853

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

车队
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;}
};

相似度为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;}
};

考场就座
在考场里，一排有 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);*/

括号的分数
给定一个平衡括号字符串 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;}
};

雇佣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;}
};

镜面反射
有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 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;}
};

亲密字符串
给你两个字符串 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;}
};