剑指offer难题

链表

链表中环的入口结点

快慢指针，等快慢指针相遇后，将慢指针重置于链表头结点，再将快慢指针都以相同步长（1）向后走，相遇得到的节点为所求节点
空指针：当快指针先走到空指针时，判定无环，退出循环

复杂链表的复制

哈希表，遍历一遍该链表，创建所有碰到的节点，用哈希表存储next关系
遍历两遍（简单方法）

二叉树

二叉树的下一个结点

给定一个节点，求其在中序遍历中的下一个节点（已知二叉树存在父节点指针）
如果给定节点有右子树，则在右子树中找到最左边的节点作为返回结果
如果没有右子树，则返回其父节点
如果是根节点，且没有右子树，返回空

序列化二叉树
空节点也需要被序列化

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        if(root == null) return "" ;
        StringBuilder builder = new StringBuilder();
        dfs(root,builder);
        return builder.toString();   
    }
    
    void dfs(TreeNode root, StringBuilder builder){
        if(root==null){
            builder.append("#,");
            return;
        }
        builder.append(root.val).append(",");
        dfs(root.left, builder);
        dfs(root.right, builder);
    }
    
    TreeNode Deserialize(String str) {
        if(str.length() == 0) return  null;
        String[] split = str.split(",");
        Queue<String> queue = new LinkedList<>();
        for(String s : split){
            queue.offer(s);
        }
        return dfs(queue);
    }
    
    TreeNode dfs(Queue<String> que){
        if(que.isEmpty()){
            return null;
        }
        String head = que.poll();
        if("#".equals(head)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(head));
        root.left = dfs(que);
        root.right = dfs(que);
        return root;
    }
    
}

二叉搜索树

二叉树树的后序遍历序列
给定一个序列，判断其是否为二叉搜索树的后序遍历序列。对子树进行递归判断。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence ==null || sequence.length == 0) return false;
        return rec(sequence, 0, sequence.length-1);
    }
    
    private boolean rec(int[] seq, int start, int root){
        if(start >= root )return true;
        int left_start;
        for(left_start=start; left_start<root; left_start++){
            if(seq[left_start] > seq[root]){
                break;
            }
        }
        //判断另一子树（右子树）是否满足“值都小于root”的条件
        for(int i=left_start; i<root; i++){
            if(seq[i] < seq[root]){
                return false;
            }
        }
        return rec(seq, start, left_start-1) && rec(seq, left_start, root-1);
    }
}

二叉搜索树与双向链表
维护pre节点和头结点root，中序遍历二叉树

public class Solution {
    TreeNode pre = null;
    TreeNode root = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        Convert(pRootOfTree.left);
        if(root==null){
            root = pRootOfTree;
        }
        if(pre!=null){
            pRootOfTree.left = pre;
            pre.right = pRootOfTree;
        }
        pre = pRootOfTree;
        Convert(pRootOfTree.right);
        return root;
    }
}

二叉搜索树的第k个结点
维护一个计数值k，采用先右后左的中序遍历顺序，每遍历一个节点则将k减1，k为0时则为所求节点

public class Solution {
    private int k = 0;
    private TreeNode res = null;    
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot == null || k ==0) return null;
        this.k = k;
        inOrder(pRoot);
        return res;
    }
    
    void inOrder(TreeNode r){
        if(r == null) return ;
        inOrder(r.left);
        if(--k == 0){
            res = r;
        } 
        inOrder(r.right);
    }
}

数组

旋转数组的最小数字
需要实现的是“最小数字”的查找。
实现O(n)时间内的查找很容易，但需要采用二分查找实现O(logn)时间内的查找。

public class Solution {
    public int minNumberInRotateArray(int[] array) {
        int i = 0, j = array.length - 1;
        while (i < j) {
            if (array[i] < array[j]) {
                return array[i];
            }
            int mid = (i + j) >> 1;
            if (array[mid] > array[i]) {
                i = mid + 1;
            } else if (array[mid] < array[j]) {
                j = mid; // 如果是mid-1，则可能会错过最小值，因为找的就是最小值
            } else i++;  // 巧妙避免了offer书上说的坑点（1 0 1 1 1）
        }
        return array[i];
    }
}

数组中出现次数超过一半的数字
使用count变量记录result出现的次数。遍历数组，当遇到与之前的result相同的数字，则将count加1,；否则减1。count为0时更改result，否则更新count。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int result= 0, count = 0;
        for(int i=0; i< array.length; i++){
            if(count == 0){
                result= array[i];
                count ++;
            }
            else if(count > 0){
                if(array[i]!=result){
                    count -- ;
                }else{
                    count++;
                }
            }
        }
        //验证是否出现了大于n/2次
        count = 0;
        for(int i=0; i< array.length; i++){
            if(array[i] == result){
                count ++;
            }
        }
        return count>(array.length/2)?result:0;
    }
}

