找出二叉查找树中出现频率最高的元素。树中结点满足left->val <= root->val <= right->val。如果多个元素出现次数相等，返回最小的元素。
http://blog.csdn.net/luckyxiaoqiang/article/details/8934593
不用额外空间. in-order
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int val) {
this->val = val;
}
};
void countNodesHelper(TreeNode *root, TreeNode *&pre, int &count, int &maxCount) {
if (root == NULL) return;
countNodesHelper(root->left,pre,count,maxCount);
if (pre == NULL) {
pre = root;
count = 1;
}else {
if (pre->val == root->val) {
count++;
if (maxCount < count) {
maxCount = count;
}
}else {
count = 1;
}
}
pre = root;
countNodesHelper(root->right,pre,count,maxCount);
}
int countNodes(TreeNode *root) {
int maxCount = 0,count = 0;
TreeNode *pre = NULL;
foo(root,pre,count,maxCount);
return maxCount;
}
-----------------------------------------------
有一个函数
long compute(int i) {
return …;
}
返回值有可能出错概率是 p=1/10000。
还有一个函数
long total(int n) {
long s = 0;
for (int i =0; i < n; i++) {
s += compute(i);
}
return s;
}
这样出错概率就是 np;
问： 如何改第二个函数，让他的出错概率小于p?
http://www.mitbbs.com/article_t/JobHunting/32996657.html
----------------------------------------------------------------------------------------------
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;
}
}
return count;
}
int countPal(string s) {
int count = 0;
for (int i = 1; i < s.length(); i++) {
count += countHelper(s,i - 1,i); // even
count += countHelper(s,i,i); // odd
}
return count + 1;
}
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 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;
}
返回路径
struct TreeNode {
int val;
vector<TreeNode *> children;
TreeNode(int val) {
this->val = val;
}
};
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.时间区间合并问题，leetcode上有相似题，关键词interval
4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
（2）优化第一部分用O（log2(N)) 时间复杂度
如果存在超过 1/4 的数，则次数必定会覆盖length / 4, length / 2, length *（3 / 4）这3点中的至少一点，所以只要对这3点上的数做二分搜索，就能找到其长度，然后与 1 / 4的长度对比。复杂度为 O(lgN)
int findFirst(vector<int> &nums, int elem) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == elem) {
if (mid - 1 >= 0 && nums[mid - 1] != nums[mid]) {
return mid;
}
right = mid - 1;
}else if (nums[mid] > elem) {
right = mid - 1;
}else {
left = mid + 1;
}
}
return 0;
}
int findLast(vector<int> &nums, int elem) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == elem) {
if (mid + 1 < nums.size() && nums[mid + 1] != nums[mid]) {
return mid;
}
left = mid + 1;
}else if (nums[mid] > elem) {
right = mid - 1;
}else {
left = mid + 1;
}
}
return 0;
}
bool helper(vector<int> &nums, int index) {
int last = findLast(nums,nums[index]);
int first = findFirst(nums,nums[index]);
if (last - first + 1 > nums.size() / 4) {
return true;
}
return false;
}
bool longerThanAQuarter(vector<int> &nums) {
int length = nums.size();
return helper(nums,length / 4) || helper(nums,length / 2) || helper(nums,length - 1 -length / 4);
}
(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.
DP
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();
}
5.有一个游戏，他说是fishing game，给一个数组vector<int> Basket, 比如里面元素
是{2，3，5，1，3，4，7}
有A，B 2个player，规定只能从Basket2端选数字，意思就是A开始的话一开始A只能选2
或者7，然后B选，同样只能2端选。所以比如一开始A选了7，B只能从2和4中选。问给定
数组A能取的最大值。B的策略已知，是greedy，就是总会取最大的那个数。
写一个 int maxA（vector<int>& Basket）；
Lintcode, Coins in a Line III http://www.lintcode.com/en/problem/coins-in-a-line-iii/#
DP, Memoization. iteration待写
int helper(vector<int> &nums, int start, int end, vector<vector<int> > &dp) {
if (start == end) return 0;
if (start + 1 == end) {
return min(nums[start],nums[end]);
}
if (dp[start][end] != 0) return dp[start][end];
if (nums[start] < nums[end]) {
end--;
}else {
start++;
}
int play_1 = helper(nums,start + 1,end,dp) + nums[start];
int play_2 = helper(nums,start,end - 1,dp) + nums[end];
dp[start][end] = max(play_1,play_2);
return max(play_1,play_2);
}
int play(vector<int> &nums) {
vector<vector<int> > dp(nums.size(),vector<int>(nums.size(),0));
return max(helper(nums,0,nums.size() - 2, dp) + nums[nums.size() - 1],helper(nums,0,nums.size() - 2, dp) + nums[nums.size() - 1]);
}
