/*
* 1.字符串移位，给出字符串abc##dfg##gh，实现将所有#移至字符串串头。输出####abcdfggh（个人认为可以用后向移位，减少移位次数）
*/
static void moveStep(char[] str){
if(str==null||str.length<1)
return ;
int len=str.length;
int s=len-1,e=len-1;
for(int i=len-1;i>=0;i--){
if(str[i]=='#'){
int j=i;
while(j>=0&&str[j]=='#')j--;
//find successive #
if(j<0)
break;
if(s==len-1)s=i;//first initial
e=j;
i=j+1;
}else{
int j=i;
while(j>=0&&str[j]!='#')j--;
//find successive abcd...
if(s==e)continue;
else{
//fill abcd
for(int k=i;k>j&&s>=0;k--){
str[s--]=str[k];
}
//fill #
for(int k=s;k>j;k--)
str[k]='#';
}
if(j<0)break;
i=j+1;
}
}
}
/*
* 给出一个二维矩阵，从（0,0）出发走到右下角，只能向右或向下走，找到一条路径，是这条路径上的总和最大。（个人认为使用动态规划或深度遍历）
*/
static int findMaxSum(int[][] nums,int row,int col){
if(row<1||col<1)
return 0;
int[][] dp=new int[row][col];
for(int i=0;i<row;i++){
if(i==0)dp[i][0]=nums[i][0];
else
dp[i][0]=dp[i-1][0]+nums[i][0];
}
for(int i=1;i<col;i++){
dp[0][i]=dp[0][i-1]+nums[0][i];
}
for(int i=1;i<row;i++){
for(int j=1;j<col;j++){
dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1])+nums[i][j];
}
}
return dp[row-1][col-1];
}
/*
* 给出一颗二叉树，两个叶节点，找到这两个叶节点互连通的一条最短路径。（个人认为主要是找两个叶节点的最近公共祖先）
*/
static int depthMin(TreeNode root,TreeNode s,TreeNode t){
if(root==null||s==t)
return 0;
ArrayList<Integer> l1=new ArrayList<Integer>();
ArrayList<Integer> l2=new ArrayList<Integer>();
find(root,s,new ArrayList<Integer>(),l1);
find(root,t,new ArrayList<Integer>(),l2);
//find common
int i=0,j=0;
/*for(int k=0;k<l1.size();k++)
System.out.print(l1.get(k)+"->");
System.out.println();
for(int k=0;k<l2.size();k++)
System.out.print(l2.get(k)+"->");
System.out.println();
*/
while(i<l1.size()&&j<l2.size()&&l1.get(i)==l2.get(j)){
i++;
j++;
}
int dep=l1.size()-i+l2.size()-j+1;
//System.out.println(i+" "+j+" "+dep);
return dep;
}
private static void find(TreeNode root, TreeNode t, ArrayList<Integer> cur,ArrayList<Integer> res) {
// TODO Auto-generated method stub
//System.out.println(root.val+" "+t.val);
if(root==null)
return;
if(t==root){
cur.add(root.val);
res.addAll(new ArrayList<Integer>(cur));
return;
}else{
cur.add(root.val);
//.for(int k=0;k<cur.size();k++)
// System.out.print(cur.get(k)+"->");
//System.out.println();
find(root.left,t,cur,res);
find(root.right,t,cur,res);
cur.remove(cur.size()-1);
}
}