Gabriel
BAN USER1. Using recursive method to solve the problem;
2. Using a function to judge if a code is valid dictionary key;
3. Assuming the input string is source, and the last valid key's end position is at cur, cur >= 0 and cur < source.size();
1)From this position,
if string(source[cur], ..., source[cur + i0]) is a valid key,
if string(source[cur], ..., source[cur + i1]) is a valid key,
...
if string(source[cur], ..., source[cur + in]) is a valid key,
2)For each situation,
add the corresponding value into a container, and continue processing it from current end position;
3)If cur == source.size()
Print current contents and return.
#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
#define DEBUG
//#undef DEBUG
using namespace std;
map<int, char> dic;
bool judgeValid(string code)
{
if(code.size() > 1 && code[0] == '0')
{
return false;
}
int num = atoi(code.c_str());
if(dic.find(num) != dic.end())
{
return true;
}
return false;
}
char getValue(string code)
{
int num = atoi(code.c_str());
return dic[num];
}
void printCode(int cur, vector<char> dcode, string source)
{
if(cur == source.size())
{
for(vector<char>::iterator it = dcode.begin(); it != dcode.end(); ++it)
{
cout << (*it);
}
cout << endl;
return;
}
string tmp;
for(int i = cur; i < source.size(); ++i)
{
tmp.push_back(source[i]);
if(judgeValid(tmp))
{
dcode.push_back(getValue(tmp));
printCode(i + 1, dcode, source);
dcode.pop_back();
}
}
}
#ifdef DEBUG
#endif
#ifdef DEBUG
void testMap()
{
for(map<int, char>::iterator it = dic.begin(); it != dic.end(); ++it)
{
cout << it>first << ", " << it>second << endl;
}
}
void testJudgeValid()
{
bool tmp;
vector<string> tvec;
tvec.push_back(string("10"));
tvec.push_back(string("16"));
tvec.push_back(string("30"));
tvec.push_back(string("01"));
tvec.push_back(string("00"));
tvec.push_back(string("8"));
for(vector<string>::iterator it = tvec.begin(); it != tvec.end(); ++it)
{
tmp = judgeValid(*it);
cout << (tmp ? "True" : "False") << endl;
}
}
void testPrintCode()
{
vector<string> tvec;
tvec.push_back("12632");
tvec.push_back("111");
tvec.push_back("101");
for(vector<string>::iterator it = tvec.begin(); it != tvec.end(); ++it)
{
cout << "Test " << (*it).c_str() << ":" << endl;
printCode(0, vector<char>(), *it);
cout << endl;
}
}
#endif
int main()
{
int i = 0;
for(i = 1; i <= 26; ++i)
{
dic[i] = char('a' + i  1);
}
#ifdef DEBUG
testMap();
testJudgeValid();
testPrintCode();
#endif
return 0;
}

Gabriel
March 25, 2014 There are some ways:
1. data slice: according to the date time span{month, season, year or more detail} or other column value (such as product name: fast food, bread or other standard) to minimize the size of certain table, after this operation, you can separate the load into smaller tables.
2. server structure: using redundant data, according to the location or business to create many mirrors.
3. using dirty data: if the business don't have high demand on data reality, you can using .json or other data formats to download part data to local machine, after the whole service, writing dirty data into database.
I believe there are many other methods, but you should do the right things after you know the real environment.
Using any one traverse method (preorder, inorder, postorder) of binary tree,
sum the nonleft nodes' values.
Below is my code which using preorder.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
struct binaryTreeNode
{
binaryTreeNode* left;
binaryTreeNode* right;
int data;
};
void createBinaryTree(binaryTreeNode*& root)
{
int itmp = 0;
cin >> itmp;
if(itmp > 0)
{
if(root == NULL)
{
root = new binaryTreeNode();
}
root>data = itmp;
root>left = 0;
root>right = 0;
createBinaryTree(root>left);
createBinaryTree(root>right);
}
}
int sumBinaryTreeNodeValue(binaryTreeNode* root)
{
int sum = 0;
binaryTreeNode* top = 0;
stack<binaryTreeNode*> bstack;
bstack.push(root);
while(!bstack.empty())
{
top = bstack.top();
bstack.pop();
if(top>left  top>right)
{
sum += top>data;
}
if(top>right)
{
bstack.push(top>right);
}
if(top>left)
{
bstack.push(top>left);
}
}
return sum;
}
void destroyBinaryTree(binaryTreeNode*& root)
{
if(root)
{
if(root>left)
{
destroyBinaryTree(root>left);
}
if(root>right)
{
destroyBinaryTree(root>right);
}
delete root;
}
}
int main()
{
binaryTreeNode* root = 0;
createBinaryTree(root);
cout << sumBinaryTreeNodeValue(root) << endl;
destroyBinaryTree(root);
return 0;
}

