San Song Daddy :)

Maximal Square

Question:
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

Example

For example, given the following matrix:

Return 4.

Answer:
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

using namespace std;

int maxSquarea(vector<vector<int> >& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int> > matrix_flag = matrix;
int r = 0;
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      matrix_flag[i][j] = 0;
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (matrix[i][j] == 0)
        continue;
      if (matrix_flag[i][j] == 1)
        continue;
      int k = 1;
      while (1) {
        bool all1 = true;
        int ii = i + k;
        int jj;
        for (jj = 0; jj <= k && ii < m && j+jj < n; jj++) {
          if (matrix[ii][j+jj] == 0) {
            all1 = false;
            break;
          }
        }
        if (!all1 || ii >= m || ((jj <= k) && (j + jj >= n)))
          break;
        jj = j + k;
        for (ii = 0; ii <= k && i+ii < m && jj < n; ii++) {
          if (matrix[i+ii][jj] == 0) {
            all1 = false;
            break;
          }
        }
        if (!all1 || ((ii <= k) && (i + ii >= m)) || jj >= n)
          break;
        k++;
      }
      if (k > 1)
        cout << i << " " << j << " " << k << endl;
      for (int jj = j; jj < j + k; jj++)
          matrix_flag[i][jj] = 1;
      if (k > r)
        r = k;
    }
}
return r;
}

void printMatrix(vector<vector<int> >& matrix) {
int m = matrix.size();
int n = matrix[0].size();
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      cout << matrix[i][j] << " ";
    }
    cout << endl;
}
}

void buildMatrix(vector<vector<int> >& matrix) {
int m = 10;
int n = 10;
srand(time(0));
for (int i = 0; i < m; i++) {
    vector<int> row;
    for (int j = 0; j < n; j++) {
      if (rand()%2)
        row.push_back(0);
      else
        row.push_back(1);
    }
    matrix.push_back(row);
}
}

int main() {
vector<vector<int> > matrix;
buildMatrix(matrix);
printMatrix(matrix);
cout << maxSquarea(matrix) << endl;
return 0;
}

Longest Palindromic Sub-string

#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

/* 0~9, a~z, A~z */
void randstring(int n, char* s) {
int fn = rand() % n;
if (fn <= n/2)
    fn = (n+1) / 2;
for (int i = 0; i < fn; i++) {
    int t = rand() % 3;
    char c;
    if (t == 0)
      s[i] = '0' + (rand()%10);
    else if (t == 1)
      s[i] = 'a' + (rand()%26);
    else
      s[i] = 'A' + (rand()%26);
}
for (int i = fn; i < n; i++) {
    s[i] = s[rand()%fn];
}
}

int main() {
srand(time(0));
int n = 20;
char* s = new char[n+1];
s[n] = '\0';
randstring(n, s);
cout << s << endl;
int n2 = (n+1)*2 + 1;
char* ns = new char[n2];
ns[0] = '$';
ns[1] = '#';
int j;
int i;
for (i = 0, j = 2; i < n; i++) {
    ns[j] = s[i];
    ns[++j] = '#';
    j++;
}
ns[j] = '#';
ns[n2-1] = '\0';
cout << ns << endl;
int* p = new int[n2];
for (i = 0; i < n2; i++)
    p[i] = 0;
int mx = 0;
int id = 0;
int pid = 0;
int pi = 0;
for (i = 1; i < n2; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (ns[i + p[i]] == ns[i-p[i]]) p[i]++;
    if ((i + p[i]) > mx) {
      mx = i + p[i];
      id = i;
    }
    if (p[i] > pid) {
      pid = p[i];
      pi = i;
    }
}
cout << " ";
for (i = 1; i < n2-1; i++)
    cout << p[i];
cout << endl;
cout << pid << " " << pi << endl;
if (pid > 2) {
    for (i = pi - p[pi] + 1; i < pi + p[pi]; i++)
      if (ns[i] != '#')
        cout << ns[i];
}
cout << endl;
delete []s;
delete []ns;
delete []p;
return 0;
}

Find the minimum larger node in binary search tree for a giving node.

Question:
Find the minimum larger node in binary search tree for a giving node.
Answer:
struct BSTreeNode {
BSTreeNode* pLeft;
BSTreeNode* pRight;
BSTreeNode* pParent;
int value;
};
BSTreeNode* findMinLarge(BSTreeNode* node) {
if (!node)
return 0;
if (Node* result = node->pRight) {
while (result && result->pLeft) {
result = result->pLeft;
}
return result;
}
if (node->pParent == 0) {
return 0;
}
if (node->pParent->pLeft == node)
return node->pParent;
BSTreeNode* parent = node->pParent;
BSTreeNode* pparent = parent->pParent;
while (1) {
if (pparent && pparent->pLeft == parent) {
return pparent;
}
if (!pparent)
break;
parent = pparent;
pparent = parent->pParent;
}
return 0;
}

the devils out of the man

