/* * 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); } }