Gabriel
June 02, 2013 Below is my code using calculating the connected components of one graph.
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int n = 10;
bool visit[n];
void dfs(int x, int seat[], vector<int>& rec)
{
visit[x] = true;
rec.push_back(x);
if(!visit[seat[x]])
{
dfs(seat[x], seat, rec);
}
}
int findMinLift(int seat[])
{
int i = 0;
int ret = 0;
vector<int> list;
memset(visit, false, sizeof(visit));
while(true)
{
list.clear();
for(i = 0; i < n; i++)
{
if(seat[i] != i && !visit[i])
{
dfs(i, seat, list);
for(vector<int>::iterator it = list.begin(); it != list.end(); it++)
{
cout << (*it) << " ";
}
cout << endl;
if(list.size() > 1)
{
ret += list.size();
}
break;
}
}
if(i == n)
{
break;
}
}
return ret;
}
int main()
{
int seat[n] = {3, 8, 9, 4, 0, 1, 5, 2, 6, 7};
int min = findMinLift(seat);
cout << min;
return 0;
}

Gabriel
June 01, 2013 The another idea, we can treat this problem as calculate the connected components of one graph.
For example:
1) if
floor[1] = person[2], floor[2] = person[3], floor[3] = person[4], floor[4] = person[1].
The connected component (or a circle) contains 4 elements, so we can do 4 lift movements to finish the operation to move person[i] to floor[i].
2) if floor[1] = person[1], under this situation, we do 0 lift movements to finish the operation.
We can DFS to find the number of connected components and the number of elements of each connected components.
We can treat this problem as sorting an array.
From any point i which contains the person j (!= i), doing sorting algorithm and recording the swap times (and the lift movements == swap times * 2).
Then we do the same operation from other point ii which contains the person jj (!= ii).
At the end, we keep track the minimum value of swap times, and it is the result we want.
public ArrayList<String> findRepeat(String[] input) {
int i = 0;
ArrayList<String> res = new ArrayList<String>();
res.clear();
for (String s : input) {
if (s.length() > 1) {
for (i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i  1)) {
res.add(s);
break;
}
}
}
}
return res;
}

Gabriel
May 30, 2013 There are two solutions to deal with this problem.
1.From head to tail
2.From tail to head
Below is the code, since the logic is not very complicated, so I believe the code is enough.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cassert>
#include <climits>
using namespace std;
void swap(int& a, int& b){ int c = a; a = b; b = c; }
void rearrangeArray1(int n, int data[])
{
int i = 0;
int j = 0;
for(i = 0; i < n; i++)
{
if(data[i] != 0 && i < n  1)
{
for(j = i + 1; j < n; j++)
{
if(data[j] == 0)
{
swap(data[i], data[j]);
break;
}
}
/* which means the elements after i are all not zero */
if(j == n)
{
break;
}
}
}
}
void rearrangeArray2(int n, int data[])
{
int i = 0;
int j = 0;
for(i = n  1; i > 0; i)
{
if(data[i] == 0)
{
for(j = i  1; j >= 0; j)
{
if(data[j] != 0)
{
swap(data[i], data[j]);
break;
}
}
if(j == 0)
{
break;
}
}
}
}
int main()
{
int a[10] = {10, 9, 0, 8, 7, 0, 12, 0, 0, 20};
rearrangeArray1(10, a);
rearrangeArray2(10, a);
for(int i = 0; i < 10; i++)
{
cout << a[i] << endl;
}
return 0;
}

