kyduke
BAN USERC++, Brute Force
unsigned long long productPrime(vector<int>& arr) {
set<int> s, t, prime;
set<int>::iterator it;
int i, k, n;
unsigned long long ans;
for (i = 0; i < arr.size(); i++) {
n = arr[i];
if (n == 0) continue;
if (n < 0) n *= -1;
s.insert(n);
}
k = 2;
while (s.size()) {
for (it = s.begin(); it != s.end(); it++) {
n = *it;
if (n % k == 0) prime.insert(k);
while (n % k == 0) n /= k;
if (n > 1) t.insert(n);
}
s = t;
t.clear();
k++;
}
if (prime.size() == 0) return 0;
ans = 1;
for (it = prime.begin(); it != prime.end(); it++) {
ans *= *it;
}
return ans;
}
C++, implementation, O(2^n * n^2)
struct Paint {
int f;
int l;
float cost;
};
bool coverAllRange(int first, int last, vector<Paint>& arr, vector<int>& v) {
vector<pair<int, int>> ranges, temp;
int f, l, i, j;
bool overlap;
for (i = 0; i < v.size(); i++) {
if (v[i] == 0) continue;
overlap = false;
f = arr[i].f;
l = arr[i].l;
for (j = 0; j < ranges.size(); j++) {
if (arr[i].f <= ranges[j].second && arr[i].l >= ranges[j].first) {
if (overlap == false) {
overlap = true;
f = min(arr[i].f, ranges[j].first);
l = max(arr[i].l, ranges[j].second);
} else {
f = min(f, min(arr[i].f, ranges[j].first));
l = max(l, max(arr[i].l, ranges[j].second));
}
if (f <= first && l >= last) return true;
} else {
temp.push_back(ranges[j]);
}
}
ranges = temp;
ranges.push_back(make_pair(f, l));
temp.clear();
}
return false;
}
float solve(int first, int last, vector<Paint>& arr) {
queue<pair<int, vector<int>>> q;
vector<int> v;
int i, r;
float cost, temp;
cost = -1.0;
q.push(make_pair(arr.size(), v));
while (!q.empty()) {
r = q.front().first;
v = q.front().second;
q.pop();
if (r > 0) {
v.push_back(0);
q.push(make_pair(r - 1, v));
v[v.size() - 1] = 1;
q.push(make_pair(r - 1, v));
} else {
if (coverAllRange(first, last, arr, v) == true) {
temp = 0.0;
for (i = 0; i < v.size(); i++) {
if (v[i] == 1) temp += arr[i].cost;
}
if (cost == -1.0 || cost > temp) cost = temp;
}
}
}
return cost;
}
C++, implementation
void printArrayCombination(vector<int>& arr, vector<int>& com) {
int i, j, k;
for (i = 0, k = 0; i < com.size() - 1; i++) {
cout << "(";
for (j = 0; j < com[i]; j++, k++) {
cout << arr[k];
}
cout << ")";
}
cout << "\n";
}
void solve(vector<int>& arr) {
vector<int> com;
queue<vector<int>> q;
int i, e, c;
com.push_back((int)arr.size());
q.push(com);
while (!q.empty()) {
com = q.front();
q.pop();
e = (int)com.size() - 1;
if (com[e] == 0) {
printArrayCombination(arr, com);
continue;
}
c = com[e];
com.push_back(0);
for (i = 1; i <= c; i++) {
com[e] = i;
com[e + 1] = c - i;
q.push(com);
}
}
}
C++, implementation, O(n)
void printLongestSubstringLexBigger(string str) {
int i, j;
bool found;
for (i = 1; i < str.size(); i++) {
found = false;
for (j = 0; i + j < str.size(); j++) {
if (str[j] > str[i + j]) {
i += j;
break;
} else if (str[j] < str[i + j]) {
found = true;
break;
}
}
if (found) {
cout << str.substr(i) << "\n";
break;
}
}
}
C++, implementaion, O(n log n)
string swapLexOrder(string str, vector<pair<int, int>> pairs) {
string result;
queue<pair<int, int>> q;
set<int> s;
set<int>::iterator it;
vector<char> c;
int i, l, a, b;
result = str;
for (i = 0; i < pairs.size(); i++) {
q.push(pairs[i]);
}
while (!q.empty()) {
l = q.size();
s.clear();
while (l--) {
a = q.front().first;
b = q.front().second;
q.pop();
if (s.size() == 0 || s.find(a) != s.end() || s.find(b) != s.end()) {
s.insert(a);
s.insert(b);
l = q.size();
continue;
}
q.push(make_pair(a, b));
}
c.clear();
for (it = s.begin(); it != s.end(); it++) {
c.push_back(result[*it - 1]);
}
sort(c.begin(), c.end(), greater<char>());
i = 0;
for (it = s.begin(); it != s.end(); it++) {
result[*it - 1] = c[i];
i++;
}
}
return result;
}
C++, implementation, O(log n)
int numberAlphabetCombination(int n, map<int, int>& cache) {
map<int, int>::iterator it;
int count;
if (n <= 0) return 1;
it = cache.find(n);
if (it != cache.end()) {
return it->second;
}
count = numberAlphabetCombination(n / 10, cache);
if ((n % 100) >= 10 && (n % 100) <= 26) {
count += numberAlphabetCombination(n / 100, cache);
}
cache.insert(make_pair(n, count));
return count;
}
int solve(int n) {
map<int, int> cache;
return numberAlphabetCombination(n, cache);
}
C++, DFS, O(n log n)
struct Node {
int x;
int y;
Node* child;
Node* sibling;
Node(int vx, int vy): child(NULL), sibling(NULL) {
x = vx;
y = vy;
}
};
struct WorkingNode {
Node* node;
int depth;
int state;
};
bool find(Node* root, int x, int y) {
stack<WorkingNode> stk;
WorkingNode w;
set<int> xs, ys;
w.node = root;
w.depth = 0;
w.state = 0;
stk.push(w);
while (!stk.empty()) {
w = stk.top();
stk.pop();
if (w.node == NULL) continue;
if (w.state == 0) {
if (w.node->x == x) {
if (ys.find(w.depth) != ys.end()) return true;
xs.insert(w.depth);
}
if (w.node->y == y) {
if (xs.find(w.depth) != xs.end()) return true;
ys.insert(w.depth);
}
w.state = 1;
stk.push(w);
w.node = w.node->child;
w.depth++;
w.state = 0;
stk.push(w);
} else {
w.node = w.node->sibling;
w.state = 0;
stk.push(w);
}
}
return false;
}
c++, implementation, O(n)
int countOfMeltDown(vector<int>& arr) {
vector<int> mins;
int i, k, count;
mins.assign(arr.size(), 0);
count = 0;
for (i = 0, k = 1; i < arr.size(); i++, k++) {
mins[i] = min(arr[i], k);
if (arr[i] <= 0) k = 0;
}
for (i = arr.size() - 1, k = 1; i >= 0; i--, k++) {
count = max(count, min(mins[i], min(arr[i], k)));
if (arr[i] <= 0) k = 0;
}
return count;
}
c++, implementation, O(n log n)
void printTreeColumnOrder(Node* root) {
map<int, vector<int>> m;
map<int, vector<int>>::iterator it;
vector<int> arr;
queue<pair<Node*, int>> q;
Node* node;
int i;
q.push(make_pair(root, 0));
while (!q.empty()) {
node = q.front().first;
i = q.front().second;
q.pop();
if (node == NULL) continue;
it = m.find(i);
if (it == m.end()) {
arr.clear();
arr.push_back(node->val);
m.insert(make_pair(i, arr));
} else {
it->second.push_back(node->val);
}
q.push(make_pair(node->left, i - 1));
q.push(make_pair(node->right, i + 1));
}
for (it = m.begin(); it != m.end(); it++) {
for (i = 0; i < it->second.size(); i++) {
cout << it->second[i] << " ";
}
}
cout << "\n";
}
c++, implementation, O(n log n)
void sortMatrix(vector<vector<int>>& matrix) {
int column, row, i, j, k;
vector<int> arr;
column = matrix.size();
if (column == 0) return;
row = matrix[0].size();
arr.assign(column * row, 0);
for (i = 0; i < column; i++) {
k = i * row;
for (j = 0; j < row; j++) {
arr[k + j] = matrix[i][j];
}
}
sort(arr.begin(), arr.end());
for (j = 0; j < row; j++) {
k = j * column;
for (i = 0; i < column; i++) {
matrix[i][j] = arr[k + i];
}
}
}
c++, implementation
void addAndNormalize(vector<int>& arr, int n) {
vector<int>::iterator it;
int r;
r = n;
if (arr.size() == 0) {
arr.push_back(n);
r = 0;
}
reverse(arr.begin(), arr.end());
it = arr.begin();
while (true) {
*it += r;
r = *it / 10;
if (r == 0) break;
*it %= 10;
it++;
if (it == arr.end()) {
it = arr.insert(it, r);
r = 0;
}
}
reverse(arr.begin(), arr.end());
}
c++, priority_queue, O(n log n)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int minCost(vector<int>& arr) {
priority_queue< int, vector<int>, greater<int> > pq;
int i, cost;
cost = 0;
for (i = 0; i < arr.size(); i++) {
pq.push(arr[i]);
}
while (pq.size() > 1) {
i = pq.top();
pq.pop();
i += pq.top();
pq.pop();
pq.push(i);
cost += i;
}
return cost;
}
int main (int argc, char* argv[]) {
vector<int> arr;
cout << minCost(arr) << endl;
arr.push_back(1);
arr.push_back(2);
arr.push_back(3);
arr.push_back(5);
arr.push_back(7);
cout << minCost(arr) << endl;
return 0;
}
c++, implemention, O(n log n)
void zigZagSort(vector<int>& arr) {
vector<int> copy = arr;
int i, k, n;
sort(copy.begin(), copy.end());
n = arr.size() * 2 - 1;
for (i = 0; i < arr.size(); i++) {
k = i * 2 + 1;
if (k >= arr.size()) k = n - k;
arr[k] = copy[i];
}
}
c++, recursion, O(2 ^ n)
#include <iostream>
#include <vector>
using namespace std;
bool nonDecreasingSequence(vector<int>& a, vector<int>& b, vector<int>&c, int idx, int bit) {
if (idx == a.size()) {
return bit == 3;
}
if (idx == 0 || a[idx] >= c[idx - 1]) {
c[idx] = a[idx];
if (nonDecreasingSequence(a, b, c, idx + 1, bit | 1) == true) return true;
}
if (idx == 0 || b[idx] >= c[idx - 1]) {
c[idx] = b[idx];
if (nonDecreasingSequence(a, b, c, idx + 1, bit | 2) == true) return true;
}
return false;
}
int main(int argc, char* argv[]) {
vector<int> a, b, c;
int t, n, i;
cin >> t;
while (t--) {
cin >> n;
a.assign(n, 0);
b.assign(n, 0);
c.assign(n, 0);
for (i = 0; i < n; i++) cin >> a[i];
for (i = 0; i < n; i++) cin >> b[i];
if (nonDecreasingSequence(a, b, c, 0, 0) == true) {
for (i = 0; i < n; i++) {
cout << c[i] << " ";
}
cout << "\n";
} else {
cout << "IMPOSSIBLE\n";
}
}
return 0;
}
c++, implementation, O(n log n)
int nthMultipleNumber(vector<int> arr, int n) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int i, ret;
if (arr.size() == 0 || n <= 0) return 0;
for (i = 0;i < arr.size(); i++) {
q.push(make_pair(arr[i], i));
}
ret = 0;
while (n) {
if (ret != q.top().first) n--;
ret = q.top().first;
i = q.top().second;
q.pop();
q.push(make_pair(ret + arr[i], i));
}
return ret;
}
c++, KMP algorithm, O(n * k)
KMP: O(n), find all substr: O(n * k)
vector< pair<string, int> > substringCountKMP(string str, int k) {
vector< pair<string, int> > ret;
vector<int> fails(str.size() + 1, -1);
vector<int> counts(str.size() + 1, 1);
int i, pos;
for (i = 1; i <= str.size(); i++) {
pos = fails[i - 1];
while (pos != -1 && str[pos] != str[i - 1]) {
pos = fails[pos];
}
fails[i] = pos + 1;
}
for (i = fails.size() - 1; i > 0; i--) {
if (fails[i] >= k) {
counts[ fails[i] ] += counts[i];
counts[i] = 0;
}
}
for (i = k; i < counts.size(); i++) {
if (counts[i] == 0) continue;
ret.push_back(make_pair(str.substr(i - k, k), counts[i]));
}
return ret;
}
c++, brute force, O(n^3)
vector< vector<int> > findTriangles(vector<int> nums) {
vector< vector<int> > triangles;
vector<int> triangle;
int i, j, k;
for (i = 0; i < nums.size() - 2; i++) {
for (j = i + 1; j < nums.size() - 1; j++) {
for (k = j + 1; k < nums.size(); k++) {
if (nums[i] + nums[j] <= nums[k]) continue;
if (nums[j] + nums[k] <= nums[i]) continue;
if (nums[k] + nums[i] <= nums[j]) continue;
triangle.clear();
triangle.push_back(nums[i]);
triangle.push_back(nums[j]);
triangle.push_back(nums[k]);
triangles.push_back(triangle);
}
}
}
return triangles;
}
javascript, implementation, O(n)
var mergeArrayU = function(arrA, arrB) {
var i, j;
i = 0;
j = 0;
while (i < arrA.length && j < arrB.length) {
if (arrA[i] === 'undefined' || arrA[i] === undefined) {
arrA[i] = arrB[j];
j++;
}
i++;
}
}
a = [2, undefined, 7, undefined, 10, undefined, undefined];
b = [5, 8, 12, 14];
mergeArrayU(a, b);
console.log(a);
// [2, 5, 7, 8, 10, 12, 14]
c++, implementation
#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long INT64;
INT64 getDiff(string startTime, string endTime) {
string command = "date +%s -d ";
char cmd[256];
char buf[256];
FILE *ptr;
INT64 start, end;
int i;
startTime = command + "'" + startTime + "'";
strcpy(cmd, startTime.c_str());
if ((ptr = popen(cmd, "r")) != NULL) {
while (fgets(buf, 256, ptr) != NULL) {
start = 0;
i = 0;
while (buf[i] >= '0' && buf[i] <= '9') {
start = start * 10 + (buf[i] - '0');
i++;
}
}
fclose(ptr);
}
endTime = command + "'" + endTime + "'";
strcpy(cmd, endTime.c_str());
if ((ptr = popen(cmd, "r")) != NULL) {
while (fgets(buf, 256, ptr) != NULL) {
end = 0;
i = 0;
while (buf[i] >= '0' && buf[i] <= '9') {
end = end * 10 + (buf[i] - '0');
i++;
}
}
fclose(ptr);
}
return end - start;
}
void findHighestTimeDifference(string filename) {
ifstream inFile(filename.c_str());
string startTime, endTime, maxStartTime, maxEndTime;
INT64 diff, maxDiff;
char buffer[256];
int i;
while(!inFile.eof()){
inFile.getline(buffer, 100);
string str(buffer);
if (str.substr(0, 10).compare("STARTTIME:") == 0) {
startTime = str.substr(10, str.size() - 10);
} else if (str.substr(0, 9).compare("ENDTIME :") == 0) {
endTime = str.substr(9, str.size() - 9);
diff = getDiff(startTime, endTime);
if (maxStartTime.size() == 0 || maxDiff < diff) {
maxStartTime = startTime;
maxEndTime = endTime;
maxDiff = diff;
}
}
}
inFile.close();
cout << "STARTTIME:" << maxStartTime << "\n";
cout << "ENDTIME :" << maxEndTime << "\n";
}
int main()
{
findHighestTimeDifference("time.log");
return 0;
}
c++, Binomial Coefficient, O(n*m)
int casesOfSoccerScore(int a, int b) {
int i, j, ret;
vector<int> even, odd;
if (a < b) {
i = a;
a = b;
b = i;
}
even.assign(a + 1, 1);
odd.assign(a + 1, 1);
for (i = 1; i <= b; i++) {
if (i % 2 == 0) {
for (j = 1; j <= a; j++) {
even[j] = even[j - 1] + odd[j];
}
} else {
for (j = 1; j <= a; j++) {
odd[j] = odd[j - 1] + even[j];
}
}
}
if (b % 2 == 0) {
ret = even[a];
} else {
ret = odd[a];
}
return ret;
}
javascript, implementation
var canArriveTarget = function(arr, visit, count, num, target) {
var i;
if (count == arr.length) {
if (num == target) return true;
return false;
}
for (i = 0; i < arr.length; i++) {
if (visit[i] == 1) continue;
visit[i] = 1;
if (canArriveTarget(arr, visit, count + 1, num + arr[i], target) == true) return true;
if (canArriveTarget(arr, visit, count + 1, num - arr[i], target) == true) return true;
if (count != 0) {
if (canArriveTarget(arr, visit, count + 1, num * arr[i], target) == true) return true;
}
visit[i] = 0;
}
return false;
}
var solve = function(str, target) {
var arr, visit;
arr = str.split(' ').map(function(item) {
return parseInt(item, 10);
});
if (arr.length == 0) return false;
visit = arr.map(function(item) {
return 0;
});
return canArriveTarget(arr, visit, 0, 0, target);
}
c++, implementation
unsigned int getMaxDecialIndex(vector<vector<int>> matrix) {
unsigned int maxIndex, i, j;
if (matrix.size() == 0) return 0;
maxIndex = 0;
for (i = 1; i < matrix.size(); i++) {
for (j = 0; j < matrix[i].size(); j++) {
if (matrix[maxIndex][j] == matrix[i][j]) continue;
if (matrix[i][j] == 1) {
maxIndex = i;
}
break;
}
}
return maxIndex + 1;
}
c++, implementation
"abcdefghijklmnopqrstuvwxyz", "xcobra" => "abc"
string latgestSubstringPresentOther(string s1, string s2) {
vector<int> arr(s1.size() + 1, 0);
int present[256] = {0, };
int i, start, maxLength, length;
for (i = 0; i < s2.size(); i++) {
present[ s2[i] ] = 1;
}
for (i = 0; i < s1.size(); i++) {
arr[i] = present[ s1[i] ];
}
start = 0;
maxLength = 0;
length = 0;
for (i = 0; i < arr.size(); i++) {
if (arr[i] == 0) {
if (maxLength < length) {
maxLength = length;
start = i - length;
}
length = 0;
continue;
}
length++;
}
return s1.substr(start, maxLength);
}
c++, implementation
typedef long long INT64;
void minimumDividableSum(vector<int>& arr, int K, int F, int idx, INT64 sum, INT64& answer) {
if (K == 0) {
if (sum != 0 && sum % F == 0 && (answer == -1 || answer > sum)) {
answer = sum;
}
return;
}
if (answer != -1 && sum > answer) return;
if (idx >= arr.size()) return;
minimumDividableSum(arr, K - 1, F, idx + 1, sum + arr[idx], answer);
minimumDividableSum(arr, K, F, idx + 1, sum, answer);
}
INT64 solve(vector<int>& arr, int K, int F) {
INT64 answer = -1;
if (K > arr.size()) return answer;
minimumDividableSum(arr, K, F, 0, 0, answer);
return answer;
}
c++, implementation
template <typename T>
class TwoStackQueue {
private:
stack<T> in;
stack<T> out;
public:
void enqueue(T v) {
in.push(v);
}
void dequeue() {
if (out.empty()) {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
}
out.pop();
}
T peek() {
if (out.empty()) {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
}
return out.top();
}
unsigned int count() {
return in.size() + out.size();
}
};
c++, fibonacci, O(log n)
typedef unsigned long long UINT64;
UINT64 fibonacci(int n) {
int k;
UINT64 a, b, ret;
if (n <= 2) return 1;
k = n / 2;
a = fibonacci(k + 1);
b = fibonacci(k);
if (n % 2 == 1) ret = a * a + b * b;
else ret = b * (2 * a - b);
return ret;
}
UINT64 casesOfReading(int n) {
return fibonacci(n + 1);
}
c++, stack, O(n log n)
void reversePositive(vector<int>& arr) {
vector<int>::iterator it;
stack<int> stck;
int head;
head = 0;
it = arr.begin();
while (it != arr.end()) {
if (*it <= 0) {
while (!stck.empty()) {
arr[head] = stck.top();
head++;
stck.pop();
}
head++;
} else {
stck.push(*it);
}
it++;
}
while (!stck.empty()) {
arr[head] = stck.top();
head++;
stck.pop();
}
}
c++, implementation
double cubeRoot(double n) {
double cube, left, right, mid;
int cnt, sign;
sign = 1;
if (n < 0.0) sign = -1;
n *= sign;
left = 0.0;
right = n;
if (n < 1.0) right = 1.0;
cnt = 100;
while (cnt--) {
mid = (left + right) * 0.5;
cube = mid * mid * mid;
if (cube > n) {
right = mid;
} else {
left = mid;
}
}
return left * sign;
}
"Hi Sivasrinivas, your Uber is arriving now!", 25 => ["Hi Sivasrinivas,(1/3)", "your Uber is arriving(2/3)", "now!(3/3)"]
"01234567890123456789", 15 => ["012345678901234(1/2)", "56789(2/2)"]
utility functions
void printStringArray(vector<string> arr) {
int i;
cout << "[";
for (i = 0; i < arr.size(); i++) {
cout << "\"" << arr[i] << "\"";
if (i != arr.size() - 1) cout << ", ";
}
cout << "]\n";
}
string integerToString(int n) {
string str;
string table[10] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
if (n == 0) return "0";
str = "";
while (n) {
str = table[n % 10] + str;
n /= 10;
}
return str;
}
c++, implementation
vector<string> splitWord(string str, int limit) {
vector<string> arr;
vector<int> marks;
vector<int> spaces;
string size;
int i, start, markIdx, spaceIdx;
for (i = 0; i < str.size(); i++) {
if (str[i] == ' ') {
spaces.push_back(i);
if (i == 0) continue;
switch (str[i - 1]) {
case ',': case '.': case '?': case '!':
marks.push_back(i);
}
}
}
spaces.push_back(i);
marks.push_back(i);
start = 0;
markIdx = 0;
spaceIdx = 0;
while (markIdx < marks.size()) {
if (marks[ markIdx ] - start <= limit) {
markIdx++;
continue;
}
if (markIdx > 0 && marks[ markIdx - 1 ] > start && marks[ markIdx - 1 ] - start <= limit) {
arr.push_back(str.substr(start, marks[ markIdx - 1 ] - start));
start = marks[ markIdx - 1 ] + 1;
} else {
while (spaceIdx < spaces.size() && spaces[ spaceIdx ] <= start + limit) spaceIdx++;
if (spaceIdx > 0 && spaces[ spaceIdx ] > start + limit) spaceIdx--;
if (spaces[ spaceIdx ] > start && spaces[ spaceIdx ] <= start + limit) {
arr.push_back(str.substr(start, spaces[ spaceIdx ] - start));
start = spaces[ spaceIdx ] + 1;
} else {
arr.push_back(str.substr(start, limit));
start += limit;
}
}
}
arr.push_back(str.substr(start, marks[ markIdx - 1 ] - start));
size = "/" + integerToString((int)arr.size()) + ")";
for (i = 0; i < arr.size(); i++) {
arr[i] += "(" + integerToString(i + 1) + size;
}
return arr;
}
c++, implementation
int maxPrice(vector<int> s, vector<int> p) {
int length, ret, i, price, count;
length = (int)min(s.size(), p.size());
ret = 0;
for (i = 0; i < length; i++) {
count = min(s[i], p[i]);
if (count <= 0) continue;
price = (p[i] + p[i] - count + 1) * count / 2;
ret = max(ret, price);
}
return ret;
}
c++, implementation
#include <iostream>
#include <string>
using namespace std;
template <typename T>
struct Iterator {
T obj;
int cnt;
Iterator(T e, int n) : obj(e), cnt(n) {}
bool operator() (T& ret) {
if (cnt > 0) {
cnt--;
ret = obj;
return true;
}
return false;
}
};
template <typename T>
Iterator<T> repeat(T e, int n) {
Iterator<T> iterator(e, n);
return iterator;
}
struct Object {
int value;
string name;
};
int main(int argc, char* argv[]) {
int n = 3;
Iterator<int> integerIterator = repeat(n, 5);
n = -1;
while (integerIterator(n)) {
cout << n << " ";
}
cout << "\n";
Object obj;
obj.value = 7;
obj.name = "ABC";
Iterator<Object> objectIterator = repeat(obj, 3);
obj.value = -1;
obj.name = "";
while (objectIterator(obj)) {
cout << "(" << obj.value << ", " << obj.name << ") ";
}
cout << "\n";
return 0;
}
We need a group table and a group matrix. At initiial state, a group table is empty and a group matrix is filled 0.
groupID: {}
groupMatrix:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
We visit each cell from top left corner and move left. Cell's left and up are 0 then cell get a new groupID.
groupID: { 1(1), 2(2) }
groupMatrix:
0 1 0 2 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Now, we fill groupID to 3rd cell of 2nd row.
groupID: { 1(1), 2(2), 3(3) }
groupMatrix:
0 1 0 2 0
0 0 3 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
4th cell of 2nd row has 2 candidates of groupID, 3 from left cell and 2 from up cell. We choice lower gropuID. And bigger groupID change to lower groupID.
groupID: { 1(1), 2(2), 3(2) }
groupMatrix:
0 1 0 2 0
0 0 3 2 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
This is final state. Number of groups is number of items of same groupID index and value.
groupID: { 1(1), 2(2), 3(2), 4(4), 5(5), 6(6), 7(7) }
groupMatrix:
0 1 0 2 0
0 0 3 2 2
4 0 0 2 0
0 5 5 0 0
6 0 5 0 7
c++, implementation, O(n)
int countOfIslands(vector<vector<int>> matrix) {
vector<vector<int>> groupMatrix;
vector<int> groupID;
int nextGroup;
int i, x, y, left, up, cnt;
groupMatrix = matrix;
for (i = 0; i < groupMatrix.size(); i++) {
groupMatrix[i].assign(groupMatrix[i].size(), 0);
}
groupID.push_back(0);
nextGroup = 1;
for (y = 0; y < matrix.size(); y++) {
for (x = 0; x < matrix[y].size(); x++) {
if (matrix[y][x] == 0) continue;
left = 0;
if (x != 0) left = groupMatrix[y][x - 1];
left = groupID[left];
up = 0;
if (y != 0) up = groupMatrix[y - 1][x];
up = groupID[up];
if (left == 0 && up == 0) {
groupMatrix[y][x] = nextGroup;
groupID.push_back(nextGroup);
nextGroup++;
} else if (left != 0 && up != 0) {
if (left > up) {
groupMatrix[y][x] = up;
groupID[left] = up;
} else {
groupMatrix[y][x] = left;
groupID[up] = left;
}
} else if (up == 0) {
groupMatrix[y][x] = left;
} else {
groupMatrix[y][x] = up;
}
}
}
cnt = 0;
for (i = 1; i < groupID.size(); i++) {
if (i == groupID[i]) cnt++;
}
return cnt;
}
c++, implementation
struct Person {
string name;
string phoneNumber;
};
class PhoneBook {
private:
vector<Person> book;
map<string, int> names;
map<string, int> phones;
int readCount;
mutex mtx;
public:
PhoneBook(vector<Person> people) : readCount(0) {
vector<Person>::iterator it;
for (it = people.begin(); it != people.end(); it++) {
if (names.find(it->name) != names.end()) continue;
if (phones.find(it->phoneNumber) != phones.end()) continue;
book.push_back(*it);
names.insert(make_pair(it->name, book.size() - 1));
phones.insert(make_pair(it->phoneNumber, book.size() - 1));
}
}
Person LookupByName(string name) {
map<string, int>::iterator it;
Person p;
mtx.lock();
readCount++;
mtx.unlock();
it = names.find(name);
if (it != names.end()) p = book[it->second];
mtx.lock();
readCount--;
mtx.unlock();
return p;
}
Person LookupByPhoneNumber(string phoneNumber) {
map<string, int>::iterator it;
Person p;
mtx.lock();
readCount++;
mtx.unlock();
it = phones.find(phoneNumber);
if (it != phones.end()) p = book[it->second];
mtx.lock();
readCount--;
mtx.unlock();
return p;
}
void AddPerson(Person person) {
while (true) {
mtx.lock();
if (readCount == 0) break;
mtx.unlock();
}
if (names.find(person.name) == names.end() && phones.find(person.phoneNumber) == phones.end()) {
book.push_back(person);
names.insert(make_pair(person.name, book.size() - 1));
phones.insert(make_pair(person.phoneNumber, book.size() - 1));
}
mtx.unlock();
}
};
c++, implementation
bool isRotatable(int n) {
vector<int> arr;
bool rotatables[10] = {1, 1, 0, 0, 0, 0, 1, 0, 1, 1};
bool selfRotatables[10] = {1, 1, 0, 0, 0, 0, 0, 0, 1, 0};
int rotateNumbers[10] = {0, 1, 0, 0, 0, 0, 9, 0, 8, 6};
int i, j;
if (n == 0) return true;
while (n) {
i = n % 10;
n /= 10;
if (rotatables[i] == false) return false;
arr.push_back(i);
}
i = 0;
j = (int)arr.size() - 1;
while (i < j) {
if (rotateNumbers[ arr[i] ] != arr[j]) return false;
i++;
j--;
}
if (i == j) return selfRotatables[ arr[i] ];
return true;
}
Case #1:
S = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 10), (10, 11)}
R = (1, 11);
while 10 x for 2 = 20. 2n => n
Case #2:
S = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11)}
R = (1, 11);
while 1 x for 10 = 10. n
Case #3:
S = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (6, 7), (6, 8), (6, 9), (6, 10), (6, 11)}
R = (1, 11);
1st while: 6 + 2nd while 4 = 10, n
Would you show me worst case sample?
c++, greedy, O(n log n)
sort: O(n log n), greedy: O(n)
struct Compare {
bool operator() (const pair<int, int>& a, const pair<int, int>& b) {
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
}
};
vector<pair<int, int>> smallestSetOfRanges(vector<pair<int, int>>& ranges, pair<int, int> R) {
vector<pair<int, int>> result;
int target, i, maxTarget, maxIndex;
bool match;
if (R.first == R.second) {
for (i = 0; i < ranges.size(); i++) {
if (ranges[i].first <= R.first && ranges[i].second >= R.second) {
result.push_back(ranges[i]);
break;
}
}
return result;
}
sort(ranges.begin(), ranges.end(), Compare());
target = R.first;
maxIndex = 0;
while (target < R.second) {
match = false;
maxTarget = target;
for (i = maxIndex; i < ranges.size(); i++) {
if (ranges[i].first <= target && ranges[i].second >= maxTarget) {
match = true;
maxTarget = ranges[i].second;
maxIndex = i;
} else if (ranges[i].first > target) {
break;
}
}
if (match == false) {
result.clear();
break;
}
result.push_back(ranges[maxIndex]);
target = maxTarget;
maxIndex++;
}
return result;
}
I fixed previous code, multiplication is used instead of addition.
{2, 3, 5, 7, 11, 23, 97}, 3 => 3
{2, 3, 5, 7, 11, 23, 97}, 1000000 => 37812219101007120
{99991}, 3 => 9998200081
{99991}, 1000000 => 0
c++, O(n * n * log n)
typedef unsigned long long UINT64;
const UINT64 LIMIT = 18446744073709551615UL;
UINT64 getNthNumber(vector<int>& primes, int n) {
set<UINT64> nums;
set<UINT64>::iterator it;
set<UINT64>::reverse_iterator rit;
UINT64 limit;
unsigned int i;
nums.insert(1);
for (i = 0; i < primes.size(); i++) {
it = nums.begin();
limit = LIMIT / primes[i];
while (it != nums.end()) {
if (*it > limit) break;
nums.insert(*it * primes[i]);
if (nums.size() == n * 2) break;
it++;
}
while (nums.size() > n) {
rit = nums.rbegin();
nums.erase(next(rit).base());
}
}
if (nums.size() < n) return 0;
return *nums.rbegin();
}
{2, 3, 5, 7, 11, 23, 97}, 3 => 3
{2, 3, 5, 7, 11, 23, 97}, 1000000 => 1244877
{99991}, 1000000 => 99990900009
c++, Sieve of Eratosthenes, O(n^2)? O(n log n)?
typedef unsigned long long UINT64;
UINT64 getNthNumber(vector<int>& primes, int n) {
set<UINT64> nums;
set<UINT64>::reverse_iterator rit;
UINT64 num;
unsigned int i;
nums.insert(1);
for (i = 0; i < primes.size(); i++) {
num = 0;
while (true) {
num += primes[i];
nums.insert(num);
if (nums.size() >= n && *nums.rbegin() == num) {
while (nums.size() > n) {
rit = nums.rbegin();
nums.erase(next(rit).base());
}
break;
}
}
}
return *nums.rbegin();
}
C++, Brute Force
0, 6, 3 => BBBBBB
1, 5, 3 => BBRBBB
2, 4, 3 => BBRBBR
3, 3, 3 => BBRRBR
- kyduke March 05, 2018