i2,i3,i5分别代表目前有几个2,3,5的因子，每次选一个最小的丑数，然后开始找下一个。当然i2，i3，i5也要跟着变。

/**
 * Created by 周杰伦 on 2018/2/25.
 * 题目描述
 在一个二维数组中，每一行都按照从左到右递增的顺序排序，
 每一列都按照从上到下递增的顺序排序。请完成一个函数，
 输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 1 2 3
 2 3 4
 3 4 5
 */
 
 解析：比较经典的一题，解法也比较巧妙，由于数组从左向右和从上到下的都是递增的，所以找一个数可以先从最右开始找。
 假设最右值为a，待查数为x，那么如果x < a说明x在a的左边，往左找即可，如果x > a，说明x 在 a的下面一行，到下面一行继续按照该规则查找，就可以遍历所有数。
 
算法的时间复杂度是O(M * N)
 
public class 二维数组中的查找 {
    public static boolean Find(int target, int[][] array) {

        if(array[0][0] > target) {
            return false;
        }

        int row = 0;
        int col = 0;
        while (row < array.length && col >0) {
            if (target == array[row][col]) {
                return true;
            }
            else if (target <array[row][col]) {
                col --;
            }
            else if (target > array[row][col]) {
                col ++;
            }
            else row++;
        }
        return false;
    }
}

//主体循环部分才5行。其实是有规律可循的。将每一层的四个边角搞清楚就可以打印出来了
        
    import java.util.ArrayList;
    public class Solution {
        public ArrayList<Integer> printMatrix(int [][] array) {
            ArrayList<Integer> result = new ArrayList<Integer> ();
            if(array.length==0) return result;
            int n = array.length,m = array[0].length;
            if(m==0) return result;
            int layers = (Math.min(n,m)-1)/2+1;//这个是层数
            for(int i=0;i<layers;i++){
                for(int k = i;k<m-i;k++) result.add(array[i][k]);//左至右
                for(int j=i+1;j<n-i;j++) result.add(array[j][m-i-1]);//右上至右下
                for(int k=m-i-2;(k>=i)&&(n-i-1!=i);k--) result.add(array[n-i-1][k]);//右至左
                for(int j=n-i-2;(j>i)&&(m-i-1!=i);j--) result.add(array[j][i]);//左下至左上
            }
            return result;       
        }
    }

快速排序的partition函数将一个数组分为左右两边，并且我们可以知道，如果flag值在k位置左边，那么往左找，如果在k位置右边，那么往左找。

这里科普一下经典快排中的一个方法partition，剑指offer书中直接跳过了这部分，让我摸不着头脑。

虽然快排用到了经典的分而治之的**，但是快排实现的前提还是在于 partition 函数。正是有了 partition 的存在，才使得可以将整个大问题进行划分，进而分别进行处理。

除了用来进行快速排序，partition 还可以用 O(N) 的平均时间复杂度从无序数组中寻找第K大的值。和快排一样，这里也用到了分而治之的**。首先用 partition 将数组分为两部分，得到分界点下标 pos，然后分三种情况：

pos == k-1，则找到第 K 大的值，arr[pos]；
pos > k-1，则第 K 大的值在左边部分的数组。
pos < k-1，则第 K 大的值在右边部分的数组。
下面给出基于迭代的实现（用来寻找第 K 小的数）：


int find_kth_number(vector<int> &arr, int k){
    int begin = 0, end = arr.size();
    assert(k>0 && k<=end);
    int target_num = 0;
    while (begin < end){
        int pos = partition(arr, begin, end);
        if(pos == k-1){
            target_num = arr[pos];
            break;
        }
        else if(pos > k-1){
            end = pos;
        }
        else{
            begin = pos + 1;
        }
    }
    return target_num;
}


该算法的时间复杂度是多少呢？考虑最坏情况下，每次 partition 将数组分为长度为 N-1 和 1 的两部分，然后在长的一边继续寻找第 K 大，此时时间复杂度为 O(N^2 )。不过如果在开始之前将数组进行随机打乱，那么可以尽量避免最坏情况的出现。而在最好情况下，每次将数组均分为长度相同的两半，运行时间 T(N) = N + T(N/2)，时间复杂度是 O(N)。

解析：用前k个数构造一个大小为k的大顶堆，然后遍历余下数字，如果比堆顶大，则跳过，如果比堆顶小，则替换掉堆顶元素，然后执行一次堆排序（即根节点向下调整)。此时的堆顶元素已被替换，

