本文共 18364 字，大约阅读时间需要 61 分钟。
下面整理一下我在刷剑指offer时，自己做的和网上大神做的各种思路与答案，自己的代码是思路一，保证可以通过，网友的代码提供出处链接。
目录
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路一：非递归/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null)return list2; if(list2==null)return list1; ListNode t=new ListNode(520);//随便哪个值都一样，反正只返回它的next ListNode list=t; while(list1!=null&&list2!=null){ if(list1.val<=list2.val){ t.next=list1; t=t.next; list1=list1.next; } else{ t.next=list2; t=t.next; list2=list2.next; } } if(list1==null)t.next=list2; if(list2==null)t.next=list1; return list.next; }} 思路二：递归
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null)return list2; if(list2==null)return list1; ListNode t=null; if(list1.val 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路一：递归，FL函数返回一个树转化为双向链表后的头节点和尾节点，对根节点的左右两个子树分别递归，然后将递归得到的左右两段与中间的根节点建立双向联系，拼起来。/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null)return null; TreeNode[] A=FL(pRootOfTree); return A[0]; } TreeNode[] FL(TreeNode p){ TreeNode[] t=new TreeNode[2];//左边放头节点，右边放尾节点 if(p.left==null&&p.right==null){ t[0]=p; t[1]=p; } else if(p.right==null){ TreeNode[] t1=FL(p.left); p.left=t1[1]; p.left.right=p; t[0]=t1[0]; t[1]=p; } else if(p.left==null){ TreeNode[] t1=FL(p.right); p.right=t1[0]; p.right.left=p; t[0]=p; t[1]=t1[1]; } else{ TreeNode[] t1=FL(p.left); TreeNode[] t2=FL(p.right); p.left=t1[1]; p.left.right=p; p.right=t2[0]; p.right.left=p; t[0]=t1[0]; t[1]=t2[1]; } return t; }} 用递归来中序遍历，用pre来保存前一个节点
public class Solution{ TreeNode head=null; TreeNode pre=null; public TreeNode Convert(TreeNode root) { f(root); return head; } void f(TreeNode t){ if(t==null)return; f(t.left); if(pre!=null){ pre.right=t; t.left=pre; } else{ head=t; } pre=t; f(t.right); } }/**//请注意，这样为什么就错了public class Solution { TreeNode head = null; public TreeNode Convert(TreeNode root) { TreeNode pre = null; f(root, pre); return head; } void f(TreeNode t, TreeNode pre) { if (t == null) return; f(t.left, pre); if (pre != null) { pre.right = t; t.left = pre; } else { head = t; } pre = t; f(t.right, pre); }}*/ 思路二：非递归，中序遍历
import java.util.Stack;public class Solution { public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null)return null; Stack s=new Stack<>(); TreeNode t=pRootOfTree; TreeNode pre=null; TreeNode head=null; do{ if(t!=null){ s.push(t); t=t.left; } else{ t=s.pop(); if(pre==null){ //第一个节点 pre=t; head=pre; //头节点要保存下来 } else{ //将遍历到的节点与前一个节点建立双向联系 pre.right=t; t.left=pre; pre=t; //更新pre } t=t.right; } }while(t!=null||!s.isEmpty()); return head; }} 思路三：不论是用栈还是递归，都要使用O(n)的空间，与前两种方法的不同在于该方法只需要O(1)空间，而且同样可以在O(n)时间内完成
来自public class Solution { public TreeNode Convert(TreeNode pRootOfTree) { TreeNode p = pRootOfTree, pre = null, res = null; while (p != null) { //p是按中序遍历顺序，如果p为空说明整个树都遍历完了 //p的左子树不为空，按中序遍历来说，左子树里面还有应该在p前面的点 while (p.left != null) { //找到p的左子树里面最右的结点，这个点的右节点指向空，但这个节点是p的前驱，所以将空的右节点指向p TreeNode q = p.left; while (q.right != null) { q = q.right; } q.right = p; //当我们可以从p的左子树里面通过上面建立的指针回到p点，p应该更新为p的左节点，然后旧的p点的左指针指向空 TreeNode tmp = p.left; p.left = null; p = tmp; } //p的左节点为空，p就是当前要加入双向链表的点，将p点与pre建立双向联系 p.left = pre; if (pre == null) { res = p; } else { pre.right = p; } pre = p; //p更新为p的右节点 p = p.right; } return res; }} 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路一：用状态数组标记public boolean duplicate(int numbers[],int length,int [] duplication) { int[] count=new int[length]; for(int i=0;i 1){ duplication[0]=numbers[i]; return true; } } return false; }} 但是int数组占用空间有点大，考虑到题目只是找重复的数，而不关心重复的数到底重复了几次，因此可以用布尔数组，或者bit-map
来自//碰到第一个重复的，输出，结束，后面的都不用看了public boolean duplicate(int numbers[], int length, int[] duplication) { boolean[] k = new boolean[length]; for (int i = 0; i < k.length; i++) { if (k[numbers[i]] == true) { duplication[0] = numbers[i]; return true; } k[numbers[i]] = true; } return false; } 思路二：由于题目保证数组中的数不会超过length-1，因此就用这个数组本身当标记数组，怎么标记呢，把num[i]+=length，弊端就是：一、改变了原来的数组，如果输入的数组有误，里面有数本来就超过了length-1，就搞不清是自己加得还是本来就这么大；二、如果length太大，加几次搞不好要溢出Integer.MAX_VALUES。
来自bool duplicate(int numbers[], int length, int* duplication) { for(int i=0;i!=length;++i){ int index=numbers[i]%length;//取余得到真面目 if(numbers[index]>=length){ //大于length-1说明重了 *duplication=index; return 1; } numbers[index]+=length; } return 0;} 思路三：交换来判断，它可以找到所有重复的数，但是：一、它改变了原数组；二、对于输入016645778，输出的是7而不是6，而第一个重复的数明明是6
来自/*1、判断输入数组有无元素非法2、从头扫到尾，只要当前元素值与下标不同，就做一次判断,numbers[i]与numbers[numbers[i]]，相等就认为找到了重复元素，返回true,否则就交换两者，继续循环。直到最后还没找到认为没找到重复元素，返回false*/class Solution {public: // Parameters: // numbers: an array of integers // length: the length of array numbers // duplication: (Output) the duplicated number in the array number // Return value: true if the input is valid, and there are some duplications in the array number // otherwise false bool duplicate(int numbers[], int length, int* duplication) { if(length<=0||numbers==NULL) return false; //判断每一个元素是否非法 for(int i=0;i length-1) return false; } for(int i=0;i 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路一：模拟栈的状态import java.util.ArrayList;public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { ArrayList a=new ArrayList<>(); //寻找第一个出栈的数字在入栈序列中的位置 int index=-1; for(int m=0;m i){ for(i++;i 同样是模拟栈的状态，大神的答案更加简洁精炼
来自import java.util.ArrayList;import java.util.Stack;public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { if(pushA.length == 0 || popA.length == 0) return false; Stack s = new Stack (); //用于标识弹出序列的位置 int popIndex = 0; for(int i = 0; i< pushA.length;i++){ s.push(pushA[i]); //如果栈不为空，且栈顶元素等于弹出序列 while(!s.empty() &&s.peek() == popA[popIndex]){ //出栈 s.pop(); //弹出序列向后一位 popIndex++; } } return s.empty(); }} 一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
思路一： O(n2) O ( n 2 ) 时间复杂度，不可取import java.util.Iterator;import java.util.LinkedList;public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { LinkedList l=new LinkedList<>(); boolean f; for(int i=0;i 需要关注
思路二：异或大法好
来自/** * 数组中有两个出现一次的数字，其他数字都出现两次，找出这两个数字 * @param array * @param num1 * @param num2 */ public static void findNumsAppearOnce(int [] array,int num1[] , int num2[]) { if(array == null || array.length <= 1){ num1[0] = num2[0] = 0; return; } int len = array.length, index = 0, sum = 0; //DABCDC异或之后，等于AB异或的值 for(int i = 0; i < len; i++){ sum ^= array[i]; } //AB异或一定不为0，那结果的二进制至少有一位为1，从右到左找出第一个为1的位的位置 for(index = 0; index < 32; index++){ if((sum & (1 << index)) != 0) break; } //以这个位置为划分标准划分两个数组，结果是，AB分别在不同数组，且每个数组剩余的数都是成对的 for(int i = 0; i < len; i++){ if((array[i] & (1 << index))!=0){ num2[0] ^= array[i]; }else{ num1[0] ^= array[i]; } } /**//来自牛客网@drdr int split = sum&~(sum - 1);//神了！！！ for(int i = 0; i < len; i++){ if((array[i] & split)!=0){ num2[0] ^= array[i]; }else{ num1[0] ^= array[i]; } } */ }/** * 数组a中只有一个数出现一次，其他数都出现了2次，找出这个数字 * @param a * @return */ public static int find1From2(int[] a){ int len = a.length, res = 0; for(int i = 0; i < len; i++){ res = res ^ a[i]; } return res; }/** * 数组a中只有一个数出现一次，其他数字都出现了3次，找出这个数字 * @param a * @return */ public static int find1From3(int[] a){ int[] bits = new int[32]; int len = a.length; for(int i = 0; i < len; i++){ for(int j = 0; j < 32; j++){ bits[j] = bits[j] + ( (a[i]>>>j) & 1); } } int res = 0; for(int i = 0; i < 32; i++){ if(bits[i] % 3 !=0){ //不是3的整数倍的位，那个单独的数这个位一定为1 res = res | (1 << i); } } return res; } 思路三：HashMap
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
思路一：单纯的递归，效率很低，有很多重复的计算，可能StackOverflow。public class Solution { public int Fibonacci(int n) { if(n==0)return 0;//这两个if可以合并啊 if(n==1)return 1; return Fibonacci(n-1)+Fibonacci(n-2); }} 尾递归，可避免溢出
来自public class Solution { public int Fibonacci(int n) { return Fibonacci(n,0,1); } private static int Fibonacci(int n,int acc1,int acc2){ if(n==0) return 0; if(n==1) return acc2; else return Fibonacci(n - 1, acc2, acc1 + acc2); }} 思路二：迭代
来自class Solution {public: int Fibonacci(int n) { int f = 0, g = 1; while(n-->0) { g += f; f = g - f; } return f; }}; 来自
public class Solution { public int Fibonacci(int n) { int preNum=1; int prePreNum=0; int result=0; if(n==0)return 0; if(n==1)return 1; for(int i=2;i<=n;i++){ result=preNum+prePreNum; prePreNum=preNum; preNum=result; } return result; }} 思路三：快速幂， O(logn) O ( l o g n ) 的时间复杂度
来自/* * O(logN)解法：由f(n) = f(n-1) + f(n-2)，可以知道 * [f(n),f(n-1)] = [f(n-1),f(n-2)] * {[1,1],[1,0]} * 所以最后化简为:[f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2) * 所以这里的核心是： * 1.矩阵的乘法 * 2.矩阵快速幂（因为如果不用快速幂的算法，时间复杂度也只能达到O(N)） */public class Solution { public int Fibonacci(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return 1; } //底 int[][] base = { { 1,1}, { 1,0}}; //求底为base矩阵的n-2次幂 int[][] res = matrixPower(base, n - 2); //根据[f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2)，f(n)就是 //1*res[0][0] + 1*res[1][0] return res[0][0] + res[1][0]; } //矩阵乘法 public int[][] multiMatrix(int[][] m1,int[][] m2) { //参数判断什么的就不给了，如果矩阵是n*m和m*p,那结果是n*p int[][] res = new int[m1.length][m2[0].length]; for (int i = 0; i < m1.length; i++) { for (int j = 0; j < m2[0].length; j++) { for (int k = 0; k < m2.length; k++) { res[i][j] += m1[i][k] * m2[k][j]; } } } return res; } /* * 矩阵的快速幂： * 1.假如不是矩阵，叫你求m^n,如何做到O(logn)？答案就是整数的快速幂： * 假如不会溢出，如10^75,把75用用二进制表示：1001011,那么对应的就是： * 10^75 = 10^64*10^8*10^2*10 * 2.把整数换成矩阵，是一样的 */ public int[][] matrixPower(int[][] m, int p) { int[][] res = new int[m.length][m[0].length]; //先把res设为单位矩阵 for (int i = 0; i < res.length; i++) { res[i][i] = 1; } //单位矩阵乘任意矩阵都为原来的矩阵 //用来保存每次的平方 int[][] tmp = m; //p每循环一次右移一位 for ( ; p != 0; p >>= 1) { //如果该位不为零，应该乘 if ((p&1) != 0) { res = multiMatrix(res, tmp); } //每次保存一下平方的结果 tmp = multiMatrix(tmp, tmp); } return res; } } 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思路：左右加逼大法import java.util.ArrayList;public class Solution { public ArrayList FindNumbersWithSum(int [] array,int sum) { ArrayList A=new ArrayList(); int len=array.length; if(len<2)return A; int small=-1,large=-1,M=Integer.MAX_VALUE; for(int m=0,n=len-1;m sum){n--;} else{ //找到了，就筛选出乘积最小的 if(m*n 不过可证明找到的第一组数字，它们之间的距离最远，所以乘积最小，所以筛选的工作可以免了。
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：这个节点有右子树，下一个点就是右子树的最左的节点；如果没有右子树，判断自己是不是自己父节点的左节点，如果是，下一个节点就是自己的父节点，如果自己是自己父节点的右节点，那就向上找子节点是父节点左节点的情况。
/**public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; }}*/public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode){ if(pNode.right!=null){ TreeLinkNode t=pNode.right; while(t.left!=null)t=t.left; return t; } TreeLinkNode p=pNode.next;//parent-node TreeLinkNode c=pNode;//child-node while(p!=null&&p.right==c){ c=p; p=p.next; } return p; }} 统计一个数字在排序数组中出现的次数。
思路一：原谅我一时没反应过来它的考点，请无视
public class Solution { public int GetNumberOfK(int [] array , int k) { int c=0; for(int i=0;i 思路二：二分查找， O(logn) O ( l o g n ) 的时间复杂度
来自public class Solution { public int GetNumberOfK(int [] array , int k) { int length = array.length; if(length == 0){ return 0; } int firstK = getFirstK(array, k, 0, length-1); int lastK = getLastK(array, k, 0, length-1); if(firstK != -1 && lastK != -1){ return lastK - firstK + 1; } return 0; } //递归写法 private int getFirstK(int [] array , int k, int start, int end){ if(start > end){ return -1; } int mid = (start + end) >> 1; //int mid=start+(end-start)>>1 //其实这样更好，避免start + end太大溢出 if(array[mid] > k){ return getFirstK(array, k, start, mid-1); }else if (array[mid] < k){ return getFirstK(array, k, mid+1, end); }else if(mid-1 >=0 && array[mid-1] == k){ return getFirstK(array, k, start, mid-1); }else{ return mid; } } //循环写法 private int getLastK(int [] array , int k, int start, int end){ int length = array.length; int mid = (start + end) >> 1; while(start <= end){ if(array[mid] > k){ end = mid-1; }else if(array[mid] < k){ start = mid+1; }else if(mid+1 < length && array[mid+1] == k){ start = mid+1; }else{ return mid; } mid = (start + end) >> 1; } return -1; }} 还有更简洁的
来自//因为data中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索k-0.5和k+0.5//这两个数应该插入的位置，然后相减即可。class Solution {public: int GetNumberOfK(vector data ,int k) { return biSearch(data, k+0.5) - biSearch(data, k-0.5) ; }private: int biSearch(const vector & data, double num){ int s = 0, e = data.size()-1; while(s <= e){ int mid = (e - s)/2 + s; if(data[mid] < num) s = mid + 1; else if(data[mid] > num) e = mid - 1; } return s; }}; 上述方法，就算k不存在于数组中，两次查找返回的值都是一样的，相减为0，没问题。
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路一：第一想法在每层节点之间加null节点来分隔，不过可以计数不用分隔符
import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;public class Solution { ArrayList > Print(TreeNode pRoot) { ArrayList > AA=new ArrayList >(); if(pRoot==null)return AA; Queue q=new LinkedList<>(); q.offer(pRoot); int count,c; ArrayList A=new ArrayList<>(); while(!q.isEmpty()){ count=q.size(); c=0; while(c++ (A)); A.clear(); } return AA; }} 思路二：层序遍历，还可以递归，扩展思路
来自//用递归做的public class Solution { ArrayList > Print(TreeNode pRoot) { ArrayList > list = new ArrayList<>(); depth(pRoot, 1, list); return list; } private void depth(TreeNode root, int depth, ArrayList > list) { if(root == null) return; if(depth > list.size())//先构造一个空的ArrayList，传入嵌套容器 list.add(new ArrayList ()); list.get(depth -1).add(root.val);//然后把同一层的节点装进去 depth(root.left, depth + 1, list); depth(root.right, depth + 1, list); }} 思路三：用两个队列，来交替存储每层的节点
转载地址：http://tehci.baihongyu.com/