/**This one passed both small and large judge.
1. Find the root : Last element in postorder is the root;
2. Find the position of the root in inorder.
The best strategy is to count the size of the left tree using inorder,
then use the size to split the postorder.
*/
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include <vector>
#include <algorithm>
#include <map>
#include <deque>
#include <array>
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
inline size_t valuePos(vector<int> const& v, int value){
return distance(v.begin(),find(v.begin(), v.end(), value));
}
TreeNode* build(vector<int> const& inorder, int const in_first, int const in_last,
vector<int> const& postorder, int const post_first, int const post_last){
if (post_last-post_first < 0) return NULL;
TreeNode* root = new TreeNode(postorder[post_last]);
if (post_last - post_first == 0) return root;
size_t const r_in = valuePos(inorder, root->val);//can narrow down the search range
size_t const sizeL = r_in - in_first;
root->left = build(inorder, in_first, r_in-1,
postorder, post_first, post_first+sizeL-1);
root->right = build(inorder, r_in+1, in_last,
postorder, post_first+sizeL, post_last-1);
return root;
}
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (inorder.empty()) return NULL;
return build(inorder, 0, inorder.size()-1,postorder, 0,postorder.size()-1);
}
};
int main(){
array<int, 3> a = {1,2,3};
vector<int> q(a.begin(),a.end());
vector<int> v(a.rbegin(),a.rend());
Solution s;
auto result = s.buildTree(q,v);
cout<<result->val<<endl;
return 0;
}
Friday, November 23, 2012
Construct Binary Tree from Inorder and Postorder Traversal
http://www.leetcode.com/onlinejudge
Wednesday, November 14, 2012
closely hovering
/**30 Answers
From the set of natural integer numbers
Let x = 1234 = {1, 2, 3, 4}
Let y = 2410 = {2, 4, 1, 0}
Write an algorithm to compute the rearrangement of x that is closest
to y but still greater than y. Both x and y have the same number of digits.
So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is
greater than y = 2410 and closer than any other arrangements of x.
And whats the time complexity of this algorithm?
- CameronWills on October 30, 2012 in United States | Report Duplicate
*/
/**In another word, we want to find a number as small as possible,
call it hoverNumber;
First we construct the largest number from x. If this number is larger than y,
it proves the hoverNumber exists for such x,y.
Next, find the exact hoverNumber. Using DP and DFS.
Two cases:
1. when the higher digits are equal to y. Then the current digit can select
from the equal digit of y, and up;
2. when the higher digits are larger than y already. Then the current digit
should be as small as possible, selecting from the remaining digit pool.
*/
#include <iostream>
#include <vector>
#include <set>
using namespace std;
unsigned int parseInt(vector<unsigned int> const& v){
//in vector v, v[0] is the highest digit position
unsigned int result = 0;
for(size_t ii = 0; ii < v.size(); ++ii){
result = (result<<3) + (result<<1)+ v[ii];//10 = 8 + 2
}
return result;
}
vector<unsigned int> parseChar(unsigned int number){
vector<unsigned int> result;
while(number){
result.push_back(number%10);
number /= 10;
}
return vector<unsigned int>(result.rbegin(),result.rend());
}
ostream& operator<<(ostream& os, vector<unsigned int>const& v){
for(size_t ii = 0; ii < v.size(); ++ii){
os<<v[ii];
}
return os;
}
int compV(vector<unsigned int> const& v1, vector<unsigned int>const& v2,
size_t end_index){//assume v1.size() == v2.size()
//range [0, end_index)
//return -1 if v1 < v2
//return 0 if v1 == v2
//return +1 if v1 > v2
if (!end_index) return 0;
for(size_t ii = 0; ii < end_index; ++ii){
if (v1[ii] < v2[ii]) return -1;
if (v1[ii] > v2[ii]) return 1;
}
return 0;
}
int compV(vector<unsigned int> const& v1, vector<unsigned int>const& v2){
return compV(v1,v2,v1.size());
}
bool operator<(vector<unsigned int> const& v1, vector<unsigned int>const& v2){
return (-1 == compV(v1,v2,v1.size()));
}
int hoverNumCalc(set<unsigned int>& digit_pool, vector<unsigned int>& result,
vector<unsigned int> const& v_y){//assume the solution exists
static int digit_level = 0;//inception...level, can use for vector index
set<unsigned int>::iterator it = digit_pool.begin();
if (digit_level + 1 == v_y.size()){//or use digit_pool.size() == 1
//last element, only one way to construct the number
result.push_back(*it);
if (compV(result, v_y) <= 0){//not a good one
result.pop_back();
return -1;
} else return 0;//succeed!
}//if last one element
if (0 == compV(result, v_y, digit_level)){//high digits the same
//choose a minimum number that is barely larger than y-digit
it = digit_pool.lower_bound(v_y[digit_level]);
}
for (;it != digit_pool.end();){
result.push_back(*it);
digit_pool.erase(it++);
++digit_level;
if (!hoverNumCalc(digit_pool, result, v_y)) return 0;//relay the success
--digit_level;
digit_pool.insert(result.back());
result.pop_back();
}//for it
return -1;
}
unsigned int hoverNumber(unsigned int number_x, unsigned int number_y){
vector<unsigned int> vx(parseChar(number_x));
set<unsigned int> sx(vx.begin(),vx.end());//small to big
vector<unsigned int> vx_max(sx.rbegin(), sx.rend());//big to small
vector<unsigned int> vy(parseChar(number_y));
if (!(vy < vx_max)) return 0;//hoverNumber does not exist
vx.resize(0);
vx.reserve(vy.size());
hoverNumCalc(sx, vx, vy);
return parseInt(vx);
}
int main(){
cout<<"Hello"<<endl;
unsigned int a = 1234;
unsigned int const b = 5678;//2410;
unsigned int result = hoverNumber(a,b);
if (!result) cout<<"No way!"<<endl;
else cout<<result<<" is hovering over "<<b<<endl;
}
Big number
/**Define a structure / class to hold a very big number
(way bigger than bigint) and add a member functions to
increment the number by 1 and decrement the number by 1
- Dee on November 06, 2012 in United States | Report Duplicate */
/**Use an array to simulate bits.
Need to take care of carry's when add/substract.
One trivial bug: negative zero.
*/
#include <array>
#include <algorithm>
#include <iostream>
using namespace std;
class HugeNumber{
private:
static const int DIGITS = 1000;
array<unsigned short, DIGITS> number;//number[0] is the lowest digit
bool negative_flag;
public:
HugeNumber(){
number.fill(0);negative_flag = false;
}
HugeNumber(int number_int){
this->assign(number_int);
}
HugeNumber(HugeNumber const& n2){
negative_flag = n2.negative_flag;
for(unsigned int ii = 0; ii < DIGITS; ++ii)
number[ii] = n2.number[ii];
}
HugeNumber& assign(int number_int){
negative_flag = (number_int < 0);
if (negative_flag) number_int = -number_int;
for(unsigned int ii = 0; number_int; ++ii){
number[ii] = number_int%10;
number_int /= 10;
}
return *this;
}//assign
HugeNumber& operator++(){
if (negative_flag){
if (count(number.begin(),number.end(), 0) == DIGITS){//0
negative_flag = false;
++number[0];
return *this;
}
negative_flag = false;
--(*this);
negative_flag = true;
return (*this);
}
++number[0];
for(unsigned int ii = 0; ii < DIGITS-1 && number[ii] >= 10; ++ii){
number[ii] -= 10;
++number[ii+1];
}
return *this;
}
HugeNumber& operator--(){
if (count(number.begin(), number.end(), 0) == DIGITS){
negative_flag = true;
++number[0];
return *this;
}
if (negative_flag){
negative_flag = false;
++(*this);
negative_flag = true;
return (*this);
}
for(unsigned int ii = 0; ii < DIGITS; ++ii){
number[ii] = 9 - number[ii];
}
++(*this);
for(unsigned int ii = 0; ii < DIGITS; ++ii){
number[ii] = 9 - number[ii];
}
return *this;
}
void output(ostream& os) const{
if (negative_flag) os<<'-';
for(unsigned int ii = DIGITS-1; ii > 0; --ii){
if (!number[ii]) continue;
os<<number[ii];
}
os<<number[0];//in case all digits are zero
}
};
ostream& operator<<(ostream& os, HugeNumber& const number){
number.output(os);
return os;
}
int main(){
cout<<"hello"<<endl;
HugeNumber hn;
hn.assign(-2);
cout<<hn<<endl;
++hn;
cout<<hn<<endl;
++hn;
cout<<hn<<endl;
++hn;
cout<<hn<<endl;
++hn;
cout<<hn<<endl;
++hn;
cout<<hn<<endl;
--hn;
cout<<hn<<endl;
--hn;
cout<<hn<<endl;
--hn;
cout<<hn<<endl;
--hn;
cout<<hn<<endl;
--hn;
cout<<hn<<endl;
return 0;
}
Word evolution
/**26 Answers
Given a source string and a destination string write a program to display
sequence of strings to travel from source to destination. Rules for traversing:
1. You can only change one character at a time
2. Any resulting word has to be a valid word from dictionary
Example: Given source word CAT and destination word DOG , one of the valid
sequence would be
CAT -> COT -> DOT -> DOG
Another valid sequence can be
CAT -> COT - > COG -> DOG
One character can change at one time and every resulting word has be a valid
word from dictionary
- Dee on November 06, 2012 in United States | Report Duplicate
*/
/**This is a graph problem. We define "neighbor" as the words off by only
one letter.
First step, find all the neighbors of the source word. Then find the neighbors
of the neighbors... and so on, until one of them is the destination word.
*/
/**The function below has memory leak... pretty bad that sometime it eats up
1G memory...
The dictionary I used was from Ubuntu 12.04 LTS, /usr/share/dict/words
*/
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <memory>
#include <set>
#include <deque>
using namespace std;
set<string> dictParser(string fileName = "words.txt"){
ifstream dictFile(fileName);
set<string> result;
if (!dictFile.good()) return result;
dictFile.seekg (0, ios::end);
size_t const fileLength = dictFile.tellg();
dictFile.seekg (0, ios::beg);
char* readInBuffer = new char[fileLength];
dictFile.read(readInBuffer, fileLength);
stringstream allWords(readInBuffer);
delete[] readInBuffer;
dictFile.close();
string word;
while(!allWords.eof()){
allWords >> word;
result.insert(word);
}
return result;
}
class Node{
public:
Node(string name):word(name),parent(0){}
string word;
vector<Node* > children;
Node* parent;
};
bool off_by_one(string const& s1, string const& s2){
if (s1.length() != s2.length()) return false;
int counter = 0;
for(int ii = 0; ii < s1.length(); ++ii){
if (s1[ii] != s2[ii]) ++counter;
}
return (1 == counter);
}
vector<string> mutationPath(string const& source, string& const dest,
set<string>& dict){
vector<string> result;
Node* sp = new Node(source);
dict.erase(source);
deque<Node* > frontier;
frontier.push_back(sp);
while(!frontier.empty()){
Node* node = frontier.front(); frontier.pop_front();
string const word = node->word;
for (auto it = dict.begin(); it != dict.end();){
string const neighbor(*it);
if (neighbor.size() != dest.size()){dict.erase(it++); continue;}
if (off_by_one(word, neighbor)){
if (dest == neighbor){
result.push_back(neighbor);
while(node){
result.push_back(node->word);
node = node->parent;
}
return vector<string>(result.rbegin(),result.rend());
}
dict.erase(it++);
auto it_n = new Node(neighbor);
node->children.push_back(it_n);
node->children.back()->parent = node;
frontier.push_back(it_n);
}else ++it;
}//for it
}//while not empty
return result;
//--------------------------
}
int main(){
set<string> dict(dictParser());//it is sorted
cout<<dict.size()<<endl;
string sourceWord("cat");
string destWord("dog");
vector<string> path(mutationPath(sourceWord, destWord, dict));
for(int ii = 0; ii < path.size(); ++ii){
cout << path[ii] <<endl;
}
return 0;
}
And here is an improved version using smart pointers that avoids memory leak:
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <memory>
#include <set>
#include <deque>
using namespace std;
set<string> dictParser(string fileName = "words.txt"){
ifstream dictFile(fileName);
set<string> result;
if (!dictFile.good()) return result;
dictFile.seekg (0, ios::end);
size_t const fileLength = static_cast<size_t>(dictFile.tellg());
dictFile.seekg (0, ios::beg);
shared_ptr<char> readInBuffer(new char[fileLength]);
dictFile.read(readInBuffer.get(), fileLength);
stringstream allWords(readInBuffer.get());
//delete[] readInBuffer;
dictFile.close();
string word;
while(!allWords.eof()){
allWords >> word;
result.insert(word);
}
return result;
}
class Node{
public:
Node(string name):word(name){}
string word;
vector<shared_ptr<Node> > children;
weak_ptr<Node> parent;
};
template <typename T>
int edit_distance(T const& s1, T const& s2){
int const s1s = s1.size(), s2s = s2.size();
vector<vector<int>> matrix(s1s+1, vector<int>(s2s+1));
//s2 horizontal, s1 vertical
for(int ii = 0; ii <= s1s; ++ii) matrix[ii][0] = ii;
for(int ii = 0; ii <= s2s; ++ii) matrix[0][ii] = ii;
for(int ii = 1; ii <= s1s; ++ii){
for(int jj = 1; jj <= s2s; ++jj){//scan from left to right
//line by line
matrix[ii][jj] = min(min(matrix[ii-1][jj], matrix[ii][jj-1])+1,
matrix[ii-1][jj-1]+static_cast<int>(s1[ii-1] != s2[jj-1]));
}//for jj
}//for ii
return matrix[s1s][s2s];
}
bool off_by_one(string const& s1, string const& s2){
if (s1.length() != s2.length()) return false;
int counter = 0;
for(unsigned int ii = 0; ii < s1.length(); ++ii){
if (s1[ii] != s2[ii]) ++counter;
}
return (1 == counter);
}
vector<string> mutationPath(string const& source, string const& dest,
set<string>& dict){
vector<string> result;
shared_ptr<Node> sp(new Node(source));
dict.erase(source);
deque<shared_ptr<Node> > frontier;
frontier.push_back(sp);
while(!frontier.empty()){
shared_ptr<Node> node(frontier.front()); frontier.pop_front();
string const word = node->word;
for (auto it = dict.begin(); it != dict.end();){
string const neighbor(*it);
if (neighbor.size() != dest.size()){dict.erase(it++); continue;}
if (off_by_one(word, neighbor)){
if (dest == neighbor){
result.push_back(neighbor);
while(node){
result.push_back(node->word);
node = node->parent.lock();
}
return vector<string>(result.rbegin(),result.rend());
}
dict.erase(it++);
shared_ptr<Node> it_n(new Node(neighbor));
node->children.push_back(it_n);
node->children.back()->parent = node;
frontier.push_back(it_n);
}else ++it;
}//for it
}//while not empty
return result;
//--------------------------
}
int main(){
set<string> dict(dictParser());//it is sorted
cout<<dict.size()<<endl;
string sourceWord("cat");
string destWord("dog");
vector<string> path(mutationPath(sourceWord, destWord, dict));
for(int ii = 0; ii < path.size(); ++ii){
cout << path[ii] <<endl;
}
return 0;
}
Tuesday, November 13, 2012
Kth Largest element of a sorted matrix
/**Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
- 646 on November 23, 2010 | Report Duplicate */
/**For me, it is easier to think of the P-th smallest element
and then use K = N*N-P
For example we have a 4*4 matrix:
1 10 19 20
2 22 30 40
21 30 40 50
39 40 50 60
The numbers are trivial, but the orders and the positions are important.
[0,0] is the smallest.
Ignore the boundary case for now. Every element has two definite directions:
going right or down, which results a larger number.
It is simpler than Dajikstra, we only need to keep the unvisited frontier
elements in a priority queue. Every time we pop an element, mark it visited,
and immediately push in its two neighbors, i.e. right and down neighbors.
*/
/**In C++, the default priorit_queue is a max heap, especially when less-than
is defined.
*/
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
#include <iostream>
#include <array>
using namespace std;
template <typename T>
class Solution{
typedef tuple<T, int, int> Element;
class ElementMore{
public:
bool operator() (const Element& lhs, const Element& rhs) const{
return get<0>(lhs) > get<0>(rhs);
}
};//class ElementLess
public:
T getSmallRank(vector<vector<T>> const& matrix, int const k){
if (matrix.empty()) return 0;
int const N = matrix.size();
if (N != matrix[0].size()) return 0;//not a square matrix
if (k < 1 || k > N*N) return 0;
//k is the desired rank to return
vector<vector<T>> visitFlag;
visitFlag.resize(matrix.size());
for(auto it = visitFlag.begin(); it != visitFlag.end(); ++it) it->resize(matrix.size());
//init visitFlag to all 0. label 1 for visited
Element element = make_tuple(matrix[0][0], 0, 0);//<value, row, col>
priority_queue<Element, vector<Element>, ElementMore> frontier;
frontier.push(element);
visitFlag[0][0] = 1;
for(int rank = 1; rank < k; ++rank){
element = frontier.top(); frontier.pop();
int const row = get<1>(element);
int const col = get<2>(element);
if (col + 1 < N && !visitFlag[row][col+1]){//element has a right neighbor
frontier.push(make_tuple(matrix[row][col+1],row,col+1));
visitFlag[row][col+1] = 1;
}//right neighbor
if (row + 1 < N && !visitFlag[row+1][col]){//has a down neighbor
frontier.push(make_tuple(matrix[row+1][col],row+1,col));
visitFlag[row+1][col] = 1;
}//down neighbor
}//for rank
return get<0>(frontier.top());
}//getSmallRankP
T getBigRank(vector<vector<T>> const& matrix, int const k){
return getSmallRank(matrix, matrix.size()*matrix.size()-k+1);
}
};
int main(){
cout<<"HEllo"<<endl;
array<int, 4> a = {1 , 10, 19, 20};
array<int, 4> b = {2 , 22, 30, 40};
array<int ,4> c = {21, 33, 40, 50};
array<int, 4> d = {39, 40, 51, 60};
//ranks: 1 ,2, 3, 4, 5, 6, 7
//elements: 1 ,2, 10, 19, 20, 21,22
//and rank 15 is 51
//and rank 16 is 60
vector<vector<int>> matrix;
matrix.resize(4);
matrix[0].assign(a.begin(),a.end());
matrix[1].assign(b.begin(),b.end());
matrix[2].assign(c.begin(),c.end());
matrix[3].assign(d.begin(),d.end());
Solution<int> s;
for(int ii = 1; ii <=7; ++ii){
auto result = s.getSmallRank(matrix,ii);
cout<<result<<endl;
}
cout<< s.getSmallRank(matrix, 15)<<endl<<endl;
cout<< s.getSmallRank(matrix, 16)<<endl<<endl;
cout<< s.getBigRank(matrix, 2)<<endl<<endl;
}
Interleave strings
The best way is to use dynamic programing. Here is an example: The two short strings are b="daba" and a="cbaa", and the long string is "dabacbaa". They are indexed 1 strings. We start from the last elements.
we find out that [4,4] is true.
Link to the C++ code
- Step1. Both a[4] and b[4] matches the element c[8], so the true/false grid [4,4] depends on its two neighbors, [4,3] and [3,4].
- Step2. For grid[4,3], a[4] matches c[7], so dependency goes up to [3,3].
- For grid[3,4], both a[3] and b[4] matches c[7], so dependency goes to two neighbors:[2,4] and [3,3]
- Step3. For grid[3,3], b[3] matches c[6], so go left to [3,2]
- For gird [2,4], a[2] matches c[6], so go up to [1,4]
- Step4. For grid[3,2], no matches to c[5], halt (mark false)
- For grid[1,4], a[1] matches c[5], go up to [0,4]
- Step5-9. [0,4]->[0,3]->[0,2]->[0,1]->[0,0]
we find out that [4,4] is true.
Link to the C++ code
/**Update 12/01/2012. This solution is not correct.
85 Answers
Three strings say A,B,C are given to you. Check weather 3rd string is
interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)
- learn on August 27, 2012 in United States | Report Duplicate
*/
/**Hints from the comments.
Simple case: pointers to A,B,C are pA,pB,pC. Compare pA (or pB) agains
pC, if matches, ++pA (or ++pB) if none of pA or pB matches, return false
Duplication case: if pA and pB points to the same character, we call it
a conflict. The conflict character is pushed into a FIFO queue, and do
both ++pA and ++pB. When a non-conflict character appears, register it,
pA, for example. Keep searching until pA does not match the next character,
then you HAVE TO consider the conflict queue before using pB.
The queue should have a higher priority than pA/pB, since the queue stores
elemenens BEFORE the pointers.
When the queue is not empty, the match process switching between pA and pB
are forbidden. Since if pA is in process, the queue equivalently stores
elements BEFORE current pB, so skipping the queue directly to pB
is not allowed.
*/
#include <string>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
class Solution{
public:
bool isInterleave(string const& A, string const& B, string const& C){
if (C.length()!= A.length() + B.length()) return false;
deque<int> conflict_que;
int conflict_flag = 0;
for(int aii = 0, bii = 0, cii = 0; cii < C.length(); ++cii){
if (!conflict_que.empty() && conflict_que.front() == C[cii]){
conflict_que.pop_front();
continue;
}//conflict_que has a match
if (A[aii] == B[bii]){
if (A[aii] == C[cii]){
++aii; ++bii; conflict_flag = 0;
conflict_que.push_back(A[aii]);
continue;
} else return false;//A==B, but no match for C
} else if (A[aii] == C[cii]){
if (!conflict_que.empty() && conflict_flag == 2) return false;
//attemp to jump over conflict_que from B
++aii; conflict_flag = 1;
continue;
} else if (B[bii] == C[cii]){
if (!conflict_que.empty() && conflict_flag == 1) return false;
++bii; conflict_flag = 2;
continue;
} else return false;//no match at all, check queue
}//for cii
return true;
}//isInterleave
};
int main(){
cout<< "Hello"<<endl;
string A("aaa");
string B("abc");
string C("aabcaa");
Solution s;
bool result = s.isInterleave(A,B,C);
cout << result <<endl;
A = "abcd"; B ="xyz"; C = "axybczd";
result = s.isInterleave(A,B,C);
cout<< result <<endl;
return 0;
}
Subscribe to:
Posts (Atom)