San Song Daddy :)

knapsack problem

knapsack problem
Question:
give two integer n and m, select rand numbers from 1,2,3,...,n-1, n,
let the sum of the combination is equal to m.

print out all possible combinations.

Examples:
n = 8 m = 10
8 2
7 3
7 2 1
6 4
6 3 1
5 4 1
5 3 2
4 3 2 1

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

using namespace std;

void printNumbersWithSum(int n, int m, vector<int>& numbers) {
if (m <= 0 || n <= 0)
    return;
if (m == n) {
    for (int number : numbers)
      cout << number << " ";
    cout << n << endl;
}
numbers.push_back(n);
printNumbersWithSum(n-1, m - n, numbers);
numbers.pop_back();
printNumbersWithSum(n-1, m, numbers);
}

int main() {
vector<int> numbers;
int n, m;
cin >> n >> m;
printNumbersWithSum(n, m, numbers);
return 0;
}

Set up Ghost with Mailgun on Google Conputer Engine

First please refer to :
https://docs.ghost.org/v1.0.0/docs/mail-config
As you may know, Google Cloud Platform doesn't allow outbound connection to ports 25, 465 and 587.
https://cloud.google.com/compute/docs/tutorials/sending-mail/
So you just change port of MailGun to other port such as 2525, it will work.
"mail": {
"transport": "SMTP",
"options": {
"service": "Mailgun",
"port": 2525,
"auth": {
"user": "yourname",
"pass": "yourpasswd"
}
}
},
When you have finished making changes to you config file don't forget to restart Ghost. ( ghost stop ghost start )

Developer set/up with ghost

Refers:
https://docs.ghost.org/docs/working-with-ghost

Very Good, 甚好

God saw all that he had made, and it was very good. And there was evening, and there was morning—the sixth day. (Genesis 1:31 NIV)
　神看着一切所造的都甚好。有晚上，有早晨，是第六日。 (创世记 1:31 和合本)

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;
}