JZ1：二维数组中的查找
左下角开始，遇大右移，遇小上移，直到超过边界都没找到，得false。否则得true。
JZ2：替换空格
自带函数replace
新建stringbuffer用append()
遍历一遍计数空格,每个空格新长度+2，setLength(),从后往前setCharAt()
JZ3：从尾到头打印链表
ArrayList.add(0,value)
递归
JZ4：重建二叉树
递归，前序遍历第一个pre[0]是根节点，在中序遍历中找到pre[0]的位置，对左右分别递归调用函数，可以使用 Arrays.copyOfRange (array,start,end)直接复制数组，左闭右开
JZ5：两个栈实现队列
出栈：栈2空时，先把栈1转移到栈2，再pop，栈2非空时，直接pop
JZ6：旋转数组的最小数字
JZ7：斐波那契数列
JZ8：跳台阶
JZ9：变态跳台阶
递归，f(n)=f(n-1)+f(n-2)+…+f(1)=2*f(n-1)
JZ10：矩形覆盖
JZ11：二进制中1的个数
JZ12：数值的整次方
快速幂，时间复杂度logn，指数的二进制形式的1才参与计算
JZ13：调整数组顺序使奇数位于偶数前面 题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变
插入排序思想，使用两个循环。假设前面的已经都是奇数，当前元素：
如果是偶数，不动；
如果是奇数，与前面的偶数一个个交换。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class Solution public void reOrderArray (int [] array) for (int i=0 ;i<array.length;i++){ if (array[i]%2 ==0 ){ continue ; } else { for (int j=i-1 ;j>=0 ;j--){ if (array[j]%2 ==0 ){ int tmp=array[j+1 ]; array[j+1 ]=array[j]; array[j]=tmp; } } } } } }
JZ14 链表中倒数第k个结点 题目：输入一个链表，输出该链表中倒数第k个结点。
快慢双指针：指针p先走k-1步，指针q再开始，两个指针之间的距离是k-1，当p到链表末端，q就是倒数第k个结点。
注意边界情况：
这三种情况都返回null
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public class Solution public ListNode FindKthToTail (ListNode head,int k) if (head==null ||k<=0 )return null ; ListNode p=head; ListNode q=head; for (int i=1 ;i<=k-1 ;i++){ q=q.next; if (q==null )return null ; } while (q.next!=null ){ q=q.next; p=p.next; } return p; } }
JZ15 反转链表 题目：输入一个链表，反转链表后，输出新链表的表头
用两个指针，p和q分别指向head的前一结点和后一结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Solution public ListNode ReverseList (ListNode head) if (head==null )return null ; ListNode p=null ; ListNode q=null ; while (head!=null ){ q=head.next; head.next=p; p=head; head=q; } return p; } }
JZ16 合并两个排序的链表 题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
新建一个结点头head，每次比较list1和list2，把更小的接在head后
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public class Solution public ListNode Merge (ListNode list1,ListNode list2) ListNode head=new ListNode(-1 ); ListNode root=head; while (list1!=null &&list2!=null ){ if (list1.val<list2.val){ head.next=list1; head=list1; list1=list1.next; } else { head.next=list2; head=list2; list2=list2.next; } } if (list1==null ){ head.next=list2; } else { head.next=list1; } return root.next; } }
JZ17 树的子结构 题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
递归思想，使用两个递归：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 public class Solution public boolean HasSubtree (TreeNode root1,TreeNode root2) boolean result=false ; if (root1!=null &&root2!=null ){ if (root1.val==root2.val){ result=DoesTree1hasTree2(root1,root2); } if (!result){ result=HasSubtree(root1.left,root2); } if (!result){ result=HasSubtree(root1.right,root2); } } return result; } boolean DoesTree1hasTree2 (TreeNode root1,TreeNode root2) if (root2==null )return true ; if (root1==null )return false ; if (root1.val!=root2.val)return false ; return DoesTree1hasTree2(root1.left,root2.left)&&DoesTree1hasTree2(root1.right,root2.right); } }
JZ18 二叉树的镜像 题目：操作给定的二叉树，将其变换为源二叉树的镜像。
1 2 3 4 5 6 7 8 9 10 11 12 二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5
递归：交换左右结点，分别对左右结点递归调用函数。
1 2 3 4 5 6 7 8 9 10 public class Solution public void Mirror (TreeNode root) if (root==null )return ; TreeNode tmp=root.left; root.left=root.right; root.right=tmp; Mirror(root.left); Mirror(root.right); } }
也可以用栈，每次把左右结点压入栈中实现前序遍历，避免递归。
JZ19 顺时针打印矩阵 题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.
三个变量row,col,start。注意开闭：
[start,col)
[start+1,row)
[col-2,start]
[row-2,start)
外层循环当row>start&&col>start时结束
单行的情况，走完第一步就返回
单列的情况，走完第二步就返回
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 import java.util.ArrayList;public class Solution public ArrayList<Integer> printMatrix (int [][] matrix) if (matrix==null )return null ; ArrayList<Integer> result=new ArrayList<Integer>(); int row=matrix.length; int col=matrix[0 ].length; int start=0 ; while (row>start&&col>start){ printMatrixIner(matrix,row,col,start,result); row--; col--; start++; } return result; } void printMatrixIner (int [][] matrix,int row,int col,int start,ArrayList<Integer> result) for (int i=start;i<col;i++){ result.add(matrix[start][i]); } if (row-start==1 )return ; for (int i=start+1 ;i<row;i++){ result.add(matrix[i][col-1 ]); } if (col-start==1 )return ; for (int i=col-2 ;i>=start;i--){ result.add(matrix[row-1 ][i]); } for (int i=row-2 ;i>start;i--){ result.add(matrix[i][start]); } } }
JZ20 包含min函数的栈 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
用两个栈，其中一个栈（stackMin）每次push时压入当前最小值（要么是新元素，要么是stackMin的栈顶元素）。
判断栈空：stack.empty()
查看栈顶（不删除）：stack.peek()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.util.Stack;public class Solution private Stack<Integer> stackOrin=new Stack<Integer> (); private Stack<Integer> stackMin=new Stack<Integer> (); public void push (int node) stackOrin.push(node); if (stackMin.empty()||stackMin.peek()>node){ stackMin.push(node); } else { stackMin.push(stackMin.peek()); } } public void pop () stackOrin.pop(); stackMin.pop(); } public int top () return stackOrin.peek(); } public int min () return stackMin.peek(); } }
JZ21 栈的压入和弹出序列 题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
一个栈模拟压入过程，不断判断栈顶元素和出栈序列是否相等，相等则出栈，不等则继续压入栈。最后栈为空则返回true
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import java.util.ArrayList;import java.util.*;public class Solution public boolean IsPopOrder (int [] pushA,int [] popA) Stack<Integer> myStack=new Stack<Integer> (); int flag=0 ; for (int i=0 ;i<pushA.length;i++){ myStack.push(pushA[i]); while (flag<popA.length&&myStack.peek()==popA[flag]){ myStack.pop(); flag++; } } return myStack.empty(); } }
JZ22 从上往下打印二叉树 题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
其实就是实现二叉树层序遍历：队列+前序遍历
队列：Queue <TreeNode> myqueue=new LinkedList <TreeNode>();
队列加元素：offer()
删队头：poll()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import java.util.ArrayList;import java.util.*;public class Solution public ArrayList<Integer> PrintFromTopToBottom (TreeNode root) ArrayList<Integer> result=new ArrayList<Integer>(); if (root==null )return result; Queue <TreeNode> myqueue=new LinkedList <TreeNode>(); myqueue.offer(root); while (!myqueue.isEmpty()){ TreeNode tmp=myqueue.poll(); result.add(tmp.val); if (tmp.left!=null ){ myqueue.offer(tmp.left); } if (tmp.right!=null ){ myqueue.offer(tmp.right); } } return result; } }
JZ23 二叉搜索树的后序遍历序列 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。
二叉搜索树（BST）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class Solution public boolean VerifySquenceOfBST (int [] sequence) if (sequence.length==0 )return false ; boolean result = subProcess(sequence,0 ,sequence.length-1 ); return result; } boolean subProcess (int []sequence,int start,int end) if (start>=end)return true ; int tmp=end-1 ; while (sequence[tmp]>sequence[end]&&tmp>start)tmp--; if (tmp==start)return true ; for (int i=start;i<=tmp;i++){ if (sequence[i]>sequence[end])return false ; } return subProcess(sequence,start,tmp)&&subProcess(sequence,tmp+1 ,end-1 ); } }
递归：
注意对于根节点前面的数都比根节点大的情况（只有右子树），此时tmp==start,可以直接返回true
JZ24 二叉树和为某一值的路径 题目：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
递归，用一个ArrayList<Integer>保存测试路径，加上根节点的val等于target，且没有左右节点了就返回，否则对左右子树递归调用。
注意调用结束后要把最后一个节点remove，才能回退到上一个节点状态。
result添加时要新建一个新的ArrayList<Integer>，这样才不会因为后续path的更新而受到影响。
对于字典排序，原始的剑指offer并没有这个要求，排序可以重写Collections.sort的compare方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;public class Solution ArrayList<ArrayList<Integer>> result =new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> path=new ArrayList<Integer>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { help(root,target); Collections.sort(result,new Comparator<ArrayList<Integer>>() { @Override public int compare (ArrayList<Integer> o1, ArrayList<Integer> o2) return o2.size()-o1.size(); } }); return result; } void help (TreeNode root,int target) if (root==null )return ; path.add(root.val); target-=root.val; if (target==0 &&root.left==null &&root.right==null ){ result.add(new ArrayList<Integer>(path)); } help(root.left,target); help(root.right,target); path.remove(path.size()-1 ); } }
JZ25 复杂链表的复制 题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public class Solution public RandomListNode Clone (RandomListNode pHead) { if (pHead==null )return null ; RandomListNode currentNode=pHead; while (currentNode!=null ){ RandomListNode tmp=new RandomListNode(currentNode.label); tmp.next=currentNode.next; currentNode.next=tmp; currentNode=tmp.next; } currentNode=pHead; while (currentNode!=null ){ currentNode.next.random=currentNode.random==null ?null :currentNode.random.next; currentNode=currentNode.next.next; } currentNode=pHead; RandomListNode result=pHead.next; while (currentNode!=null ){ RandomListNode tmp=currentNode.next; currentNode.next=tmp.next; tmp.next=tmp.next==null ?null :tmp.next.next; currentNode=currentNode.next; } return result; } }
JZ26 二叉搜索树与双向链表 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
递归：即假设经过这个函数后，左右子树都整理好，并返回当前头结点
如果左右子树都为null，则返回当前节点
当前节点和整理好的左子树的末端节点连接，和整理好的右子树的头结点连接
最终返回值：如果有左子树，返回整理好的左子树的头结点；如果没有，返回当前节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class Solution public TreeNode Convert (TreeNode pRootOfTree) if (pRootOfTree==null )return pRootOfTree; if (pRootOfTree.left==null &&pRootOfTree.right==null )return pRootOfTree; TreeNode finalResult=pRootOfTree; if (pRootOfTree.right!=null ){ TreeNode head=Convert(pRootOfTree.right); pRootOfTree.right=head; head.left=pRootOfTree; } if (pRootOfTree.left!=null ){ TreeNode head=Convert(pRootOfTree.left); TreeNode tmp=head; while (tmp.right!=null ){ tmp=tmp.right; } tmp.right=pRootOfTree; pRootOfTree.left=tmp; finalResult=head; } return finalResult; } }
JZ27 字符串排列 题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba
递归+回溯法
String转char数组：toCharArray()
char数组转String：String s=String.valueOf(charstr);
第0位分别和第012位交换得到第二行排列
第1位分别和12位交换得到第三行排列
到达最终叶节点（index==chararray.length-1),该排列加入结果队列
字典序排列：Collections.sort()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.util.ArrayList;import java.util.Collections;public class Solution public ArrayList<String> Permutation (String str) ArrayList<String> result=new ArrayList<>(); if (str!=null ){ PermutationHelp(str.toCharArray(),0 ,result); } Collections.sort(result); return result; } void PermutationHelp (char [] charstr,int i,ArrayList<String> result) if (i!=charstr.length-1 ){ for (int j=i;j<charstr.length;j++){ swap(charstr,i,j); PermutationHelp(charstr,i+1 ,result); swap(charstr,i,j); } } else { String s=String.valueOf(charstr); if (!result.contains(s))result.add(s); } } void swap (char [] charstr,int i,int j) char tmp=charstr[i]; charstr[i]=charstr[j]; charstr[j]=tmp; } }
JZ28 数组中超过一半的数 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思想：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。
用一个变量candi保存候选数，一个变量num保存候选数出现次数
遍历数组，候选数和下一个数相等，num++；不等，num–；num==0,下一个遍历的数成为新的候选数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class Solution public int MoreThanHalfNum_Solution (int [] array) int candi=0 ,num=0 ; if (array.length==0 )return 0 ; for (int i=0 ;i<array.length;i++){ if (num==0 ){ candi=array[i]; num++; } else if (candi==array[i]){ num++; } else { num--; } } num=0 ; for (int tmp:array){ if (tmp==candi)num++; } return num>array.length/2 ?candi:0 ; } }
JZ29 最小的K个数 题目：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
思路一：排序，取前K个。Arrays.sort()
思路二：用优先级队列PriorityQueue<Integer>，通过重写比较函数，降序排列（队列头是最大值）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.*;public class Solution static Comparator<Integer> cmp=new Comparator<Integer>(){ @Override public int compare (Integer a, Integer b) return b-a; } }; public ArrayList<Integer> GetLeastNumbers_Solution (int [] input, int k) ArrayList<Integer> result=new ArrayList<Integer>(); if (input.length==0 ||k>input.length||k==0 )return result; PriorityQueue<Integer> myQueue=new PriorityQueue<Integer>(k,cmp); for (int i=0 ;i<input.length;i++){ myQueue.offer(input[i]); if (myQueue.size()>k)myQueue.poll(); } for (int i=0 ;i<k;++i){ result.add(myQueue.poll()); } Collections.reverse(result); return result; } }
JZ30 连续子数组的最大和 题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
两个变量，sum存储子数组的和，max存储和最大的子数组和。如果sum+当前数比当前数小，sum更新为当前数。如果sum比max大，更新max为sum。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class Solution public int FindGreatestSumOfSubArray (int [] array) if (array.length==0 ) return 0 ; int max=array[0 ]; int sum=array[0 ]; for (int i=1 ;i<array.length;i++){ if (sum+array[i]<array[i]){ sum=array[i]; } else { sum+=array[i]; } if (sum>max)max=sum; } return max; } }
JZ31 整数中1出现的次数 归纳：以百位为例
该数百位为0，例如12012，则从0到12012的数，百位为1的有100199,11001199，…，11100~11199，共12*100个，即高位数决定
该数百位为1，例如12112，则从0到12112的数，百位为1的有100199,11001199，…，1110011199和1210012112共12*100+12+1个，高位数和低位数决定
该数百位为29，例如12212，则从0到12212的数，百位为1的有100199,11001199，…，1110011199和12100~12199共（12+1）*100个
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public class Solution public int NumberOf1Between1AndN_Solution (int n) int i=1 ; int sum=0 ; while (i<=n){ int num=(n/i)%10 ; if (num==0 ){ int high=n/(i*10 ); sum+=(high*i); } else if (num==1 ){ int high=n/(i*10 ); int low=n%i; sum+=(high*i+low+1 ); } else { int high=n/(i*10 ); sum+=((high+1 )*i); } i*=10 ; } return sum; } }
JZ32 把数组排成最小的数 问题： 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
两个字符串a,b，如果a + b < b + a, 我们希望a排在b的前面。 自定义排序规则，使得ArrayList中字符串都满足如上规则，那么最后的结果肯定是最小的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.util.*;public class Solution Comparator<Integer> myCmp=new Comparator<Integer>(){ @Override public int compare (Integer a,Integer b) String ab=a+"" +b; String ba=b+"" +a; return ab.compareTo(ba); } }; public String PrintMinNumber (int [] numbers) String result="" ; if (numbers.length==0 )return result; ArrayList<Integer> myArray=new ArrayList<Integer>(); for (int i:numbers){ myArray.add(i); } Collections.sort(myArray,myCmp); for (int i:myArray){ result+=("" +i); } return result; } }
JZ33 丑数 题目： 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
一个丑数是一个比他小的丑数乘以2、3、5得到的
生成丑数的过程中，每个丑数只会分别乘以1次2、3、5
用三个int：n2, n3, n5分别记录还未乘以过2, 3, 5的位置
每次将n2, n3, n5这三个位置的丑数生成的新丑数中最小的那个加入结果数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public class Solution public int GetUglyNumber_Solution (int index) if (index<=0 )return 0 ; int [] result=new int [index]; int n2=0 ,n3=0 ,n5=0 ; result[0 ]=1 ; for (int i=1 ;i<index;i++){ int newcs=minOfThree(result[n2]*2 ,result[n3]*3 ,result[n5]*5 ); if (newcs==result[n2]*2 )n2++; if (newcs==result[n3]*3 )n3++; if (newcs==result[n5]*5 )n5++; result[i]=newcs; } return result[index-1 ]; } int minOfThree (int a,int b,int c) int min=a<b?a:b; min=min<c?min:c; return min; } }
JZ34 第一个只出现一次的字符 题目：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数 )
创建一个数组，index是字符的ASCII值，value是该字符出现次数。
第一次遍历str,记录得到每个字符出现次数，第二次遍历str，得到第一个出现次数为1的字符
字符的ASCII：Integer.valueOf('a')
1 2 3 4 5 6 7 8 9 10 11 12 public class Solution public int FirstNotRepeatingChar (String str) int [] result=new int [128 ]; for (int i=0 ;i<str.length();i++){ result[Integer.valueOf(str.charAt(i))]+=1 ; } for (int i=0 ;i<str.length();i++){ if (result[Integer.valueOf(str.charAt(i))]==1 )return i; } return -1 ; } }
JZ35 数组中的逆序对 题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
对于$50%$的数据,$size\leq 10^4$
输入描述: 题目保证输入的数组中没有的相同的数字
思路：递归，把数组均分为两个数组
左段数组排序并计算逆序对数
右段数组排序并计算逆序对数
将两个排好序的数组合并并计算逆序对数。
递归到底的条件是数组中只有一个数。
两个数组合并：由于数组已经排好序，从左到右递增
使用两个指针left和right指向两个数组的最大值。
然后使用归并排序思想操作
left和right比，大的放到tmp中。如果left大，逆序对数result还要加上right-mid
最后如果其中一个数组先遍历完，把另一个数组剩下的依序放入tmp中
在tmp数组中得到排好序的数组，最后把array数组中对应的部分改为tmp中排好序的结果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 public class Solution int result=0 ; public int InversePairs (int [] array) int [] tmp=new int [array.length]; int start=0 ,end=array.length-1 ; cutPairs(array,tmp,start,end); return result; } void cutPairs (int []array,int []tmp,int start,int end) if (end-start>0 ){ cutPairs(array,tmp,start,(end+start)/2 ); cutPairs(array,tmp,(end+start)/2 +1 ,end); merge(array,tmp,start,end); } } void merge (int []array,int []tmp,int start,int end) int mid=(end+start)/2 ; int left=mid,right=end; for (int i=end;i>start-1 ;i--){ if (left>=start&&right>=mid+1 ){ if (array[left]>array[right]){ tmp[i]=array[left]; result+=(right-mid); result=result%1000000007 ; left--; } else { tmp[i]=array[right]; right--; } } else { if (left<start){ tmp[i]=array[right]; right--; } else { tmp[i]=array[left]; left--; } } } for (int i=end;i>start-1 ;i--){ array[i]=tmp[i]; } } }
JZ36 两个链表的第一个公共结点 题目： 输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
有了第一个公共点后，之后的结点都是公共点（因为单链表只有一个next）
使用两个指针，分别从两个链表头开始遍历，遍历到尾端时（next==null）再从另一条链表头遍历，这样他们就会同时到达链表末端（下图中的5结点），也就是说他们会在第一个公共结点相遇（下图中的8）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public class Solution public ListNode FindFirstCommonNode (ListNode pHead1, ListNode pHead2) ListNode p1=pHead1; ListNode p2=pHead2; if (pHead1==null ||pHead2==null )return null ; while (p1!=p2){ p1=p1.next; p2=p2.next; if (p1==null &&p2==null )return null ; if (p1==null )p1=pHead2; if (p2==null )p2=pHead1; } return p1; } }
JZ37 数字在排序数组中出现的次数 题目：
二分查找法查找k，找到k后，往前计数有多少个k，往后计数有多少个k
上一种方法时间复杂度O(n)，改进：使用二分法查找k，找到后对前半段继续二分查找k，直到该k前一位不等于k，则表示找到了第一个k，同理找最后一个k，index相减得到次数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public class Solution public int GetNumberOfK (int [] array , int k) int start=0 ,end=array.length-1 ; if (array.length==0 )return 0 ; return subGet(array,k,start,end); } private int subGet (int [] array,int k,int start,int end) int mid=(start+end)/2 ; int num=0 ; if (array[mid]==k){ int index=mid; while (index>=start&&array[index]==k){ num++; index--; } index=mid+1 ; while (index<=end&&array[index]==k){ num++; index++; } return num; } else if (array[mid]>k){ if (mid==start)return 0 ; return subGet(array,k,start,mid-1 ); } else { if (mid==end)return 0 ; return subGet(array,k,mid+1 ,end); } } }
JZ38 二叉树深度
1 2 3 4 5 6 7 8 9 public class Solution public int TreeDepth (TreeNode root) int left=0 ,right=0 ; if (root==null )return 0 ; left=TreeDepth(root.left); right=TreeDepth(root.right); return left>right?left+1 :right+1 ; } }
JZ39 平衡二叉树 题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树。平衡二叉树 （Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
递归获取子树深度，设定非平衡二叉树深度为-1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class Solution public boolean IsBalanced_Solution (TreeNode root) if (root==null )return true ; return getDepth(root)!=-1 ; } int getDepth (TreeNode root) if (root==null )return 0 ; int left=getDepth(root.left); if (left==-1 )return -1 ; int right=getDepth(root.right); if (right==-1 )return -1 ; if (Math.abs(right-left)>1 ){ return -1 ; } else { return Math.max(right,left)+1 ; } } }
JZ40 数组中只出现一次的数字 题目： 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class Solution public void FindNumsAppearOnce (int [] array,int num1[] , int num2[]) if (array.length==0 )return ; int tmp=0 ; for (int i:array){ tmp^=i; } tmp&=(-tmp); for (int i:array){ if ((i&tmp)==0 ){ num1[0 ]^=i; } else { num2[0 ]^=i; } } } }
JZ41 和为S的连续正数序列 题目： 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
滑动窗口：
两个指针left和right，如果窗口内的和小于S，right++;如果大于，left++，等于就把结果加入result中。
由于至少包括两个数，所以循环停止的条件是left>S/2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.util.ArrayList;public class Solution public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { int left=1 ,right=2 ; ArrayList<ArrayList<Integer>> result=new ArrayList<>(); if (sum<3 )return result; while (left<=sum/2 ){ int sumtmp=(left+right)*(right-left+1 )/2 ; if (sumtmp>sum){ left++; } else if (sumtmp<sum){ right++; } else { ArrayList<Integer> resulttmp=new ArrayList<Integer>(); for (int i=left;i<=right;++i){ resulttmp.add(i); } result.add((resulttmp)); left++; } } return result; } }
JZ42 和为S的两个数字 题目： 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
left和right两个指针。left=0 right=array.length-1
left小的，两个数的乘积更小
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.ArrayList;public class Solution public ArrayList<Integer> FindNumbersWithSum (int [] array,int sum) ArrayList<Integer> result=new ArrayList<Integer>(); int left=0 ,right=array.length-1 ; if (right<=0 )return result; while (left<right){ int sumtmp=array[left]+array[right]; if (sumtmp<sum){ left++; } else if (sumtmp>sum){ right--; } else { result.add(array[left]); result.add(array[right]); return result; } } return result; } }
JZ43 左旋转字符串 题目： 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
主要两个函数：String.concat()和String.substring()
1 2 3 4 5 6 7 public class Solution public String LeftRotateString (String str,int n) if (str=="" ||str==null ||str.length()==0 )return str; n=n%str.length(); return str.concat(str).substring(n,str.length()+n); } }
JZ44 翻转单词顺序列 题目： 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
创建一个ArrayList<String>来保存每个单词，用两个指针遍历，分别记录单词起始字符和终止字符
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.util.*;public class Solution public String ReverseSentence (String str) if (str==null ||str.length()==0 )return str; int left=0 ,right=0 ; boolean flag=true ; ArrayList<String> result=new ArrayList<>(); while (left<str.length()){ while (left<str.length()&&str.charAt(left)==' ' ){ left++; } if (flag==true &&left==str.length()){ return str; } flag=false ; right=left+1 ; while (right<str.length()&&str.charAt(right)!=' ' ){ right++; } result.add(str.substring(left,right)); left=right+1 ; } String finalresult=result.get(result.size()-1 ); for (int i=result.size()-2 ;i>=0 ;i--){ finalresult+=" " ; finalresult+=result.get(i); } return finalresult; } }
JZ45 扑克牌顺子 题目： LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
先排序，然后找到除去0以外的最小的数和最大的数。
如果除0外，数组中有相等的数，则不是顺子
如果两数之差<=numbers,length-1，则是顺子；否则不是
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import java.util.*;public class Solution public boolean isContinuous (int [] numbers) if (numbers.length==0 ||numbers==null )return false ; Arrays.sort(numbers); int start=0 ; while (numbers[start]==0 &&start<numbers.length)start++; for (int i=start;i<numbers.length-1 ;i++){ if (numbers[i]==numbers[i+1 ])return false ; } int dis=numbers[numbers.length-1 ]-numbers[start]; if (dis<=numbers.length-1 ){ return true ; } return false ; } }
JZ46 圆圈中最后剩下的数 题目：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
递归： 长度为 n 的序列会先删除第 m % n 个元素，然后剩下一个长度为 n - 1 的序列。 假设我们已知n - 1的序列最后留下的是 f(n - 1, m) 号小朋友，那么对于n个小朋友的序列，f(n - 1, m) 号小朋友的位置其实是(f(n - 1, m) + m )%n
下图中就是，对于6个小朋友时，假设已知最后留下的是0号小朋友，那么在上一轮中，0号小朋友的位置就是3=（0+3）%7
1 2 3 4 5 6 7 8 9 10 11 public class Solution public int LastRemaining_Solution (int n, int m) if (n<=0 )return -1 ; if (n==1 ){ return 0 ; } else { return (m+LastRemaining_Solution(n-1 ,m))%n; } } }
JZ47 1+2+3+…+n 递归，&&运算先算左边，成立再算右边，不成立就不算右边了；而&两边同时算。所以可以用&&来实现当i=0时就不递归了（右边不继续算了）
1 2 3 4 5 6 7 public class Solution public int Sum_Solution (int n) int ite=n; boolean flag=(n!=0 )&&((ite+=Sum_Solution(n-1 ))!=0 ); return ite; } }
JZ48 不用加减乘除做加法 题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
二进制中，异或^就是相加（不含进位），按位与&就是求进位，再用递归即可。
1 2 3 4 5 6 7 8 public class Solution public int Add (int num1,int num2) int sum=num1^num2; int carry=(num1&num2)<<1 ; if (carry==0 )return sum; return Add(sum,carry); } }
JZ49 字符串转换成整数 题目：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入描述:输入一个字符串,包括数字字母符号,可以为空
返回值描述:如果是合法的数值表达则返回该数字，否则返回0
思路：
0位只能是’+’ ‘-‘或者数字
中间有非数字就返回0
注意越界，Integer.MAX_VALUE和Integer.MIN_VALUE，可以先用long存储数值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public class Solution public int StrToInt (String str) long num=0L ; int zf=0 ; if (str.length()==0 ||str==null )return 0 ; for (int i=0 ;i<str.length();i++){ if (i==0 &&str.charAt(i)=='-' ){ zf=1 ; continue ; } if (i==0 &&str.charAt(i)=='+' ){ zf=0 ; continue ; } if ((str.charAt(i)-'0' >=0 )&&('9' -str.charAt(i)>=0 )){ num=num*10 +(str.charAt(i)-'0' ); } else { return 0 ; } } if (zf==0 &&num>Integer.MAX_VALUE)return 0 ; if (zf==1 &&(-num<Integer.MIN_VALUE))return 0 ; int result=(int )num; return zf==0 ?result:-result; } }
JZ50 数组中重复的数字：
利用现有数组设置标志，当一个数字被访问过后，可以设置对应位上的数+n，之后再遇到相同的数时，会发现对应位上的数已经大于等于n了，那么直接返回这个数即可。不需要额外的空间消耗，时间效率是O(n)
HashMap
JZ51 构建乘积数组 题目：给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1] …*A[i-1]A[i+1] …*A[n-1]。不能使用除法。
注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];
对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
思路：
先计算下三角到B[]中，再计算上三角到B[]中
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import java.util.ArrayList;public class Solution public int [] multiply(int [] A) { int []B=new int [A.length]; B[0 ]=1 ; int tmp=1 ; for (int i=1 ;i<A.length;i++){ tmp*=A[i-1 ]; B[i]=tmp; } tmp=1 ; for (int i=A.length-2 ;i>=0 ;i--){ tmp*=A[i+1 ]; B[i]*=tmp; } return B; } }
JZ52 正则表达式匹配 使用递归
模式中的第二个字符是’*’时：
模式中的第二个字符不是’*’时
字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
字符串第一个字符和模式中的第一个字符相不匹配，直接返回false
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public class Solution public boolean match (char [] str, char [] pattern) if (str == null || pattern == null ) { return false ; } int strIndex = 0 ; int patternIndex = 0 ; return matchCore(str, strIndex, pattern, patternIndex); } public boolean matchCore (char [] str, int strIndex, char [] pattern, int patternIndex) if (strIndex == str.length && patternIndex == pattern.length) { return true ; } if (strIndex != str.length && patternIndex == pattern.length) { return false ; } if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1 ] == '*' ) { if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) { return matchCore(str, strIndex, pattern, patternIndex + 2 ) || matchCore(str, strIndex + 1 , pattern, patternIndex + 2 ) || matchCore(str, strIndex + 1 , pattern, patternIndex); } else { return matchCore(str, strIndex, pattern, patternIndex + 2 ); } } if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) { return matchCore(str, strIndex + 1 , pattern, patternIndex + 1 ); } return false ; } }
JZ53 表示数值的字符串 题目：
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
思路：
只能有一个小数点
只能有1个e
e后面必须有一个数且是整数
正负号只能出现在第一位或e后面的第一位
小数点前一位只能是0~9或者+-，可以是第一位
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 public class Solution public boolean isNumeric (char [] str) boolean flagfloat=false ; boolean flage=false ; for (int i=0 ;i<str.length;i++){ if (str[i]=='+' ||str[i]=='-' ){ if (i==0 ){ continue ; } else { return false ; } } if (!flage&&(str[i]=='e' ||str[i]=='E' )){ flage=true ; if (i<str.length-1 ){ if (str[i+1 ]=='+' ||str[i+1 ]=='-' )i++; continue ; } else { return false ; } } if ((!flagfloat)&&(!flage)&&(str[i]=='.' )){ flagfloat=true ; if (i==0 ){ continue ; } else if ((str[i-1 ]>='0' &&str[i-1 ]<='9' )|| str[i-1 ]=='-' || str[i-1 ]=='+' ){ continue ; } } if (str[i]>='0' &&str[i]<='9' )continue ; return false ; } return true ; } }
JZ54 字符流中第一个不重复的字符 题目：
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。
思路：
用一个数组存储每个字符出现的次数，没出现是0，出现1次是1，超过1次是2.
用一个队列存储出现过的字符，多次出现不重复入队
每次找只出现一次的字符：查看队头，数组中对应值是1，则返回该字符，不是1就出队。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.util.*;public class Solution int [] allchar=new int [256 ]; Queue<Character> charqueue=new LinkedList<>(); public void Insert (char ch) { if (allchar[ch]==0 ){ charqueue.offer(ch); allchar[ch]=1 ; } else if (allchar[ch]==1 ){ allchar[ch]=2 ; } } public char FirstAppearingOnce () { while (!charqueue.isEmpty()){ char tmp=charqueue.peek(); if (allchar[tmp]==1 ){ return tmp; } else { charqueue.poll(); } } return '#' ; } }
JZ55 链表中环的入口结点 题目：
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路：
快慢指针:
两个结论：
设置快慢指针从head开始走，快指针每次走两步，慢指针每次走一步。假如有环，他们最后一定相遇。
两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。
证明结论1 ：设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇（因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上）。
证明结论2：
设：
链表头到环入口长度为–a
环入口到相遇点长度为–b
相遇点到环入口长度为–c
相遇时
快指针路程=a+(b+c)k+b ，k>=1 其中b+c为环的长度，k为绕环的圈数（k>=1,即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾）。
慢指针路程=a+b
快指针走的路程是慢指针的两倍，所以：
（a+b）*2=a+(b+c)k+b
化简可得：
a=(k-1)(b+c)+c 这个式子的意思是： 链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度 。其中k>=1,所以k-1>=0 圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public class Solution public ListNode EntryNodeOfLoop (ListNode pHead) { ListNode pfast=pHead; ListNode pslow=pHead; while (pfast!=null &&pfast.next!=null ){ pfast=pfast.next.next; pslow=pslow.next; if (pslow==pfast)break ; } if (pfast==null ||pfast.next==null )return null ; pslow=pHead; while (pslow!=pfast){ pslow=pslow.next; pfast=pfast.next; } return pslow; } }
JZ56 删除链表中重复的结点 题目：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路：
两个指针，一个记录前一个结点，一个记录当前结点
创建一个meta结点接在pHead前，以处理第一个结点就是重复结点的情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public class Solution public ListNode deleteDuplication (ListNode pHead) { ListNode meta=new ListNode(0 ); meta.next=pHead; ListNode p1=meta; ListNode p2=pHead; if (p2==null )return p2; while (p2!=null &&p2.next!=null ){ if (p2.next.val==p2.val){ while (p2.next!=null &&p2.next.val==p2.val){ p2=p2.next; } p1.next=p2.next; p2=p2.next; } else { p1=p1.next; p2=p2.next; } } return meta.next; } }
JZ57 二叉树的下一个结点 题目：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：
有右孩子，找到右孩子的最左左孩子
没有右孩子
节点是父节点的左孩子，返回父节点
节点是父节点的右孩子，递归父节点
节点或父节点是null，返回null
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class Solution public TreeLinkNode GetNext (TreeLinkNode pNode) { TreeLinkNode tmpNode; if (pNode.right!=null ){ tmpNode=pNode.right; while (tmpNode.left!=null )tmpNode=tmpNode.left; return tmpNode; } else { return rightNode(pNode); } } TreeLinkNode rightNode (TreeLinkNode pNode) { if (pNode==null ||pNode.next==null )return null ; if (pNode.next.left==pNode){ return pNode.next; } else { return rightNode(pNode.next); } } }
JZ58 对称的二叉树 题目：
请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路：
JZ59 按之字形顺序打印二叉树 题目：
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路：
层序遍历，然后分奇偶插入Deque的前后
层序遍历，然后分奇偶插入做Collections.reverse
用两个栈。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import java.util.ArrayList;import java.util.Stack;public class Solution public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { Stack<TreeNode> stackji=new Stack<>(); Stack<TreeNode> stackou=new Stack<>(); ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>(); if (pRoot==null )return result; stackji.push(pRoot); while (!stackou.empty()||!stackji.empty()){ ArrayList<Integer> jishu=new ArrayList<Integer>(); while (!stackji.empty()){ TreeNode tmp=stackji.pop(); if (tmp==null )continue ; jishu.add(tmp.val); stackou.push(tmp.left); stackou.push(tmp.right); } ArrayList<Integer> oushu=new ArrayList<Integer>(); while (!stackou.empty()){ TreeNode tmp2=stackou.pop(); if (tmp2==null )continue ; oushu.add(tmp2.val); stackji.push(tmp2.right); stackji.push(tmp2.left); } if (!jishu.isEmpty())result.add(jishu); if (!oushu.isEmpty())result.add(oushu); } return result; } }
JZ60 把二叉树打印成多行 题目：
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行
思路：
层序遍历
JZ61 序列化二叉树 题目：
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树
思路：
以前序遍历为例，写个前序遍历，再写个递归来反序列化。重点是：
String类型要比较的话要用equals()
String类型分割用split()成String[]
String转Int用Integer.parseInt()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.util.Stack;public class Solution int index=0 ; String Serialize (TreeNode root) { StringBuilder result=new StringBuilder("" ); Stack<TreeNode> myStack=new Stack<>(); myStack.push(root); TreeNode tmp; while (!myStack.empty()){ tmp=myStack.pop(); if (tmp==null ){ result.append("#!" ); continue ; } else { result.append(String.valueOf(tmp.val)+"!" ); myStack.push(tmp.right); myStack.push(tmp.left); } } return result.toString(); } TreeNode Deserialize (String str) { index=0 ; String[]strnew=str.split("!" ); return Des(strnew); } TreeNode Des (String []strnew) { TreeNode newtree=null ; if (strnew[index].equals("#" )){ index++; return newtree; } else { int now=Integer.parseInt(strnew[index]); newtree=new TreeNode(now); index++; newtree.left=Des(strnew); newtree.right=Des(strnew); return newtree; } } }
JZ62 二叉搜索树的第k个结点 题目：
给定一棵二叉搜索树，请找出其中的第k小的结点。
思路：
中序遍历，注意k的界限判定
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import java.util.*;public class Solution TreeNode KthNode (TreeNode pRoot, int k) { TreeNode newnode=pRoot; LinkedList<TreeNode> relink=new LinkedList<>(); Stack<TreeNode> restack=new Stack<>(); while (!restack.empty()||newnode!=null ){ while (newnode!=null ){ restack.push(newnode); newnode=newnode.left; } TreeNode tmp=restack.pop(); relink.add(tmp); newnode=tmp.right; } if (k<1 ||k>relink.size())return null ; return relink.get(k-1 ); } }
JZ63 数据流中的中位数 题目：
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路：
用两个优先级队列，一个小顶堆min一个大顶堆max，min队首是队中最小值，max队首是队中最大值。保证min的队首>max的队首。每次都插入新数据到min，如果min队首小于max了，就将队首放到max中。如果两个堆的size相差2了，就平衡一下两个堆的元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*;public class Solution PriorityQueue<Integer> minHeap=new PriorityQueue<>(); PriorityQueue<Integer> maxHeap=new PriorityQueue<>(maxcp); public static Comparator<Integer> maxcp=new Comparator<Integer>(){ @Override public int compare (Integer c1,Integer c2) return (int )(c2-c1); } }; public void Insert (Integer num) minHeap.offer(num); if (!maxHeap.isEmpty()&&minHeap.peek()<maxHeap.peek()){ maxHeap.offer(minHeap.poll()); } if (minHeap.size()-maxHeap.size()==2 ){ maxHeap.offer(minHeap.poll()); } if (minHeap.size()-maxHeap.size()==-2 ){ minHeap.offer(maxHeap.poll()); } } public Double GetMedian () if (minHeap.size()>maxHeap.size()){ return minHeap.peek().doubleValue(); } else if (minHeap.size()<maxHeap.size()){ return maxHeap.peek().doubleValue(); } else { return (maxHeap.peek().doubleValue()+minHeap.peek().doubleValue())/2.0 ; } } }
JZ64 滑动窗口的最大值 题目：
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度的时候，返回空
思路：
假设我们当前遍历到下标i，对于下标i+1的元素（假设i和i+1都在同一个窗口）
如果arr[i+1] >arr[i], 那么arr[i]永远不可能是窗口最大值
如果arr[i+1] < arr[i]，那么arr[i]和arr[i+1]都需要保留，因为之后可能arr[i]之前的最大值会失效
所以使用双端队列ArrayDeque
遍历数组的每一个元素，
如果容器为空，则直接将当前元素加入到容器中。
如果容器不为空，则让当前元素和容器的最后一个元素比较，如果大于，则将容器的最后一个元素删除，然后继续讲当前元素和容器的最后一个元素比较
如果当前元素小于容器的最后一个元素，则直接将当前元素加入到容器的末尾
如果容器头部的元素已经不属于当前窗口的边界，则应该将头部元素删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.util.*;public class Solution public ArrayList<Integer> maxInWindows (int [] num, int size) { ArrayList<Integer> result=new ArrayList<>(); if (size>num.length||size<=0 )return result; int flag=0 ; ArrayDeque<Integer> wd=new ArrayDeque<>(); for (int i=0 ;i<num.length;i++){ if (wd.isEmpty()){ wd.addFirst(num[0 ]); } else { if (i>=size&&num[i-size]==wd.peek()){ wd.pollFirst(); } while (!wd.isEmpty()&&(num[i]>wd.getLast())){ wd.pollLast(); } wd.addLast(num[i]); } if (i>=size-1 )result.add(wd.getFirst()); } return result; } }
JZ65 矩阵中的路径 题目：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路：
使用回溯递归。
算法框架：
1 2 3 4 5 6 7 8 9 10 result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 public class Solution public boolean hasPath (char [] matrix, int rows, int cols, char [] str) { for (int i=0 ;i<rows;i++){ for (int j=0 ;j<cols;j++){ int []done=new int [rows*cols]; int stridx=0 ; if (head(i,j,done,rows,cols,matrix,str,stridx))return true ; } } return false ; } boolean head (int nowrow,int nowcol,int []done, int rows,int cols, char []matrix,char []str,int stridx) if (matrix[nowrow*cols+nowcol]!=str[stridx]){ return false ; } else { stridx++; if (stridx==str.length)return true ; done[nowrow*cols+nowcol]=1 ; if (nowcol-1 >=0 &&done[nowrow*cols+nowcol-1 ]!=1 ){ boolean bleft=head(nowrow,nowcol-1 ,done,rows,cols,matrix,str,stridx); if (bleft)return true ; } if (nowcol+1 <cols&&done[nowrow*cols+nowcol+1 ]!=1 ){ boolean bright=head(nowrow,nowcol+1 ,done,rows,cols,matrix,str,stridx); if (bright)return true ; } if (nowrow-1 >=0 &&done[(nowrow-1 )*cols+nowcol]!=1 ){ boolean bup=head(nowrow-1 ,nowcol,done,rows,cols,matrix,str,stridx); if (bup)return true ; } if (nowrow+1 <rows&&done[(nowrow+1 )*cols+nowcol]!=1 ){ boolean bdown=head(nowrow+1 ,nowcol,done,rows,cols,matrix,str,stridx); if (bdown)return true ; } return false ; } } }
JZ66 机器人的运动范围 题目：
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路：
回溯递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public class Solution int num=0 ; public int movingCount (int threshold, int rows, int cols) { num=0 ; int [][]done=new int [rows][cols]; next(threshold,rows,cols,0 ,0 ,done); return num; } public void next (int thre,int rows,int cols,int nowrow,int nowcol,int [][]done) if (nowrow<rows && nowcol<cols && nowrow>=0 && nowcol>=0 && done[nowrow][nowcol]!=1 && legal(nowrow,nowcol,thre)){ num++; done[nowrow][nowcol]=1 ; next(thre,rows,cols,nowrow,nowcol-1 ,done); next(thre,rows,cols,nowrow,nowcol+1 ,done); next(thre,rows,cols,nowrow+1 ,nowcol,done); next(thre,rows,cols,nowrow-1 ,nowcol,done); } } public boolean legal (int row,int col,int thre) int tmp=0 ; while (row!=0 ){ tmp+=row%10 ; row/=10 ; } while (col!=0 ){ tmp+=col%10 ; col/=10 ; } if (tmp>thre)return false ; return true ; } }
JZ67 剪绳子 题目：
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
思路：
暴力递归会超时，采用一个数组，记录已经计算过的值。
另外注意对于2,3来说，如果是绳子长，那么最大值分别是1和2，如果是递归中，那么最大值是2和3.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public class Solution public int cutRope (int target) int [] done=new int [target+1 ]; if (target==2 )return 1 ; if (target==3 )return 2 ; for (int i=1 ;i<=4 ;i++){ done[i]=i; } return back(target,done); } public int back (int target,int []done) int maxnum=0 ; if (target<=4 )return target; for (int i=1 ;i<target;i++){ if (done[target-i]==0 ){ done[target-i]=back(target-i,done); } maxnum=Math.max(maxnum,i*done[target-i]); } return maxnum; } }
