55、从前序与中序遍历序列构造二叉树

前序是根左右，中序是左根右

写一个递归函数，build（preorder,0,preorder.length-1,inorder,0,inorder.length-1）;接收的参数是先序遍历数组，起始位置，长度，中序位置与长度,递归出口是起始位置不能超出数组长度

最上根结点肯定是先序数组的起始位置也就是preorder[0],然后从中序数组找到根的下标，计算长度，然后递归，root.left=build(左) root.right=build(右) 返回root

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*///中序遍历：左根右
//先序遍历：根左右
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {//递归，判断根root=preorder[0],找到inorder中root的位置分成左右两份，左边是左子树//右边是右子树，从preorder中从root后找到左子树，第一个元素就是根，递归return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}public TreeNode build(int[] preorder,int prestart,int preend,int[] inorder,int instart,int inend){if(prestart>preend||instart>inend){return null;}TreeNode root=new TreeNode(preorder[prestart]);int index=0;for(int i=instart;i<=inend;i++){if(inorder[i]==preorder[prestart]){index=i;break;}}int leftsize=index-instart;root.left=build(preorder,prestart+1,prestart+leftsize,inorder,instart,index-1);root.right=build(preorder,prestart+leftsize+1,preend,inorder,index+1,inend);return root;}
}

56、子集

经典回溯

class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> result=new ArrayList<>();if(nums==null||nums.length==0){return result;}backtrack(nums,0,new ArrayList<>(),result);return result;}private void backtrack( int[] nums,int start,List<Integer> current,List<List<Integer>> result){result.add(new ArrayList<>(current));for(int i=start;i<nums.length;i++){current.add(nums[i]);backtrack(nums,i+1,current,result);current.remove(current.size()-1);}}}

过于经典的模板，遍历，退回，输出答案

57、字符串相乘

class Solution {public String multiply(String num1, String num2) {int n=num1.length(),m=num2.length();if(num1.charAt(0)=='0'||num2.charAt(0)=='0')return "0";int[] res=new int[n+m-1];for(int i=0;i<n;i++){for(int j=0;j<m;j++){res[i+j]+=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');}}int tmp=0;for(int k=res.length-1;k>=0;k--){res[k]+=tmp;tmp=res[k]/10;res[k]%=10;}StringBuilder sb=new StringBuilder();if(tmp>0){sb.append(tmp);}for(int x:res){sb.append(x);}return sb.toString();}
}