funcoolgeek
BAN USERint findMinFlip(vector<int>& binary)
{
size_t count = 0, last_left = -1, last_right = -1;
size_t left = 0, right = binary.size() - 1;
for (; left < right; ) {
if (binary[left] == 0)
last_left = left;
else if (last_left != -1 && last_left != left) {
count += left - last_left;
last_left = -1;
}
if (binary[right] == 1)
last_right = right;
else if (last_right != -1 && last_right != right) {
count += last_right - right;
last_right = -1;
}
left++;
right--;
}
if (last_left != -1 && last_left != left) {
count += left - last_left;
last_left = left;
}
if (last_right != -1 && last_right != right) {
count += last_right - right;
last_right = right;
}
return count;
}
Use suffix tree!
- funcoolgeek October 31, 2017Simple. Use a map with indexes of the nodes in the list as keys and integer value. For every node pointed to, increase the integer value. Valid if the map has only ONE entry with value 0 and the rest having value 1.
- funcoolgeek October 26, 2017Go diagonally from bottom right until it hits '0' (i,j). This eliminates the (I,j) block and adds this dimension to count. Then, increment i for as long as it is '0', add this to count. Then, increment j for as long as it is '0', add this to count.
long MatrixPatternCount(vector<vector<long>>& data)
{
long i = data.size() - 1, j = data[0].size() -1;
long count = 0;
for (; i >= 0 && j >= 0; i--, j--)
if (!data[i][j]) {
count = (i + 1) * (j + 1);
break;
}
long ii = i, jj = j;
if (ii < data.size() - 1)
for (; j >= 0; j--)
for (i = ii + 1; !data[i][j]; i++)
count++;
i = ii;
if (jj < data[ii].size() - 1)
for (; i >= 0; i--)
for (j = jj + 1; !data[i][j]; j++)
count++;
return count;
}
How could this work!?!
- funcoolgeek June 07, 2016void FindAnagrams(vector<string> const& s, vector<vector<string>> &result)
{
map<string, vector<string>> anagrams;
for (vector<string>::const_iterator it = s.begin(); it != s.end(); it++) {
string s1(*it);
sort(s1.begin(), s1.end());
anagrams[s1].push_back(*it);
}
for (map<string, vector<string>>::const_iterator it = anagrams.begin(); it != anagrams.end(); it++)
result.push_back(it->second);
}
string FindBiggestPalindromeSubstring(string const& s)
{
string tmp, palindrome;
for (size_t i = 1; i < s.size() - 1; i++) {
if (s[i] == s[i + 1]) { // Even palindrome
for (size_t j = i, k = i + 1; j >= 0; j--, k++) {
if (s[j] == s[k]) {
tmp = s.substr(j, k - j + 1);
if (tmp.size() > palindrome.size())
palindrome = tmp;
} else
break;
}
} else if (s[i - 1] == s[i + 1]) { // Odd palindrome
for (size_t j = i - 1, k = i + 1; j >= 0; j--, k++) {
if (s[j] == s[k]) {
tmp = s.substr(j, k - j + 1);
if (tmp.size() > palindrome.size())
palindrome = tmp;
}
else
break;
}
}
}
return palindrome;
}
This is a problem of finding all string permutations.
- funcoolgeek May 18, 2016(1) Reverse the string
(2) Reverse individual words
"Doubles (and floats in general) are designed so that when ordered lexicographically, they'll be ordered from the largest to the smallest" <= How true is this? The most significant bit is a sign bit.
- funcoolgeek May 08, 2016map<string, size_t> order = { { "a", 0 },{ "b", 1 },{ "c", 2 },{ "ch", 3 },{ "cz", 4 },{ "d", 5 },{ "e", 6 },{ "f", 7 },{ "g", 8 },{ "h", 9 },{ "i", 10 },{ "j", 11 },{ "k", 12 },{ "l", 13 },{ "m", 14 },{ "n", 15 },{ "o", 16 },{ "p", 17 },{ "q", 18 },{ "r", 18 },{ "s", 19 },{ "t", 20 },{ "u", 21 },{ "v", 22 },{ "w", 23 },{ "x", 24 },{ "y", 24 },{ "z", 25 } };
bool LexicographicSort(string s1, string s2)
{
size_t i, j;
map<string, size_t>::iterator s1It = order.end(), s2It = order.end();
std::transform(s1.begin(), s1.end(), s1.begin(), ::tolower);
std::transform(s2.begin(), s2.end(), s2.begin(), ::tolower);
for (i = 0, j = 0; i < s1.size(), j < s2.size(); ) {
if (i < s1.size() - 1) {
s1It = order.find(s1.substr(i, 2));
if (s1It != order.end())
i += 2;
}
if (s1It == order.end())
s1It = order.find(s1.substr(i++, 1));
if (j < s2.size() - 1) {
s2It = order.find(s2.substr(j, 2));
if (s2It != order.end())
j += 2;
}
if (s2It == order.end())
s2It = order.find(s2.substr(j++, 1));
if (s1It->second == s2It->second) {
s1It = order.end();
s2It = order.end();
} else
return s1It->second < s2It->second;
}
return (s1.size() - i) < (s2.size() - j);
}
vector<string> strings;
strings.push_back("abcczch");
strings.push_back("abcchcz");
strings.push_back("abcde");
strings.push_back("ABCCZCH");
strings.push_back("ABCCHCZ");
strings.push_back("ABCDE");
sort(strings.begin(), strings.end(), LexicographicSort);
assert(strings[0] == "abcchcz");
assert(strings[1] == "ABCCHCZ");
assert(strings[2] == "abcczch");
assert(strings[3] == "ABCCZCH");
assert(strings[4] == "abcde");
assert(strings[5] == "ABCDE");
enum direction {
Up, Down, NoChange
};
size_t LongestAlternatingSubSequence(const vector<long>& data, vector<long>& result)
{
map<size_t, size_t> sequences;
direction direction = NoChange, flag = NoChange;
size_t count = 0, start = 0, index = 0;
if (data.size() > 1) {
for (vector<long>::const_iterator it = data.begin() + 1; it != data.end(); it++, index++) {
flag = *it > *(it - 1) ? Up : *it < *(it -1 ) ? Down : NoChange;
if (flag != direction) {
count++;
direction = flag;
} else {
direction = NoChange;
if (sequences.find(index - start) == sequences.end())
sequences.emplace(index - start, start);
start = index;
}
}
}
if (sequences.size() > 0)
for (size_t i = 0; i <= sequences.rbegin()->first; i++)
result.push_back(data[i + sequences.rbegin()->second]);
return result.size();
}
Use Pre-Order traversal:
template<class T>
void Tree<T>::PrintTreeColumns()
{
map<long, vector<T>*> columns;
// Use In-Order traversal to print node values
if (m_root) {
vector<T>* list = new vector<T>();
list->push_back(m_root->Item());
columns.emplace(0, list);
PrintColumns(m_root, 0, columns);
for (map<long, vector<T>*>::iterator it = columns.begin(); it != columns.end(); it++)
for (vector<T>::iterator it1 = it->second->begin(); it1 != it->second->end(); it1++)
cout << *it1 << ", ";
cout << endl;
}
}
template<class T>
void Tree<T>::AddToColumn(T value, long column, map<long, vector<T>*>& columns)
{
if (columns.find(column) == columns.end())
{
vector<T>* list = new vector<T>();
list->push_back(value);
columns.emplace(column, list);
} else
columns[column]->push_back(value);
}
template<class T>
void Tree<T>::PrintColumns(Node<T> *node, long column, map<long, vector<T>*>& columns)
{
// Use Pre-Order traversal
if (node) {
if (node->Left())
AddToColumn(node->Left()->Item(), column - 1, columns);
if (node->Right())
AddToColumn(node->Right()->Item(), column + 1, columns);
PrintColumns(node->Left(), column - 1, columns);
PrintColumns(node->Right(), column + 1, columns);
}
}
template<class T>
T Tree<T>::MinDiffInBST()
{
return m_root ? MinDiffInBST(m_root, nullptr) : -1;
}
template<class T>
T Tree<T>::MinDiffInBST(Node<T>* current, Node<T>* previous)
{
T min = LONG_MAX;
// Use In-Order traversal to find min diff between any 2 nodes
if (current) {
min = MinDiffInBST(current->Left(), current);
if (previous)
min = MIN(min, abs(current->Item() - previous->Item()));
min = MIN(min, MinDiffInBST(current->Right(), current));
}
return min;
}
void MatrixSort(vector<vector<long>>& data)
{
vector<long> sorted;
for (size_t i = 0; i < data.size(); i++)
for (size_t j = 0; j < data[i].size(); j++)
sorted.push_back(data[i][j]);
QuickSort(sorted, 0, sorted.size() - 1);
size_t k = 0;
for (size_t i = 0; i < data.size(); i++)
for (size_t j = 0; j < data[i].size(); j++)
data[j][i] = sorted[k++];
}
long ConsecutiveLargestSum(vector<long>& data, vector<long>& result)
{
long max_ending_here = 0, max_so_far = 0;
vector<long>::iterator start, end;
for (vector<long>::iterator it = data.begin(); it != data.end(); it++) {
max_ending_here += *it;
if (max_ending_here < 0) {
max_ending_here = 0;
start = end = data.begin();
}
if (max_so_far < max_ending_here) {
max_so_far = max_ending_here;
if (start == data.begin())
start = it;
end = it;
}
}
result.assign(start, end + 1);
return max_so_far;
}
bool CanShuffleWithoutRepeat(string& str)
{
map<char, size_t> repeats;
size_t max = 0;
for (string::iterator it = str.begin(); it != str.end(); it++) {
if (repeats.find(*it) == repeats.end())
repeats.emplace(*it, 1);
else
repeats[*it]++;
max = Max(max, repeats[*it]);
}
return str.size() - max >= max - 1;
}
Repellahrivas6, Android test engineer at 247quickbookshelp
I am working as an internist and I work in medical offices, clinics, and hospitals. An internist may work independently ...
- funcoolgeek December 15, 2017