Deo
BAN USERcould sort them by the stock prices preserving the original index, the number of the span will be the new index minus the number of pairs which the previous element's original index is higher than the current one.e.g:
input:{2,4,6,9,5,7,1};
internal sorted result {1,2,4,5,6,7,9} with index{6,0,1,4,2,5,3}
output:{-1,1,2,3,2,3,-1}
expected time complexity o(nlogn) + o(n)
space complexity o(n)
#include <algorithm>
#include <utility>
#include <iostream>
vector<int>& calculateSpan(const vector<int>& stock_prices) {
// result of the span calculation
vector<int> *span = new vector<int>(stock_prices.size(), -1);
if (span->size() > 1) {
// sorted the stock prices, preserving the original index
vector<pair<int, int> > sorted_prices;
for (int i = 0; i < stock_prices.size(); ++i) {
sorted_prices.push_back(make_pair(stock_prices[i], i));
}
sort(sorted_prices.begin(), sorted_prices.end());
// whenever we find a value with its index lower than the previous one, we
// increase the count
int higher_index_count = 0;
for (int i = 1; i < sorted_prices.size(); ++i) {
if (sorted_prices[i].second < sorted_prices[i - 1].second) {
++higher_index_count;
}
// the span is calcuated by the index minus the higher index count
const int number_of_span = i - higher_index_count;
(*span)[sorted_prices[i].second] = number_of_span == 0? -1: number_of_span;
}
}
return *span;
}
if two people are known by every other of the group, they must know each other.
use an int array of n, where n is the number of people in the party, (0 for a, 1 for b, etc), whenever a person is known, +1 for it, then finally find out the index with number n-1.
e.g for the above situation:
[4,4,4,0,0]
so the answer is 0,1,2, which is a,b,c
trying to shrink the map from the edge to find the rectangle, ideally this won't need to visit all the nodes, worst case if there's only one black in the middle, will need to visit extra 1.5row.
#include <iostream>
#include <vector>
void findMinRectangle(const vector<vector<int> > &map) {
const int num_row = map.size();
const int num_column = map[0].size();
int row_min = 0;
int column_min = 0;
int row_max = num_row - 1;
int column_max = num_column - 1;
// Finds the top.
bool find_black = false;
for (; row_min < num_row; ++row_min) {
for (const auto &c: map[row_min]) {
if (c == 1) {
find_black = true;
break;
}
}
if (find_black) break;
}
if (!find_black) {
// There is no black point in the map.
cout << "No black in the map." << endl;
return;
}
// Finds the left.
find_black = false;
for (; column_min < num_column; ++column_min) {
for (int r = row_min; r < num_row; ++r) {
if (map[r][column_min] == 1) {
find_black = true;
break;
}
}
if (find_black) break;
}
// Finds the bottom.
find_black = false;
for (; row_max > row_min; --row_max) {
for (int c = column_min; c < num_column; ++c) {
if (map[row_max][c] == 1) {
find_black = true;
break;
}
}
if (find_black) break;
}
// Finds the right.
find_black = false;
for (; column_max > column_min; --column_max) {
for (int r = row_min; r <= row_max; ++r) {
if (map[r][column_max] == 1) {
find_black = true;
break;
}
}
if (find_black) break;
}
cout <<
"(" << row_min << "," << column_min << ") - (" <<
row_max << "," << column_max << ")" << endl;
}
time (n), space o(1)
#include <string>
bool hasPattern(const string &input, const string &pattern) {
if (input.empty() || pattern.empty() || pattern.size() > input.size()) {
// error cases
return false;
}
// Uses counting on the alphabet to track anagram.
char pattern_count[26] = {0};
for (auto &c : pattern) {
++pattern_count[c - 'a'];
}
// Uses slide window of pattern size to compare whether it could be an anagram
char input_count[26] = {0};
// When extra_count equals to zero after initialization, it means it's an
// anagram.
int extra_count = 0;
for (int i = 0; i < pattern.size(); ++i) {
int index = input[i] - 'a';
++input_count[index];
if (input_count[index] > pattern_count[index]) {
++extra_count;
}
}
int i = 0;
// Moves the slide window.
while (extra_count > 0 && i < input.size() - pattern.size()) {
int index = input[i] - 'a';
if (input_count[index] > pattern_count[index]) {
--extra_count;
}
--input_count[index];
index = input[i + pattern.size()] - 'a';
++input_count[index];
if (input_count[index] > pattern_count[index]) {
++extra_count;
}
++i;
}
return extra_count == 0;
}
use a stack to track the folder names sequence.
#include <string>
#include <vector>
bool pushFolderName(const string &path, const int start,
const int length, vector<string> &path_buffer) {
string folder_name = path.substr(start, length);
if (folder_name == "..") {
// Pops a folder name from the stack, if stack is empty, return "".
if (path_buffer.empty()) return false;
path_buffer.pop_back();
} else if (folder_name != ".") {
path_buffer.push_back(folder_name);
}
return true;
};
bool getFolderNames(
const string &path, vector<string> &path_buffer) {
int start = 0;
int end = 0;
// Loops the input absolute path and push the folder names into stack.
while (true) {
end = path.find_first_of('/', end);
if (end == string::npos) break;
if (end > start + 1 &&
!pushFolderName(path, start, end - start, path_buffer)) {
return false;
}
++end;
start = end;
}
// The last folder name in absolute path may not contain '/'.
if (path.back() != '/' &&
!pushFolderName(path, start, end - start, path_buffer)) {
return false;
}
return true;
};
string &getAbsolutePath(
const string &absolute, const string &relative) {
// a stack to store the new absolute path's folder names.
vector<string> path_buffer;
// the return absolute path, default to empty.
string *path = new string();
if (!getFolderNames(absolute, path_buffer)) return *path;
if (!getFolderNames(relative, path_buffer)) return *path;
// Joins the new absolute path.
for (auto &folder_name : path_buffer) {
path->append("/");
path->append(folder_name);
}
return *path;
}
time o(n) space o(n), get all the guard nodes to a min-heap and expand them to adjacent nodes, keep adding them to the min-heap if reachable. assuming obstacle is -2, guard is -1 for easy processing.
struct Node {
int x;
int y;
int distance;
Node(int x_i, int y_i, int distance_i) {
x = x_i;
y = y_i;
distance = distance_i;
}
bool operator>(const Node &node) const {
return distance > node.distance;
}
};
void markDistance(vector<vector<int> >& map) {
priority_queue<Node, vector<Node>, greater<Node> > min_heap;
const int x_max = map.size() - 1;
const int y_max = map[0].size() - 1;
// get the guard nodes.
for (int x = 0; x < map.size(); ++x) {
for (int y = 0; y < map[x].size(); ++y) {
if (map[x][y] == -1) {
min_heap.emplace(x, y, 0);
}
}
}
while (!min_heap.empty()) {
auto node = min_heap.top();
min_heap.pop();
for (int x = -1; x <= 1; ++x) {
for (int y = -1; y <= 1; ++y) {
// only visit the up/down/left/right node.
if ((x == 0 && y == 0) || (x != 0 && y != 0)) continue;
// get real (x, y) on the map
int x_map = node.x + x;
int y_map = node.y + y;
// skip the node out of boundary or it's obstacle and guard
if (x_map < 0 || y_map < 0 || x_map > x_max || y_map > y_max ||
map[x_map][y_map] < 0) continue;
// update the node if we have a shorter path to it or it's not visited.
if (map[x_map][y_map] == 0 || node.distance + 1 < map[x_map][y_map]) {
map[x_map][y_map] = node.distance + 1;
min_heap.emplace(x_map, y_map, map[x_map][y_map]);
}
}
}
}
}
assuming the maximum we can get is '123456789', so it's invalid for input bigger than '123456788'
then we plus the input by 1, so we can check our generated result by greater or equal function.
first we generate the biggest valid number we could have for the length of input, e.g 899 as input, the biggest is 789
if it's smaller than input+1, simply return 1234, as we know it's the smallest valid result.
if for input 688, the maximum 789 is bigger than it, so we scrimp it from the highest bit.
time complexity is (n^2) which n is the length of input string, space complexity is n.
#include <vector>
template<typename T>
bool _ge(const T &str_1, const string &str_2) {
if (str_1.size() > str_2.size()) return true;
if (str_1.size() < str_2.size()) return false;
if (str_1.size() == str_2.size()) {
for (int i = 0; i < str_1.size(); ++i) {
if (str_1[i] < str_2[i]) return false;
if (str_1[i] > str_2[i]) return true;
}
}
return true;
}
string* nextInteger(const string& input_0) {
// valid input should not greater than 123456788
if (!_ge(string("123456788"), input_0)) return NULL;
// plus the input by one
string input(input_0);
for (int i = input.size() - 1; i >= 0; --i) {
if (input[i] == '9') {
input[i] = '0';
if (i == 0) {
input = "1" + input;
}
} else {
input[i] += 1;
break;
}
}
vector<char> buffer;
// construct a string of the maximum for the same length.
for (int i = input.size() - 1; i >= 0; --i) {
buffer.push_back('9' - i);
}
// the next greater one needs extra significant bit.
if (!_ge(buffer, input)) {
string *next = new string(input.size() + 1, '0');
for (int i = 0; i <= input.size(); ++i) {
(*next)[i] += i + 1;
}
return next;
}
// the next greater one doesn't need extra significant bit.
char prev = input[0];
int i = 0;
for (; i < input.size(); ++i) {
// choose the bigger one, the previous bit + 1 or the input bit.
buffer[i] = prev > input[i]? prev: input[i];
if (!_ge(buffer, input)) {
// if we found the current number is lower than the input one, increase
// current bit by 1
buffer[i] += 1;
++i;
break;
}
prev = buffer[i] + 1;
}
for (; i < input.size(); ++i) {
// since previous bit has been increased by 1, the smaller one for the rest
// bits will just increase 1 each.
buffer[i] = buffer[i - 1] + 1;
}
string *next = new string(buffer.size(), '0');
for (int i = 0; i < buffer.size(); ++i) (*next)[i] = buffer[i];
return next;
}
void insertNode(Node* &head, Node *node) {
// empty list
if (!head) {
head = node;
node->next = node;
return;
}
// insert before head
if (node->value <= head->value) {
Node *tail = head;
while (tail->next != head) tail = tail->next;
tail->next = node;
node->next = head;
head = node;
} else {
Node* it = head;
while (it->next != head) {
if (node->value > it->next->value) {
it = it->next;
continue;
}
// insert in the middle.
node->next = it->next;
it->next = node;
return;
}
// insert tail.
node->next = head;
it->next = node;
}
}
n^2 in time and n in space
// Increases the value at a position and move the tens to previous bit if
// necessary.
void increase(list<int>::iterator it, int value) {
*it += value;
while (*it > 9) {
// Adds up the previous bit if current one is bigger than 9.
value = *it / 10;
*it %= 10;
// TODO: this may be out of range if not handled by outer method correctly.
--it;
*it += value;
}
}
forward_list<int>* multiply(
const forward_list<int> &fl_a, const forward_list<int> &fl_b) {
if (fl_a.empty() || fl_b.empty()) {
// Checks that both of the input are not empty.
return NULL;
}
// Uses a doubly linked list to store the multiplied result.
list<int> result;
// There may be one extra MSB at the beginning, add it to avoid out of index.
result.push_back(0);
auto main_it = result.begin();
bool first_iteration = true;
for (auto &b : fl_b) {
result.push_back(0);
++main_it;
auto current_it = main_it;
for (auto &a : fl_a) {
increase(current_it, a * b);
if (first_iteration) result.push_back(0);
++current_it;
}
if (first_iteration) {
first_iteration = false;
result.pop_back();
}
}
// Removes the leading 0s.
forward_list<int>* return_result = new forward_list<int>;
auto it = result.begin();
//while (*it == 0 && it != result.end()) ++it;
if (it == result.end()) {
// the result is zero.
return_result->assign(1, 0);
} else {
return_result->insert_after(
return_result->before_begin(), it, result.end());
}
return return_result;
need to check if they are adjacent and the number of each letter.
- Deo April 04, 2014