剑指 Offer 05. 替换空格

  1. s.trim();
  2. StringBuilder builder=new StringBuilder();
  3. for(int i=0;i<s.length();i++){
  4.   if(s.substring(i,i+1).equals(" ")){
  5.     builder.append("%20");
  6.   }else{
  7.     builder.append(s.substring(i,i+1));
  8.   }
  9. }
  10. return builder.toString();

剑指 Offer 09. 用两个栈实现队列

  1. public void appendTail(int value) {
  2.   stack1.push(value);
  3. }
  5. public int deleteHead() {
  6.   //如果栈2是空
  7.   if(stack2.empty()){
  8.     //如果栈1也是空
  9.     if(stack1.empty()){
  10.       return -1;
  11.     }else{
  12.       //栈1一直弹出，直到栈1为空
  13.       while (!stack1.empty()) {
  14.         stack2.push(stack1.pop());
  15.       }
  16.     }
  17.   }
  18.   return stack2.pop();
  19. }

剑指 Offer 11. 旋转数组的最小数字

  1. if(right-left<=1){
  2.   return Math.min(nums[left],nums[right]);
  3. }
  4. if(nums[left]<nums[right]){
  5.   return nums[left];
  6. }
  7. int mid=(left+right)/2;
  8. return Math.min(findMin(nums, left, mid-1),findMin(nums,mid,right));

剑指 Offer 16. 数值的整数次方

  1. public class Solution2 {
  2.     double res=1;
  3.     public double myPow(double x,int n){
  4.         while (n>0){
  5.             if(n%2==0) {
  6.                 x *= x;
  7.                 n/=2;
  8.             }
  9.             res*=x;
  10.             n--;
  11.         }
  12.         while (n<0){
  13.             if(n%2==0){
  14.                 x*=x;
  15.                 n/=2;
  16.             }
  17.             res*=1/x;
  18.             n++;
  19.         }
  20.         return res;
  21.     }
  22. }

剑指 Offer 26. 树的子结构

  1. public boolean isSubStructure(TreeNode A, TreeNode B) {
  2.         if(A==null||B==null){
  3.             return false;
  4.         }
  5.         return Compare(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
  6.     }
  7.     private boolean Compare(TreeNode A,TreeNode B){
  8.         if(B==null){
  9.             return true;
  10.         }else if(A==null||A.val!=B.val){
  11.             return false;
  12.         }
  13.         return Compare(A.left,B.left)&&Compare(A.right,B.right);
  14.     }

剑指 Offer 31. 栈的压入、弹出序列

  1. Stack<Integer> stack = new Stack<>();
  2. int index=0;
  3. for(int i=0;i<pushed.length;i++){
  4.   stack.push(pushed[i]);
  5.   while (!stack.isEmpty()&&stack.peek()==popped[index]){
  6.     stack.pop();
  7.     index++;
  8.   }
  9. }
  10. return stack.isEmpty();

剑指 Offer 32 - III. 从上到下打印二叉树 III

  1. if(root==null){
  2.   return res;
  3. }
  4. Deque<TreeNode>queue=new LinkedList<>();
  5. queue.addLast(root);
  6. int index=0;
  7. while (!queue.isEmpty()){
  8.   List<Integer>singleRes=new ArrayList<>();
  9.   int size=queue.size();
  10.   for(int i=0;i<size;i++) {
  11.     TreeNode node = queue.pollFirst();
  12.     singleRes.add(node.val);
  13.     if(node.left!=null){
  14.       queue.addLast(node.left);
  15.     }
  16.     if(node.right!=null){
  17.       queue.addLast(node.right);
  18.     }
  19.   }
  20.   if(index%2==1){
  21.     Collections.reverse(singleRes);
  22.   }
  23.   res.add(singleRes);
  24.   index++;
  25. }
  26. return res;

剑指 Offer 33. 二叉搜索树的后序遍历序列

  1. if(postorder.length==0||postorder.length==1){
  2.   return true;
  3. }
  4. return check(postorder,0,postorder.length-1);
  5. }
  6. private boolean check(int[]postorder,int left,int right){
  7.   if(left>=right){
  8.     return true;
  9.   }
  10.   int leftEnd=left;
  11.   while (leftEnd<right&&postorder[leftEnd]<postorder[right]){
  12.     leftEnd++;
  13.   }
  14.   int temp=leftEnd;
  15.   while (temp<right){
  16.     if(postorder[temp]<postorder[right]){
  17.       return false;
  18.     }else{
  19.       temp++;
  20.     }
  21.   }
  22. return check(postorder, left, leftEnd-1)&&check(postorder, leftEnd, right-1);

剑指 Offer 35. 复杂链表的复制

  1. Map<Node,Node> map=new HashMap<>();
  2. Node temp=head;
  3. while (temp!=null){
  4.   map.put(temp,new Node(temp.val));
  5.   temp=temp.next;
  6. }
  7. temp=head;
  8. while (temp!=null){
  9.   map.get(temp).next=map.get(temp.next);
  10.   map.get(temp).random=map.get(temp.random);
  11.   temp=temp.next;
  12. }
  13. return map.get(head);

剑指 Offer 36. 二叉搜索树与双向链表

  1. Node pre;
  2. Node head;
  3. public Node treeToDoublyList(Node root) {
  4.   if(root==null){
  5.     return root;
  6.   }
  7.   build(root);
  8.   pre.right=head;
  9.   head.left=pre;
  10.   return head;
  11. }
  12. private void build(Node root){
  13.   if(root==null){
  14.     return;
  15.   }
  16.   build(root.left);
  17.   if(pre==null){
  18.     head=root;
  19.   }else{
  20.     root.left=pre;
  21.     pre.right=root;
  22.   }
  23.   pre=root;
  24.   build(root.right);
  25. }
  26. }

