解析
max ksubarray sum: 最大和 of 连续子序列 => 最大和 of k份连续子序列 属于dp，30行代码搞定，注意一些边界。
substr diff: 无queue的区间滑动窗口，记录当前最大值
maxtree:
九章算法中有讲到， 对每个节点，找到离他最近且比它大的左右两个节点中较小的那个，作为他的父节点。
其中，找父节点： 用递增栈分别从左向右和从右向左扫描一次，对每个节点取栈顶元素即可。 在O（n）时间里就可以找到距离该节点最近的比他大的节点。
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param A: Given an integer array with no duplicates.
* @return: The root of max tree.
*/
TreeNode* maxTree(vector<int> A) {
// write your code here
int n = A.size();
// allocate tree
TreeNode * nodes = new TreeNode[n];
for(int i =0; i<n; i++){
nodes[i] = TreeNode(A[i]);
}
// obtain the left/right nearest larger node
stack<int> ss;
vector<int> lp(n, -1), rp(n, -1);
for(int i =0; i<n; i++){
while(!ss.empty() && A[i]>A[ss.top()]){
ss.pop();
}
if(!ss.empty()){
lp[i] = ss.top();
}
ss.push(i);
}
ss=stack<int>();
for(int i =n-1; i>=0; i--){
while(!ss.empty() && A[i]>A[ss.top()]){
ss.pop();
}
if(!ss.empty()){
rp[i] = ss.top();
}
ss.push(i);
}
// construct tree
TreeNode * root = NULL;
for(int i = 0; i<n; i++){
if(lp[i]>=0 && (rp[i]<0 || A[rp[i]]>A[lp[i]])){
nodes[lp[i]].right = &nodes[i];
}
else if(rp[i]>=0 && (lp[i]<0 || A[lp[i]]>A[rp[i]])){
nodes[rp[i]].left = &nodes[i];
}else{
root = &nodes[i];
}
}
return root;
}
};
tree iterator:
实质：找一个节点的中序下一个节点。
用dfs(root, p) 在root树中，找p的下一个节点。 代价是Ｏ（logn)
如果要Ｏ(1)的时间代价，需要一个栈（空间Ｏ(logn)）保存当前的路径(root ->xx -> p)。
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
* Example of iterate a tree:
* Solution iterator = new Solution(root);
* while (iterator.hasNext()) {
* TreeNode node = iterator.next();
* do something for node
* }
*/
public class Solution {
TreeNode r;
TreeNode p;
boolean org;
//@param root: The root of binary tree.
public Solution(TreeNode root) {
// write your code here
r = p = root;
if(p!=null) while(p.left != null) p=p.left;
org = true;
}
//@return: True if there has next node, or false
public boolean hasNext() {
// write your code here
TreeNode q = p;
if(!org) q = dfs(r, p);
return q != null;
}
//@return: return next node
public TreeNode next() {
// write your code here
if(!org) p = dfs(r, p);
org = false;
return p;
}
private TreeNode dfs(TreeNode root, TreeNode p){
if(root == null || p == null) return null;
if(root.val>p.val){
TreeNode q= dfs(root.left, p);
if(q != null) return q;
else return root;
}else{
return dfs(root.right, p) ;
}
}
}
动态Ｍedian
用一个大顶堆维护较小的一半序列，一个小顶堆维护较大的一半序列。
保持两边序列长度平衡，每次取大顶堆的顶，即为中位数。
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of numbers
*/
vector<int> medianII(vector<int> &nums) {
// write your code here
priority_queue<int> lq;
priority_queue<int, vector<int>, greater<int> >rq; // top small, bottom bigger
vector<int> rs;
for(int i = 0; i<nums.size(); i++){
if(lq.empty() || nums[i]<=lq.top())
lq.push(nums[i]);
else rq.push(nums[i]);
if(lq.size()>rq.size()+1){
int t = lq.top();
lq.pop(), rq.push(t);
}else if(lq.size()<rq.size()){
int t = rq.top();
rq.pop(), lq.push(t);
}
rs.push_back(lq.top());
}
return rs;
}
};
remove bst node
这个题目不好写，如果删除一个节点p，先找到他的父节点prt，然后找到他的左子数最大点pre以及父节点preprt，或右子树最小点nxt以及父节点nxtprt，然后用该点pre/nxt替换掉自己就可以了。
指针运算很容易出错地奥！ 尤其是当preprt == p的时候， prt==null的时候，都需要注意。
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param value: Remove the node with given value.
* @return: The root of the binary search tree after removal.
*/
TreeNode* removeNode(TreeNode* root, int value) {
// write your code here
if(!root) return NULL;
if(root->val == value ){
if(root->left){
TreeNode *t;
TreeNode *p = preNode(root, &t);
// remove pre, insert at root
if(t!=root){
t->right = p->left, p->left = root->left;
}
p->right = root->right;
delete root; return p;
}else if(root->right){
TreeNode *t;
TreeNode *p = nxtNode(root, &t);
if(t!=root){
t->left= p->right, p->right = root->right;
}
p->left = root->left;
delete root; return p;
}else{
delete root; return NULL;
}
}else{
if(root->val > value){
root->left = removeNode(root->left, value);
return root;
}else{
root->right =removeNode(root->right, value);
return root;
}
}
}
// @param root: no equal to NULL
// get root's largest smaller sub-node, and its parent
TreeNode *preNode(TreeNode *root, TreeNode **prt){
TreeNode *p = root->left; *prt = root;
if(p) while(p->right) *prt = p, p = p->right;
return p;
}
TreeNode *nxtNode(TreeNode *root, TreeNode **prt){
TreeNode *p = root->right; *prt = root;
if(p) while(p->left) *prt = p, p = p->left;
return p;
}
};
Word Search II
class Solution {
public:
/**
* @param board: A list of lists of character
* @param words: A list of string
* @return: A list of string
*/
vector<string> wordSearchII(vector<vector<char> > &board, vector<string> &words) {
// write your code here
int m = board.size();
vector<string> res;
if(!m) return res;
int n = board[0].size();
vector<vector<bool> >visit(m, vector<bool>(n, false));
dr[0][0] = -1, dr[0][1] = 0, dr[1][0] = 1, dr[1][1] = 0;
dr[2][0] = 0, dr[2][1] = -1, dr[3][0] = 0, dr[3][1] = 1;
for(int i = 0; i<words.size(); i++){
for(int j = 0; j<m; j++){
int k = 0;for( ; k<n; k++){
if(dfs(board, words[i], visit, 0, j, k)) {
res.push_back(words[i]);
break;
}
}
if(k<n) break;
}
}
return res;
}
int dr[4][2] ;//= {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool dfs(vector<vector<char> >& board, const string &word, vector<vector<bool> > &visit, int idx, int x, int y){
//if(idx>=word.length()) return true;//@remove
if(board[x][y]!=word[idx]) return false;
if(idx==word.length()-1) return true; //@add
visit[x][y] = true;
bool s = false;
int m = visit.size(), n = visit[0].size();
for(int i = 0; i<4; i++){
int x1 = x+dr[i][0], y1 = y+dr[i][1];
if(x1>=0 && x1<m && y1>=0 && y1<n && !visit[x1][y1])
if(dfs(board, word, visit, idx+1, x1, y1)){
s = true; break;
}
}
visit[x][y] = false;
return s;
}
};
MAX k subarray sum
三维DP：
- maxn [i][k] = max{ maxn[i-1][k], maxn[j<i][k-1] + maxsub[j+1][i] }
其中maxsub[i][j]代表【i，j】区间最大的连续子段的sum，
- maxsub[i][j] = max{maxsub[i][j-1], max{ sum([k, j-1]), i<=k<=j }+ nums[j] }, 前后两项分别表示该子段不使用nums[j]和使用
class Solution {
public:
/**
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping subarrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
int maxKSubArrays(vector<int> nums, int K) {
// write your code here
int n = nums.size();
if(!n || n<K) return 0;
vector<vector<int> > one(n, vector<int>(n, 0));
for(int i = 0; i<n; i++){
one[i][i] = nums[i];
int lst = max(0, nums[i]);
for(int j = i+1; j<n; j++){
one[i][j] = max(one[i][j-1], lst+nums[j]);
lst += nums[j];//@error: not nums[i]
if(lst<0) lst = 0;
// cout<<i<<','<<j<<": "<<one[i][j]<<endl;
}
}
vector<vector<int> > m(n, vector<int>(K+1));
for(int i = 0; i<n; i++){
m[i][1] = one[0][i];
for(int j = 2; j<=i+1 && j<=K; j++){
m[i][j] = m[i-1][j-1]+nums[i];
if(j<i+1) m[i][j] =max(m[i][j], m[i-1][j]);
if(nums[i]>0 && j<i+1)
for(int k = i-1; k>=j-1; k--){//@error: k>=j-1 not j
m[i][j] = max(m[i][j], m[k-1][j-1]+one[k][i]);
}
// cout<<i<<" divide "<<j<<": "<<m[i][j]<<endl;
}
}
return m[n-1][K];
}
};
substr diff
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
//int cnt[i][j][l]= m; // given m, return max l
// cnt[i-j]
int N; cin>>N;
for(int ii=0; ii<N; ii++){
string s, t; int m;
cin>>m>>s>>t;
int maxL=-1;
int n = s.length();
for(int i = 0; i<n; i++){
int c = 0, k = i;
for(int j = i; j<n; j++){
if(s[j] != t[j-i]) c++;
while(c>m) { while(s[k] == t[k-i]) k++; k++; c--;}
maxL = max(maxL, j-k+1);
}
}
for(int i = 0; i<n; i++){
int c = 0, k = i;
for(int j = i; j<n; j++){
if(t[j] != s[j-i]) c++;
while(c>m) { while(t[k] == s[k-i]) k++; k++; c--;}
maxL = max(maxL, j-k+1);
}
}
cout<<maxL<<endl;
}
return 0;
}
附加：二叉树线索化
http://baike.baidu.com/link?url=h2Z7V2zrCul8bVb5ARq9YFxRKLp_0ba_eoxtB1FcUetAhOy-l0SulzlB9Me_wHxJ7O_3-NRubjsPxWHc2n42Da
建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
下面是建立中序二叉树的递归算法，其中pre为全局变量。
序列化和反序列化
方法1 BFS
BFS分层序列化，空指针用#代替。反序列化的时候，用一个队列不断把当前节点的子节点添加进来，空节点利用bfs顺序的固定性。
(node) (node) ... # .. (node) ... #