Sergey
BAN USER// O(n), n - number of tickets. Toposort approach.
#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
void topoSort(const string& node, const unordered_map<string, string>& nodes, vector<string>& itenarary, unordered_set<string>& visited) {
if (visited.find(node) != visited.end())
return;
visited.insert(node);
auto it = nodes.find(node);
if (it != nodes.end())
topoSort(it->second, nodes, itenarary, visited);
itenarary.push_back(node);
}
vector<string> buildItenarary(vector<pair<string, string>> tickets) {
unordered_map<string, string> nodes;
for (int i = 0; i != tickets.size(); ++i) {
nodes.insert(tickets[i]);
}
vector<string> itenarary;
unordered_set<string> visited;
for (auto it = nodes.begin(), it_e = nodes.end(); it != it_e; ++it) {
topoSort(it->first, nodes, itenarary, visited);
}
reverse(itenarary.begin(), itenarary.end());
return itenarary;
}
int main() {
vector<pair<string, string>> tickets;
tickets.push_back(make_pair("MUC", "LHR"));
tickets.push_back(make_pair("CDG", "MUC"));
tickets.push_back(make_pair("SFO", "SJC"));
tickets.push_back(make_pair("LHR", "SFO"));
vector<string> itenarary = buildItenarary(tickets);
for (int i = 0; i != itenarary.size(); ++i)
cout << itenarary[i] << " ";
}
O(nlogn)
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Interval {
int index = 0;
int left;
int right;
Interval(int left, int right) : left(left), right(right) {}
};
vector<int> getOverllaped(vector<Interval> intervals) {
vector<int> res;
if (intervals.empty()) return res;
// store original indices before sorting
for (int i = 0; i != intervals.size(); ++i)
intervals[i].index = i;
// sort by left value
sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b){ return a.left < b.left; });
Interval interval = intervals[0];
for (int i = 1; i != intervals.size(); ++i) {
if (interval.right < intervals[i].left) {
interval = intervals[i];
} else {
if (i == 1) res.push_back(intervals[0].index);
res.push_back(intervals[i].index);
interval = Interval(min(interval.left, intervals[i].left), max(interval.right, intervals[i].right));
}
}
return res;
}
int main()
{
vector<Interval> intervals;
intervals.push_back(Interval(1, 2));
intervals.push_back(Interval(5, 6));
intervals.push_back(Interval(1, 5));
intervals.push_back(Interval(7, 8));
intervals.push_back(Interval(1, 6));
cout << "Overllapped: ";
vector<int> res = getOverllaped(intervals);
for (int i = 0; i != res.size(); ++i)
cout << res[i] << " ";
}
#include <string>
#include <sstream>
using namespace std;
string div(int num, int den, int N) {
stringstream ss;
if (den == 0) return ss.str();
ss << num / den;
if (N == 0) return ss.str();
ss << ".";
int r = num % den;
for (; N > 0; --N) {
r *= 10;
if (r < den) {
ss << "0";
} else {
ss << r / den;
r = r % den;
}
}
return ss.str();
}
int main()
{
for (;;) {
int num;
std::cout << "Numerator: "; cin >> num;
int den;
std::cout << "Denominator: "; cin >> den;
int N;
std::cout << "N: "; cin >> N;
std::cout << "Result: " << div(num, den, N) << "\n";
}
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> produce(string p) {
vector<string> res;
if (p.empty()) return res;
vector<int> wildcards;
for (int i = 0; i != p.size(); ++i)
if (p[i] == '?')
wildcards.push_back(i);
for (int i = 0; i != (1 << wildcards.size()); ++i) {
string r(p);
for (int j = 0; j != wildcards.size(); ++j) {
r[wildcards[j]] = (i & (1 << j)) ? '1' : '0';
}
res.push_back(r);
}
return res;
}
int main() {
string p;
cout << "Enter pattern: ";
getline (cin, p);
vector<string> res = produce(p);
for (int i = 0; i != res.size(); ++i) {
cout << res[i] << endl;
}
}
In your approach NextFavorite(t) will take O(n).
- Sergey May 29, 2015