Leetcode: Google interview questions #1

Leetcode: Google interview questions #1
REF http://www.mitbbs.com/article_t/JobHunting/32980969.html

1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
      （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
(string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
,b,b,b,a,c,bb, bbb, bb, abbba.

int countHelper(string &s, int left, int right) {

   int count = 0;

 

   while (left >= 0 && right < s.length()) {

      if (s[left] == s[right]) {

         count++;

         right++;

         left--;

      }else {

         break;

      }

   }

  

}

 

int countPal(string s) {

   int count = 0;

  

   for (int i = 1; i < s.length(); i++) {

      count += countHelper(s,i - 1,i) + 2; // even

      count += countHelper(s,i,i); // odd

   }

  

   return count;

}

2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长[连续]
路径。
例如（括号对应上面node）  [修改：还有条件是 连续]
   树：                     2
                 |            |            |                |
                5            7          3                 6
         （|       | ）（   | ）   （|）         （|       |）
            6       3         2          4             5       8
                                 |
                                  3

返回3因为 （2-3-4） 这条线。优化要求时间O(n)
DFS，tree寻找路径
increasing order

struct TreeNode {

    int val;

    vector<treenode> children;

    TreeNode(int val) {

        this->val = val;

    }

};

  

int longestPathHelper(TreeNode *root, int &longest) {

   

    int cur = 1;

    for (int i = 0; i < root->children.size(); i++) {

        TreeNode *child = (root->children)[i];

        if (root->val == child->val - 1) {

            cur = max(cur,longestPathHelper(root->children[i],longest) + 1);

        }else {

            cur = longestPathHelper(child,longest);

        }

    

    }

    longest = max(cur,longest);

    return cur;

}

  

int longestIncreasingPath(TreeNode *root) {

    if (root == NULL) return 0;

    int longest = 0;

    longestPathHelper(root,longest);

    return longest;

}

返回路径 

  

void longestPathHelper(TreeNode *root,TreeNode *pre, vector<int> path, vector<int> &longestPath) {

    vector<int> curLongest;

    if (pre != NULL && root->val == pre->val + 1) {

        curLongest = path;   

    }

    curLongest.push_back(root->val);

 

    for (int i = 0; i < root->children.size(); i++) {

        longestPathHelper(root->children[i],root,curLongest,longestPath);

    }

     

    if (longestPath.size() < curLongest.size()) {

        longestPath = curLongest;   

    }

}

  

void longestIncreasingPath(TreeNode *root) {

    vector<int> longestPath,path;

    if (root == NULL) return;

     

    longestPathHelper(root,NULL,path,longestPath);

    for (int i : longestPath) {

        cout << i << endl;

    }

}

(3)完全平方解集，做一个：int minsol（int i）。
比如1=1^2 所以minsol(1)返回1,
2=1^2+1^2 返回2,
4=2^2或者4个1^2,1比4小， 返回1，
12=2^2+2^2+2^2或者3^2+3个1^2返回3.

int shortest(int num) {

    int t = sqrt(num);

    if (t * t == num) return 1;

        

    vector<int> dp(num + 1,INT_MAX);

    dp[1] = 1;

    dp[2] = 2;

     

    for (int i = 3; i <= num; i++) {

    int sq = sqrt(i);

        if (sq * sq == i) {

            dp[i] = 1;

        }else {

            for (int j = 1; j < i / 2 + 1; j++) {

                dp[i] = min(dp[i],dp[j] + dp[i - j]);

            }

        }

    }

     

    return dp.back();

}

Read full article from Leetcode: Google interview questions #1