然后遍历完所有元素，堆中的元素就是最小的k个元素了。

如果要求最大的k个元素，则构造小顶堆就可以了。

构造堆的方法是，数组的第N/2号元素到0号元素依次向下调整，此时数组就构成了堆。

实际上我们可以使用现成的集合类，红黑树是一棵搜索树，他是排序的，所以可以得到最大和最小值，那么我们每次和最小值比较，符合条件就进行替换即可。复杂度是O（nlogn)


public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer>arrayList=new ArrayList<>();
        if(input==null || input.length==0 ||k==0 ||k>input.length)return arrayList;

        TreeSet<Integer> treeSet=new TreeSet<>();


        for(int i=0;i<input.length;i++){
            if(treeSet.size()<k){
                treeSet.add(input[i]);
            }

            else {

                if(input[i]<treeSet.last()){
                    treeSet.pollLast();
                    treeSet.add(input[i]);
                }
            }
        }

        for(Integer x:treeSet){
        arrayList.add(x);

        }
        return arrayList;

    }

 */

public class 连续数字序列的最大和 {
    public int FindGreatestSumOfSubArray(int[] array) {
       if(array==null || array.length==0)return 0;
        int sum=0;int max=array[0];

        for(int i=0;i<array.length;i++){
           //如果当前和<0，那就不加，直接赋新值
            if(sum<=0){
               sum=array[i];
           }//如果当前和大于零，则继续加。
           else {
               sum+=array[i];
           }
           if(max<sum){
            max=sum;
           }

        }
        return max;
    }

 Arrays.sort(arr);
        for (int i = 1 ;i < arr.length;i ++) {
            if (arr[i] == arr[i - 1]) {
                return false;
            }
            if (arr[i] - arr[i - 1] == 1) {
                continue;
            }else if (arr[i] - arr[i - 1]  - 1 <= cnt) {
                cnt -= arr[i] - arr[i - 1] - 1;
            }else {
                return false;
            }
        }
        return true;
    }

public boolean duplicate(int array[],int length,int [] duplication) {
    if ( array==null ) return false;

    // key step
    for( int i=0; i<length; i++ ){
        while( i!=array[i] ){
            if ( array[i] == array[array[i]] ) {
                duplication[0] = array[i];
                return true;
            }

            int temp = array[i];
            array[i] = array[array[i]];
            array[array[i]] = temp;
        }
    }

    return false;
}

public class Solution {

    static ArrayList<Integer> list = new ArrayList<>();
    public static void Insert(Integer num) {
        list.add(num);
        Collections.sort(list);
    }

    public static Double GetMedian() {
        if (list.size() % 2 == 0) {
            int l = list.get(list.size()/2);
            int r = list.get(list.size()/2 - 1);
            return (l + r)/2.0;
        }
        else {
            return list.get(list.size()/2)/1.0;
        }
    }


}

import java.util.*;
/**
用一个双端队列，队列第一个位置（队头）保存当前窗口的最大值，当窗口滑动一次
1.判断当前最大值是否过期（如果最大值所在的下标已经不在窗口范围内，则过期）
2.对于一个新加入的值，首先一定要先放入队列，即使他比队头元素小，因为队头元素可能过期。
3.新增加的值从队尾开始比较，把所有比他小的值丢掉(因为队列只存最大值，所以之前比他小的可以丢掉)

*/
public class Solution {
   public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<>();
        if(size == 0) return res;
        int begin; 
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for(int i = 0; i < num.length; i++){
            begin = i - size + 1;
            if(q.isEmpty())
                q.add(i);
            else if(begin > q.peekFirst())
                q.pollFirst();
         
            while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                q.pollLast();
            q.add(i);  
            if(begin >= 0)
                res.add(num[q.peekFirst()]);
        }
        return res;
    }
}

解析：这是一个全排列问题，也就是N个不同的数排成所有不同的序列，只不过把数换成了字符串。
全排列的过程就是，第一个元素与后续的某个元素交换，然后第二个元素也这么做，直到最后一个元素为之，过程是一个递归的过程，也是一个dfs的过程。

注意元素也要和自己做一次交换，要不然会漏掉自己作为头部的情况。

然后再进行一次字典序的排序即可。

