BIN
BAN USERThis is O(nlogn) solution.
vector<vector<int>> find3Sum(vector<int> &num, int sum)
{
sort(num);
int n = num.size();
vector<vector<int>> vv;
for(int i=0, j=n-1; i<j;)
{
if (num[i] + num[j] >= sum)
{
j--;
}
else
{
int k = binarySearch(num, i+1, j-1, sum - num[i] - num[j]);
if (k>= 0)
{
vector<int> v;
v.push_back(num[i]);
v.push_back(num[j]);
v.push_back(num[k]);
vv.push_back(v);
}
i++;
}
}
return vv;
}
int permutation(int n, int k)
{
int u = 1;
for(int i=0; i<k; i++)
{
u *= n-i;
}
return u;
}
int combination(int n, int k)
{
return permutation(n, k)/permutation(k,k);
}
int seeWaysOfTopKFromOneSide(int n, int k)
{
if (n == k)
return 1;
if (n < k)
{
return 0;
}
if (k == 1)
return 1;
int c = 0;
for(int m=0; m<n; m++)
{
c+= combination(n-1, m) * seeWaysOfTopKFromOneSide(m, k-1) * permutation(n-m, n-m);
}
return c;
}
int seeWaysOfTopKFromBothSides(int n, int l, int r)
{
int c = 0;
for(int m=0; m<n; m++)
{
c+= combination(n-1, m) * seeWaysOfTopKFromOneSide(m, l-1) * seeWaysOfTopKFromOneSide(n-m-1, r-1);
}
return c;
}
bitwise and easier to be understandable
int findIntOnceOfThrees(int* A, int n)
{
int M[32]={0x01};
for(int i= 1; i<32; i++)
{
M[i] = M[0] << i;
}
int C[32] = {0};
for(int i=0; i<n; i++)
{
for(int j=0; j<32; j++)
{
if (A[i] & M[j])
{
C[j] = (C[j]+1)%3;
}
}
}
int ret = 0;
for(int i=0; i<32; i++)
{
if (C[i])
{
ret |= M[i];
}
}
return ret;
}
DP, o(n^2)
// before passing into this function, A is sorted
// which takes additional n*logn time
int biggestArithmeticSequence(int* A, int n)
{
int max = 0;
vector<unordered_map<int,int>> disMap(n);
for(int i=1; i<n; i++)
{
for(int j=i-1; j>=0; j--)
{
int dis = A[i]-A[j];
int cmax = 1;
if (disMap[j].find(dis) != disMap[j].end())
{
cmax += disMap[j][dis];
}
disMap[j][dis] = cmax;
if (cmax > max)
{
max = cmax;
}
}
}
return max;
}
struct SumNode3{
int i;
int j;
int k;
int sum;
int key;
SumNode3(int* A, int i, int j, int k):i(i), j(j), k(k), sum(A[i] + A[j] + A[k]){
key = A[i] + 100*A[j] + 10000*A[k];
}
SumNode3(int* A, int i, int j):i(i), j(j), k(-1), sum(A[i] + A[j]){
key = A[i] + 100*A[j];
}
SumNode3(int* A, int i):i(i), j(-1), k(-1), sum(A[i]){
key = A[i];
}
};
vector<int> sortWithSum3(int*A, int n, int ksmall){
vector<SumNode3> sums;
sums.push_back(SumNode3(A, 0));
sums.push_back(SumNode3(A, 0, 1));
sums.push_back(SumNode3(A, 0, 1, 2));
unordered_set<int> set;
set.insert(sums[0].key);
set.insert(sums[1].key);
set.insert(sums[2].key);
vector<int> ret;
while(ksmall-- > 0 && !sums.empty())
{
int k = 0;
for(int j=1; j<sums.size(); j++)
{
if (sums[j].sum < sums[k].sum)
{
k = j;
}
}
ret.push_back(sums[k].sum);
cout<<sums[k].sum <<" i="<<sums[k].i<<" j="<<sums[k].j<<" k="<<sums[k].k<<endl;
if (sums[k].j == -1) // {1,2....}
{
if (sums[k].i < n-1)
{
sums[k] = SumNode3(A, sums[k].i+1);
set.insert(sums[k].key);
}
else
{
sums.erase(sums.begin()+k);
}
}
else if (sums[k].k == -1) // { sum(1,2) ....}
{
if (sums[k].i < n-2)
{
SumNode3 next(A, sums[k].i+1, sums[k].i+2);
if (set.find(next.key) == set.end())
{
sums.push_back(next);
set.insert(next.key);
}
}
if (sums[k].j < n-1)
{
sums[k] = SumNode3(A, sums[k].i, sums[k].j+1);
set.insert(sums[k].key);
}
else
{
sums.erase(sums.begin()+k);
}
}
else// { sum(1,2,3) ....}
{
if (sums[k].i < n-3)
{
SumNode3 next(A, sums[k].i+1, sums[k].i+2, sums[k].i+3);
if (set.find(next.key) == set.end())
{
sums.push_back(next);
set.insert(next.key);
}
}
if (sums[k].j < n-2)
{
SumNode3 next(A, sums[k].i, sums[k].j+1, sums[k].j+2);
if (set.find(next.key) == set.end())
{
sums.push_back(next);
set.insert(next.key);
}
}
if (sums[k].k < n-1)
{
sums[k] = SumNode3(A, sums[k].i, sums[k].j, sums[k].k+1);
set.insert(sums[k].key);
}
else
{
sums.erase(sums.begin()+k);
}
}
}
return ret;
}
Try to simplify this questin, we only consider a+b, but not a+b+c.
int node1; // initialize with 0 which represents index of A[0]
vector<Sum2Node> nodes2; // first initialize with A[0]+A[1], it represnets sum from A[i] + A[j], let's use {i, j}
each time, we compare all nodes.
if the min is from node1, then put A[node1] into heap and node1++;
if min is from nodes2[k], in such case, if k == nodes2.size()-1, then we need to compare {i,j} and {i+1, i+2}
if {i+1, i+2} is smaller, we add a new node to nodes2.
both cases we move {i,j} to next {i,j+1}, and if j>=A.size(), remove this node.
e.g. A={1,2,3,4,5,6}
the stack would like:
1
{1,2}
....
6
{1,5}
{2,3}
...
node1=none
{2,4}
...
{2,6}
{3,4}
...
{3,5}
...
{4,5}
Rectangle
int maxRectangle(vector<vector<int>> &matrix)
{
int n = matrix.size();
if (n == 0)
return 0;
int m = matrix[0].size();
for(int i=1; i<n; i++)
{
for(int j=0; j<m; j++)
{
if (matrix[i][j] == 1)
{
matrix[i][j] += matrix[i-1][j];
}
}
}
int max = 0;
for(int i=0; i<n; i++)
{
int v = largestRectangleArea(matrix, m, i);
if (v > max)
{
max = v;
}
}
return max;
}
int largestRectangleArea(vector<vector<int>> &matrix, int m, int k) {
vector<int> vm(m, 0);
vector<int> v;
vector<int> vh;
for(int i = 0;i<m; i++)
{
int h = matrix[k][i];
int start = i;
while (v.size() > 0 && h <= vh[v.size()-1])
{
start = v[v.size()-1];
v.pop_back();
vh.pop_back();
}
v.push_back(start);
vh.push_back(h);
vm[i] = (i-start +1) * h;
}
v.clear();
vh.clear();
int max = 0;
for(int i = m-1;i>= 0; i--)
{
int h = matrix[k][i];
int start = i;
while (v.size() > 0 && h <= vh[v.size()-1])
{
start = v[v.size()-1];
v.pop_back();
vh.pop_back();
}
v.push_back(start);
vh.push_back(h);
vm [i] += (start -i + 1 -1) *h;
if (vm [i] > max)
{
max = vm [i];
}
}
return max;
}
// assume 1 not colored
// and 0 colored
int maxSquare(vector<vector<int>> &matrix)
{
int n = matrix.size();
if (n == 0)
return 0;
int m = matrix[0].size();
int max = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if (matrix[i][j] == 1)
{
int min = -1;
if (j > 0){
min = matrix[i][j-1];
}
if (i > 0)
{
if (min == -1 || min > matrix[i-1][j])
{
min = matrix[i-1][j];
}
}
if (min == -1)
min = 0;
matrix[i][j] = matrix[i-min][j-min] > 0? min+1 : min;
if (max < matrix[i][j])
{
max = matrix[i][j];
}
}
}
}
return max*max;
}
For the square problem, there is an o(N^2) solution:
when A[i][j] == 1
def preLen = min( maxSquareSideLen(i-1,j), maxSquareSideLen(i,j-1) )
maxSquareSideLen(i,j) = A[i-preLen][j-preLen] == 1? preLen+1 : prelen;
For rectangle problem, there is also a N^2 solution:
first, you need to convert this matrix to another format:
which A[i][j] indicate the max height between A[i][j] .... A[i][k] (between A[i][j] and A[i][k], they are all not colored).
Then this become a finding max rectangle problem from histogram:
see the detail description about this problem below which can be solved by O(n) solution
oj.leetcode.com/problems/largest-rectangle-in-histogram/
for each row, we try to find max rectangle. so the complexity is also O(n^2)
int countAllVisited(vector<vector<int>> &matrix)
{
int n = matrix.size();
if (n == 0)
return 0;
int m = matrix[0].size();
int total = 0;
for(int i = 0; i<n; i++)
{
for(int j = 0; j<m; j++)
{
if (matrix[i][j] == 0)
{
total ++;
}
}
}
return countAllVisited(matrix, 0, 0, n, m, 0, total);
}
int countAllVisited(vector<vector<int>> &matrix, int x, int y, int n, int m, int c, int total)
{
static int dx[4] = {-1, 0, 1, 0};
static int dy[4] = {0, 1, 0, -1};
if (x<0 || y < 0 || x>=n || y>=m || matrix[x][y] != 0){
return 0;
}
++c;
if(x == n-1 && y == m-1)
{
if ( c == total)
{
return 1;
}
return 0;
}
int count = 0;
matrix[x][y] = 1;
for(int i=0; i<4; i++)
{
count += countAllVisited(matrix, x+ dx[i], y + dy[i], m, n, c, total);
}
matrix[x][y] = 0;
return count;
}
There is a better solution than permutation. The trick is when given digital from s1 and s2, there is only one possible digital on s3.
0+1 => 1
1+1 => 2
9+8 => 7.
Take the example "send" "more" "money", I can get s=9 & m=1, and others = 0
// assume s1 and s2 the same length
bool testCombination(string s1, string s2, string s3, int p, int c, int e, int e3, unordered_map<char, int> &map)
{
int p12 =e - p;
int p3 =e3 - p;
if (p12 < 0)
{
// s3 same length as s1, s2
if (p3 < 0 && c == 0)
{
for (unordered_map<char,int>::iterator ite = map.begin(); ite != map.end(); ite++)
{
cout<<ite->first<<" = "<<ite->second<<endl;
}
return true;
}
else if (c > 0 && (map.find(s3[p3]) == map.end() || map[s3[p3]] == c))
{
map[s3[p3]] = c;
for (unordered_map<char,int>::iterator ite = map.begin(); ite != map.end(); ite++)
{
cout<<ite->first<<" = "<<ite->second<<endl;
}
return true;
}
return false;
}
int start1 = map.find(s1[p12]) == map.end()? 0 : map[s1[p12]];
int end1 = map.find(s1[p12]) == map.end()? 9 : map[s1[p12]];
int start2 = map.find(s2[p12]) == map.end()? 0 : map[s1[p12]];
int end2 = map.find(s2[p12]) == map.end()? 9 : map[s1[p12]];
for(int i=start1; i<= end1; i++)
{
int cv1 = i;
unordered_set<char> newValues1;
if (map.find(s1[p12]) == map.end())
{
map[s1[p12]] = i;
newValues1.insert(s1[p12]);
}
else if (i > start1) // already tested once
{
break;
}
else
{
cv1 = map[s1[p12]];
}
for(int j=start2; j<= end2; j++)
{
unordered_set<char> newValues2;
int cv2 = j;
if (map.find(s2[p12]) == map.end())
{
map[s2[p12]] = j;
newValues2.insert(s2[p12]);
}
else if (j > start2)
{
break;
}
else
{
cv2 = map[s2[p12]];
}
int cv3 = cv1+cv2+c;
int cv31 = cv3 % 10;
int cv32 = cv3 / 10;
// never seen before
if (map.find(s3[p3]) == map.end())
{
map[s3[p3]] = cv31;
newValues2.insert(s3[p3]);
if (testCombination(s1, s2, s3, p+1, cv32, e, e3, map))
{
return true;
}
}
else if (map[s3[p3]] == cv31)
{
if (testCombination(s1, s2, s3, p+1, cv32, e, e3, map))
{
return true;
}
}
// recover back
for (unordered_set<char>::iterator ite = newValues2.begin(); ite != newValues2.end(); ite++)
{
map.erase(*ite);
}
}
// recover back
for (unordered_set<char>::iterator ite = newValues1.begin(); ite != newValues1.end(); ite++)
{
map.erase(*ite);
}
}
return false;
}
bool testCombination(string s1, string s2, string s3)
{
unordered_map<char, int> map;
return testCombination(s1, s2, s3, 0, 0, s1.length()-1, s3.length()-1, map);
}
Just have the same idea. post my code here:
int partitionBST(vector<int> &bstval, vector<int> &heapval, int s, int e)
{
int k = s;
for(int i=s+1; i<=e; i++)
{
if (heapval[i] > heapval[k])
{
k = i;
}
}
swap(heapval, k, e);
swap(bstval, k, e);
int i = s-1;
for(int j=s; j<e; j++)
{
if (bstval[j] <= bstval[e])
{
i++;
swap(bstval, i, j);
swap(heapval, i, j);
}
}
i++;
swap(bstval, i, e);
swap(heapval, i, e);
return i;
}
TreeNode2* buildBSTHeap(vector<int> &bstval, vector<int> &heapval, int s, int e)
{
if (s > e)
{
return NULL;
}
else if (s == e)
{
return new TreeNode2(bstval[s], bstval[e]);
}
int k = partitionBST(bstval, heapval, s, e);
TreeNode2* root = new TreeNode2(bstval[k], bstval[k]);
root->left = buildBSTHeap(bstval, heapval, s, k-1);
root->right = buildBSTHeap(bstval, heapval, k+1, e);
return root;
}
there is an O(n) solution, which passed from online judge:
oj.leetcode.com/problems/largest-rectangle-in-histogram/
int largestRectangleArea(vector<int> &height) {
int m = height.size();
if (m == 0)
return 0;
vector<int> vm(m, 0);
vector<int> v;
vector<int> vh;
for(int i = 0;i<height.size(); i++)
{
int h = height[i];
int start = i;
while (v.size() > 0 && h <= vh[v.size()-1])
{
start = v[v.size()-1];
v.pop_back();
vh.pop_back();
}
v.push_back(start);
vh.push_back(h);
vm[i] = (i-start +1) * h;
}
v.clear();
vh.clear();
int max = 0;
for(int i = height.size()-1;i>= 0; i--)
{
int h = height[i];
int start = i;
while (v.size() > 0 && h <= vh[v.size()-1])
{
start = v[v.size()-1];
v.pop_back();
vh.pop_back();
}
v.push_back(start);
vh.push_back(h);
vm [i] += (start -i + 1 -1) *h;
if (vm [i] > max)
{
max = vm [i];
}
}
return max;
}
there is a m*n*n solution
// n size of A, m #transactions
int maxprofit(int* A, int n, int m)
{
vector<int> profits(n+1, 0);
for(int i=0; i<m; i++)
{
vector<int> nprofits(n+1, 0);
int maxprofit = 0;
for(int j = 0; j < n; j++)
{
int max = A[j];
int maxrightprofit = 0;
for(int k = j-1; k>=0; k--)
{
if (A[k] > max)
{
max = A[k];
}
int rightprofit = max - A[k];
if (rightprofit > maxrightprofit)
{
maxrightprofit = rightprofit;
}
int profit= profits[k] + maxrightprofit;
if (profit > maxprofit)
{
maxprofit = profit;
}
}
nprofits[j+1] = maxprofit;
}
profits = nprofits;
}
return profits[n];
}
test case:
int A[] = {1, 4, 2, 5, 3, 6 };
int p1 = s.maxprofit(A, 6, 1); // 5
int p2 = s.maxprofit(A, 6, 2); // 7
int p3 = s.maxprofit(A, 6, 3); // 9
DP Algo
vector<int> LIS(int * A, int n)
{
vector<vector<int>> vv(1);
for(int i=0; i<n; i++)
{
int m = vv.size();
if (m == 1 || A[i] > vv[m-1].back())
{
vector<int> nv(vv[m-1]);
nv.push_back(A[i]);
vv.push_back(nv);
}
for(int j=m-1; j>=1; j--)
{
if ((vv[j-1].size() == 0 || A[i] > vv[j-1].back()))
{
if (A[i] < vv[j].back())
{
vector<int> nv(vv[j-1]);
nv.push_back(A[i]);
vv[j] = nv;
}
}
}
}
return vv[vv.size() -1];
}
DP Algo
vector<int> LIS(int * A, int n)
{
vector<vector<int>> vv(1);
for(int i=0; i<n; i++)
{
int m = vv.size();
if (m == 1 || A[i] > vv[m-1].back())
{
vector<int> nv(vv[m-1]);
nv.push_back(A[i]);
vv.push_back(nv);
}
for(int j=m-1; j>=1; j--)
{
if ((vv[j-1].size() == 0 || A[i] > vv[j-1].back()))
{
if (A[i] < vv[j].back())
{
vector<int> nv(vv[j-1]);
nv.push_back(A[i]);
vv[j] = nv;
}
}
}
}
return vv[vv.size() -1];
}
LCS should work, the worst case is O(N^2) when there is no match.
But we would be able to return early when this is match with K.
bool isKPalindrom(string input, int k)
{
string reverse = reverseStr(input);
int n = input.length();
vector<int> v(n+1, 0);
int max = n-k;
for(int i=0; i<n; i++){
vector<int> nv(n+1, 0);
for(int j=0; j<n; j++)
{
int c = input[j] == reverse[i] ? 1 + v[j] : 0;
nv[j+1] = maxNum(c, v[j+1], nv[j]);
if (nv[j+1] == max)
return true;
}
v = nv;
}
return false;
}
string reverseStr(string input)
{
int n = input.length();
for(int i=0; i<= n/2; i++)
{
int t = input[i];
input[i] = input[n-1-i];
input[n-1-i] = t;
}
return input;
}
int maxNum(int n1, int n2, int n3)
{
n1 = n1<n2? n2: n1;
n1 = n1 < n3? n3: n1;
return n1;
}
the key thing is that if the inputs are sorted.
we should skip expending the powerset from current element, if it has the same value as previous.
vector<vector<int>> powersets(vector<int> &num)
{
vector<vector<int>> ret;
vector<vector<int>> vv;
vector<int> v;
vv.push_back(v);
ret.push_back(v);
vector<int> ends;
ends.push_back(-1);
for(int i=0; i<num.size(); i++)
{
vector<vector<int>> nvv;
vector<int> nends;
for(int j=0; j<vv.size(); j++)
{
vector<int> v = vv[j];
int pre = -1;
for(int k=ends[j]+1; k<num.size(); k++)
{
if (pre >= 0 && num[k] == num[pre]){
continue;
}
pre = k;
vector<int> nv(v);
nv.push_back(num[k]);
nvv.push_back(nv);
nends.push_back(k);
ret.push_back(nv);
}
}
vv = nvv;
ends = nends;
}
return ret;
}
this could be done by BFS several times.
1) find the first reach able island by BFS from start point.
and let's count the #mov
2) empty that start point, and set the node the we found from previous as start point and repeat 1) again
int valid(vector<vector<int>> &vv, int n, int nx, int ny, queue<Point*> &nq)
{
if (nx >= 0 && nx < n && ny >=0 && ny < n && (vv[nx][ny] == 0 || vv[nx][ny] == 1))
{
Point * p = new Point(nx, ny);
nq.push(p);
int ret = vv[nx][ny];
vv[nx][ny] = -1;
return ret;
}
return -1;
}
int traval(int n, vector<Point> &spec, vector<Point> &dan, Point* start){
// no need to travel
if (spec.size() == 0)
return 0;
// init matrix, set as all pass
vector<vector<int>> vv;
for(int i=0; i<n; i++)
{
vector<int> v(n, 0);
vv.push_back(v);
}
// set spec points
for(int i=0; i<spec.size(); i++)
{
vv[spec[i].x][spec[i].y] = 1;
}
// set dangerous points
for(int i=0; i<dan.size(); i++)
{
vv[dan[i].x][dan[i].y] = 2;
}
int mov = 0;
for(int i=0; i<spec.size(); i++)
{
int nmov = nextNode(n, vv, start);
if (nmov > 0){
mov +=nmov;
}
else{ // no possible path
return -1;
}
}
return mov;
}
int nextNode(int n, vector<vector<int>> &vv, Point* &start)
{
// reset
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if (vv[i][j] < 0)
{
vv[i][j] = 0;
}
}
}
// BFS, start from start point
queue<Point*> q;
vv[start->x][start->y] = -1;
q.push(start);
int mindepth = INT_MAX;
int depth = 0;
while(!q.empty())
{
queue<Point*> nq;
depth ++;
while(!q.empty())
{
// for each current, add children
Point* p = q.front();
q.pop();
if (valid(vv, n, p->x-1, p->y, nq) == 1)
{
start = p;
return depth;
}
if (valid(vv, n, p->x, p->y-1, nq) == 1)
{
start = p;
return depth;
}
if (valid(vv, n, p->x+1, p->y, nq) == 1)
{
start = p;
return depth;
}
if (valid(vv, n, p->x, p->y+1, nq) == 1){
start = p;
return depth;
}
}
q = nq;
}
return 0; // not possible
}
DP solution.
use array to record previous match.
when s[i] == p[j] or p[j] is '.' current match is true only when p's previous match s's previous
but when p[j] is '*', there are two conditions:
1) ignore the '*', current match is true only when p's previous match current s
2) delete previous p[j-1], current match is true only when p's previous'previous match with current s
bool isMatch(string s, string p)
{
int n = s.length();
int m = p.length();
vector<bool> pv(n+1, false); // row -2
vector<bool> v(n+1, false); // row - 1
v[0] = true;
for(int i=0; i<m; i++)
{
vector<bool> nv(n+1, false);
for(int j=0; j<n; j++)
{
if (p[j] == s[i] || p[j] == '.') // 'a' == 'a'
{
nv[j+1] = v[j]; // only when previous match
}
else if (p[j] == '*')
{
nv[j+1] = v[j+1] || pv[j+1]; // ignore * || delete previous c
}
}
pv = v; // row i-2 for next round
v = nv; // row i-1 for next round
}
return v[n];
}
bool isBST(TreeNode * root, int min, int max, int &depth)
{
if (!root){
depth = 0;
return true;
}
if (root->val < min || root->val > max){
return false;
}
int ldep, rdep;
if (isBST(root->left, min, root->val, ldep) && isBST(root->right, root->val, max, rdep))
{
if ((ldep - rdep) <= 1 && (ldep - rdep) >= -1)
{
depth = 1+ max(ldep, rdep);
return true;
}
}
return false;
}
We can use a binary search to optimize this to O(logn)
int findmissingnumber(int A[], int n)
{
int dis1 = A[1] - A[0];
int dis2 = A[2] - A[1];
int dis = dis1<= dis2? dis1:dis2;
return findmissingnumber(A, 0, n-1, dis);
}
int findmissingnumber(int A[], int s, int e, int d)
{
if ((A[e] - A[s]) == d*(e-s))
{
return A[e] + d;
}
if (e - s == 1)
{
return (A[e] + A[s]) / 2;
}
int m = (s+e)/2;
if ((A[m] - A[s]) == d * (m-s))
{
return findmissingnumber(A, m ,e ,d);
}
else
{
return findmissingnumber(A, s ,m ,d);
}
}
a faster method to count number of 1s and 0s
void countint0(unsigned int p)
{
int c0 = 0;
int c1 = 0;
if (p == 0)
{
c0 = 1;
}
while(p > 0)
{
if (p & 1 == 1)
{
if (p == 0xffff)
{
c0 = 0;
c1 = 32;
break;
}
else
{
int q = p+1;
int cc1 = ((p ^ q) + 1) /4;
cc1 = 1+ log(cc1) / log(2);
c1 += cc1;
p = p >> cc1;
}
}
else
{
int q = p-1;
int cc0 = ((p ^ q) + 1) /4;
cc0 = 1 + log(cc0)/ log(2);
c0 += cc0;
p = p >> cc0;
}
}
}
Providing Google employee referral. @securefer.com
- BIN August 16, 2014