Alex
BAN USER@Rob. That's correct. Using a bidirectional BFS it's easy to find the subgraph that contains the shortest path. But what if the subgraph still contains millions of links. Yes, there are only 3 hops, but each node can have 1 million weighted edges. It would be 1,000,000 ^ 3 paths to scan.
- Alex November 27, 2017I assume repeating characters may be different. E.g.
"abcdc" - 1 repeating char.
"abcdcb" - 2 repeating chars, no matter the repeating chars a different.
"abcdcbb" - 3 repeating chars.
#include <iostream>
#include <unordered_map>
using namespace std;
pair<int, int> LongestSubstring(string const &s, int k)
{
pair<int, int> out(-1, -1);
if (k >= s.size()) {
if (!s.empty()) {
out = pair<int, int>(0, s.size() - 1);
}
return out;
}
if (k > 0) {
int start = 0;
int max_size = 0;
unordered_map<char, int> seen;
int repeted_chars_count = 0;
for (int i = 0; i < s.size(); ++i) {
if (++seen[s[i]] > 1) {
++repeted_chars_count;
while (repeted_chars_count > k) {
if (--seen[s[start++]] != 0) {
--repeted_chars_count;
}
}
}
int size = i - start + 1;
if (size > max_size) {
max_size = size;
out = pair<int, int>(start, i);
}
}
}
return out;
}
int main() {
auto out = LongestSubstring("alblabljln", 2);
cout << out.first << " - " << out.second << "\n";
}
For k <= 64, we can have O(n) time solution (the code below).
Followup 2 sounds like "find the shortest string that contains all of the given words". We can start with a string containing k zeros, and for each next number string, if the cumulative string doesn't contain it, we try to merge it in all possible ways, and go to the next number recursively for each of the branches.
bool ContainsAllBinaryStrings(string const &s, int k)
{
if (k > 0 &&
k <= sizeof(uint64_t) * 8)
{
unordered_set<uint64_t> seen;
uint64_t val = 0;
int size = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i - k] == '0' ||
s[i - k] == '1')
{
if (i >= k) {
val -= (s[i - k] - '0') << (k - 1);
--size;
}
}
val <<= 1;
if (s[i] == '0' ||
s[i] == '1')
{
val += s[i] - '0';
++size;
}
if (size == k) {
seen.insert(val);
if (seen.size() == (1 << k)) {
return true;
}
}
}
}
return false;
}
If the input doesn't contain duplicates, O(log n) time, O(1) space.
If the input contains a lot of duplicates, O(n) time, O(log n) space.
#include <iostream>
#include <vector>
using namespace std;
int Peak(vector<int> const &a, int start, int end)
{
int l = start + 1;
int r = end - 1;
while (l <= end &&
l - 1 >= start &&
r >= start &&
r + 1 <= end &&
l <= r)
{
int i = (l + r) / 2;
if (a[i - 1] < a[i] &&
a[i + 1] < a[i])
{
return i;
} else if ((a[i - 1] <= a[i] && a[i + 1] > a[i]) ||
(a[i - 1] < a[i] && a[i + 1] >= a[i]))
{
l = i + 1;
} else if ((a[i - 1] >= a[i] && a[i + 1] < a[i]) ||
(a[i - 1] > a[i] && a[i + 1] <= a[i]))
{
r = i - 1;
} else {
int left = Peak(a, l, i - 1);
if (left != -1) {
return left;
}
return Peak(a, i + 1, r);
}
}
return -1;
}
int main() {
vector<int> in = {1, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1};
cout << Peak(in, 0, in.size() - 1) << "\n";
}
We can use a trie. O(N^2) time and space.
#include <iostream>
#include <unordered_map>
using namespace std;
class Node {
public:
Node(char c, Node *parent)
{
c_ = c;
parent_ = parent;
}
Node()
{
c_ = 0;
parent_ = NULL;
}
Node *GetChild(char c) const
{
auto it = children_.find(c);
return (it == children_.end()) ? NULL : it->second;
}
Node *AddChild(char c)
{
Node *n = GetChild(c);
if (!n) {
n = new Node(c, this);
children_[c] = n;
}
return n;
}
char GetCharacter() const
{
return c_;
}
Node *GetParent() const
{
return parent_;
}
private:
char c_;
unordered_map<char, Node*> children_;
Node *parent_;
};
class Trie {
public:
Node *GetRoot()
{
return &root_;
}
private:
Node root_;
};
string LargestRepeatingSubstring(string const &s)
{
Trie trie;
int max_size = 0;
Node *terminal_node = NULL;
for (int i = 0; i < s.size(); ++i) {
Node *n = trie.GetRoot();
int size = 0;
int substring_broken = false;
for (int j = i; j < s.size(); ++j) {
Node *next_node = n->GetChild(s[j]);
if (next_node) {
if (!substring_broken &&
++size > max_size)
{
max_size = size;
terminal_node = next_node;
}
} else {
substring_broken = true;
next_node = n->AddChild(s[j]);
}
n = next_node;
}
}
string out;
for (Node *n = terminal_node; n != NULL; n = n->GetParent()) {
out += n->GetCharacter();
}
reverse(out.begin(), out.end());
return out;
}
int main() {
cout << LargestRepeatingSubstring("banana") << "\n";
}
void Serialize(Node const *n, vector<int> &out)
{
if (n == NULL) {
out.push_back(numeric_limits<int>::min());
return;
}
out.push_back(n->val_);
Serialize(n->left_, out);
Serialize(n->right_, out);
}
Node *Deserialize(vector<int> const &in, int &idx)
{
if (idx >= in.size() ||
in[idx] == numeric_limits<int>::min())
{
++idx;
return NULL;
}
Node *n = new Node(in[idx++]);
n->left_ = Deserialize(in, idx);
n->right_ = Deserialize(in, idx);
return n;
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Tracker {
public:
Tracker(int k)
{
k_ = k;
}
void AddNumber(int n)
{
if (pq_.size() >= k_ &&
n > pq_.top())
{
pq_.pop();
}
if (pq_.size() < k_) {
pq_.push(n);
}
}
vector<int> GetMaxNumbers()
{
vector<int> out;
while (!pq_.empty()) {
out.push_back(pq_.top());
pq_.pop();
}
for (int n : out) {
pq_.push(n);
}
reverse(out.begin(), out.end());
return out;
}
private:
int k_;
priority_queue<int, vector<int>, greater<int>> pq_;
};
int main(int argc, char const **argv)
{
vector<int> in = {4, 5, 2, 1, 7, 3, 6, 20, 0, -5, 1, 100};
Tracker tr(3);
for (int n : in) {
tr.AddNumber(n);
auto max_numbers = tr.GetMaxNumbers();
for (int m : max_numbers) {
cout << m << ", ";
}
cout << "\n";
}
}
We can build a Binary Search Tree, keeping mapping of idx_in_orig_array => node_in_bst.
Then, we iterate through the array. We remove the BST node of the i-th element in the array. We do a search in the BST to find the value which is next higher of the value of the i-th element. We replace the i-th element with the next higher value, if any. Then, we do the same for the next element.
Worst case time is O(N^2), because the BST can degrade into a list, and searching for the next higher value would be O(N). But expected time would be something like O(N log N).
void Update(Node *head)
{
int size = 0;
for (Node *n = head; n != NULL; n = n->next_) {
++size;
}
int half = size / 2;
stack<int> st;
int i = 0;
for (Node *n = head; n != NULL; n = n->next_, ++i) {
if (size % 2 == 1 ? i <= half : i < half) {
st.push(n->val_);
}
if (i >= half) {
n->val_ += st.top();
st.pop();
}
}
}
Fixed to actually O(n) (I accidentally posted O(n^2) as Anonymous).
#include <vector>
#include <iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
}
void Connect(Node *to_node)
{
for (auto n : adjacent_nodes_) {
if (n == to_node) {
return;
}
}
adjacent_nodes_.push_back(to_node);
to_node->Connect(this);
}
int val_;
vector<Node *> adjacent_nodes_;
};
void DistributeSum(Node *node)
{
if (node) {
int sum = node->val_;
for (auto to_node : node->adjacent_nodes_) {
sum += to_node->val_;
}
node->val_ = sum;
for (auto to_node : node->adjacent_nodes_) {
to_node->val_ = sum;
}
}
}
int main(int argc, char const **argv)
{
Node n1(1), n2(2), n3(3), n4(4), n5(5);
n1.Connect(&n2);
n1.Connect(&n3);
n1.Connect(&n4);
n1.Connect(&n5);
n2.Connect(&n3);
n2.Connect(&n4);
n2.Connect(&n5);
n3.Connect(&n4);
n3.Connect(&n5);
n4.Connect(&n5);
DistributeSum(&n5);
cout << n1.val_ << ", ";
for (auto to_node : n1.adjacent_nodes_) {
cout << to_node->val_ << ", ";
}
cout << "\n";
return 0;
}
BFS (bidirectional BFS for efficiency) should work.
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
class Cell {
public:
Cell(int r, int c)
{
r_ = r;
c_ = c;
}
bool operator==(Cell const &other) const
{
return r_ == other.r_ &&
c_ == other.c_;
}
bool Valid() const
{
return r_ >= 0 &&
c_ >= 0 &&
r_ < 8 &&
c_ < 8;
}
int r_, c_;
};
int MinMovesCount(Cell source, Cell target)
{
vector<vector<bool>> m = vector<vector<bool>>(8, vector<bool>(8, false));
vector<pair<int, int>> moves = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
queue<Cell> q1, q2;
queue<Cell> *parents = &q1;
queue<Cell> *children = &q2;
parents->push(source);
int moves_count = 0;
while(!parents->empty()) {
while(!parents->empty()) {
Cell c = parents->front();
parents->pop();
if (c.Valid() &&
!m[c.r_][c.c_])
{
m[c.r_][c.c_] = true;
if (c == target) {
return moves_count;
}
for (auto move : moves) {
children->push(Cell(c.r_ + move.first, c.c_ + move.second));
}
}
}
swap(parents, children);
++moves_count;
}
return -1;
}
int main()
{
for (int r = 0; r < 8; ++r) {
for (int c = 0; c < 8; ++c) {
for (int r2 = 0; r2 < 8; ++r2) {
for (int c2 = 0; c2 < 8; ++c2) {
cout << r << ", " << c << ", " << r2 << ", " << c2 << ", " << MinMovesCount(Cell(r, c), Cell(r2, c2)) << "\n";
}
}
}
}
return 0;
}
I assume it can be any parent - child pair. I.e. for every node we find max diff (in value) with all of the nodes forming the subtree of the node.
My idea is to find the min and max values of the node's children. Max diff should be produced by either min or max of the children and the node's value.
#include <iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};
pair<int, int> MaxDiff(Node *n, int &max_diff)
{
if (!n) {
return pair<int, int>(numeric_limits<int>::max(), numeric_limits<int>::min());
}
auto min_max_l = MaxDiff(n->left_, max_diff);
auto min_max_r = MaxDiff(n->right_, max_diff);
int children_min = min(min_max_l.first, min_max_r.first);
int children_max = max(min_max_l.second, min_max_r.second);
if (children_min != numeric_limits<int>::max()) {
max_diff = max(max_diff, abs(n->val_ - children_min));
}
if (children_max != numeric_limits<int>::min()) {
max_diff = max(max_diff, abs(n->val_ - children_max));
}
return pair<int, int>(min(n->val_, children_min), max(n->val_, children_max));
}
int main()
{
/*
(1)
/ \
(2) (5)
/\ /\
(3)(4) (6)(7)
\
(8)
*/
Node n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7), n8(8);
n1.left_ = &n2;
n1.right_ = &n5;
n2.left_ = &n3;
n2.right_ = &n4;
n5.left_ = &n6;
n5.right_ = &n7;
n6.right_ = &n8;
int max_diff = 0;
MaxDiff(&n1, max_diff);
cout << max_diff << "\n";
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};
pair<vector<Node *> *, vector<Node *> *> Path(Node *n, Node *n1, Node *n2, vector<Node *> &path)
{
if (!n ||
!n1 ||
!n2 ||
n1 == n2 ||
!path.empty())
{
return pair<vector<Node *> *, vector<Node *> *>(NULL, NULL);
}
vector<Node *> *p1 = NULL;
vector<Node *> *p2 = NULL;
if (n == n1) {
p1 = new vector<Node *>();
}
if (n == n2) {
p2 = new vector<Node *>();
}
if (!p1 ||
!p2)
{
auto l = Path(n->left_, n1, n2, path);
if (l.first) {
p1 = l.first;
}
if (l.second) {
p2 = l.second;
}
}
if (!p1 ||
!p2)
{
auto r = Path(n->right_, n1, n2, path);
if (r.first) {
p1 = r.first;
}
if (r.second) {
p2 = r.second;
}
}
if (path.empty()) {
if (p1) {
p1->push_back(n);
}
if (p2) {
p2->push_back(n);
}
if (p1 &&
p2)
{
path = *p1;
for (int i = p2->size() - 2; i >= 0; --i) {
path.push_back((*p2)[i]);
}
}
}
return pair<vector<Node *> *, vector<Node *> *>(p1, p2);
}
int TurnsCount(vector<Node *> const &path)
{
int count = 0;
int prev_dir = 0;
for (int i = 0; i + 1 < path.size(); ++i) {
Node *n = path[i];
Node *parent = path[i + 1];
if (n->left_ == parent ||
n->right_ == parent)
{
swap(n, parent);
}
int dir = parent->left_ == n ? 1 : 2;
if (prev_dir != 0 &&
prev_dir != dir)
{
++count;
}
prev_dir = dir;
}
return count;
}
int main()
{
/*
(1)
/ \
(2) (5)
/\ /\
(3)(4) (6)(7)
\
(8)
*/
Node n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7), n8(8);
n1.left_ = &n2;
n1.right_ = &n5;
n2.left_ = &n3;
n2.right_ = &n4;
n5.left_ = &n6;
n5.right_ = &n7;
n6.right_ = &n8;
vector<Node *> path;
Path(&n1, &n3, &n8, path);
cout << TurnsCount(path) << "\n";
for (auto n : path) {
cout << n->val_ << "->";
}
cout << "\n";
return 0;
}
I assume '?' means "any one character".
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
class TrieNode {
public:
TrieNode()
{
terminal_ = false;
}
~TrieNode()
{
for (auto &child : children_) {
delete child.second;
}
}
TrieNode *AddChild(char ch)
{
TrieNode *child = children_[ch];
if (!child) {
child = new TrieNode();
children_[ch] = child;
}
return child;
}
TrieNode const *Child(char ch) const
{
auto it = children_.find(ch);
return it != children_.end() ? it->second : NULL;
}
unordered_map<char, TrieNode *> const &Children() const
{
return children_;
}
void Terminal(bool terminal)
{
terminal_ = terminal;
}
bool Terminal() const
{
return terminal_;
}
private:
unordered_map<char, TrieNode *> children_;
bool terminal_;
};
class Trie {
public:
void Add(string const &s)
{
TrieNode *n = &root_;
for (auto const &c : s) {
n = n->AddChild(c);
}
n->Terminal(true);
}
TrieNode *Root()
{
return &root_;
}
private:
TrieNode root_;
};
void Search(TrieNode const *n, string const &pattern, vector<string> &out, string word = "", int idx = 0)
{
if (idx < 0 ||
idx > pattern.size() ||
!n)
{
return;
}
if (idx == pattern.size()) {
if (n->Terminal()) {
out.push_back(word);
}
return;
}
if (pattern[idx] == '?') {
for (auto &el : n->Children()) {
char ch = el.first;
TrieNode const *child_node = el.second;
Search(child_node, pattern, out, word + ch, idx + 1);
}
} else {
Search(n->Child(pattern[idx]), pattern, out, word + pattern[idx], idx + 1);
}
}
int main(int argc, char const **argv)
{
vector<string> const dict = {"cat", "rat", "mat", "apple", "boy", "bat"};
Trie trie;
for (string const &word : dict) {
trie.Add(word);
}
vector<string> out;
Search(trie.Root(), "?at", out);
for (auto &s : out) {
cout << s << "\n";
}
return 0;
}
O(log n) time for the update and range sum queries, using Binary Indexed Tree.
#include <vector>
#include <iostream>
using namespace std;
class BinaryIndexedTree {
public:
BinaryIndexedTree(int size)
{
a_.resize(size + 1, 0);
}
void Update(int idx, int diff)
{
for (int i = idx + 1; i < a_.size(); i += i & -i) {
a_[i] += diff;
}
}
int GetSum(int idx) const
{
int sum = 0;
for (int i = idx + 1; i > 0; i -= i & -i) {
sum += a_[i];
}
return sum;
}
private:
vector<int> a_;
};
class SumTracker {
public:
SumTracker(int size) : tree_(size)
{
a_.resize(size, 0);
}
void Update(int idx, int val)
{
int diff = val - a_[idx];
a_[idx] = val;
tree_.Update(idx, diff);
}
int RangeSum(int idx1, int idx2) {
return tree_.GetSum(idx2) - tree_.GetSum(idx1 - 1);
}
int Size() const
{
return a_.size();
}
private:
vector<int> a_;
BinaryIndexedTree tree_;
};
int main(int argc, char const **argv)
{
SumTracker t(10);
for (int i = 0; i < t.Size(); ++i) {
t.Update(i, i + 1);
}
cout << t.RangeSum(3, 5) << "\n";
return 0;
}
pair<int, int> SortPatch(vector<int> const &a)
{
if (a.empty()) {
return pair<int, int>(-1, -1);
}
vector<int> min_to_right, max_to_left;
min_to_right.resize(a.size());
max_to_left.resize(a.size());
int max_val = numeric_limits<int>::min();
for (int i = 0; i < a.size(); ++i) {
max_val = max(max_val, a[i]);
max_to_left[i] = max_val;
}
int min_val = numeric_limits<int>::max();
for (int i = a.size() - 1; i >= 0; --i) {
min_val = min(min_val, a[i]);
min_to_right[i] = min_val;
}
int i = 0;
for (; i < a.size(); ++i) {
if (a[i] > min_to_right[i]) {
break;
}
}
int j = a.size() - 1;
for (; j >= 0; --j) {
if (a[j] < max_to_left[j]) {
break;
}
}
if (i >= j) {
return pair<int, int>(0, 0);
}
return pair<int, int>(i, j);
}
I assume it's a singly linked list, and the head place has greater value than the tail place.
Looks like the requirement of O(1) space doesn't leave a lot of choice.
#include <iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
next_ = NULL;
}
int val_;
Node *next_;
};
Node *AddDigit(Node *head, int digit)
{
int size = 0;
for (Node *n = head; n != NULL; n = n->next_) {
++size;
}
int carry = digit;
for (int i = size; i > 0 && carry != 0; --i) {
Node *n = head;
for (int j = 0; j < i - 1; ++j) {
n = n->next_;
}
int sum = n->val_ + carry;
n->val_ = sum % 10;
carry = sum >= 10 ? 1 : 0;
}
if (carry != 0) {
Node *new_head = new Node(carry);
new_head->next_ = head;
head = new_head;
}
return head;
}
void Print(Node *head)
{
for (Node *n = head; n != NULL; n = n->next_) {
cout << n->val_ << ", ";
}
cout << "\n";
}
int main()
{
Node *head = NULL;
for (int i = 0; i < 100; ++i) {
head = AddDigit(head, 1);
Print(head);
}
return 0;
}
O(log n * log n) time, O(1) space, where n is size of the text to split.
#include <iostream>
#include <string>
using namespace std;
int SuffixesSize(int n)
{
int size = n * (3 + to_string(n).size());
int top = 9;
while (n > 0) {
size += n;
n -= top;
top *= 10;
}
return size;
}
int Cut(int text_size, int k)
{
int l = 1;
int r = text_size;
int best_blockes_count = -1;
int best_delta = numeric_limits<int>::max();
while (l <= r) {
int blocks_count = (l + r) / 2;
int split_text_size = SuffixesSize(blocks_count) + text_size;
if (split_text_size > (blocks_count - 1) * k &&
split_text_size <= blocks_count * k)
{
int delta = blocks_count * k - split_text_size;
if (delta < best_delta) {
best_blockes_count = blocks_count;
}
}
if (split_text_size > blocks_count * k) {
l = blocks_count + 1;
} else {
r = blocks_count - 1;
}
}
return best_blockes_count;
}
int main()
{
cout << Cut(18, 10) << "\n"; // 4
cout << Cut(13, 8) << "\n"; // 5
cout << Cut(31, 9) << "\n"; // 8
cout << Cut(31, 8) << "\n"; // 22
cout << Cut(31, 7) << "\n"; // -1
}
#include <iostream>
#include <string>
using namespace std;
string Add(string s1, string s2, int place)
{
if (s2 != "0") {
while (place-- > 0) {
s2 += '0';
}
}
string out;
int i = s1.size() - 1;
int j = s2.size() - 1;
int carry = 0;
while (i >= 0 ||
j >= 0 ||
carry != 0)
{
int summand1 = (i >= 0) ? s1[i--] - '0' : 0;
int summand2 = (j >= 0) ? s2[j--] - '0' : 0;
int sum = summand1 + summand2 + carry;
out += (sum % 10) + '0';
carry = sum >= 10 ? 1 : 0;
}
reverse(out.begin(), out.end());
return out;
}
string MultiplyByDigit(string s, char digit)
{
string out;
int digit_val = digit - '0';
for (int i = s.size() - 1; i >= 0; --i) {
out = Add(out, to_string((s[i] - '0') * digit_val), s.size() - 1 - i);
}
return out;
}
string Multiply(string const &s1, string const &s2)
{
string out;
for (int i = s2.size() - 1; i >= 0; --i) {
out = Add(out, MultiplyByDigit(s1, s2[i]), s2.size() - 1 - i);
}
return out;
}
int main()
{
cout << Multiply("240834975028740983740298740325723952835357021759874592475924875290475293573295", "7047851704578497502349857405927430957340597320457329045873") << "\n";
}
As far as I understood it, we should paint N posts using K colors so, that after painting, looking at any group of 4 consecutive posts, we see 4 different colors. And we should count how many ways are there to satisfy the rule.
In this case, number of ways can be found using the following formula:
K * (K - 1) * (K - 2) * (K - 3)^(N - 3)
The code below proves the formula by comparing with brute force.
#include <iostream>
#include <vector>
using namespace std;
bool Valid(vector<int> const &comb)
{
for (int i = 0; i < comb.size(); ++i) {
for (int j = 1; j <= 3; ++j) {
if (i >= j &&
comb[i - j] == comb[i])
{
return false;
}
}
}
return true;
}
uint64_t BruteForce(int n, int k)
{
vector<int> comb;
comb.resize(n, 1);
uint64_t count = 0;
do {
if (Valid(comb)) {
++count;
}
for (int i = comb.size() - 1; i >= 0; --i) {
if (++comb[i] <= k) {
break;
}
if (i != 0) {
comb[i] = 1;
}
}
} while (comb[0] <= k);
return count;
}
uint64_t Formula(int n, int k)
{
uint64_t count = k;
if (n > 1) {
count *= (k - 1);
if (n > 2) {
count *= (k - 2);
}
}
for (int i = 0; i < n - 3; ++i) {
count *= k - 3;
}
return count;
}
int main()
{
for (int n = 1; n <= 9; ++n) {
for (int k = 1; k <= 9; ++k) {
uint64_t count1 = BruteForce(n, k);
uint64_t count2 = Formula(n, k);
cout << n << ", " << k << ", " << count1 << ", " << count2 << "\n";
if (count1 != count2) {
cerr << "error\n";
exit(-1);
}
}
}
return 0;
}
@Anonymous. At each position, we just try to flip to 0 and see how many flips are needed for the rest of the bits. And at the same position we also try to flip to 1 and see how many flips are needed for the rest of the bits. And we choose minimum from the two flip counts. Also, we use memoization to optimize time.
- Alex November 10, 2017O(n) time and space.
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int MinFlipsCount(uint8_t const *a, int size, unordered_map<uint64_t, int> &memo, int prev = 1, int idx = 0)
{
if (idx < 0 ||
idx > size)
{
return -1;
}
if (idx == size) {
return 0;
}
uint64_t memo_key = (static_cast<uint64_t>(idx) << 32) | prev;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
int bit = ((a[idx >> 3] & (1 << (7 - (idx % 8)))) == 0) ? 0 : 1;
int flip_to_zero_count = numeric_limits<int>::max();
int flip_to_one_count = numeric_limits<int>::max();
if (idx != 0) {
flip_to_zero_count = (bit == 0 ? 0 : 1) + MinFlipsCount(a, size, memo, 0, idx + 1);
}
if (idx != size - 1 &&
prev == 1)
{
flip_to_one_count = (bit == 1 ? 0 : 1) + MinFlipsCount(a, size, memo, 1, idx + 1);
}
memo[memo_key] = min(flip_to_zero_count, flip_to_one_count);
return memo[memo_key];
}
int main () {
vector<pair<uint8_t, int>> bit_arrays = {
{0b10110000, 7},
{0b10110000, 7},
{0b00001000, 5},
{0b10101010, 8},
{0b00001111, 8},
{0b10011100, 8},
{0b10111111, 8},
};
for (auto el : bit_arrays) {
unordered_map<uint64_t, int> memo;
cout << MinFlipsCount(&el.first, el.second, memo) << "\n";
}
return 0;
}
void Combs(unordered_map<char, vector<char>> &map, string const &digits,
vector<string> &combs, string const comb = "")
{
if (comb.size() == digits.size()) {
if (!comb.empty()) {
combs.push_back(comb);
}
return;
}
auto it = map.find(digits[comb.size()]);
if (it != map.end()) {
vector<char> const &chars = it->second;
for (char c : chars) {
Combs(map, digits, combs, comb + c);
}
}
}
Time O(s * w^2), space O(s), where s is size of the string to break, and w is max size of the dictionary words.
Time can be improved to O(s * w) if we use a trie for dictionary.
#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int MinBreaksCount(string const &s, unordered_set<string> const dict, unordered_map<int, int> &memo, int idx = 0)
{
if (idx < 0 ||
idx > s.size())
{
return numeric_limits<int>::max();
}
if (idx == s.size()) {
return 0;
}
auto it = memo.find(idx);
if (it != memo.end()) {
return it->second;
}
int min_count = numeric_limits<int>::max();
for (int i = idx; i < s.size(); ++i) {
if (dict.find(s.substr(idx, i - idx + 1)) != dict.end()) {
int count = MinBreaksCount(s, dict, memo, i + 1);
if (count != numeric_limits<int>::max()) {
if (i != s.size() - 1) {
++count;
}
min_count = min(min_count, count);
}
}
}
memo[idx] = min_count;
return memo[idx];
}
int main () {
unordered_set<string> dict = {"cat", "mat", "ca", "tm", "at", "c", "dog", "og", "do"};
unordered_map<int, int> memo;
cout << MinBreaksCount("catmat", dict, memo) << "\n";
return 0;
}
I assume that islands are solid. I.e. an island can't have a lake in the middle.
The idea is to walk along the shore.
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
bool Shore(vector<vector<int>> const &m, int r, int c)
{
if (r >= 0 &&
r < m.size() &&
c >= 0 &&
c < m[r].size() &&
m[r][c] == 1)
{
if (r + 1 >= m.size() ||
r - 1 < 0 ||
c + 1 >= m[r].size() ||
c - 1 < 0 ||
m[r + 1][c] == 0 ||
m[r - 1][c] == 0 ||
m[r][c + 1] == 0 ||
m[r][c - 1] == 0)
{
return true;
}
}
return false;
}
int PerimeterFromCell(vector<vector<int>> &m, int r, int c)
{
int perimeter = 0;
stack<pair<int, int>> st;
st.push(pair<int, int>(r, c));
while (!st.empty()) {
r = st.top().first;
c = st.top().second;
st.pop();
if (Shore(m, r, c)) {
++perimeter;
st.push(pair<int, int>(r + 1, c));
st.push(pair<int, int>(r - 1, c));
st.push(pair<int, int>(r, c + 1));
st.push(pair<int, int>(r, c - 1));
m[r][c] = 2;
}
}
return perimeter;
}
vector<int> Perimeters(vector<vector<int>> &m)
{
vector<int> out;
for (int r = 0; r < m.size(); ++r) {
for (int c = 0; c < m[r].size(); ++c) {
int perimeter = PerimeterFromCell(m, r, c);
if (perimeter > 0) {
out.push_back(perimeter);
}
}
}
return out;
}
int main()
{
vector<vector<int>> m = {
{0,0,0,0,1,1,1,1},
{0,1,1,1,0,0,1,1},
{0,1,1,1,0,0,1,1},
{0,1,1,0,0,1,0,0},
{0,0,0,1,1,1,0,0},
{0,0,0,1,1,1,1,0},
{0,1,0,1,1,1,1,0}
};
vector<int> out = Perimeters(m);
for (int n : out) {
cout << n << ", ";
}
cout << "\n";
return 0;
}
void Sort(vector<int> &a)
{
int space_idx = -1;
for (int i = 0; i < a.size() && space_idx == -1; ++i) {
if (a[i] == 0) {
space_idx = i;
}
}
if (space_idx != -1) {
for (int i = 0; i < a.size(); ++i) {
while (i != space_idx &&
a[i] != i + 1)
{
int space_idx_stored = space_idx;
swap(a[a[i] - 1], a[space_idx]);
space_idx = a[i] - 1;
swap(a[i], a[space_idx]);
space_idx = i;
if (a[space_idx_stored] != space_idx_stored + 1) {
swap(a[space_idx_stored], a[space_idx]);
space_idx = space_idx_stored;
}
}
}
}
}
O(n * k) time and O(n) space. Space can be improved to O(k) by using a linked list instead of inc and dec arrays.
#include <vector>
#include <iostream>
using namespace std;
vector<int> Diffs(vector<int> const &a, int k)
{
vector<int> out;
vector<int> inc, dec;
inc.resize(a.size(), 0);
dec.resize(a.size(), 0);
int inc_sum = 0;
int dec_sum = 0;
for (int i = 0; i < a.size(); ++i) {
for (int j = i - 1; j >= 0 && j > i - k && a[j + 1] > a[j]; --j) {
++inc[j];
++inc_sum;
}
for (int j = i - 1; j >= 0 && j > i - k && a[j + 1] < a[j]; --j) {
++dec[j];
++dec_sum;
}
if (i >= k - 1) {
if (i >= k) {
inc_sum -= inc[i - k];
dec_sum -= dec[i - k];
}
out.push_back(inc_sum - dec_sum);
}
}
return out;
}
int main()
{
vector<int> out = Diffs({188930, 194123, 201345, 154243, 154243}, 3);
for (int n : out) {
cout << n << ", ";
}
cout << "\n";
return 0;
}
Worst case time O(n^2). When points are distributed uniformly on the plane, O(n * √n).
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Point {
public:
Point(int32_t x, int32_t y)
{
x_ = x;
y_ = y;
}
int32_t x_, y_;
};
uint64_t MaxArea(vector<Point> const &points)
{
uint64_t max_area = 0;
unordered_map<int32_t, vector<int32_t>> y_to_xes;
for (auto &p : points) {
y_to_xes[p.y_].push_back(p.x_);
}
unordered_map<uint64_t, pair<int32_t, int32_t>> x1x2_to_min_max_y;
for (auto &el : y_to_xes) {
int32_t y = el.first;
vector<int32_t> const &xes = el.second;
for (int i = 0; i < xes.size(); ++i) {
for (int j = i + 1; j < xes.size(); ++j) {
int x1 = xes[i];
int x2 = xes[j];
if (x2 < x1) {
swap(x1, x2);
}
int32_t min_y = y;
int32_t max_y = y;
uint64_t key = ((uint64_t)x1 << 32) | x2;
auto it = x1x2_to_min_max_y.find(key);
if (it != x1x2_to_min_max_y.end()) {
min_y = min(min_y, it->second.first);
max_y = max(max_y, it->second.second);
}
x1x2_to_min_max_y[key] = pair<int32_t, int32_t>(min_y, max_y);
max_area = max(max_area, (uint64_t)(x2 - x1) * max(y - min_y, max_y - y));
}
}
}
return max_area;
}
int main()
{
cout << MaxArea({{0,0}, {0,3},{0,6},{2,0},{2,3},{2,6},{5,6},{6,0},{6,4}}) << "\n";
return 0;
}
I assume that
if multiplying {{a,b}, {c,d}} = {{a,c}, {a,d}, {b,c}, {b,d}}
then, multiplying {{a,b}, {c,d}, {e,f}} = multiplying {{a,c}, {a,d}, {b,c}, {b,d}} by {e,f} = {a,e}, {a,f}, {c,e}, {c,f}, {a,e}, {a,f}, {d,e}, {d,f}, {b,e}, {b,f}, {c,e}, {c,f}, {b,e}, {b,f}, {d,e}, {d,f}
void Multiply(vector<vector<char>> const &a, vector<vector<char>> &out, char c1 = 0, int idx = 0)
{
if (idx < 0 ||
idx >= a.size() ||
(c1 == 0 && idx != 0))
{
return;
}
for (char c2 : a[idx]) {
if (c1 != 0 &&
idx == a.size() - 1)
{
out.push_back({c1, c2});
}
Multiply(a, out, c1, idx + 1);
Multiply(a, out, c2, idx + 1);
}
}
#include<iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
next_ = NULL;
}
int val_;
Node *next_;
};
pair<Node *, Node *> Separate(Node *head)
{
Node *head2 = head ? head->next_ : NULL;
Node *n1 = head;
Node *n2 = head2;
while (n1 &&
n2)
{
Node *next_n1 = n2->next_;
Node *next_n2 = n2->next_ ? n2->next_->next_ : NULL;
n1->next_ = n2->next_;
n2->next_ = next_n2;
n1 = next_n1;
n2 = next_n2;
}
return pair<Node*, Node*>(head, head2);
}
Node *Merge(Node *head1, Node *head2)
{
Node *n1 = head1;
Node *n2 = head2;
while (n1 &&
n2)
{
Node *next_n1 = n1->next_;
Node *next_n2 = n2->next_;
n1->next_ = n2;
if (next_n1) {
n2->next_ = next_n1;
}
n1 = next_n1;
n2 = next_n2;
}
return head1;
}
void Print(Node *n) {
while (n) {
cout << n->val_ << "->";
n = n->next_;
}
cout << "\n";
}
int main()
{
Node n1(1), n2(2), n3(3), n4(4), n5(5);
n1.next_ = &n2;
n2.next_ = &n3;
n3.next_ = &n4;
n4.next_ = &n5;
pair<Node *, Node *> out = Separate(&n1);
Print(out.first);
Print(out.second);
Node *head = Merge(out.first, out.second);
Print(head);
return 0;
}
RepSWE
RepHire high professional child development center in Charlotte. Pal-A-Roo’s Child Development Center is a family-owned child care facility offering ...
Rep
RepIf you want to attract someone then astrologer kumar can help you. Astrologer kumar is specialized in offering kamdev vashikaran ...
- Alex November 27, 2017