剑指 Offer 41. 数据流中的中位数

  1. class MedianFinder {
  2.     private PriorityQueue<Integer>queue1=new PriorityQueue<>();
  3.     private PriorityQueue<Integer>queue2=new PriorityQueue<>(new Comparator<Integer>() {
  4.         @Override
  5.         public int compare(Integer o1, Integer o2) {
  6.             return o2-o1;
  7.         }
  8.     });
  9.     /** initialize your data structure here. */
  10.     public MedianFinder() {
  11.     }
  12.     public void addNum(int num) {
  13.         //如果size相等，先加入小顶堆，再poll到大顶堆；
  14.         //如果size不相等，先加入到大顶堆，再poll到小顶堆；
  15.         if(queue1.size()==queue2.size()){
  16.             queue1.add(num);
  17.             queue2.add(queue1.poll());
  18.         }else{
  19.             queue2.add(num);
  20.             queue1.add(queue2.poll());
  21.         }
  22.     }
  23.     public double findMedian() {
  24.         if(queue1.size()==queue2.size()){
  25.             int num1=queue1.peek();
  26.             int num2=queue2.peek();
  27.             double res=(num1+num2)/2.0;
  28.             return res;
  29.         }else{
  30.             return queue2.peek()/1.0;
  31.         }
  32.     }
  33. }

剑指 Offer 44. 数字序列中某一位的数字

  1. //数字范围
  2. long start=1;
  3. //位数
  4. int base=1;
  5. //数字数量
  6. long weight=9;
  7. while (n>base*weight){
  8.   n-=base*weight;
  9.   base+=1;
  10.   weight*=10;
  11.   start*=10;
  12. }
  13. long res=start+(n-1)/base;
  14. int index=(n-1)%base;
  15. return Long.toString(res).charAt(index)-'0';

剑指 Offer 45. 把数组排成最小的数

  1. String[]dp=new String[nums.length];
  2. for(int i=0;i<nums.length;i++){
  3.   dp[i]=String.valueOf(nums[i]);
  4. }
  5. Arrays.sort(dp, new Comparator<String>() {
  6.   @Override
  7.   public int compare(String o1, String o2) {
  8.     Long long1=Long.valueOf(o1+o2);
  9.     Long long2=Long.valueOf(o2+o1);
  10.     if(long1<long2){
  11.       return -1;
  12.     }else{
  13.       return 1;
  14.     }
  15.   }
  16. });
  17. StringBuilder res = new StringBuilder();
  18. for(int i=0;i<dp.length;i++){
  19.   res.append(dp[i]);
  20. }
  21. return res.toString();

剑指 Offer 46. 把数字翻译成字符串

  1. char[] chars = String.valueOf(num).toCharArray();
  2. int[]dp=new int[chars.length+1];
  3. dp[0]=1;
  4. dp[1]=1;
  5. for(int i=2;i<dp.length;i++){
  6.   if(chars[i-2]=='1'||(chars[i-2]<='2'&&chars[i-1]<='5')){
  7.     dp[i]=dp[i-2]+dp[i-1];
  8.   }else{
  9.     dp[i]=dp[i-1];
  10.   }
  11. }
  12. return dp[dp.length-1];

剑指 Offer 49. 丑数

  1. if(n==1){
  2.   return 1;
  3. }
  4. int[]dp=new int[n];
  5. dp[0]=1;
  6. int index1=0;
  7. int index2=0;
  8. int index3=0;
  9. int value1=0;
  10. int value2=0;
  11. int value3=0;
  12. for(int i=1;i<n;i++){
  13.   value1=dp[index1]*2;
  14.   value2=dp[index2]*3;
  15.   value3=dp[index3]*5;
  16.   dp[i]=Math.min(value1,Math.min(value2,value3));
  17.   if(dp[i]==value1){
  18.     index1++;
  19.   }
  20.   if(dp[i]==value2){
  21.     index2++;
  22.   }
  23.   if(dp[i]==value3){
  24.     index3++;
  25.   }
  26. }
  27. return dp[dp.length-1];