public static ArrayList<String> Permutation(String str) {
        char []arr = str.toCharArray();
        List<char []> list = new ArrayList<>();
        all(arr, 0, arr.length - 1, list);
        Collections.sort(list, (o1, o2) -> String.valueOf(o1).compareTo(String.valueOf(o2)));
        ArrayList<String> res = new ArrayList<>();
        for (char[] c : list) {
            if (!res.contains(String.valueOf(c)))
            res.add(String.valueOf(c));
        }
        return res;
    }

    //注意要换完为之，因为每换一次可以去掉头部一个数字，这样可以避免重复
    public static void all(char []arr, int cur, int end, List<char[]> list) {
        if (cur == end) {
//            System.out.println(Arrays.toString(arr));
            list.add(Arrays.copyOf(arr, arr.length));
        }
        for (int i = cur;i <= end;i ++) {
            //这里的交换包括跟自己换，所以只有一轮换完才能确定一个结果
            swap(arr, cur, i);
            all(arr, cur + 1, end, list);
            swap(arr, cur, i);
        }
    }
    public static void swap(char []arr, int i, int j) {
        if (i > arr.length || j > arr.length || i >= j)return;
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

/**
 * Created by 周杰伦 on 2018/2/25.
 * 请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
 */
 
 解析：如果单纯地按顺序替换空格，每次替换完还要将数组扩容，再右移，这部操作的时间复杂度就是O（2*N）=O（N)，所以总的复杂度是O（n^2)，所以应该采取先扩容的办法，统计出空格数，然后扩容，接下来按顺序添加字符，遇到空格直接改成添加%20即可，这样避免了右移操作和多次扩容，复杂度是O（N)
 
 
public class 替换空格 {
    public static String replaceSpace(StringBuffer str) {
        int newlen = 0;
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == ' ') {
                newlen = newlen + 3;
            }
            else {
                newlen ++;
            }
        }
        char []newstr = new char[newlen];
        int j = 0;
        for(int i = 0 ; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                newstr[j++] = '%';
                newstr[j++] = '2';
                newstr[j++] = '0';
            }else {
                newstr[j++] = str.charAt(i);
            }
        }
        return String.valueOf(newstr);
    }

这个解法很经典，先把每个单词逆序，再把整个字符串逆序，结果就是把每个单词都进行了翻转。

字符串循环左移N位的处理方法也很经典，先把前N位逆序，再把剩余字符串逆序，最后整体逆序。

abcXYZdef -> cbafedZYX -> XYZdefabc

不得不说这种题型太恶心了，就是需要一直判断边界条件

参考一个答案。比较完整

    bool isNumeric(char* str) {
        // 标记符号、小数点、e是否出现过
        bool sign = false, decimal = false, hasE = false;
        for (int i = 0; i < strlen(str); i++) {
            if (str[i] == 'e' || str[i] == 'E') {
                if (i == strlen(str)-1) return false; // e后面一定要接数字
                if (hasE) return false;  // 不能同时存在两个e
                hasE = true;
            } else if (str[i] == '+' || str[i] == '-') {
                // 第二次出现+-符号，则必须紧接在e之后
                if (sign && str[i-1] != 'e' && str[i-1] != 'E') return false;
                // 第一次出现+-符号，且不是在字符串开头，则也必须紧接在e之后
                if (!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E') return false;
                sign = true;
            } else if (str[i] == '.') {
              // e后面不能接小数点，小数点不能出现两次
                if (hasE || decimal) return false;
                decimal = true;
            } else if (str[i] < '0' || str[i] > '9') // 不合法字符
                return false;
        }
        return true;
    }

StringBuilder sb = new StringBuilder();
    int []map = new int[256];
    public  void Insert(char ch)
    {
        sb.append(ch);
        if (map[ch] == 0) {
            map[ch] = 1;
        }else {
            map[ch] ++;
        }
        System.out.println(FirstAppearingOnce());
        
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for (int i = 0;i < sb.length();i ++) {
            if (map[sb.charAt(i)] == 1) {
                return sb.charAt(i);
            }
        }
        return '#';
    }

public static void printReverse(Node node) {
        if (node.next != null) {
            printReverse(node.next);
        }
        System.out.print(node.val + " ");
}

public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null)return head;
        ListNode pre,next;
        pre=null;
        next=null;
        while(head!=null){
            //保存下一个结点
            next=head.next;
            //连接下一个结点
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
}

    int cnt = 0;
    int sum = 0;
    for (int i = 0;i < n;i = (i + 1) % n) {
        if (arr[i] == -1) {
            continue;
        }
        cnt ++;
        if (cnt == m) {
            arr[i] = -1;
            cnt = 0;
            sum ++;
        }
        if (sum == n) {
            return i;
        }
    }
    return n - 1;
}