数组中的逆序对
采用归并排序的思路来处理。
逆序对的总数 = 左边数组中的逆序对的数量 + 右边数组中逆序对的数量 + 左右结合成新的顺序数组时中出现的逆序对的数量
？
数字在排序数组中出现的次数

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0) return 0;
        int r = rightMost(array, k); 
        int l = leftMost(array, k);
        if (r !=-1 && l != -1 ) return r-l+1;
        return 0;
    }
    
    private int rightMost (int [] array, int k){
        int len = array.length;
        int left = 0, right = len-1;
        while(left<right){
            int mid = left + (right - left+1)/2;
            if(array[mid] > k){
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        if(left >= 0 && left < len && array[left] == k){
            return left;    
        }
        return -1;
    }
    
     private int leftMost (int [] array, int k){
        int len = array.length;
        int left = 0, right = len-1;
        while(left<right){
            int mid = left + (right - left)/2;
            if(array[mid] < k){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(left >= 0 && left < len&& array[left] == k){
            return left;    
        }
        return -1;
    }
}

字符串

字符串的排列
回溯加哈希表。若是要字典序，则先把字符数组进行排序。
把字符串转换成整数
自动机或者标记法遍历

53.表示数值的字符串
自动机或者标记法遍历

正则表达式匹配
动态规划，递归
？

栈

栈的压入、弹出序列

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int len = popA.length;
        for(int i=0, j=0; i<len; i++ ){
            stack.push(pushA[i]);
            while(!stack.isEmpty() && stack.peek()==popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

递归

变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
规律： f(n)=2^(n-1)

回溯

矩阵中的路径

import java.util.*;
public class Solution {
    public boolean hasPath (char[][] matrix, String word) {
        //循环多次找到首个字母的初始位置
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]==word.charAt(0)){
                    //找到初始位置，设置访问标记数组，可能不是一个，所有每次都创建新数组
                    boolean vis[][]=new boolean[matrix.length][matrix[0].length];
                    //dfs传入初始位置，访问数组，矩阵，寻找的字符位置，字符串
                    if(dfs(i,j,vis,matrix,0,word)==true)return true;
                }
            }
        }
        return false;
    }
    boolean dfs(int m,int n,boolean[][] vis,char[][] matrix,int k,String word){
        //如果m，n位置在矩阵外返回false，如果这一节点走过返回false
        if(m<0||n<0||m>=matrix.length||n>=matrix[0].length||vis[m][n]==true)return false;
        //如果这个位置字母和字符串尾字母一样，且字符串序号就是最后一个，代表遍历完了，返回true，不在遍历
        if(word.charAt(word.length()-1)==matrix[m][n]&&(k==word.length()-1))return true;
        //字符串字母是序号对应字母
        if(word.charAt(k)==matrix[m][n]){
            //访问过了
            vis[m][n]=true;
            //如果上下左右有下一个字母（k+1）则继续遍历，否则访问设置为未访问（每个字母这能经过一次，没有找到下一个字母，所以其实没有访问过）
            if(dfs(m+1,n,vis,matrix,k+1,word)||dfs(m,n+1,vis,matrix,k+1,word)||dfs(m,n-1,vis,matrix,k+1,word)||dfs(m-1,n,vis,matrix,k+1,word)){
                return true;
            }else{
                vis[m][n]=false;
                return false;
            }
        }else{  
            //当前不是对应字母，返回false
            vis[m][n]=false;
            return false;
        }
    }
}

排序算法及应用

最小的K个数
快速排序或者堆排序

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(input==null || input.length==0 || k == 0 || k>input.length){
            return res;
        }
        int left = 0;
        int right = input.length-1;
        int j = quicksort(input, left, right);
        while(j+1 !=k){
            if(j+1<k){
                left = j+1;
            }else{
                right = j;
            }
            j = quicksort(input, left, right);
        }
        for(int i=0; i<=j; i++){
            res.add(input[i]);
        }
        return res;
    }
    
    public int quicksort(int [] input, int low, int high){
        int pivot = input[low];
        int i = low, j = high;
        while(i<j){
            while(i<j&&input[j]>pivot){--j;}
            while(i<j&&input[i]<pivot){++i;}
            
            if(i>=j) break;
            
            int tmp = input[i];
            input[i] = input[j];
            input[j] = tmp;
            ++i;
            --j;
        }
        return i;
    }
}