Gabriel
May 17, 2013 Using a stack, and set a flag to record whether this time pop some elements.
flag == 0 means there is no element being poped in prior loop,
flag == 1 means there is one element being poped in prior loog.
1. Input an element, when the stack is empty
1)if the element is equal to the stack[top]
2)if the element is not equal to the stack[top]
2. Input an element, when the stack is not empty
You can find the detail logic in the following code segments.
The time complexity is O(n).
int getLongestEvenPalindrome(char source[], int& end)
{
int i = 0, top = 1;
int max = 1, pop = 0;
int tmp = 0, tend = 0;
int len = strlen(source);
char stack[MAX];
for(i = 0; i < len; i++)
{
if(top > 1)
{
if(source[i] == stack[top])
{
if(pop == 0)
{
pop = 1;
tmp = 2;
tend = i;
}
else if(pop == 1)
{
tmp += 2;
tend = i;
}
top;
}
else if(source[i] != stack[top])
{
if(pop == 1)
{
top = 1;
pop = 0;
stack[++top] = source[i];
if(tmp > max)
{
max = tmp;
end = tend;
}
tmp = 0;
}
else if(pop == 0)
{
stack[++top] = source[i];
}
}
}
else if(top == 1)
{
stack[++top] = source[i];
}
}
if(tmp > max)
{
max = tmp;
end = tend;
}
return max;
}
int main()
{
int end = 0;
char source[MAX] = "abcicbbcdefggfed";
int max = getLongestEvenPalindrome(source, end);
cout << max << endl;
for(int i = max  1; i >= 0; i)
{
cout << source[end  i];
}
return 0;
}

Gabriel
May 15, 2013 if we use greedy algorithm, the greedy standard is using the minimum number of coins to form the result.
First, order the coins array by their values, after that, the value will be in nondescending order.
Second, search the array from the largest point.
If the largest value is equal to the 'A', we set the element has been visited;
else if the largest value is less than 'A', we set the element has been visited, and search the elements which can be added to get 'A',
if we should add three or more values to get 'A', we can also use a temp value to replace 'A';
if the largest value is larger than 'A', just ignore it and set the element has been visited.
This method can ensure we use the least number of coins to get 'A'.
I think at first we should understand the question, as we know, a binary tree has three traverse orders, using anyone we can get an order, we can also call this order as one serialization of the binary tree.
And you know if we know the order of
1) inorder and preorder or 2) inorder and postorder we can construct a binary tree,
if we only know the preorder and postorder, we can't construct a binary tree, I don't know whether the question has some relationship with this knowledge.
But in my opinion, to serialize or deserialize a Binary tree, the operations all need a order of the Binary tree's elements.
That a good idea. I also wrote the code.
It will be better to use vectors instead of array in real applications.
struct pn
{
int n; /* belong to which array */
int d; /* the data value */
pn(int _n, int _d) { n = _n; d = _d; }
pn(const pn& _pn) { n = _pn.n; d = _pn.d; }
};
inline void swap(pn& a, pn& b) { pn c = a; a = b; b = c; }
void adjust(int n, pn a[])
{
int i = 0, max = 0;
int l = 0, r = 0;
for(i = n / 2; i >= 0; i)
{
max = i;
l = 2 * i + 1;
r = 2 * i + 2;
if(l < n && a[l].d > a[max].d) { max = l; }
if(r < n && a[r].d > a[max].d) { max = r; }
if(max != i) { swap(a[max], a[i]); }
}
}
void heapsort(int n, pn a[])
{
int i = 0;
adjust(n, a);
for(i = n  1; i > 0; i)
{
swap(a[0], a[i]);
adjust(i, a);
}
}
int main()
{
int i = 0, j = 0;
const int m = 3;
const int n = 5;
int ms = 0, me = 0;
int ts = 0, te = 0;
int a[m][n] = { {4, 10, 15, 24, 26}, {0, 9, 12, 20, 35}, {5, 18, 22, 30, 50} };
int cur[m] = {1, 1, 1}; /* record the current positions of each array which haven't been used */
pn heap[m] = {pn(0, a[0][0]), pn(1, a[1][0]), pn(2, a[2][0])};
heapsort(m, heap);
ms = heap[0].d;
me = heap[m  1].d;
while(true)
{
heapsort(m, heap);
ts = heap[0].d;
te = heap[m  1].d;
/* if the current range is smaller than the minimum range */
if(te  ts < me  ms) { ms = ts; me = te; }
/* if the subarray which the smallest element comes from hasn't to the end */
if(cur[heap[0].n] != n)
{
heap[0].d = a[heap[0].n][cur[heap[0].n]];
cur[heap[0].n] += 1;
}
else
{
break;
}
}
cout << ms << endl;
cout << me << endl;
return 0;
}

