题目描述:矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
public class Test10 { //448ms 递归方法 public int RectCover(int target) { if(target==0) return 0; if(target==1 || target==2) return target; return RectCover(target-1)+RectCover(target-2); } //10ms 非递归方法 public int RectCover2(int target) { if(target==0) return 0; if(target==1 || target==2) return target; int[] res=new int[target+1]; res[1]=1;res[2]=2; for(int i=3;i<target+1;i++) res[i]=res[i-1]+res[i-2]; return res[target]; } public static void main(String[] args) { } }
题目描述:二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
public class Test11 { public static int NumberOf1(int n) { int res=0; char[] ch=Integer.toBinaryString(n).toCharArray(); for(char c: ch) if(c=='1') res++; return res; } public static int NumberOf1_2(int n) { int res=0; while(n!=0) { n=n&(n-1); res++; } return res; } public static int NumberOf1_3(int n) { int res=0; while(n!=0) { if((n&1)==1) res++; n=n>>>1; //>>>逻辑右移 【>>算术右移当为负数时，高位补1,会无限循环，所以必须用逻辑右移】 } return res; } public static int NumberOf1_4(int n) { int res=0; int flag=1; while(flag!=0) { if((n&flag)!=0) res++; flag = flag<<1; } return res; } public static void main(String[] args) { System.out.println(NumberOf1(-2147483648)); } }
题目描述：合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } public class mergeList { //递归方法 public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null)return list2; if(list2==null)return list1; if(list1.val< list2.val) { list1.next=Merge(list1.next, list2); return list1; } else { list2.next=Merge(list2.next, list1); return list2; } } //非递归方法 public ListNode Merge1(ListNode list1,ListNode list2) { if(list1==null)return list2; if(list2==null)return list1; ListNode merge=null; ListNode cur=null; while(list1!=null && list2!=null) { if(list1.val<list2.val) { if(merge==null) merge=cur=list1; else { cur.next=list1; cur=cur.next; } list1=list1.next; } else { if(merge==null) merge=cur=list2; else { cur.next=list2; cur=cur.next; } list2=list2.next; } } if(list1!=null) cur.next=list1; if(list2!=null) cur.next=list2; return merge; } public static void main(String[] args) { // TODO Auto-generated method stub } }
题目描述:重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
//方法1 public class Test4 { public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre.length==0 || in.length==0) return null; return ReBuild(pre,0,pre.length-1,in,0,in.length-1); } private TreeNode ReBuild(int[] pre, int i, int end1, int[] in, int j, int end2) { if(end1<i) return null; TreeNode root=new TreeNode(pre[i]); for(int index=j;index<=end2;index++){ if(in[index]==pre[i]) { root.left=ReBuild(pre,i+1,i+index-j, in, j, index-1); root.right=ReBuild(pre,i+1+index-j, end1, in,index+1,end2); break; } } return root; } public static void main(String[] args) { // TODO Auto-generated method stub } } //方法2 import java.util.Arrays; public class Test4_1 { public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre.length==0 || in.length==0) return null; TreeNode root=new TreeNode(pre[0]); for(int i=0;i<in.length;i++) { if(in[i]==pre[0]) { root.left=reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i)); root.right=reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length)); break; } } return root; } public static void main(String[] args) { // TODO Auto-generated method stub } }
题目描述：树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
public class Test14 { public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1==null || root2==null) return false; boolean res=false; if(root1.val==root2.val) { res=isSubtree(root1, root2); } if(!res) { res=HasSubtree(root1.left, root2); } if(!res) { res=HasSubtree(root1.right, root2); } return res; } private boolean isSubtree(TreeNode root1, TreeNode root2) { if(root2==null) return true; if(root1==null&&root2!=null) return false; if(root1.val==root2.val) return isSubtree(root1.left, root2.left)&&isSubtree(root1.right, root2.right); else return false; } public static void main(String[] args) { // TODO Auto-generated method stub } }
题目描述：顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
import java.util.ArrayList; public class PrintMatrix { public ArrayList<Integer> printMatrix(int [][] matrix) { int row=matrix.length; int col=matrix[0].length; ArrayList<Integer> res=new ArrayList<Integer>(); if(matrix==null ||row==0 ||col==0) return null; if(row==1) { for(int i=0;i<col;i++) res.add(matrix[0][i]); return res; } if(col==1) { for(int i=0;i<row;i++) res.add(matrix[i][0]); return res; } for(int i=0;i<row-i;i++) { int j=i; if(j<col-i) { for(;j<col-i;j++) res.add(matrix[i][j]); for(int k=i+1;k<row-i;k++) res.add(matrix[k][col-1-i]); int f=row-1-i; if(f>i) { for(int m=col-1-i-1;m>=i;m--) res.add(matrix[f][m]); for(int n=f-1;n>i;n--) res.add(matrix[n][i]); } } } return res; } public static void main(String[] args) { // TODO Auto-generated method stub } }
题目描述：最小的k个数
todo
用堆数据结构解决
题目描述：整数中1出现的次数
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。