kyduke
BAN USERc++, implementation, O(n^2)
typedef long long INT64;
bool consecutiveSubSum(vector<int>& arr, int target) {
vector<INT64> subsum;
int i, j;
subsum.assign(arr.size() + 1, 0);
for (i = 0; i < arr.size(); i++) {
subsum[i + 1] = subsum[i] + arr[i];
}
for (i = 0; i < subsum.size(); i++) {
for (j = 0; j < i; j++) {
if (subsum[i] - subsum[j] == target) return true;
}
}
return false;
}
c++, implementation, O(n^2)
Loop: O(n), distance: O(n). This is not fast solution.
vector<int> remainGreaterCount(vector<int>& arr) {
multiset<int> s;
multiset<int>::iterator it;
vector<int> result;
int i, j;
result.assign(arr.size(), 0);
for (i = arr.size() - 1; i >= 0; i--) {
s.insert(arr[i]);
it = s.upper_bound(arr[i]);
result[i] = distance(it, s.end());
}
return result;
}
c++, implementation, O(1)
preCalcSum: O(n)
typedef long long INT64;
vector<INT64> sums;
void preCalcSum(vector<int>& arr) {
int i;
if (arr.size() == 0) return;
sums.clear();
sums.assign(arr.size() + 1, 0);
for (i = 0; i < arr.size(); i++) {
sums[i + 1] = sums[i] + arr[i];
}
}
int subSum(vector<int>& arr, int x1, int x2) {
if (x1 > x2 || x1 < 0 || x2 >= arr.size()) return 0;
return sums[x2 + 1] - sums[x1];
}
int main() {
int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> arr(data, data + 10);
preCalcSum(arr);
cout << subSum(arr, 0, 9) << "\n"; // 55
cout << subSum(arr, 0, 0) << "\n"; // 1
cout << subSum(arr, 9, 9) << "\n"; // 10
cout << subSum(arr, 2, 7) << "\n"; // 33
cout << subSum(arr, -1, 9) << "\n"; // 0
cout << subSum(arr, 0, 10) << "\n"; // 0
cout << subSum(arr, 9, 0) << "\n"; // 0
return 0;
}
c++, implementation
{2, 3, 4}, 2 => {2, 2}, {2, 3}, {2, 4}, {3, 2}, {3, 3}, {3, 4}, {4, 2}, {4, 3}, {4, 4}
bool nextIndex(vector<int>& indexes, int size) {
int i, up;
up = 0;
i = indexes.size() - 1;
indexes[i]++;
while (i >= 0) {
indexes[i] += up;
if (indexes[i] < size) return true;
indexes[i] = 0;
up = 1;
i--;
}
return false;
}
vector<vector<int>> getPermutation(vector<int>& arr, int n) {
vector<vector<int>> permutations;
if (arr.size() == 0 || n <= 0 || arr.size() < n) return permutations;
vector<int> indexes;
vector<int> item;
int i;
indexes.assign(n, 0);
while (true) {
item.clear();
for (i = 0; i < indexes.size(); i++) {
item.push_back(arr[ indexes[i] ]);
}
permutations.push_back(item);
if (nextIndex(indexes, arr.size()) == false) break;
}
return permutations;
}
I do not make new array and do not change array size.
javascript, implementation, O(n) without indexOf
function sort(A, B) {
var temp, from, to, idx;
if (!(A instanceof Array) || !(B instanceof Array)) return;
if (A.length != B.length) return;
for (from = 0; from < A.length; from++) {
to = B[from];
if (from == to) continue;
temp = A[from];
A[from] = A[to];
A[to] = temp;
idx = B.indexOf(from);
if (idx > from) {
B[idx] = to;
}
}
}
c++, implementation
struct Object {
char value;
Object(char v) {
value = v;
}
};
void solve(vector<Object>& A, vector<int> B) {
int from, to, i;
Object temp(' ');
if (A.size() != B.size()) return;
for (from = 0; from < A.size(); from++) {
to = B[from];
if (from == to) continue;
temp = A[from];
A[from] = A[to];
A[to] = temp;
i = from + 1;
while (i < A.size()) {
if (B[i] == from) {
B[i] = to;
break;
}
i++;
}
}
}
If first character is ')', then n is 0 and this function return false.
This function is working correctly with ')))((('.
If we check only one type of parentheses such as '()', we do not need to use stack. Stack need to check valid with multiple type of parentheses and brackets such as '(){}[]'.
c++, implementation
struct Node {
int val;
Node* next;
Node(int v) : next(NULL) {
val = v;
}
};
bool isFibonacci(int n) {
int k, r;
k = n * n * 5 - 4;
r = sqrt((double)k);
if (r * r == k) return true;
k = n * n * 5 + 4;
r = sqrt((double)k);
if (r * r == k) return true;
return false;
}
void divideLinkedList(Node* node, Node** fRoot, Node** oRoot) {
Node* fNode = NULL;
Node* oNode = NULL;
while (node) {
if (isFibonacci(node->val) == true) {
if (fNode == NULL) {
*fRoot = node;
fNode = *fRoot;
} else {
fNode->next = node;
fNode = fNode->next;
}
} else {
if (oNode == NULL) {
*oRoot = node;
oNode = *oRoot;
} else {
oNode->next = node;
oNode = oNode->next;
}
}
node = node->next;
}
if (fNode) fNode->next = NULL;
if (oNode) oNode->next = NULL;
}
c++, implementation
int distanceTwoWordsInString(string str, string wordA, string wordB) {
vector<int> positionA;
vector<int> positionB;
string sub;
int i, start, wordIndex, indexA, indexB, distance;
i = 0;
start = 0;
wordIndex = 0;
while (i <= str.size()) {
if (i == str.size() || str[i] == ' ') {
sub = str.substr(start, i - start);
start = i + 1;
if (sub.compare(wordA) == 0) positionA.push_back(wordIndex);
if (sub.compare(wordB) == 0) positionB.push_back(wordIndex);
wordIndex++;
if (i == str.size()) break;
}
i++;
}
if (positionA.size() == 0 || positionB.size() == 0) return -1;
indexA = 0;
indexB = 0;
distance = wordIndex;
while (indexA < positionA.size() && indexB < positionB.size()) {
if (positionA[indexA] > positionB[indexB]) {
distance = min(distance, positionA[indexA] - positionB[indexB]);
indexB++;
} else if (positionA[indexA] < positionB[indexB]) {
distance = min(distance, positionB[indexB] - positionA[indexA]);
indexA++;
} else {
indexA++;
}
}
return distance;
}
Distance between consumer k and left of k-1's producer is not shorter than distance between consumer k and k-1's producer. Also, distance between consumer k and right of k+1's producer is not shorter than distance between consumer k and k+1's producer. We can solve this problem using binary search.
c++, binary search, O(n log n)
typedef unsigned long long UINT64;
const UINT64 MAX_DISTANCE = 18446744073709551615;
struct Point {
int x;
int y;
Point(int coordX, int coordY) {
x = coordX;
y = coordY;
}
bool operator<(const Point& a) const {
return x < a.x;
}
};
struct ConsumerData {
int index;
int left;
int right;
ConsumerData(int i, int l, int r) {
index = i;
left = l;
right = r;
}
};
int findNearestProducer(vector<Point>& producers, int consumer, int startIndex, int endIndex) {
int nearestIndex, i;
UINT64 minDistance, currDistance;
nearestIndex = 0;
minDistance = MAX_DISTANCE;
for (i = startIndex; i <= endIndex; i++) {
currDistance = (producers[i].x - consumer) * (producers[i].x - consumer) + producers[i].y * producers[i].y;
if (currDistance < minDistance) {
minDistance = currDistance;
nearestIndex = i;
}
}
return nearestIndex;
}
vector<Point> findNearestProducers(vector<Point>& producers, vector<int>& consumers) {
vector<Point> nearestProducers;
vector<int> nearestIndex;
queue<ConsumerData> q;
int i, index;
if (producers.size() == 0 || consumers.size() == 0) return nearestProducers;
sort(producers.begin(), producers.end());
sort(consumers.begin(), consumers.end());
nearestProducers.assign(consumers.size(), Point(0, 0));
nearestIndex.assign(consumers.size(), -1);
i = 0;
index = findNearestProducer(producers, consumers[i], 0, producers.size() - 1);
nearestIndex[i] = index;
nearestProducers[i] = producers[index];
if (consumers.size() == 1) return nearestProducers;
i = consumers.size() - 1;
index = findNearestProducer(producers, consumers[i], nearestIndex[0], producers.size() - 1);
nearestIndex[i] = index;
nearestProducers[i] = producers[index];
if (consumers.size() == 2) return nearestProducers;
q.push(ConsumerData(i / 2, 0, i));
while (!q.empty()) {
ConsumerData c = q.front();
q.pop();
i = c.index;
index = findNearestProducer(producers, consumers[i], nearestIndex[c.left], nearestIndex[c.right]);
nearestIndex[i] = index;
nearestProducers[i] = producers[index];
if (c.left < i - 1) {
q.push(ConsumerData((i + c.left) / 2, c.left, i));
}
if (c.right > i + 1) {
q.push(ConsumerData((i + c.right) / 2, i, c.right));
}
}
return nearestProducers;
}
Sorting is O(n log n). Finding maximum coverage with minimum items is O(n).
c++, implementation
struct sort_first_second {
bool operator()(const pair<int, int>& left, const pair<int, int>& right) {
if (left.first != right.first) return left.first < right.first;
return left.second < right.second;
}
};
void optimizeArray(vector<pair<int, int>>& arr) {
vector<pair<int, int>> result;
int i, limit, start, end, index;
if (arr.size() == 0) return;
sort(arr.begin(), arr.end(), sort_first_second());
limit = arr[arr.size() - 1].second;
start = arr[0].first;
end = start;
i = 0;
while (end < limit) {
index = -1;
while (i < arr.size()) {
if (arr[i].first <= start) {
if (arr[i].second > end) {
end = arr[i].second;
index = i;
}
} else {
if (index == -1) {
start = arr[i].first;
}
break;
}
i++;
}
if (index != -1) {
start = end;
result.push_back(arr[index]);
}
}
arr = result;
}
c++, implementation
void printCombination(vector<char> arr) {
queue< pair<string, int> > q;
string str;
int i;
str = "";
for (i = 0; i < arr.size(); i++) {
q.push(make_pair(str + arr[i], i));
}
while (q.size()) {
str = q.front().first;
i = q.front().second + 1;
q.pop();
for (; i < arr.size(); i++) {
q.push(make_pair(str + arr[i], i));
}
cout << str;
if (q.size()) cout << ",";
}
cout << "\n";
}
c++, O(n^2): Loop is O(n) and substr is O(n)
string reveseWords(string inStr) {
string outStr;
int start, end;
bool period;
outStr = "";
end = inStr.size();
if (end == 0) return outStr;
end--;
if (inStr[end] == '.') {
period = true;
end--;
} else {
period = false;
}
for (start = end; start >= 0; start--) {
if (inStr[start] == ' ') {
outStr.append(inStr.substr(start + 1, end - start));
outStr.append(" ");
end = start - 1;
}
}
outStr.append(inStr.substr(start + 1, end - start));
if (period == true) outStr.append(".");
return outStr;
}
c++, greedy
#include <map>
string rearrange(string str) {
string result, last, temp;
map<string, int> counts;
map<string, int>::iterator it;
multimap<int, string> remains;
multimap<int, string>::reverse_iterator rit;
int i;
for (i = 0; i < str.size(); i++) {
temp = str.substr(i, 1);
it = counts.find(temp);
if (it != counts.end()) {
it->second++;
} else {
counts.insert(make_pair(temp, 1));
}
}
for (it = counts.begin(); it != counts.end(); it++) {
remains.insert(make_pair(it->second, it->first));
}
counts.clear();
result = "";
if (remains.size() > 0) {
rit = remains.rbegin();
if (rit->first * 2 - 2 >= str.size()) return "No valid output";
last = "";
while (remains.size()) {
rit = remains.rbegin();
if (last.compare(rit->second) == 0) rit++;
i = rit->first;
last = rit->second;
remains.erase(next(rit).base());
result.append(last);
if (i > 1) remains.insert(make_pair(i - 1, last));
}
}
return result;
}
java, implementation
int getKthElementFromSortedSubarray(int[] arr, int a, int b, int k) {
int[] subarray;
if (a < 0 || b < 0 || a >= b || k > (b - a) || a >= arr.length || b > arr.length) return -1;
subarray = new int[b - a];
System.arraycopy(arr, a, subarray, 0, b - a);
Arrays.sort(subarray);
return subarray[k];
}
c++, implementation
int getKthElementFromSortedSubarray(vector<int> arr, int a, int b, int k) {
vector<int> subarray;
if (a < 0 || b < 0 || a >= b || k > (b - a) || a >= arr.size() || b > arr.size()) return -1;
subarray.assign(arr.begin() + a, arr.begin() + b);
sort(subarray.begin(), subarray.end());
return subarray[k];
}
c++, implement
bool verify(string& str) {
stack<char> s;
int i;
for (i = 0; i < str.size(); i++) {
if (str[i] == '<' || str[i] == '[' || str[i] == '(') {
s.push(str[i]);
} else if (str[i] == '>') {
if (s.size() == 0 || s.top() != '<') return false;
s.pop();
} else if (str[i] == ']') {
if (s.size() == 0 || s.top() != '[') return false;
s.pop();
} else if (str[i] == ')') {
if (s.size() == 0 || s.top() != '(') return false;
s.pop();
}
}
if (s.size() > 0) return false;
return true;
}
Convert BT to set. Compare 2 sets.
c++, brute force
void makeIntegerArray(Node* node, set<int>& arr) {
if (node == NULL) return;
arr.insert(node->value);
makeIntegerArray(node->left, arr);
makeIntegerArray(node->right, arr);
}
bool haveSameIntegers(Node* a, Node* b) {
set<int> arrA, arrB;
set<int>::iterator itA, itB;
makeIntegerArray(a, arrA);
makeIntegerArray(b, arrB);
if (arrA.size() != arrB.size()) return false;
itA = arrA.begin();
itB = arrB.begin();
while (itA != arrA.end() && itB != arrB.end()) {
if (*itA != *itB) return false;
itA++;
itB++;
}
return true;
}
Compress array.
{0, 2, 3, 4, 5, 9} => {9, 0, 2, 2, 5, 9}
[2, 2, 5] means [2, 3, 4, 5]. [0, 0, 100] means [0, 1, ..., 100].
If 2n-1 number is stored in not end of array, it is empty space.
Then, you can fill missing number from left to right.
void findMissing(vector<UINT32>& arr) {
int i, j;
UINT32 last, start, prev, count, firstFrom, firstTo, secondFrom, secondTo;
if (arr.size() == 0) return;
if (arr.size() == 1) {
arr[0] = (arr[0] + 1) % 2;
return;
}
sort(arr.begin(), arr.end());
last = arr.size() + arr.size() - 1;
// find continuous sequence
start = last;
prev = last;
count = 0;
for (i = 0; i < arr.size(); i++) {
if (prev + 1 == arr[i]) {
count++;
if (count > 3) {
arr[i - 3] = last;
arr[i - 2] = start;
arr[i - 1] = start;
}
} else {
start = arr[i];
count = 1;
}
prev = arr[i];
}
// move empty element to first
for (i = arr.size() - 2; i > 0; i--) {
if (arr[i] != last) continue;
for (j = i - 1; j >= 0; j--) {
if (arr[j] == last) continue;
arr[i] = arr[j];
arr[j] = last;
break;
}
}
// skip empty space
for (i = 0; i < arr.size(); i++) {
if (arr[i] != last) break;
}
j = 0;
firstFrom = 0;
firstTo = 0;
secondFrom = 0;
secondTo = 0;
while (j < arr.size()) {
// find first empty sequency
firstFrom = secondTo;
firstTo = secondTo;
for (; i < arr.size(); i++) {
if (arr[i] <= firstFrom || (i > 2 && arr[i - 2] == arr[i - 1])) {
firstFrom = arr[i] + 1;
firstTo = last + 1;
} else {
firstTo = arr[i];
break;
}
}
// find second empty sequency
secondFrom = firstTo;
secondTo = firstTo;
for (; i < arr.size(); i++) {
if (arr[i] <= secondFrom || (i > 2 && arr[i - 2] == arr[i - 1])) {
secondFrom = arr[i] + 1;
secondTo = last + 1;
} else {
secondTo = arr[i];
break;
}
}
for (; j < arr.size(); j++) {
if (firstFrom == firstTo) break;
arr[j] = firstFrom;
firstFrom++;
}
for (; j < arr.size(); j++) {
if (secondFrom == secondTo) break;
arr[j] = secondFrom;
secondFrom++;
}
}
}
Split log to 2 nodes, start and end. Start node has positive memory and end node has negative memory. Sort all nodes, and process each nodes.
Example)
100207 100208 2
100305 100307 5
100207 100209 4
split ==>
100207 2
100208 -2
100305 5
100307 -5
100207 4
100209 -4
sort ==>
100207 2
100207 4
100208 -2
100209 -4
100305 5
100307 -5
#include <iostream>
#include <map>
using namespace std;
int findBusyHour(int log[][3], int n) {
multimap<int, int> nodes;
multimap<int, int>::iterator it;
int i, maxHour, maxMemory, hour, memory, released;
i = 0;
while (i < n) {
nodes.insert(make_pair(log[i][0], log[i][2]));
nodes.insert(make_pair(log[i][1], -log[i][2]));
i++;
}
maxHour = -1;
maxMemory = 0;
hour = -1;
memory = 0;
released = 0;
it = nodes.begin();
while (it != nodes.end()) {
if (hour != it->first) {
hour = it->first;
memory += released;
released = 0;
}
if (it->second > 0) {
memory += it->second;
if (memory > maxMemory) {
maxHour = hour;
maxMemory = memory;
}
} else {
released += it->second;
}
it++;
}
return maxHour;
}
int main(int argc, char* argv[]) {
int log[][3] = {
{100207, 100208, 2},
{100305, 100307, 5},
{100207, 100209, 4},
{111515, 121212, 1}
};
cout << findBusyHour(log, 4) << "\n";
return 0;
}
Find 1st popular item and delete it. Repeat i times.
String find(List<Item> items, int i) {
List<Item> copy;
int idx, maxIdx, maxQuantity;
String result;
result = "";
if (i <= 0 || i > items.size()) return result;
copy = new ArrayList<Item>();
copy.addAll(items);
maxIdx = 0;
while (true) {
maxQuantity = -1;
for (idx = 0; idx < copy.size(); idx++) {
if (copy.get(idx).quantitySold > maxQuantity) {
maxIdx = idx;
maxQuantity = copy.get(idx).quantitySold;
}
}
i--;
if (i == 0) {
result = copy.get(maxIdx).itemId;
break;
}
copy.remove(copy.get(maxIdx));
}
return result;
}
C++, Caching
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> primes;
void initPrime(int a) {
int i, j, l;
bool p;
for (i = 2; i <= a; i++) {
l = (int)sqrt((double)i);
p = true;
for (j = 0; j < primes.size(); j++) {
if (l < primes[j]) break;
if (i % primes[j] == 0) {
p = false;
break;
}
}
if (p) primes.push_back(i);
}
}
bool isPrime(int n) {
int i, l;
if (n < 2) return false;
l = (int)sqrt((double)n);
for (i = 0; i < primes.size(); i++) {
if (l < primes[i]) break;
if (n % primes[i] == 0) return false;
}
primes.push_back(n);
return true;
}
int solve(int a, int n) {
initPrime(a);
while (n) {
if (isPrime(++a)) n--;
}
return a;
}
int main(int argc, char* argv[]) {
int a, n;
cin >> a >> n;
cout << solve(a, n) << "\n";
return 0;
}
For each a, number in A
- find bSmall, largest number is less equal a in B
- find bBig, smallest number is greater equal a in B
- find cSmall, largest number is less equal a in C
- find cBig, smallest number is greater equal a in C
- calculate distance and find minimum: {a, bSmall, cSmall}, {a, bSmall, cBig}, {a, bBig, cSmall}, {a, bBig, cBig}
C++, O(n^2)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_INTEGER = 2147483646;
void compareDistance(int& a, int& b, int& c, int& minDistance, int A, int B, int C) {
int t;
t = abs(A - B) + abs(B - C) + abs(C - A);
if (t < minDistance) {
minDistance = t;
a = A;
b = B;
c = C;
}
}
void findMinDistanceInThreeArray(vector<int>& A, vector<int>& B, vector<int>& C) {
int minDistance, t;
int a, b, c;
int i, j, k;
bool foundSmallB, foundEqualB, foundBigB;
bool foundSmallC, foundEqualC, foundBigC;
sort(A.begin(), A.end());
sort(B.begin(), B.end());
sort(C.begin(), C.end());
a = b = c = 0;
minDistance = MAX_INTEGER;
j = 0;
k = 0;
for (i = 0; i < A.size(); i++) {
if (j < 0) j = 0;
if (j < B.size()) {
foundSmallB = false;
foundEqualB = false;
foundBigB = false;
while (j < B.size() - 1 && B[j] < A[i]) j++;
if (B[j] == A[i]) {
foundEqualB = true;
} else {
if (B[j] > A[i] && j - 1 >= 0) j--;
if (B[j] < A[i]) {
foundSmallB = true;
if (j + 1 < B.size() && B[j + 1] > A[i]) foundBigB = true;
} else {
foundBigB = true;
j--;
}
}
}
if (k < 0) k = 0;
if (k < C.size()) {
foundSmallC = false;
foundEqualC = false;
foundBigC = false;
while (k < C.size() - 1 && C[k] < A[i]) k++;
if (C[k] == A[i]) {
foundEqualC = true;
} else {
if (C[k] > A[i] && k - 1 >= 0) k--;
if (C[k] < A[i]) {
foundSmallC = true;
if (k + 1 < C.size() && C[k + 1] > A[i]) foundBigC = true;
} else {
foundBigC = true;
k--;
}
}
}
if (foundEqualB && foundEqualC) {
minDistance = 0;
a = A[i];
b = B[j];
c = C[k];
break;
} else if (foundEqualB) {
if (foundSmallC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k]);
if (foundBigC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k + 1]);
} else if (foundEqualC) {
if (foundSmallB) compareDistance(a, b, c, minDistance, A[i], B[j], C[k]);
if (foundBigB) compareDistance(a, b, c, minDistance, A[i], B[j + 1], C[k]);
} else {
if (foundSmallB) {
if (foundSmallC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k]);
if (foundBigC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k + 1]);
}
if (foundBigB) {
if (foundSmallC) compareDistance(a, b, c, minDistance, A[i], B[j + 1], C[k]);
if (foundBigC) compareDistance(a, b, c, minDistance, A[i], B[j + 1], C[k + 1]);
}
}
}
cout << a << ", " << b << ", " << c << "\n";
}
int main(int argc, char* argv[]) {
vector<int> A, B, C;
A.push_back(1);
A.push_back(5);
A.push_back(100);
B.push_back(1);
B.push_back(45);
B.push_back(75);
C.push_back(1);
C.push_back(100);
C.push_back(200);
findMinDistanceInThreeArray(A, B, C);
return 0;
}
C++, A* algorithm
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int cityBlockDistance(pair<int, int> a, pair<int, int> b) {
int x, y;
x = a.first - b.first;
if (x < 0) x = -x;
y = a.second - b.second;
if (y < 0) y = -y;
return x + y;
}
vector<pair<int, int>> findPathAStar(vector<vector<int>> original, pair<int, int> start, pair<int, int> end) {
vector<vector<int>> matrix;
vector<pair<int, int>> path;
multimap<int, pair<pair<int, int>, vector<pair<int, int>>>> candidate;
multimap<int, pair<pair<int, int>, vector<pair<int, int>>>>::iterator it;
pair<int, int> p;
int x, y, w, h;
matrix = original;
matrix[start.second][start.first] = 0;
path.push_back(start);
candidate.insert(make_pair(cityBlockDistance(start, end), make_pair(start, path)));
h = matrix.size() - 1;
w = matrix[0].size() - 1;
while (candidate.size()) {
it = candidate.begin();
p = it->second.first;
x = p.first;
y = p.second;
if (x == end.first && y == end.second) {
return it->second.second;
}
if (x > 0 && matrix[y][x - 1] == 1) {
p = make_pair(x - 1, y);
matrix[y][x - 1] = 0;
path = it->second.second;
path.push_back(p);
candidate.insert(make_pair(cityBlockDistance(p, end), make_pair(p, path)));
}
if (x < w && matrix[y][x + 1] == 1) {
p = make_pair(x + 1, y);
matrix[y][x + 1] = 0;
path = it->second.second;
path.push_back(p);
candidate.insert(make_pair(cityBlockDistance(p, end), make_pair(p, path)));
}
if (y > 0 && matrix[y - 1][x] == 1) {
p = make_pair(x, y - 1);
matrix[y - 1][x] = 0;
path = it->second.second;
path.push_back(p);
candidate.insert(make_pair(cityBlockDistance(p, end), make_pair(p, path)));
}
if (y < h && matrix[y + 1][x] == 1) {
p = make_pair(x, y + 1);
matrix[y + 1][x] = 0;
path = it->second.second;
path.push_back(p);
candidate.insert(make_pair(cityBlockDistance(p, end), make_pair(p, path)));
}
candidate.erase(it);
}
path.clear();
return path;
}
int main(int argc, char* argv[]) {
int data[10][10] = {
{0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 1, 1, 0, 1, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 1, 1, 1},
{0, 0, 1, 1, 1, 0, 0, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 0, 0, 1, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
vector<pair<int, int>> path;
vector<vector<int>> matrix;
vector<int> row;
int i;
for (i = 0; i < 10; i++) {
row.clear();
row.assign(data[i], data[i] + 10);
matrix.push_back(row);
}
path = findPathAStar(matrix, make_pair(1, 1), make_pair(8, 8));
for (i = 0; i < path.size(); i++) {
cout << path[i].first << ", " << path[i].second << "\n";
}
return 0;
}
C++, O(n)
#include <iostream>
#include <string>
using namespace std;
string removeDupAndSort(string& s) {
int i, f[123] = {0, };
string result;
for (i = 0; i < s.size(); i++) f[ s[i] ] = 1;
for (i = 'a'; i <= 'z'; i++) if (f[i] == 1) result.push_back(i);
return result;
}
int main(int argc, char* argv[]) {
string s = "bcabc";
cout << removeDupAndSort(s) << "\n";
return 0;
}
Brute Force, Recursive, C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Task {
int maxPoint;
int pointsPerMinute;
int requiredTime;
int visit;
Task() {
maxPoint = 0;
pointsPerMinute = 0;
requiredTime = 0;
visit = 0;
}
};
void processInput(int& totalTime, vector<Task>& tasks) {
string buffer;
int taskIndex, i, t;
cin >> totalTime;
cin >> buffer;
i = 0;
t = 0;
while (i <= (int)buffer.size()) {
if (i == buffer.size() || buffer[i] == ',') {
Task task;
task.maxPoint = t;
tasks.push_back(task);
t = 0;
} else {
t = t * 10 + (buffer[i] - '0');
}
i++;
}
cin >> buffer;
taskIndex = 0;
i = 0;
t = 0;
while (i <= (int)buffer.size()) {
if (i == buffer.size() || buffer[i] == ',') {
tasks[taskIndex].pointsPerMinute = t;
taskIndex++;
t = 0;
} else {
t = t * 10 + (buffer[i] - '0');
}
i++;
}
cin >> buffer;
taskIndex = 0;
i = 0;
t = 0;
while (i <= (int)buffer.size()) {
if (i == buffer.size() || buffer[i] == ',') {
tasks[taskIndex].requiredTime = t;
taskIndex++;
t = 0;
} else {
t = t * 10 + (buffer[i] - '0');
}
i++;
}
}
int solve(int totalTime, vector<Task>& tasks, int time) {
int ret, i, point;
if (time >= totalTime) return 0;
ret = 0;
for (i = 0; i < (int)tasks.size(); i++) {
if (tasks[i].visit == 1) continue;
tasks[i].visit = 1;
point = tasks[i].maxPoint - (time + tasks[i].requiredTime) * tasks[i].pointsPerMinute;
ret = max(ret, point + solve(totalTime, tasks, time + tasks[i].requiredTime));
tasks[i].visit = 0;
}
return ret;
}
int main(int argc, char* argv[]) {
vector<Task> tasks;
int totalTime;
processInput(totalTime, tasks);
cout << solve(totalTime, tasks, 0) << "\n";
return 0;
}
I changed test case.
[..., 15, 3, 56, ...] -> [..., 56, 3, 15, ...]
My solution to the problem in JavaScript.
var orderByInput = [];
var orderByValue = [];
var findMaxInWindow = function (windowSize, value) {
var maxInWindow = orderByValue[0] || value;
orderByInput.push(value);
if (maxInWindow > value) {
orderByValue.push(value);
} else {
orderByValue.splice(0, 0, value);
maxInWindow = value;
}
if (orderByInput.length > windowSize) {
var removeIndex = orderByValue.indexOf( orderByInput.shift() );
orderByValue.splice(removeIndex, 1);
if (removeIndex == 0) {
orderByValue.sort(function(a, b){return b - a});
maxInWindow = orderByValue[0];
}
}
return maxInWindow;
}
var main = function ( ){
var windowSize = 3;
var stream = [1, 4, 2, 7, 9, 15, 11, 26, 96, 56, 3, 15, 25];
for (var i = 0 ; i < stream.length; i++) {
console.log (i + " ) " + stream[i] +" - MAX : " + findMaxInWindow(windowSize, stream[i]));
}
}
main();
Result:
0 ) 1 - MAX : 1
1 ) 4 - MAX : 4
2 ) 2 - MAX : 4
3 ) 7 - MAX : 7
4 ) 9 - MAX : 9
5 ) 15 - MAX : 15
6 ) 11 - MAX : 15
7 ) 26 - MAX : 26
8 ) 96 - MAX : 96
9 ) 56 - MAX : 96
10 ) 3 - MAX : 96
11 ) 15 - MAX : 56
12 ) 25 - MAX : 25
My solution to the problem in C++.
#include <iostream>
#include <queue>
#include <set>
using namespace std;
class MaxInWindow {
private:
queue<int> orderByInput;
multiset<int> orderByValue;
public:
int findMaxInWindow(int windowSize, int value) {
orderByInput.push(value);
orderByValue.insert(value);
if (orderByInput.size() > windowSize) {
orderByValue.erase( orderByInput.front() );
orderByInput.pop();
}
return *orderByValue.rbegin();
}
};
int main(int argc, char* argv[]) {
MaxInWindow mw;
int arr[] = {1, 4, 2, 7, 9, 15, 11, 26, 96, 56, 3, 15, 25};
int i;
for (i = 0; i < 13; i++) {
cout << mw.findMaxInWindow(3, arr[i]) << "\n";
}
return 0;
}
Result
1
4
4
7
9
15
15
26
96
96
96
56
25
C++
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int value;
Node* left;
Node* right;
};
bool isFirst = true;
void printNode(Node* node) {
if (node == NULL) return;
cout << "(";
printNode(node->left);
cout << node->value;
printNode(node->right);
cout << ")";
}
Node* createNode(int value) {
Node* node;
node = new Node();
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
void deleteNodeAll(Node* node) {
if (node->left) {
deleteNodeAll(node->left);
delete node->left;
}
if (node->right) {
deleteNodeAll(node->right);
delete node->right;
}
}
void findSumInStack(vector<Node*>& stack, int sum) {
int i, j, l, s;
l = stack.size() - 1;
s = 0;
for (i = l; i >= 0; i--) {
s += stack[i]->value;
if (s == sum) {
if (isFirst == false) {
cout << ", {";
} else {
isFirst = false;
cout << "{";
}
for (j = i; j < l; j++) {
cout << stack[j]->value << ", ";
}
cout << stack[l]->value;
cout << "}";
}
}
}
void searchBTreeSum(Node* node, vector<Node*>& stack, int sum) {
if (node == NULL) return;
stack.push_back(node);
findSumInStack(stack, sum);
searchBTreeSum(node->left, stack, sum);
searchBTreeSum(node->right, stack, sum);
stack.pop_back();
}
int main(int argc, char* argv) {
Node* root;
vector<Node*> stack;
root = createNode(2);
root->left = createNode(3);
root->right = createNode(5);
root->left->left = createNode(4);
root->left->right = createNode(8);
root->right->left = createNode(6);
root->right->right = createNode(-2);
root->right->right->right = createNode(2);
printNode(root);
cout << "\n";
searchBTreeSum(root, stack, 7);
cout << "\n";
deleteNodeAll(root);
delete root;
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
struct Node {
char name;
Node* left;
Node* right;
Node* next;
};
void fillNext(Node* node, vector<Node*>& depthNodes, int depth) {
Node* prev;
if (node == NULL) return;
if (depthNodes.size() > depth) {
prev = depthNodes[depth];
if (prev) {
prev->next = node;
cout << prev->name << " - " << node->name << "\n";
}
depthNodes[depth] = node;
} else {
depthNodes.push_back(node);
}
fillNext(node->left, depthNodes, depth + 1);
fillNext(node->right, depthNodes, depth + 1);
}
int main(int argc, char* argv[]) {
Node A, B, C, D, F, G, H, I;
vector<Node*> depthNodes;
A.name = 'A';
A.left = &B;
A.right = &C;
A.next = NULL;
B.name = 'B';
B.left = &D;
B.right = NULL;
B.next = NULL;
C.name = 'C';
C.left = &F;
C.right = &G;
C.next = NULL;
D.name = 'D';
D.left = &H;
D.right = &I;
D.next = NULL;
F.name = 'F';
F.left = NULL;
F.right = NULL;
F.next = NULL;
G.name = 'G';
G.left = NULL;
G.right = NULL;
G.next = NULL;
H.name = 'H';
H.left = NULL;
H.right = NULL;
H.next = NULL;
I.name = 'I';
I.left = NULL;
I.right = NULL;
I.next = NULL;
depthNodes.clear();
fillNext(&A, depthNodes, 0);
depthNodes.clear();
return 0;
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void textPermutation(vector<int>& visited, string& str, string& working) {
if (str.size() == working.size()) {
cout << working << "\n";
}
for (int i = 0; i < str.size(); i++) {
if (visited[i] == 0) {
visited[i] = 1;
working.push_back(str[i]);
textPermutation(visited, str, working);
working.erase(working.size() - 1, 1);
visited[i] = 0;
}
}
}
int main()
{
string str, working;
vector<int> visited;
working = "";
str = "tree";
for (int i = 0; i < str.size(); i++) {
visited.push_back(0);
}
textPermutation(visited, str, working);
return 0;
}
c++, brute force, O(n^2)
- kyduke October 29, 2015