Gabriel
May 04, 2013 int n = 0;
int board[MAX][MAX];
bool g_visited[MAX][MAX];
vector<vector<int> > res;
vector<vector<int> > g_px;
vector<vector<int> > g_py;
int mlength = INT_MIN;
int dx[4] = {1, 0, 1, 0};
int dy[4] = {0, 1, 0, 1};
inline int abs(int x) { return x > 0 ? x : x; }
void dfs(int x, int y, vector<int> current, vector<int> px, vector<int> py, bool visited[][MAX])
{
int change = 0, i = 0;
for(i = 0; i < 4; i++)
{
if(x + dx[i] >= 0 && x + dx[i] < n &&
y + dy[i] >= 0 && y + dy[i] < n &&
!visited[x + dx[i]][y + dy[i]] &&
abs(board[x][y]  board[x + dx[i]][y + dy[i]]) == 1)
{
change = 1;
visited[x + dx[i]][y + dy[i]] = true;
current.push_back(board[x + dx[i]][y + dy[i]]);
px.push_back(x + dx[i]);
py.push_back(y + dy[i]);
dfs(x + dx[i], y + dy[i], current, px, py, visited);
visited[x + dx[i]][y + dy[i]] = false;
current.pop_back();
px.pop_back();
py.pop_back();
}
}
if(!change && current.size() > 0)
{
if((int)current.size() >= mlength)
{
if((int)current.size() > mlength)
{
res.clear();
g_px.clear();
g_py.clear();
mlength = current.size();
}
res.push_back(current);
g_px.push_back(px);
g_py.push_back(py);
for(i = 0; i < (int)current.size(); i++)
{
printf("%d ", current[i]);
}
printf("\n");
}
}
}
bool checkpath(int x, int y)
{
bool ret = false;
for(int i = 0; i < (int)g_px.size() && !ret; i++)
{
for(int j = 0; j < (int)g_px[i].size() && !ret; j++)
{
if(g_px[i][j] == x && g_py[i][j] == y)
{
ret = true;
}
}
}
return ret;
}
int find()
{
int i = 0, j = 0;
vector<int> current;
vector<int> px;
vector<int> py;
bool visited[MAX][MAX];
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
if(!checkpath(i, j))
{
current.clear();
px.clear();
py.clear();
memset(visited, 0, sizeof(visited));
visited[i][j] = true;
current.push_back(board[i][j]);
px.push_back(i);
py.push_back(j);
dfs(i, j, current, px, py, visited);
}
}
}
return 0;
}
int main()
{
int i = 0, j = 0;
memset(board, 0, sizeof(board));
scanf("%d", &n);
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
scanf("%d", &board[i][j]);
}
}
find();
return 0;
}