int LastRemaining_Solution(int n, int m) {
        if (m == 0 || n == 0) {
            return -1;
        }
        ArrayList<Integer> data = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            data.add(i);
        }
        int index = -1;
        while (data.size() > 1) {
//          System.out.println(data);
            index = (index + m) % data.size();
//          System.out.println(data.get(index));
            data.remove(index);
            index--;
        }
        return data.get(0);
    }

public TreeNode Convert(TreeNode root) {
        if(root==null)
            return null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        TreeNode pre = null;// 用于保存中序遍历序列的上一节点
        boolean isFirst = true;
        while(p!=null||!stack.isEmpty()){
            while(p!=null){
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            if(isFirst){
                root = p;// 将中序遍历序列中的第一个节点记为root
                pre = root;
                isFirst = false;
            }else{
                pre.right = p;
                p.left = pre;
                pre = p;
            }      
            p = p.right;
        }
        return root;
    }
}

     * 题目描述
 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 */
 
 解析：首先，头结点一定是先序遍历的首位，并且该节点把中序分为左右子树，根据这个规则，左子树由左边数组来完成，右子树由右边数组来完成，根节点由中间节点来构建，于是便有了如下的递归代码。该题的难点就在于边界的判断。
 
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
    if(pre.length == 0||in.length == 0){
        return null;
    }
    TreeNode node = new TreeNode(pre[0]);
    for(int i = 0; i < in.length; i++){
        if(pre[0] == in[i]){
            node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));//为什么不是i和i-1呢，因为要避免出错，中序找的元素需要再用一次。
            node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
        }
    }
    return node;
}

/**
 * Created by 周杰伦 on 2018/3/27.
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 */

    解析：本题还是有点难度的，子结构要求节点完全相同，所以先判断节点是否相同，然后使用先序遍历进行递判断，判断的依据是如果子树为空，则说明节点都找到了，如果原树节点为空，说明找不到对应节点,接着递归地判断该节点的左右子树是否符合要求.

    public class 树的子结构 {

        public boolean HasSubtree(TreeNode root1, TreeNode root2) {
            boolean res = false;
            if (root1 != null && root2 != null) {
                if (root1.val == root2.val) {
                    res = aHasb(root1, root2);
                }
                if (res == false) {
                    res = HasSubtree(root1.left,root2);
                }
                if (res == false) {
                    res = HasSubtree(root1.right,root2);
                }
                return res;
            }
            else return false;
        }
        public boolean aHasb(TreeNode t1, TreeNode t2){
            if (t2 == null) return true;
            if (t1 == null) return false;
            if (t1.val != t2.val) return false;
    
            return aHasb(t1.left,t2.left) && aHasb(t1.right,t2.right);
        }
    }

/**
 * Created by 周杰伦 on 2017/3/19.操作给定的二叉树，将其变换为源二叉树的镜像。
 输入描述:
 二叉树的镜像定义：源二叉树
  8
 /  \
 6   10
 / \  / \
 5  7 9 11
 镜像二叉树
   8
 /  \
 10   6
 / \  / \
 11 9 7  5
 */


解析：其实镜像二叉树就是交换所有节点的左右子树，所以使用遍历并且进行交换即可。

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

 public TreeNode(int val) {
 this.val = val;

 }

 }
 */
public class 镜像二叉树 {
    public void Mirror(TreeNode root) {
        if(root == null)return;
        if(root.left!=null || root.right!=null)
        {
            TreeNode temp=root.left;
            root.left=root.right;
            root.right=temp;
        }
        Mirror(root.left);
        Mirror(root.right);

    }

public class 二叉搜索树的后序遍历序列 {
    public static void main(String[] args) {
        int []a = {7,4,6,5};
        System.out.println(VerifySquenceOfBST(a));
    }
    public static boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return isBST(sequence, 0, sequence.length - 1);
    }
    public static boolean isBST(int []arr, int start, int end) {
        if (start >= end) return true;
        int root = arr[end];
        int mid = start;
        for (mid  = start;mid < end && arr[mid] < root;mid ++) {

        }
        for (int i = mid;i < end; i ++) {
            if (arr[i] < root)return false;
        }
        return isBST(arr, start, mid - 1) && isBST(arr, mid, end - 1);
    }
}

解析：给出一个比较好懂的解法，中序遍历的结果存在集合中，找到根节点，进行中序遍历，然后找到该节点，下一个节点就是集合后一位