鬼被赶出

        耶稣问他说：“你名叫什么？”他说：“我名叫‘群’”；这是因为附着他的鬼多。鬼就央求耶稣，不要吩咐他们到无底坑里去。那里有一大群猪在山上吃食。鬼央求耶稣，准他们进入猪里去。耶稣准了他们，鬼就从那人出来，进入猪里去。于是那群猪闯下山崖，投在湖里淹死了。 (路加福音 8:30-33 和合本)

        And Jesus asked him, saying, What is thy name?And he said, Legion: because many devils were entered into him.And they besought him that he would not command them to go out into the deep.And there was there an herd of many swine feeding on the mountain: and they besought him that he would suffer them to enter into them. And he suffered them.Then went the devils out of the man, and entered into the swine: and the herd ran violently down a steep place into the lake, and were choked. (Luke 8:30-33 KJV)

         耶稣问这人的名字，得到的回答是群，这似乎是在说有一整个军团的鬼进到他里面（一个罗马军团约有六千个士兵）。可见这个人里面住了很多鬼。那些鬼知道它们必须离开这人，就不断恳求耶稣不要吩咐它们到无底坑里去。无底坑是拘禁群鬼、甚至撒但的所在（启二十1及下）。它们央求耶稣准许它们进到正在附近吃食的一大群猪里面去，耶稣准了它们，鬼就离了那人，进入猪里去。那猪群闯下山崖，投在湖里淹死了。这里可能有人会问耶稣竟牺牲猪群的主人来医治这个人？对这个问题，基本的答复应该是：这人的痊愈要比一群猪重要得多。可有任何人当真以为猪应该得救，而这人应该继续留在不得救的情景中吗？同样地，发拉尔指出：“对于全城而言，将邻舍从这野蛮疯子的危险和恐惧中释放出来，这个收益要比损失这群猪更大。”我们也要记得：耶稣既未打发鬼进到猪里去（祂不过是准许它们罢了），也没有打发猪投到湖里去（这故事并未说祂愿意猪死亡）。

Where is your faith?

这到底是谁？

耶稣对他们说：“你们的信心在哪里呢？”他们又惧怕又希奇，彼此说：“这到底是谁？他吩咐风和水，连风和水也听从他了。” (路加福音 8:25 和合本)

And he said unto them, Where is your faith?And they being afraid wondered, saying one to another, What manner of man is this! for he commandeth even the winds and water, and they obey him. (Luke 8:25 KJV)

祂查问，你们的信心在哪里呢？暗示门徒不该惧怕，他们应该信靠祂。可见耶稣希望门徒对祂有信心。他们对这件事的反应，仿佛是见了神的面一样。他们充满了敬畏（惧怕），他们惊奇地问：“这到底是谁？”这是重要的问题，路加不容他的读者忽略它。这件事情，更新了门徒对耶稣的认识，他们更深地认识了祂的奥秘和奇妙。这才是最大的收获。今日的世界，充满艰难试探，很多时候神的计划看起来似乎岌岌可危。基督似乎睡着了。但是，不要叫醒祂。不要以为神想藉着你我的手来保护方舟，来托起小船。祂不需要这样作。

Rebuild Binary Tree from Preorder and Inorder Traversal

Question:
struct NODE {
NODE* pLeft;
NODE* pRight;
char chValue;
};
e.g.
preorder traversal : a b d c e f
inorder traversal : d b a e c f

Answer:

include

using namespace std;

struct NODE {
NODE* pLeft;
NODE* pRight;
char chValue;
};

void PrintPreOrder(NODE* pRoot) {
if (!pRoot)
return;
cout << pRoot->chValue;
PrintPreOrder(pRoot->pLeft);
PrintPreOrder(pRoot->pRight);
}

void PrintInOrder(NODE* pRoot) {
if (!pRoot)
return;
PrintInOrder(pRoot->pLeft);
cout << pRoot->chValue;
PrintInOrder(pRoot->pRight);
}

void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot) {
if (pPreOrder == 0 || pInOrder == 0)
return;
NODE* pTemp = new NODE;
pTemp->pLeft = 0;
pTemp->pRight = 0;
pTemp->chValue = *pPreOrder;
if (pRoot == 0)
pRoot = pTemp;
if (nTreeLen == 1)
return;
char pOrgInOrder = pInOrder;
char pLeftEnd = pInOrder;
int nTempLen = 0;
while (*pPreOrder != *pLeftEnd) {
nTempLen++;
if (nTempLen > nTreeLen)
break;
pLeftEnd++;
}
int nLeftLen = (int)(pLeftEnd - pOrgInOrder);
int nRightLen = nTreeLen - nLeftLen - 1;
if (nLeftLen > 0)
Rebuild(pPreOrder+1, pInOrder, nLeftLen, &(pTemp->pLeft));
if (nRightLen > 0)
Rebuild(pPreOrder+nLeftLen+1, pInOrder + nLeftLen + 1, nRightLen, &(pTemp->pRight));
}

int main() {
char* pPreOrder = "abdcef";
char* pInOrder = "dbaecf";
NODE* pRoot = 0;
int nTreeLen = 6;
Rebuild(pPreOrder, pInOrder, nTreeLen, &pRoot);
PrintPreOrder(pRoot);
cout << endl;
PrintInOrder(pRoot);
cout << endl;
return 0;
}

Array Right Shift K Steps

Question:
An array has N numbers, move each elements to right for K steps.
time limit : O(N)
e.g.
abcd1234 move 4 steps turns out
1234abcd
Answer:
void Reverse(int* arr, int b, int e)
{
for (; b < e; b++, e--) {
int temp = arr[e];
arr[e] = arr[b];
arr[b] = temp;
}
}
void RightShift(int* arr, int N, int K)
{
K %= N;
Reverse(arr, 0, N - K - 1);
Reverse(arr, N-K, N-1);
Reverse(arr, 0, N-1);
}