数据流中的中位数
两个堆：大根堆保存较小的一半数，小根堆保存较大的一半数

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
    //小顶堆，用该堆记录位于中位数后面的部分
    private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

    //大顶堆，用该堆记录位于中位数前面的部分
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    //记录偶数个还是奇数个
    int count = 0;
    //每次插入小顶堆的是当前大顶堆中最大的数
    //每次插入大顶堆的是当前小顶堆中最小的数
    //这样保证小顶堆中的数永远大于等于大顶堆中的数
    //中位数就可以方便地从两者的根结点中获取了
    //优先队列中的常用方法有：增加元素，删除栈顶，获得栈顶元素，和队列中的几个函数应该是一样的
    //offer peek poll,
    public void Insert(Integer num) {
        //个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入小顶堆中。因为我们在取数的时候假定的时候当奇数的时候从小顶堆中取数据，偶数的时候从两个顶部取数据。所以当当前个数为偶数是，其实预期要将数字放在小顶堆，所以先放在大顶堆，然后再放到小顶堆。当前个数为奇数的时候是同样的道理。
        if(count % 2 == 0){
            maxHeap.offer(num);
            int max = maxHeap.poll();
            minHeap.offer(max);
        }else{
            //个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入大顶堆中
            minHeap.offer(num);
            int min = minHeap.poll();
            maxHeap.offer(min);
        }
        count++;
    }
    public Double GetMedian() {
        //当前为偶数个，则取小顶堆和大顶堆的堆顶元素求平均
        if(count % 2 == 0){
            return new Double(minHeap.peek() + maxHeap.peek())/2;
        }else{
            //当前为奇数个，则直接从小顶堆中取元素即可，所以我们要保证小顶堆中的元素的个数。
            return new Double(minHeap.peek());
        }
    }
}

双指针法

和为S的连续正数序列
设定两个指针，一个指向第一个数，一个指向最后一个数，在此之前需要设定第一个数和最后一个数的值，由于是正数序列，所以可以把第一个数设为1，最后一个数为2（因为是要求是连续正数序列，最后不可能和第一个数重合）。下一步就是不断改变第一个数和最后一个数的值，如果从第一个数到最后一个数的和刚好是要求的和，那么把所有的数都添加到一个序列中；如果大于要求的和，则说明从第一个数到最后一个数之间的范围太大，因此减小范围，需要把第一个数的值加1，同时把当前和减去原来的第一个数的值；如果小于要求的和，说明范围太小，因此把最后一个数加1，同时把当前的和加上改变之后的最后一个数的值。这样，不断修改第一个数和最后一个数的值，就能确定所有连续正数序列的和等于S的序列了。
滑动窗口的最大值

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (num == null || num.length ==0 || size ==0 ||size > num.length) return res;
        int len = num.length;
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0, j = 1 - size; i < len; i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(j > 0 && deque.peekFirst() == num[j - 1]){
                deque.removeFirst();
            }
            
          // 保持 deque 递减(把小于当前数的队列元素出队)
            while(!deque.isEmpty() && deque.peekLast() < num[i]){
                deque.removeLast();
            }

            deque.addLast(num[i]);

            // 记录窗口最大值
            if(j >= 0){
                res.add(deque.peekFirst());
            }
        }
        return res;
    }
}

其他

扑克牌顺子

import java.util.Arrays;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        if(numbers == null || numbers.length == 0) return false;
        Arrays.sort(numbers);
        int len = numbers.length;
        int i =0;
        for(int j = 0; j< len; j++){
            if(numbers[j] == 0){
                ++i;
                continue;
            }
            if(j+1<len && numbers[j] == numbers[j+1]) return false;
        }
        return (numbers[len-1] - numbers[i]) <5;
    }
}

约瑟夫环
递推公式: f(i)表示i个人玩报m退出的最终胜利者

f(1) = 0;
f(i) = (f(i-1) + m) % i;
迭代解法：

int LastRemaining_Solution(int n, int m)
{
  if(n < 1 || m < 1){
    return -1;
  }
  int last = 0;
  for(int i = 2; i <= n; i++){
      last = (last + m) % i;
  }
  return last;
}

求1+2+...+n

public class Solution {
    public int Sum_Solution(int n) {
        int res = n;
        boolean a = (res==0) || ((res += Sum_Solution(n-1)) == 0);
        return res;
    }
}

不用加减乘除的加法
三步走的方式计算二进制值相加： 101，111

第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
第三步：重复上述两步，各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。

public class Solution {
    public int Add(int num1,int num2) {
        int a = num1 ^ num2;
        int b = (num1 & num2)<<1;
        while(b!=0){
            int tmp = a ^ b;
            b = (a & b) << 1;
            a = tmp;
        }
        return a;
    }
}