Gabriel
April 19, 2013 Dhass's method also can work, but if the input number is larger than 32 or 64, it won't work.
Use a array (integer or bool), which length is n,
as {x(n), x(n1), ..., x(1)} and x(i) = 1 or 0 (true or false),
imitating the process, add 1 (or do bit operation from x(1) to x(n).
Repeat the process until the array become all 0 (or all false).
@aka
And there is another problem, if some point has been pushed into the longest snakes, we can judge, this two paths' start point, we call them p1(x1, y1) and p2(x2, y2), and call the two paths P1={} and P2={}.
If p2 belongs to P1 which means the point has been visited and checked, can be ignored.
If p2 doesn't belong to P1, the program can be processed continue, even when some points exist in the two paths.
@aka
Yes, I have to admit the algorithm can't avoid the situation that it maybe traverse the sampe path two times, like {1, 2, 3, 4} and {4, 3, 2, 1}.
Since if I use the recursive method, the code structure ensure I won't traverse the same path two times, for example, I won't traverse {1, 2, 3, 4} again. Since the loop will turn to the other directions, and won't traverse the same direction of any point.
Two different path may share some elements, such as {1, 2, 3, 4} and {1, 2, 3, 2}
@aka
I use mlength to remember the length of current longest snakes, and use map<int, vector<int> > to remember all snakes whose length are all mlength.
Using recursive method as I wrote above, I use vector<int> current to remember the snake contents till this point, when you visited some point and can't find any neighbour of can satisfy the condition, then the snake can't be longer.
And use the length of current to compare with mlength,
(1) if it's shorter than the mlength snakes, ignore it;
(2) if it's longer than the mlength snakes, clear the map<int, vector<int> > res, push the snake into it;
(2) if it's equal to the mlength snakes, then push it to the set.
From any point of the graph;
Then use dfs to search its neighbours
if it satisfies the condition: the difference of them is 1 or 1
then add the neighbout to some place
recursively, from this point repeat the process
to other neighbour, till search its four direct neighbours
if its neighbours are all been visited all don't satisfy the condition, judge its length is larger than the default max length(Initiall, it maybe INT_MIN),
if its length is larger than the default one or saved ones, modify the max_length, and push the list to some place.
Below is the code:
#include <cstdio>
#include <cstring>
#include <climits>
#include <vector>
#define MAX 100
using namespace std;
int n = 0;
int board[MAX][MAX];
vector<vector<int> > res;
int mlength = INT_MIN;
int dx[4] = {1, 0, 1, 0};
int dy[4] = {0, 1, 0, 1};
inline int abs(int x) { return x > 0 ? x : x; }
void dfs(int x, int y, vector<int> current, bool visited[][MAX])
{
int change = 0, i = 0;
for(i = 0; i < 4; i++)
{
if(x + dx[i] >= 0 && x + dx[i] < n &&
y + dy[i] >= 0 && y + dy[i] < n &&
!visited[x + dx[i]][y + dy[i]] &&
abs(board[x][y]  board[x + dx[i]][y + dy[i]]) == 1)
{
change = 1;
visited[x + dx[i]][y + dy[i]] = true;
current.push_back(board[x + dx[i]][y + dy[i]]);
dfs(x + dx[i], y + dy[i], current, visited);
visited[x + dx[i]][y + dy[i]] = false;
current.pop_back();
}
}
if(!change && current.size() > 0)
{
if((int)current.size() >= mlength)
{
if((int)current.size() > mlength)
{
res.clear();
mlength = current.size();
}
res.push_back(current);
for(i = 0; i < (int)current.size(); i++)
{
printf("%d ", current[i]);
}
printf("\n");
}
}
}
int find()
{
int i = 0, j = 0, k = 0;
vector<int> current;
bool visited[MAX][MAX];
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
current.clear();
memset(visited, 0, sizeof(visited));
visited[i][j] = true;
current.push_back(board[i][j]);
dfs(i, j, current, visited);
}
}
return 0;
}
int main()
{
int i = 0, j = 0;
memset(board, 0, sizeof(board));
scanf("%d", &n);
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
scanf("%d", &board[i][j]);
}
}
find();
return 0;
}

