本文共 16810 字，大约阅读时间需要 56 分钟。
下面整理一下我在刷剑指offer时，自己做的和网上大神做的各种思路与答案，自己的代码是思路一，保证可以通过，网友的代码提供出处链接。
目录
n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。
思路一：用数组模拟环public class Solution { public int LastRemaining_Solution(int n, int m) { boolean[] flag=new boolean[n];//已经删除的要做标记 int alive=n-1; int index=0; int c=0; while(alive>0){ while(c!=m){ if(!flag[index]){c++;}//删除过的就不理它 if(index+1==n)index=0; else index++; } //将应该删除的点置true if(index==0)flag[n-1]=true; else flag[index-1]=true; alive--; c=0; } for(int i=0;i 数组做标记到后期有很多无谓的判断，因为好多都已经标记为删除了，不是很好。
思路二：用链表模拟，真正的删除，时间和空间复杂度都是 O(n) O ( n )
来自import java.util.LinkedList;public class Solution { public int LastRemaining_Solution(int n, int m) { LinkedList list = new LinkedList (); for (int i = 0; i < n; i ++) { list.add(i); } int bt = 0; while (list.size() > 1) { bt = (bt + m - 1) % list.size(); list.remove(bt); } return list.size() == 1 ? list.get(0) : -1; }} 思路三：推出递推公式。设A轮为：从n个人中删去下标为m-1的数，下一轮B：记下标为m的数下标为0，重新开始删除，假设从B轮开始最后留下的数下标是x，那么这个数在A轮该数的下标就是(x+m)%n
B—A0— m
1—m+1 2—m+2 ~~~ n-m-1—n-1 n-m—0 n-m+1—1 ~~ n-2—m-2 n-1—m-1（A到B时已经删掉了）所以最后一轮只有一个人的局，留下的是0，那么倒数第二轮有两个人的局，留下的是（0+m）%2，···，然后一直算到有n个人的局
public class Solution { public int LastRemaining_Solution(int n,int m) { if(n==0) return -1; int s=0; for(int i=2;i<=n;i++){ s=(s+m)%i; } return s; }} 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路一：层序遍历，遍历完每一层判断序列是否对称，如果子节点为空则标记为“#”
import java.util.Queue;import java.util.LinkedList;public class Solution { boolean isSymmetrical(TreeNode pRoot){ if(pRoot==null)return true; Queue q=new LinkedList<>(); StringBuffer sb=new StringBuffer(); q.add(pRoot); TreeNode t; while(!q.isEmpty()){ int count=q.size(); while(count-->0){ t=q.poll(); if(t.left==null){sb.append("#");} else{q.offer(t.left);sb.append(t.left.val);} if(t.right==null){sb.append("#");} else{q.offer(t.right);sb.append(t.right.val);} } String s=sb.toString(); sb=new StringBuffer(); int m=0,n=s.length()-1; while(m 将根节点的左右子树看作两颗树，对这两棵树同步遍历（同时遍历镜像中的对应的点），边遍历边判断
来自//层序，左树从左到右，右树从右到左class Solution {public: bool isSymmetric(TreeNode* root) { if(root==NULL) return true; queue q1,q2; TreeNode *left,*right; q1.push(root->left); q2.push(root->right); while(!q1.empty() and !q2.empty()){ left = q1.front(); q1.pop(); right = q2.front(); q2.pop(); //两边都是空 if(NULL==left && NULL==right) continue; //只有一边是空 if(NULL==left||NULL==right) return false; if (left->val != right->val) return false; q1.push(left->left); q1.push(left->right); q2.push(right->right); q2.push(right->left); } return true; }}; 来自
//左树中序遍历，右树跟着左树镜像遍历class Solution {public: bool isSymmetrical(TreeNode* pRoot){ stack s1,s2; TreeNode *p1,*p2; p1=p2=pRoot; while((!s1.empty()&&!s2.empty())||(p1!=NULL&&p2!=NULL)){ while(p1!=NULL&&p2!=NULL){ s1.push(p1); s2.push(p2); p1=p1->left; p2=p2->right; } p1=s1.top(); s1.pop(); p2=s2.top(); s2.pop(); if(p1->val!=p2->val) return false; p1=p1->right; p2=p2->left; } if(!s1.empty()||!s2.empty()) return false; if(p1!=NULL||p2!=NULL) return false; return true; }}; 思路二：只用一个栈或者队列，将镜像中对应的点，即一个对子，同时入，并且同时出
来自//DFSboolean isSymmetricalDFS(TreeNode pRoot){ if(pRoot == null) return true; Stack s = new Stack<>(); s.push(pRoot.left); s.push(pRoot.right); while(!s.empty()) { TreeNode right = s.pop();//成对取出 TreeNode left = s.pop(); if(left == null && right == null) continue; if(left == null || right == null) return false; if(left.val != right.val) return false; //成对插入 s.push(left.left); s.push(right.right); s.push(left.right); s.push(right.left); } return true; } //BFSboolean isSymmetricalBFS(TreeNode pRoot){ if(pRoot == null) return true; Queue s = new LinkedList<>(); s.offer(pRoot.left); s.offer(pRoot.right); while(!s.isEmpty()) { TreeNode right = s.poll();//成对取出 TreeNode left = s.poll(); if(left == null && right == null) continue; if(left == null || right == null) return false; if(left.val != right.val) return false; //成对插入 s.offer(left.left); s.offer(right.right); s.offer(left.right); s.offer(right.left); } return true; } 思路三：递归
来自boolean isSymmetrical(TreeNode pRoot) { if (pRoot == null)return true; return f(pRoot.left,pRoot.right); } boolean f(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 != null && t2 != null) return t1.val == t2.val && f(t1.left,t2.right) && f(t1.right, t2.left); return false; } 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路一：对每层的节点计数
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<>(); TreeNode t; 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())//先添加个空A进去，再将同一层的节点加入这个A中 list.add(new ArrayList ()); list.get(depth -1).add(root.val); depth(root.left, depth + 1, list); depth(root.right, depth + 1, list); }} 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。
思路一： YX=(XTYT)T Y X = ( X T Y T ) Tpublic class Solution { public String LeftRotateString(String str,int n) { if(str==null||str.length()==0||n==0)return str; char[] chars = str.toCharArray(); n%=chars.length; reverse(chars, 0, n-1); reverse(chars, n, chars.length-1); reverse(chars, 0, chars.length-1); return new String(chars); } public void reverse(char[] chars,int low,int high){ char temp; while(low 思路二：来自
类似于java的Collections的rotate方法的实现: Collections的rotate有两种实现：本题可看做是第一种，因此采用递推的思想：
public class Solution { //rotation public String LeftRotateString(String str,int n) { int len = str.length(); if (n == 0 || len == 0) return str; n %= len; char[] ch = str.toCharArray(); int doneCnt = 0, i = 0; while (doneCnt < len && i < len) { int j = i++; char cur = ch[j];//cur与 旋转后它应该在的位置 上的数比较，不同就交换，相同则cur已经在旋转后的位置上了 while (cur != ch[j=(j-n+len)%len]) { char tmp = ch[j]; ch[j] = cur; cur = tmp; //exchange doneCnt++; } } return new String(ch); }} 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路一：
/** public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead){ if(pHead==null||pHead.next==null)return null; ListNode fast=pHead; ListNode slow=pHead; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow)break; //异速指针相遇 } if(fast!=slow)return null;//没有环 slow=pHead; while(fast!=slow){ //一个从相遇点，一个从起点，同速运动 fast=fast.next; slow=slow.next; } return fast; }} 思路二：断链法，破坏了链表结构，不推荐。
来自/**时间复杂度为O（n），两个指针，一个在前面，另一个紧邻着这个指针，在后面。两个指针同时向前移动，每移动一次，前面的指针的next指向NULL。也就是说：访问过的节点都断开，最后到达的那个节点一定是尾节点的下一个，也就是循环的第一个。这时候已经是第二次访问循环的第一节点了，第一次访问的时候我们已经让它指向了NULL，所以到这结束。*/class Solution {public: ListNode* EntryNodeOfLoop(ListNode* pHead){ if (!pHead->next) return NULL; ListNode* previous = pHead; ListNode* front = pHead ->next; while (front){ previous->next = NULL; previous = front; front = front->next; } return previous; }}; 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路一：快速幂
public class Solution { public double Power(double base, int exponent) { double result=1; int i=0; boolean flag=false; if(exponent<0){exponent=-exponent;flag=true;} while(i<32){ //if((exponent&(1< >i&1)==1){ result*=base; } i++; if((1< exponent)break; base*=base; } return flag?1/result:result; }} 上面我写的很乱，而且没有判断base是不是等于0，下面
来自//快速幂 public double Power(double base, int exponent) { if (exponent == 0) { return 1.0; } if (base - 0.0 == 0.00001 || base - 0.0 == -0.00001) { if (exponent < 0) { throw new RuntimeException("除0异常"); }else{ return 0.0; } } int e = exponent > 0 ? exponent: -exponent; double res = 1; while (e != 0) { //等于0就停止循环 res = (e & 1) != 0 ? res * base : res; base *= base; e = e >> 1; } return exponent > 0 ? res : 1/res; } 思路二：递归，分奇数偶数
// 递归 public double Power(double base, int exponent) { if (exponent == 0) { return 1.0; } if (base - 0.0 == 0.00001 || base - 0.0 == -0.00001) { if (exponent < 0) { throw new RuntimeException("除0异常"); }else{ return 0.0; } } return exponent > 0 ? getPower(base, exponent) : 1/getPower(base, -exponent); } public static double getPower(double base, int e) { if (e == 1) { return base; } double halfPower = getPower(base, e >> 1);//e右移一位，e是奇数则结果是（e-1）/2，e偶数则是e/2 return (e & 1) != 0 ? base * halfPower * halfPower : halfPower * halfPower; } 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路：用空间换时间，需要辅助栈存最小数。//辅助栈的高度与存储栈的一样import java.util.Stack;public class Solution { Stack s=new Stack<>(); Stack sAssist=new Stack<>(); public void push(int node) { s.push(node); if(!sAssist.isEmpty()&&sAssist.peek() 考虑每次入栈的时候，如果入栈的元素比min中的栈顶元素小或等于则入栈，否则不如栈。比如，
data中依次入栈，5, 4, 3, 8, 10, 11, 12, 1 则min依次入栈，5, 4, 3，no,no, no, no, 1 但是这种方法在输入有多个重复最小值时，min栈出去一个最小值就没有这个值了，所有这种方法不太好。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：注意是非递减数列，可能有重复的。AB，A<=B，BA，最小值就是A部分的第一个值import java.util.ArrayList;public class Solution { public int minNumberInRotateArray(int [] array) { if(array==null||array.length==0)return 0; int s=0,e=array.length-1,mid; while(s array[s])s=mid+1;//说明mid在前一个非递减部分,最小值在mid的右边，s=mid+1 else s++;//不知道mid在前半部分还是后半部分，如22222212，22122222，我只能判定一个边界s++肯定不影响找到最小值 } else{ //头大于尾 if(array[mid]>=array[s]){s=mid+1;}//mid在前面一个序列 else{ e=mid;} } } return array[s]; }} 输入两个链表，找出它们的第一个公共结点。
思路一：最开始我想的是，将其中一条链变成环，知道环的长度，然后从另一条链的起点开始，一个指针先走环的长度的步数，另一个指针再走，两指针相遇的地方就是环的入口，也就是第一个公共节点。
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode p=pHead1; int c=1; while(p.next!=null){ p=p.next; c++; } p.next=pHead1; ListNode p1=pHead2; ListNode p2=pHead2; while(c!=0){ p1=p1.next; c--; } while(p1!=null){ p1=p1.next; p2=p2.next; if(p1==p2)return p1; } return null; }} 但是这代码一直显示循环超时，原来是我改变了链表的结构，牛客网打印返回的链表，从第一个公共节点开始往后是一个环，所以这个链表打印不出来。实际上是没必要更改链表结构的，要实现环的效果，手动将指针从尾部跳到头部就好了。
/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1==null||pHead2==null)return null; ListNode p=pHead1; //找到pHead1的长度，即环的长度 int c=1; while(p.next!=null){ p=p.next; c++; } //两个指针从pHead2的起点出发 ListNode p1=pHead2; ListNode p2=pHead2; for(;c>0;c--){ //p1先走环的长度，手动连接环的头尾 p1=p1.next==null?pHead1:p1.next; } //如果p2为空表示这两个链表根本就没有相交 while(p2!=null){ if(p1==p2)return p1; p1=p1.next==null?pHead1:p1.next; p2=p2.next; } return null; }} 思路二：找到两个链表长度之差，从长的链表的起点开始，一个指针先走长度之差，另一个指针从短的链表开始，相遇点就是两个链表的交点。
来自public ListNode FindFirstCommonNodeII(ListNode pHead1, ListNode pHead2) { ListNode current1 = pHead1;// 链表1 ListNode current2 = pHead2;// 链表2 if (pHead1 == null || pHead2 == null) return null; int length1 = getLength(current1); int length2 = getLength(current2); // 两连表的长度差 // 如果链表1的长度大于链表2的长度 if (length1 >= length2) { int len = length1 - length2; // 先遍历链表1，遍历的长度就是两链表的长度差 while (len > 0) { current1 = current1.next; len--; } } // 如果链表2的长度大于链表1的长度 else if (length1 < length2) { int len = length2 - length1; // 先遍历链表1，遍历的长度就是两链表的长度差 while (len > 0) { current2 = current2.next; len--; } } //开始齐头并进，直到找到第一个公共结点 while(current1!=current2){ current1=current1.next; current2=current2.next; } return current1; } // 求指定链表的长度 public static int getLength(ListNode pHead) { int length = 0; ListNode current = pHead; while (current != null) { length++; current = current.next; } return length; } 思路三：一个链表是AN，一个是BN，一个指针从A开始到链表尾部后跳到B，一个指针从B开始到链表尾部后跳到A，最终在交点处相遇，每个指针都走了A+B+N的距离。不过如果两个链表没有交点，下面的循环不会结束。
来自class Solution {public: ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) { ListNode *p1 = pHead1; ListNode *p2 = pHead2; while(p1!=p2){ p1 = (p1==NULL ? pHead2 : p1->next); p2 = (p2==NULL ? pHead1 : p2->next); } return p1; }}; 如1~13中包含1的数字有1、10、11、12、13。因此共出现6次。
思路一：递归public class Solution { public int NumberOf1Between1AndN_Solution(int n) { if(n==0)return 0; int x=1; while(n/(10*x)!=0)x*=10; //x为与N同位数的最小数，如n=134,x=100 if(x==1)return 1;//说明n为1到9 int a=n/x;//最高位上的数，如n=134，a=1 int b=n%x;//最高位后面的数，如n=134，b=34 // b里面含有1的个数+a*（1到x-1中含有1的个数）+最高位为1的个数 return f(b,x/10)+a*f(x-1,x/10)+(a>1?x:b+1); } //为了不用每次都循环找x int f(int n,int x){ if(n==0)return 0; if(x==1)return 1; int a=n/x; int b=n%x; //a可能为0 int c; if(a>1)c=x; else if(a==1)c=b+1; else c=0; return f(b,x/10)+a*f(x-1,x/10)+c; }} 思路二：待更新
转载地址：http://xehci.baihongyu.com/