public TreeLinkNode GetNext(TreeLinkNode TreeLinkNode)
    {
        return findNextNode(TreeLinkNode);
    }
    public TreeLinkNode findNextNode(TreeLinkNode anynode) {
        if (anynode == null) return null;
        TreeLinkNode p = anynode;
        while (p.next != null) {
            p = p.next;
        }
        ArrayList<TreeLinkNode> list = inOrderSeq(p);
        for (int i = 0;i < list.size();i ++) {
            if (list.get(i) == anynode) {
                if (i + 1 < list.size()) {
                    return list.get(i + 1);
                }
                else return null;
            }
        }
        return null;

    }
    static ArrayList<TreeLinkNode> list = new ArrayList<>();
    public static ArrayList<TreeLinkNode> inOrderSeq(TreeLinkNode TreeLinkNode) {
        if (TreeLinkNode == null) return null;
        inOrderSeq(TreeLinkNode.left);
        list.add(TreeLinkNode);
        inOrderSeq(TreeLinkNode.right);
        return list;
    }

boolean isSymmetrical(TreeNode pRoot)
    {
        TreeNode temp = copyTree(pRoot);
        Mirror(pRoot);
        return isSameTree(temp, pRoot);
    }


    void Mirror(TreeNode root) {
        if(root == null)return;
        Mirror(root.left);
        Mirror(root.right);
        if(root.left!=null || root.right!=null)
        {
            TreeNode temp=root.left;
            root.left=root.right;
            root.right=temp;
        }


    }
    boolean isSameTree(TreeNode t1,TreeNode t2){
        if(t1==null && t2==null)return true;
        else if(t1!=null && t2!=null && t1.val==t2.val) {
            boolean left = isSameTree(t1.left, t2.left);
            boolean right = isSameTree(t1.right, t2.right);
            return left && right;
        }
        else return false;
    }

    TreeNode copyTree (TreeNode root) {
        if (root == null) return null;
        TreeNode t = new TreeNode(root.val);
        t.left = copyTree(root.left);
        t.right = copyTree(root.right);
        return t;
    }

ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode root = pRoot;
        if(root == null) {
            return new ArrayList<>();
        }
        TreeNode last = root;
        TreeNode nlast = root;
        queue.offer(root);
        ArrayList<Integer> list = new ArrayList<>();
        list.add(root.val);
        ArrayList<Integer> one = new ArrayList<>();
        one.addAll(list);
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        lists.add(one);
        list.clear();

        int row = 1;
        while (!queue.isEmpty()){

            TreeNode t = queue.poll();

            if(t.left != null) {
                queue.offer(t.left);
                list.add(t.left.val);
                nlast = t.left;
            }
            if(t.right != null) {
                queue.offer(t.right);
                list.add(t.right.val);
                nlast = t.right;
            }
            if(t == last) {
                if(!queue.isEmpty()) {
                    last = nlast;
                    row ++;
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.addAll(list);
                    list.clear();
                    if (row % 2 == 0) {
                        Collections.reverse(temp);
                    }
                    lists.add(temp);

                }
            }
        }

        return lists;
    }

String Serialize(TreeNode root) {
       if(root == null) {
        sb.append("#!") ;
    }
    else {
        sb.append(root.val + "!");
        Serialize(root.left);
        Serialize(root.right);
    }

    return sb.toString();

解析：二叉搜索树的中序遍历是有序的，只需要在中序中判断数字是否在第k个位置即可。
如果在左子树中发现了，那么递归返回该节点，如果在右子树出现，也递归返回该节点。注意必须要返回，否则结果会被递归抛弃掉。

TreeNode KthNode(TreeNode pRoot, int k)
    {
        count = 0;
        return inOrderSeq(pRoot, k);
    }
    static int count = 0;
    public TreeNode inOrderSeq(TreeNode treeNode, int k) {
        if (treeNode == null) return null;
        TreeNode left = inOrderSeq(treeNode.left, k);
        if (left != null) return left;
        if (++ count == k) return treeNode;
        TreeNode right = inOrderSeq(treeNode.right, k);
        if (right != null) return right;
        return null;
    }

    题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解析：本题是比较抽象的，首先，根据入栈出栈的规则，我们可以建立一个栈A，用于保存压栈序列，然后压入第一个元素，比较出栈序列的第一个元素，如果不相等，继续压栈，直到二者相等，此时栈A元素出栈，然后重复上一步的操作。

如果在每次压栈过程中，入栈序列已经全部入栈A但是还是找不到出栈序列的第一个元素时，则说明不是出栈序列。

当栈A的元素全部压入并出栈后，如果出栈序列也出栈完毕，则满足题意。

public static boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        int i = 0;
        while (i < pushA.length) {
            stack.push(pushA[i]);
            i++;
            while (!stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
            if (i == pushA.length) {
                if (!stack.empty()) {
                    return false;
                } else return true;
            }
        }
        return false;
    }

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解析：这题的思路很巧妙，如果直接遍历复杂度为O（N），但是使用二分查找可以加快速度，因为两边的数组都是递增的最小值一定在两边数组的边缘，于是通过二分查找，逐渐缩短左右指针的距离，知道左指针和右指针只差一步，那么右指针所在的数就是最小值了。
复杂度是O（logN)