Gabriel
April 18, 2013 c++ code:
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
using namespace std;
int main()
{
int i = 0;
int t = 0;
int n = 0;
map<int, vector<int> > position;
scanf("%d", &n);
for(i = 0; i < n; i++)
{
scanf("%d", &t);
position[t].push_back(i);
}
for(map<int, vector<int> >::iterator it = position.begin(); it != position.end(); it++)
{
t = 0;
if(it>second.size() > 0)
{
t = it>second[it>second.size()  1]  it>second[0];
}
printf("max(%d)=%d\n", it>first, t);
}
return 0;
}

Gabriel
April 17, 2013 #include <cstdio>
using namespace std;
void getMax(int& _buy, int& _sell, int n, int price[])
{
int buy = price[0];
int sell = price[1]  price[0];
for(int i = 2; i < n; i++)
{
buy = price[i  1] < buy ? price[i  1] : buy;
if(price[i]  buy > sell)
{
_buy = buy;
_sell = price[i];
sell = price[i]  buy;
}
}
}
int main()
{
int n = 0;
int a[100];
int buy = 0, sell = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
getMax(buy, sell, n, a);
printf("%d %d\n", buy, sell);
return 0;
}

Gabriel
April 16, 2013 Test case:
1) by value, to test the correction of the function
1. normal cases: like some integers in some fixed range
2. very large cases: give some integers which are out of integer range
3. blank cases: give {}
2) by element quantity, to test the speed of the function
1. small set
2. large set
3) give some special test cases, want have the results expected or speed demand
If the integer values of s1 and s2 are all larger than 32bit, or 64bit integer, what will happen?
Thus I think we should handle them as strings, instead of converting them to integers.
Below is my C++ code.
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
bool isLarger(char* s1, char* s2)
{
bool flag = false;
int l1 = strlen(s1), l2 = strlen(s2), l = l1 > l2 ? l1 : l2, i = 0;
char* f1 = new char[l];
char* f2 = new char[l];
for(i = 0; i < l1; f1[i] = s1[i], i++);
for(; i < l; f1[i++] = '9');
for(i = 0; i < l2; f2[i] = s2[i], i++);
for(; i < l; f2[i++] = '9');
for(i = 0; i < l; i++)
{
if(s1[i] < s2[i])
{
flag = true;
break;
}
}
delete f1;
delete f2;
return flag;
}
char* spellNumber(char* s1, char* s2)
{
int i = 0;
char* spell = new char[strlen(s1) + strlen(s2) + 1];
if(isLarger(s1, s2))
{
for(i = 0; i < strlen(s2); i++)
{
spell[i] = s2[i];
}
for(; i < strlen(s1) + strlen(s2); i++)
{
spell[i] = s1[i  strlen(s2)];
}
}
else
{
for(i = 0; i < strlen(s1); i++)
{
spell[i] = s1[i];
}
for(; i < strlen(s1) + strlen(s2); i++)
{
spell[i] = s2[i  strlen(s1)];
}
}
spell[i] = '\0';
return spell;
}
int main()
{
char* s1 = "1243";
char* s2 = "5634";
char* spell = spellNumber(s1, s2);
cout << spell << endl;
delete spell;
return 0;
}
Typical graph issue, using BFS and remember the visit state can solve it.
 Gabriel March 19, 2019But you should clarify one issue at first, each node can only be access once or not.