LANorth
BAN USERWe can use binary search.
1. Double the half square side. When we reach the number of collected apples, it stops.
2. Use the binary search to get the minimal perimeter.
int CalculateApples(int x)
{
int result = 0;
for (int i = -x+1; i <= x-1; i++)
{
result += abs(i) + x;
}
result = result * 4 + (x+x)*4;
return result;
}
int GetMinimalPerimeter(int X)
{
int result;
int cur = 1;
while (true)
{
int num_apples = CalculateApples(cur);
if (num_apples == X)
{
result = 8 * cur;
return result;
}
if (num_apples > X)
{
result = 8 * cur;
break;
}
cur *= 2;
}
if (cur == 1) return result;
int left = cur / 2, right = cur;
while (left <= right)
{
int m = left + (right - left) / 2;
int num_apples = CalculateApples(m);
if (num_apples == X)
{
result = 8 * m;
return result;
}
else if (num_apples > X)
{
result = 8 * m;
right = m - 1;
}
else
{
left = m + 1;
}
}
return result;
}
struct Edge
{
int from;
int to;
};
bool CheckRestrictedPath(const unordered_map<int, int>& edges, const vector<Edge>& R)
{
for (const auto& e : R)
{
int start = e.from;
while (true)
{
auto it = edges.find(start);
if (it == edges.end())
break;
if (it->second == e.to)
return false;
start = it->second;
}
}
return true;
}
vector<Edge> AddEdges(const vector<Edge>& M, const vector<Edge>& K)
{
vector<Edge> ret;
unordered_map<int, int> edge_map;
for (const auto& e : M)
{
edge_map[e.from] = e.to;
if (!CheckRestrictedPath(edge_map, K))
{
auto it = edge_map.find(e.from);
if (it != edge_map.end())
edge_map.erase(it);
continue;
}
ret.emplace_back(e);
}
return ret;
}
vector<string> CompareDocuments(const vector<string>& d1, const vector<string>& d2, int n)
{
vector<string> ret;
set<string> comm_set;
unordered_map<string, int> str_idx;
for (int i = 0; i < d1.size(); i++)
{
str_idx[d1[i]] = i;
}
int idx = 0;
int prev_idx = 0;
string com_str;
while (idx + n -1 < d2.size())
{
com_str = "";
prev_idx = 0;
for (int i = 0; i <= n; i++)
{
if (i == n)
{
comm_set.emplace(com_str);
break;
}
com_str += i==0?d2[idx + i]: " " + d2[idx + i];
unordered_map<string, int>::iterator it = str_idx.find(d2[idx+i]);
if (it == str_idx.end())
break;
else
{
if (i && it->second != prev_idx + 1)
break;
prev_idx = it->second;
}
}
idx++;
}
for (auto i = comm_set.begin(); i != comm_set.end(); i++)
{
ret.emplace_back(*i);
}
return ret;
}
int main()
{
vector<string> d1{ "Today", "is", "Sunday" };
vector<string> d2{ "Today", "is", "Saturday" };
//ret = {Today, is}
vector<string> ret = CompareDocuments(d1, d2, 1);
//ret = {Today is}
ret = CompareDocuments(d1, d2, 2);
//ret = empty, 0
ret = CompareDocuments(d1, d2, 3);
return 0;
}
int GetMinimalTime(const vector<int>& A, int k)
{
int ret = 0;
int total = 0;
for (const int& a : A)
total += a;
int ave_num = total / k;
int max_from_left = 0, cur_val = 0;
int num_painter = k;
for (int i = 0; i < A.size(); i++)
{
cur_val += A[i];
if (cur_val == ave_num)
{
if (num_painter) num_painter--;
max_from_left = max(max_from_left, cur_val);
if (num_painter)
cur_val = 0;
}
else if (cur_val > ave_num)
{
if (num_painter) num_painter--;
if (num_painter)
{
cur_val -= A[i];
max_from_left = max(max_from_left, cur_val);
cur_val = A[i];
}
else
{
max_from_left = max(max_from_left, cur_val);
}
}
if (num_painter == 0 && i == A.size()-1)
break;
}
int max_from_right = 0;
cur_val = 0;
num_painter = k;
for (int i = A.size()-1; i >=0; --i)
{
cur_val += A[i];
if (cur_val == ave_num)
{
if (num_painter) num_painter--;
max_from_right = max(max_from_right, cur_val);
if (num_painter)
cur_val = 0;
}
else if (cur_val > ave_num)
{
if (num_painter) num_painter--;
if (num_painter)
{
cur_val -= A[i];
max_from_right = max(max_from_right, cur_val);
cur_val = A[i];
}
else
{
max_from_right = max(max_from_right, cur_val);
}
}
if (num_painter == 0 && i == 0)
break;
}
ret = min(max_from_left, max_from_right);
return ret;
}
int main()
{
vector<int> A{ 10,10,10,10 };
int k = 2;
//ret = 20
int ret = GetMinimalTime(A, k);
A = {10,20,30,40};
//ret = 60
ret = GetMinimalTime(A, k);
A = { 10,20,30,40,50 };
k = 3;
//ret = 60
ret = GetMinimalTime(A, k);
A = { 10,20,50,30,40};
//ret = 70
ret = GetMinimalTime(A, k);
A = { 10,20,50,30,40,60 };
//ret = 80
ret = GetMinimalTime(A, k);
return 0;
}
struct Interval
{
bool operator<(const Interval& in)
{
return left < in.left;
}
int left;
int right;
};
vector<Interval> UnionInverval(const vector<Interval>& A)
{
vector<Interval> ret;
if (A.size() == 0) return ret;
Interval cur(A.front());
for (int i = 1; i < A.size(); i++)
{
if (cur.right >= A[i].left)
{
if (A[i].right > cur.right)
cur.right = A[i].right;
}
else
{
ret.emplace_back(cur);
cur = A[i];
}
}
ret.emplace_back(cur);
return ret;
}
bool IsIntervalCovered(vector<Interval> A, const Interval& a)
{
sort(A.begin(), A.end());
bool ret = false;
vector<Interval> union_A = UnionInverval(A);
int left = 0, right = union_A.size() - 1;
while (left <= right)
{
int m = left + (right - left) / 2;
if (union_A[m].left == a.left) {
ret = a.right <= union_A[m].right;
break;
}
else if (union_A[m].left < a.left) {
left = m + 1;
if (m + 1 < union_A.size() && union_A[m + 1].left > a.left)
{
ret = a.right <= union_A[m].right;
break;
}
}
else
{
right = m - 1;
if (m - 1 >= 0 && union_A[m - 1].left <= a.left)
{
ret = a.right <= union_A[m - 1].right;
break;
}
}
}
return ret;
}
int main()
{
vector<Interval> A;
A.emplace_back(Interval{ 2,5 });
A.emplace_back(Interval{ 5,7 });
A.emplace_back(Interval{ 1,4 });
Interval a{ 1, 6 };
bool ret = IsIntervalCovered(A, a);
A.clear();
A.emplace_back(Interval{ 1,4 });
A.emplace_back(Interval{ 6,7 });
A.emplace_back(Interval{ 2,5 });
a = { 2, 6 };
ret = IsIntervalCovered(A, a);
a = { 0, 4 };
ret = IsIntervalCovered(A, a);
return 0;
}
vector<int> GetRandomSublist(vector<int> A, int n)
{
default_random_engine seed((random_device())());
if (n < 0 || n >= A.size()) return {};
for (int i = 0; i < n; i++)
{
uniform_int_distribution<int> rand_gen(i, A.size() - 1);
int num = rand_gen(seed);
swap(A[i], A[num]);
}
vector<int> ret;
for (int i = 0; i < n; i++)
ret.emplace_back(A[i]);
sort(ret.begin(), ret.end());
return ret;
}
struct Session
{
int start;
int end;
};
struct SessionPoint
{
bool operator<(const SessionPoint& p)
{
return time != p.time ? time < p.time : (IsStart && (!p.IsStart));
}
int time;
bool IsStart;
};
int GetMaxConcurrentSessions(const vector<Session>& sessions)
{
vector<SessionPoint> sps;
for (const Session& se : sessions)
{
sps.emplace_back(SessionPoint{ se.start, true });
sps.emplace_back(SessionPoint{ se.end, false });
}
sort(sps.begin(), sps.end());
int max_num = 0, cur_num = 0;
for (int i = 0; i < sps.size(); i++)
{
if (sps[i].IsStart)
{
cur_num++;
max_num = max(max_num, cur_num);
}
else
cur_num--;
}
return max_num;
}
vector<int> GetOverallArray(const vector<vector<int>>& A)
{
vector<int> result;
multimap<int, pair<vector<int>::const_iterator, vector<int>::const_iterator>> itr_tail;
for (const auto& arr : A)
{
itr_tail.emplace(arr.front(), make_pair(arr.cbegin(), arr.cend()));
}
while (true)
{
bool not_process = false;
auto prev_it = itr_tail.begin();
if (itr_tail.size() <= 1)
break;
if (prev_it != itr_tail.end())
{
int cur_val = prev_it->first;
int count = 0;
for (auto it = next(prev_it); it != itr_tail.end(); ++it)
{
if (cur_val == it->first)
{
not_process = true;
count++;
auto next_it = next(prev_it->second.first);
if (next_it != prev_it->second.second)
{
itr_tail.emplace(*next_it, make_pair(next_it, prev_it->second.second));
}
itr_tail.erase(prev_it);
}
else
{
if (count > 0)
{
auto next_it = next(prev_it->second.first);
if (next_it != prev_it->second.second)
{
itr_tail.emplace(*next_it, make_pair(next_it, prev_it->second.second));
}
itr_tail.erase(prev_it);
result.emplace_back(cur_val);
}
count = 0;
cur_val = it->first;
}
prev_it = it;
}
if (count > 0)
{
auto next_it = next(prev_it->second.first);
if (next_it != prev_it->second.second)
{
itr_tail.emplace(*next_it, make_pair(next_it, prev_it->second.second));
}
itr_tail.erase(prev_it);
result.emplace_back(cur_val);
}
if (!not_process)
{
prev_it = itr_tail.begin();
if (prev_it != itr_tail.end())
{
auto next_it = next(prev_it->second.first);
if (next_it != prev_it->second.second)
{
itr_tail.emplace(*next_it, make_pair(next_it, prev_it->second.second));
}
itr_tail.erase(prev_it);
}
}
}
}
return result;
}
int main()
{
vector<vector<int>> A;
A.emplace_back(vector<int>{1,3,5});
A.emplace_back(vector<int>{1, 3, 9});
A.emplace_back(vector<int>{9, 5});
vector<int> ret = GetOverallArray(A);
return 0;
}
vector<string> getUnion(const vector<string>& A, const vector<string>& B)
{
vector<string> result;
unordered_set<string> setRemove;
vector<string>::iterator itr;
for (itr = B.cbegin(); itr != B.cend(); itr++)
{
setRemove.emplace(*itr);
}
for (itr = A.cbegin(); itr != A.cend(); itr++)
{
if (!setRemove.count(*itr))
result.push_back(*itr);
}
setRemove.clear();
for (itr = A.cbegin(); itr != A.cend(); itr++)
{
setRemove.emplace(*itr);
}
for (itr = B.cbegin(); itr != B.cend(); itr++)
{
if (!setRemove.count(*itr))
result.push_back(*itr);
}
return result;
}
void ReorganizeArray(int arr[], int n)
{
int write_indx = 0, read_indx = 0;
while (read_indx < n)
{
if (arr[read_indx] != 0)
{
if (write_indx != read_indx)
arr[write_indx++] = arr[read_indx];
else
write_indx++;
}
read_indx++;
}
while (write_indx < n)
arr[write_indx++] = 0;
}
int GetMinimalCost(vector<vector<int>>& grid)
{
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[i].size(); j++)
{
if (i == 0 && j > 0)
grid[i][j] += grid[i][j-1];
if (j == 0 && i > 0)
grid[i][j] += grid[i-1][j];
if (i > 0 && j > 0)
grid[i][j] += min(min(grid[i][j-1], grid[i-1][j]), grid[i-1][j-1]);
}
}
return grid[grid.size()-1][grid[0].size()-1];
}
int main()
{
vector<vector<int>> grid;
int arr[3][3] = {{4,5,6},{1,2,3},{0,1,2}};
for (int i = 0; i< 3; i++)
{
vector<int> vArr(begin(arr[i]), end(arr[i]));
grid.push_back(vArr);
}
int cost = GetMinimalCost(grid);
return 0;
}
//pair<index, length>
pair<int, int> findMinimalLength(int A[], int m, int S[], int n)
{
pair<int, int> ret(-1, INT_MAX);
if (m == 0 || n == 0)
return ret;
unordered_map<int, int> mpSub;
int i;
for (i = 0; i < n; i++)
mpSub[S[i]] = 0;
int startIndex = -1, len = -1;
unordered_map<int, int>::iterator itr;
for (i = 0; i < m; i++)
{
if (mpSub.find(A[i]) != mpSub.end())
{
if (startIndex == -1 || mpSub[A[i]] == 1)
{
startIndex = i;
if (mpSub[A[i]] == 1)
{
for (itr = mpSub.begin(); itr != mpSub.end(); itr++)
itr->second = 0;
}
mpSub[A[i]] = 1;
}else
{
mpSub[A[i]] = 1;
for (itr = mpSub.begin(); itr != mpSub.end(); itr++)
{
if (itr->second != 1)
break;
}
if (itr == mpSub.end())
{
if (len == -1 || len > i - startIndex + 1)
{
len = i - startIndex + 1;
ret = make_pair(startIndex, len);
}
for (itr = mpSub.begin(); itr != mpSub.end(); itr++)
itr->second = 0;
startIndex = -1;
}
}
}
}
return ret;
}
I think your code always sets the start index as 0. If the first element is not 7 or 42, what happens? I'm not sure if this is the correct code.
int findIndex(int A[],int N,int X,int Y)
{
int nx =0;
int ny=0;
int result = -1;
int startIndx = -1;
for( int i=0;i<N;i++)
{
if(A[i] == X) nx+=1;
if(A[i] == Y) ny+=1;
if ((nx!=0 || ny!=0) && (startIndx == -1))
startIndx = i;
if(nx== ny&& nx!=0&&ny!=0)
result = i;
}
if ((startIndx != -1) && (result!=-1))
result = result - startIndx;
return result;
}
typedef struct _Node
{
int value;
struct _Node* next;
} Node;
void ReorganizeLinkedList(Node*& head)
{
Node* slow=head, *fast = head;
while (fast && fast->next && fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
}
//Reverse the second half
Node* nextNode=NULL, *tail = slow->next;
slow->next = NULL;
Node* current = tail, *prevNode = NULL, *reverseHead = tail;
while (current != NULL)
{
nextNode = current->next;
current->next = prevNode;
prevNode = current;
current = nextNode;
}
reverseHead = prevNode;
//Merge two lists
current = head;
nextNode = reverseHead;
tail = NULL;
while (current && nextNode)
{
prevNode = current->next;
if (tail)
tail->next = current;
current->next = nextNode;
tail = nextNode;
current = prevNode;
nextNode = nextNode->next;
}
//Check if either list has some nodes left
if (current && tail)
tail->next = current;
if (nextNode && tail)
tail->next = nextNode;
}
int solution(int A[], int n)
{
if (n <= 0) return -1;
if (n == 1) return 0;
int sum = 0, sumLeft = 0, sumRight = 0;
for (int i = 0; i < n; i++)
sum += A[i];
if ((sum - A[0]) == 0)
return 0;
sumRight = sum - A[0];
sumLeft = A[0];
int indx = 1;
int previndx = -1;
while (indx < n)
{
sumRight -= A[indx];
if (sumLeft == sumRight)
{
previndx = indx;
break;
}
sumLeft += A[indx];
indx++;
}
return previndx;
}
If the sort starts from the end, it can keep the 0s and 1s in their original order. That means the last 1 should be at the end and the first 0 should be at the beginning. Here is the function.
void swap(vector<int>& arr, int one_pos, int zero_pos)
{
int tmp = arr[one_pos];
arr[one_pos] = arr[zero_pos];
arr[zero_pos] = tmp;
}
void sortInPlace(vector<int>& arr)
{
int zero_pos = arr.size()-1;
for (int i = arr.size()-1; i>=0; i--)
{
if (arr[i] == 0 && arr[zero_pos]!=0)
zero_pos = i;
else if (arr[i] == 1 && arr[zero_pos] == 0)
{
swap(arr, i, zero_pos);
zero_pos--;
}
}
}
struct TreeNode {
int value;
struct TreeNode* left;
struct TreeNode* right;
};
void traversalTree(TreeNode* root, TreeNode* node1, TreeNode* node2, int& h1, int& h2)
{
queue<TreeNode*> travQueue;
int levelheight = 1;
int numNodes = 1;
int hNode1 = 0, hNode2 = 0;
TreeNode* curNode = nullptr;
if (root == NULL || node1 == NULL || node2 == NULL)
return;
travQueue.emplace(root);
while (!travQueue.empty())
{
curNode = travQueue.front();
travQueue.pop();
numNodes--;
if (curNode == node1) hNode1 = levelheight;
if (curNode == node2) hNode2 = levelheight;
if (hNode1 != 0 && hNode2 != 0)
break;
if (curNode->left)
travQueue.emplace(curNode->left);
if (curNode->right)
travQueue.emplace(curNode->right);
if (numNodes == 0)
{
levelheight++;
numNodes = travQueue.size();
}
}
h1 = hNode1;
h2 = hNode2;
}
void findNodesHeightDifference(TreeNode* root, TreeNode* node1, TreeNode* node2, int& diff)
{
int h1=0, h2=0;
traversalTree(root, node1, node2, h1, h2);
if (h1!=0 && h2 != 0)
diff = abs(h1-h2);
else
diff = 0;
}
void ConvertWordsinRowCol(const vector<string>& vWords, int numRows, int numCols, vector<string>& LineofWords)
{
int cols = 0, rows = 0;
int sizes = vWords.size();
int last = 0;
bool first = true;
string rowStr;
while (rows < numRows)
{
while (cols < numCols)
{
for (int i = last; i < sizes; i++)
{
if (first)
cols += vWords[i].length();
else
cols += vWords[i].length() + 1;
if (cols > numCols)
{
last = i; break;
}
if (first)
first = false;
else
rowStr += ' ';
rowStr += vWords[i];
}
if (cols <= numCols) last = 0;
}
LineofWords.push_back(rowStr);
rows++; cols = 0;
first = true; rowStr = "";
}
}
typedef struct _MNode
{
struct _MNode* right;
struct _MNode* down;
char a;
} MNode;
void flattenOneNode(MNode*& head)
{
MNode* tmphead = head;
while (tmphead->down != nullptr)
{
tmphead->right = tmphead->down;
tmphead = tmphead->down;
}
head = tmphead;
}
void flatten(MNode*& head)
{
MNode* tmphead = head;
MNode* next = nullptr;
while (tmphead != nullptr)
{
next = tmphead->right;
flattenOneNode(tmphead);
tmphead->right = next;
tmphead = next;
}
}
int set_bit_l_to_r(int x, int y, int l, int r)
{
int sizeInt = sizeof(int)*8;
if (l >= sizeInt || r >= sizeInt)
return y;
if (l > r)
{
int tmp = l;
l = r;
r = tmp;
}
int maskSet = static_cast<int>(pow(2, r+1) -1) ^ static_cast<int>(pow(2, l) -1);
y = y | (x & maskSet);
return y;
}
- LANorth July 08, 2019