剑指 Offer 53 - II. 0～n-1中缺失的数字

  1. int len=nums.length;
  2. int left=0;
  3. int right=len-1;
  4. while (left<=right){
  5.   int mid=(left+right)/2;
  6.   if(nums[mid]==mid){
  7.     left=mid+1;
  8.   }else{
  9.     right=mid-1;
  10.   }
  11. }
  12. return left;

剑指 Offer 56 - I. 数组中数字出现的次数

  1. int base=0;
  2. for(int i=0;i<nums.length;i++){
  3.   base^=nums[i];
  4. }
  5. int s=1;
  6. while ((base&s)==0){
  7.   s<<=1;
  8. }
  9. int[]res=new int[2];
  10. for(int i=0;i<nums.length;i++){
  11.   if((s&nums[i])==0){
  12.     res[0]^=nums[i];
  13.   }else{
  14.     res[1]^=nums[i];
  15.   }
  16. }
  17. return res;

剑指 Offer 57. 和为s的两个数字

  1. int[]res=new int[2];
  2. int left=0;
  3. int right=nums.length-1;
  4. while (left<right){
  5.   if(nums[left]+nums[right]<target){
  6.     left++;
  7.   }else if(nums[left]+nums[right]>target){
  8.     right--;
  9.   }else{
  10.     res[0]=nums[left];
  11.     res[1]=nums[right];
  12.     break;
  13.   }
  14. }
  15. return res;

剑指 Offer 57 - II. 和为s的连续正数序列

  1. int left=1;
  2. int right=1;
  3. int limit=target/2+1;
  4. while (right<=limit&&left<=limit){
  5.   sum+=right;
  6.   while (sum>=target){
  7.     if(sum==target){
  8.       int[]singleRes=new int[right-left+1];
  9.       int index=0;
  10.       for(int i=left;i<=right;i++){
  11.         singleRes[index++]=i;
  12.       }
  13.       res.add(singleRes);
  14.     }
  15.     sum-=left;
  16.     left++;
  17.   }
  18.   right++;
  19. }
  20. return res.toArray(new int[res.size()][]);

剑指 Offer 59 - II. 队列的最大值

  1. class MaxQueue {
  2.     private Deque<Integer> queue1=new LinkedList<>();
  3.     private Deque<Integer> queue2=new LinkedList<>();
  4.     public MaxQueue() {
  6.     }
  7.     public int max_value() {
  8.         if(queue2.isEmpty()){
  9.             return -1;
  10.         }
  11.         return queue2.peekFirst();
  12.     }
  13.     public void push_back(int value) {
  14.         queue1.addLast(value);
  15.         while (!queue2.isEmpty()&&value>queue2.peekLast()){
  16.             queue2.pollLast();
  17.         }
  18.         queue2.offerLast(value);
  19.     }
  20.     public int pop_front() {
  21.         if(queue1.isEmpty()){
  22.             return -1;
  23.         }
  24.         int value = queue1.pollFirst();
  25.         if(queue2.peekFirst().equals(value)){
  26.             queue2.pollFirst();
  27.         }
  28.         return value;
  29.     }
  30. }

剑指 Offer 60. n个骰子的点数

  1. double[]dp=new double[]{1/6d,1/6d,1/6d,1/6d,1/6d,1/6d};
  2. for(int i=2;i<=n;i++){
  3.   double[] temp=new double[5*i+1];
  4.   for(int j=0;j<dp.length;j++){
  5.     for(int k=0;k<6;k++){
  6.       temp[j+k]+=dp[j]/6.0;
  7.     }
  8.   }
  9.   dp=temp;
  10. }
  11. return dp;

剑指 Offer 61. 扑克牌中的顺子

  1. int max=0;
  2. int min=14;
  3. Set<Integer>set=new HashSet<>();
  4. for(int i=0;i<nums.length;i++){
  5.   if(nums[i]==0){
  6.     continue;
  7.   }
  8.   if(set.contains(nums[i])){
  9.     return false;
  10.   }
  11.   max=Math.max(max,nums[i]);
  12.   min=Math.min(min,nums[i]);
  13.   set.add(nums[i]);
  14. }
  15. return max-min<5;

剑指 Offer 62. 圆圈中最后剩下的数字（约瑟夫杀人）

  1. int index=0;
  2. //总的思路就是，每杀死一个人后，都把他后面的元素往左边移，然后溯源，找到存活的人最初的那个位置。
  3. //如果是n个数，就需要n-1次循环才能溯源到最先存活的位置
  4. int size=1;
  5. for(int i=0;i<n-1;i++){
  6.   size++;
  7.   index=(index+m)%size;
  8. }
  9. return index;

剑指 Offer 64. 求1+2+…+n

  1. boolean x=n>1&&(sumNums(n-1))>0;
  2. res+=n;
  3. return res;

剑指 Offer 65. 不用加减乘除做加法

  1. while (b!=0){
  2.   int c=a^b;
  3.   b=(a&b)<<1;
  4.   c=a;
  5. }
  6. return a;