Nuts 和 Bolts 的问题
描述
给定一组 n 个不同大小的 nuts 和 n 个不同大小的 bolts。nuts 和 bolts 一一匹配。 不允许将 nut 之间互相比较，也不允许将 bolt 之间互相比较。也就是说，只许将 nut 与 bolt 进行比较， 或将 bolt 与 nut 进行比较。请比较 nut 与 bolt 的大小。
您在真实的面试中是否遇到过这个题？
是 样例
【Nuts 和 Bolts 的问题】给出 nuts = ['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC']
你的程序应该找出bolts和nuts的匹配。
一组可能的返回结果是：
nuts = ['ab','bc','dd','gg'], bolts = ['AB','BC','DD','GG']
我们将给你一个匹配的比较函数，如果我们给你另外的比较函数，可能返回的结果是：
nuts = ['ab','bc','dd','gg'], bolts = ['BC','AB','DD','GG']
因此的结果完全取决于比较函数，而不是字符串本身。
因为你必须使用比较函数来进行排序。
各自的排序当中nuts和bolts的顺序是无关紧要的，只要他们一一匹配就可以。
/**
* class Comparator {
*public:
*int cmp(string a, string b);
* };
* You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
* if "a" is bigger than "b", it will return 1, else if they are equal,
* it will return 0, else if "a" is smaller than "b", it will return -1.
* When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
class Solution {
public:
/**
* @param nuts: a vector of integers
* @param bolts: a vector of integers
* @param compare: a instance of Comparator
* @return: nothing
*/
void sortNutsAndBolts(vector &nuts, vector &bolts, Comparator compare) {
// write your code here
if (nuts.size() != bolts.size()) {
return;
}
int i = 0;
int j = nuts.size() - 1;
// call recursive function
partitionNutsAndBolts(nuts, bolts, compare, i, j);
}
void partitionNutsAndBolts(vector &nuts, vector &bolts, Comparator compare, int start, int end) {
if (start < end) {
// use nuts to partition bolts
int i = start;
int j = end;
while(i < j) {
while(i < j && compare.cmp(nuts[start], bolts[i]) > 0) {
i++;
}
while(i < j && compare.cmp(nuts[start], bolts[j]) < 0) {
j--;
}
if (i < j) {
swap(bolts[i], bolts[j]);
}
}
// update to the same pos as nuts and keep splitpos
swap(bolts[start], bolts[i]);
int splitpos = i;
// use bolts to partition nuts
i = start + 1;
j = end;
while(i < j) {
while(i < j && compare.cmp(nuts[i], bolts[start]) < 0) {
i++;
}
while(i < j && compare.cmp(nuts[j], bolts[start]) > 0) {
j--;
}
if (i < j) {
swap(nuts[i], nuts[j]);
}
}
// recursive
partitionNutsAndBolts(nuts, bolts, compare, start + 1, splitpos);
partitionNutsAndBolts(nuts, bolts, compare, splitpos + 1, end);
}
}
};
推荐阅读
- 急于表达——往往欲速则不达
- 第三节|第三节 快乐和幸福（12）
- 20170612时间和注意力开销记录
- 2.6|2.6 Photoshop操作步骤的撤消和重做 [Ps教程]
- 对称加密和非对称加密的区别
- 眼光要放高远
- 樱花雨
- 前任
- 2020-04-07vue中Axios的封装和API接口的管理
- 烦恼和幸福