bertelli.lorenzo
BAN USERO(nlogn) implementation using map.
It is based on Bin Packing First Fit heuristic, just using the map to speed up the finding of an available bin (with enough space to fit the new item)
int firstFitOpt(vector<int>& items, int capacity)
{
int n = items.size();
map<int, int> binCapacity;
int res = 0;
for (int i = 0; i < n; ++i)
{
auto it = binCapacity.lower_bound(items[i]);
int residual = capacity;
if (it != binCapacity.end())
{
residual = it->first;
it->second--;
if (it->second == 0)
binCapacity.erase(it);
}
else
{
++res;
}
residual -= items[i];
if (residual > 0)
binCapacity[residual]++;
}
return res;
}
int main() {
vector<int> items;
int c = 10;
for (int i = 0; i < 50000; ++i)
items.push_back(rand() % 10 + 1);
std::cout << "Opt: " << firstFitOpt(items, c) << std::endl;
}
The key is delete the vertexes following the decreasing order of their degree.
It can be implemented using heaps, but in C++ priority queues don't have the decrease key method. A simple hack with a secondary vector need to be used:
int deleteMaxOrbs(vector<vector<int>> &adj)
{
int n = adj.size();
vector<int> realEdgesCounter(n);
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; ++i)
{
realEdgesCounter[i] = adj[i].size();
if (realEdgesCounter[i] > 0)
pq.push({realEdgesCounter[i], i});
}
int deleted = 0;
while (!pq.empty())
{
int numEdges = pq.top().first;
int vertex = pq.top().second;
pq.pop();
if (numEdges == realEdgesCounter[vertex])
{
++deleted;
realEdgesCounter[vertex] = 0;
for (int i: adj[vertex])
{
if (realEdgesCounter[i] > 0)
{
realEdgesCounter[i]--;
if (realEdgesCounter[i] > 0)
pq.push({realEdgesCounter[i], i});
}
}
}
}
return deleted;
}
int main()
{
vector<vector<char>> matrix =
{{'O', 'X', 'O', 'X', 'X', 'O'},
{'X', 'X', 'X', 'X', 'X', 'O'},
{'X', 'X', 'X', 'X', 'O', 'X'}};
vector<pair<int, int>> orbs;
for (int i = 0; i < matrix.size(); ++i)
{
for (int j = 0; j < matrix[0].size(); ++j)
{
if (matrix[i][j] == 'O')
orbs.push_back({i, j});
}
}
int n = orbs.size();
vector<vector<int>> adj(n, vector<int>());
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i != j && (orbs[i].first == orbs[j].first ||
orbs[i].second == orbs[j].second))
{
adj[i].push_back(j);
}
}
}
int res = deleteMaxOrbs(adj);
cout << "Deleted: " << res << endl;
return 0;
}
Simple C++ implementation with STL list:
class TextEditor
{
public:
TextEditor()
{
text.push_back('|');
cursor = text.begin();
}
void insertCharacter(char c)
{
text.insert(cursor, c);
undoStack.push("b");
}
void moveCursorLeft()
{
if (cursor != text.begin())
{
text.splice(std::prev(cursor), text, cursor);
undoStack.push("r");
}
}
void moveCursorRight()
{
if (cursor != std::prev(text.end()))
{
text.splice(std::next(cursor, 2), text, cursor);
undoStack.push("l");
}
}
void backspace()
{
if (cursor != text.begin())
{
char c = *std::prev(cursor);
string s = "a";
undoStack.push(s + c);
text.erase(std::prev(cursor));
}
}
void undo()
{
if (!undoStack.empty())
{
string s = undoStack.top();
undoStack.pop();
if (s[0] == 'b')
backspace();
else if (s[0] == 'r')
moveCursorRight();
else if (s[0] == 'l')
moveCursorLeft();
else if (s[0] == 'a')
insertCharacter(s[1]);
// this second pop is needed because also the undo write to stack :D
undoStack.pop();
}
}
void print()
{
for (auto it = text.begin(); it != text.end(); ++it)
std::cout << *it;
std::cout << endl;
}
private:
list<char> text;
list<char>::iterator cursor;
stack<string> undoStack;
};
int main() {
TextEditor te;
te.print();
te.insertCharacter('c');
te.insertCharacter('i');
te.insertCharacter('a');
te.insertCharacter('o');
te.print();
te.moveCursorLeft();
te.moveCursorLeft();
te.print();
te.moveCursorRight();
te.moveCursorRight();
te.print();
te.backspace();
te.print();
te.undo();
te.print();
te.undo();
te.print();
}
C++ solution with BFS, extended to track back nodes and the parent (to reconstruct the path):
class Graph
{
private:
int V;
vector<int>* adj;
public:
Graph(int V) :
V(V),
parents(V, -1)
{
adj = new vector<int>[V];
}
~Graph()
{
delete[] adj;
}
void addEdge(int src, int dest)
{
adj[src].push_back(dest);
}
bool findShortestCycle(int root)
{
vector<bool> visited(V, false);
vector<bool> backNode(V, false);
queue<int> q;
q.push(root);
visited[root] = true;
while(!q.empty())
{
int t = q.front();
q.pop();
for (int &a: adj[t])
{
if (backNode[a])
{
if (a == root)
{
parents[a] = t;
return true;
}
continue;
}
if (!visited[a])
{
visited[a] = true;
parents[a] = t;
q.push(a);
}
}
backNode[t] = true;
}
return false;
}
vector<int> parents;
};
int main() {
Graph g(6);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 1);
g.addEdge(3, 2);
g.addEdge(3, 4);
g.addEdge(4, 3);
g.addEdge(4, 5);
g.addEdge(5, 2);
cout << "Cycle found: " << g.findShortestCycle(3) << endl;
string path = "3 <- ";
int v = 3;
while (g.parents[v] != 3)
{
path += std::to_string(g.parents[v]) + " <- ";
v = g.parents[v];
}
cout << path << "3 <- " << endl;
return 0;
}
An O(nlogn) solution in C++, when the team size << total number of players:
#include <iostream>
int getTeams(vector<int> &players, int teamSize)
{
if (players.empty()) return 0;
int counter = 0;
priority_queue<int> pq(players.begin(), players.end());
stack<int> tmpStack;
int n = 0;
while (pq.size() >= teamSize)
{
n = 0;
while (n < teamSize && !pq.empty())
{
tmpStack.push(pq.top() - 1);
pq.pop();
++n;
}
if (n == teamSize) ++counter;
while (!tmpStack.empty())
{
int t = tmpStack.top();
tmpStack.pop();
if (t > 0) pq.push(t);
}
}
return counter;
}
int main()
{
vector<int> v = {5, 3, 3, 5};
std::cout << getTeams(v, 3) << std::endl;
}
C++ solution N^2. The counter is incremented using the number of subsets that can be obtained from the interval (min, max) of every iteration.
#include <iostream>
int findSubsets(vector<int> &v, int k)
{
int counter = 0;
int n = v.size();
std::sort(v.begin(), v.end());
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n; ++j)
{
if (v[i] + v[j] <= k)
{
if (i == j)
++counter;
else
counter += 1 << (j - i - 1);
}
}
}
return counter;
}
int main()
{
vector<int> v = {2, 4, 5, 7};
std::cout << findSubsets(v, 8) << std::endl;
}
Linear time C++ solution, using a hash set and a heap to collect the nearest results.
The heap contains the 3 results that have the minimum distance of the mistype.
Time complexity is O(n*26*log(3)) = O(n) where n is the length of the word (not of the dictionary, that usually is orders of magnitude bigger).
#include <iostream>
#include <unordered_set>
typedef std::pair<int, string> diffType;
vector<string> findAlternatives(string s, const unordered_set<string> &dict)
{
vector<string> out;
if (dict.empty()) return out;
priority_queue<diffType> pq;
const int maxElements = 3;
for (int i = 0; i < s.length(); ++i)
{
char backupChar = s[i];
for (char c = 'a'; c <= 'z'; ++c)
{
s[i] = c;
if (dict.find(s) != dict.end())
{
pq.push({std::abs(c - backupChar), s});
if (pq.size() > maxElements)
pq.pop();
}
}
s[i] = backupChar;
}
while (!pq.empty())
{
out.push_back(pq.top().second);
pq.pop();
}
return out;
}
int main()
{
std::unordered_set<string> dictSet = {"wil", "vil", "sil",
"pil", "men", "pion", "pal"};
std::vector<string> res = findAlternatives("mil", dictSet);
for (string &s: res)
std::cout << s << " ";
std::cout << std::endl;
}
N^2 C++ solution, with constrain that the pattern should start from first character and end with the last:
pair<string, int> findPattern(const string &s)
{
int n = s.length();
int divisor = 2;
while (divisor <= n)
{
if (n % divisor == 0)
{
int patternLen = n / divisor;
int repetitions = n / patternLen;
bool match = true;
for (int i = 1; i < repetitions; ++i)
{
for (int j = 0; j < patternLen; ++j)
{
if (s[j] != s[i * patternLen + j])
{
match = false;
break;
}
}
if (!match)
break;
}
if (match)
return {s.substr(0, patternLen), repetitions};
}
++divisor;
}
return {"", 0};
}
Using recursion is quite simple, just allocate a new node and recursively set the left and right children inverting them.
My C is a little rusty, but this is a complete implementation of the mirroring so you can fully understand the structure and debug it:
- bertelli.lorenzo September 29, 2019