//这段代码忽略了三者相等的情况
public int minNumberInRotateArray(int [] array) {
        if (array.length == 0) return 0;
        if (array.length == 1) return array[0];
        int min = 0;

        int left = 0, right = array.length - 1;
        //只有左边值大于右边值时，最小值才可能出现在中间
        while (array[left] > array[right]) {
            int mid = (left + right)/2;
            if (right - left == 1) {
                min = array[right];
                break;
            }
            //如果左半部分递增，则最小值在右侧
            if (array[left] < array[mid]) {
                left = mid;
            }
            //如果右半部分递增，则最小值在左侧。
            //由于左边值比右边值大，所以两种情况不会同时发生
            else if (array[right] > array[mid]) {
                right = mid ;
            }
        }
        return array[min];

    }
    

    注意：但是当arr[left] = arr[right] = arr[min]时。三个数都相等无法确定最小值，此时只能遍历。

    int temp = num2;
    while(num2!=0) {
        temp = num1 ^num2;
        num2 = (num1 & num2)<<1;
        num1 = temp;
    }
    return num1;
}

public class 矩阵中的路径 {
    public static void main(String[] args) {
        char[][]arr = {{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}};
        char []str = {'b','c','c','e','d'};
        System.out.println(hasPath(arr, arr.length, arr[0].length, str));
    }
    static int flag = 0;
    public static boolean hasPath(char[][] matrix, int rows, int cols, char[] str)
    {
        int [][]visit = new int[rows][cols];
        StringBuilder sb = new StringBuilder();
        for (int i = 0;i < rows;i ++) {
            for (int j = 0;j < cols;j ++) {
                if (matrix[i][j] == str[0]) {
                    visit[i][j] = 1;
                    sb.append(str[0]);
                    dfs(matrix, i, j, visit, str, 1, sb);
                    visit[i][j] = 0;
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
        return flag == 1;
    }
    public static void dfs(char [][]matrix, int row, int col, int [][]visit, char []str, int cur, StringBuilder sb) {
        if (sb.length() == str.length) {
//            System.out.println(sb.toString());
            flag = 1;
            return;
        }

        int [][]pos = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int i = 0;i < pos.length;i ++) {
            int x = row + pos[i][0];
            int y = col + pos[i][1];
            if (x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0) {
                continue;
            }
            if (visit[x][y] == 0 && matrix[x][y] == str[cur]) {
                sb.append(matrix[x][y]);
                visit[x][y] = 1;
                dfs(matrix, x, y, visit, str, cur + 1, sb);
                sb.deleteCharAt(sb.length() - 1);
                visit[x][y] = 0;
            }
        }
    }

public class Solution {
    static int count = 0;
    public static int movingCount(int threshold, int rows, int cols)
    {
        count = 0;
        int [][]visit = new int[rows][cols];
        dfs(0, 0, visit, threshold);
        return count;
    }

    public static void dfs(int row, int col, int[][]visit, int k) {
        if (row >= visit.length || row < 0 || col >= visit[0].length || col < 0) {
            return;
        }
        if (sum(row) + sum(col) > k) {
            return;
        }

        if (visit[row][col] == 1){
            return;
        }

        visit[row][col] = 1;
        count ++;
        dfs(row + 1,col,visit, k);
        dfs(row - 1,col,visit, k);
        dfs(row,col + 1,visit, k);
        dfs(row,col - 1,visit, k);

    }

    public static int sum(int num) {
        String s = String.valueOf(num);
        int sum = 0;
        for (int i = 0;i < s.length();i ++) {
            sum += Integer.valueOf(s.substring(i, i + 1));
        }
        return sum;
    }
}