剑指offer刷题(中等等级)

(6) 数值的整数次方

注意指数为负数时

（7）调整数组顺序使奇数位于偶数前面(一)

注意此题是调整后保持奇偶数内部的相对位置

(8)链表中环的入口结点

这里忽视的问题是，slow走一步，fast走两步是slow=pHead.next,fast=pHead.next.next;

错误1:slow=pHead,fast=pHead.next.next;这相当于slow一步没走

错误2:在一起走c步时，从pHead开始

（9）树的子结构

重点看一下递归部分。易忽略，如果一开始root1==null则肯定是false

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null||root2==null)
            return false;
        Stack stack1 = new Stack();
        stack1.push(root1);
        while(!stack1.isEmpty()){
            TreeNode node = stack1.pop();
            if(isSame(node,root2)){
                return true;
            }
            if(node.left!=null)
                stack1.push(node.left);
            if(node.right!=null)
                stack1.push(node.right);
        }
        return false; 
    }
    public boolean isSame(TreeNode node,TreeNode root2){
        if(node==null&&root2!=null)
            return false;
        if(root2==null)
            return true; 
        if(node.val!=root2.val)
            return false;    
        return isSame(node.left,root2.left)&&isSame(node.right,root2.right);
    }

(10)栈的压入、d出序列

空间复杂度小的方式：与用栈辅助思想一致，但时利用数组已经入栈的部分当作栈。

top指向栈顶，pushIndex指向下一个要 *** 作的数

 public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length==0)
            return true;
        int pushIndex = 0,top=-1,popIndex=0;
        while(popIndex=0&&popA[popIndex]==pushA[top]){
                top--;
                popIndex++;
            }
            else{
                if(pushIndex>=pushA.length)
                    return false;
                else{
                    pushA[++top]=pushA[pushIndex];
                    pushIndex++;
                }
            }
        }
        return true;
    }

(11)二叉搜索树的后序遍历序列

对于使用stack实现的得递归方法，不理解

(12)二叉树中和为某一值的路径(二)

此题递归与利用队列时间控件复杂度一致，且非递归实现起来麻烦，故仅练习了递归。

(13)二叉搜索树与双向链表

1、采用中序遍历的思想，这样便利结束才是有序的

2、利用head记录第一个节点，用pre记录遍历序列的前一个节点。注意当需要对pre进行更新时，pre为null，此时遍历序列的第一个节点记为head；

3、不要陷入要记录后一个节点的误区，无法做到。变通即pre.right指向现在的，现在的left指向pre。

递归方法实现：

 private TreeNode head = null;
    private TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)
            return null;
        convert(pRootOfTree);
        return head;
    }
    public void convert(TreeNode root){
        if(root==null)
            return ;
        convert(root.left);
        if(pre == null){
            head = root;
        }
        else{
           pre.right = root;
           root.left = pre;
        }
        pre = root;
        convert(root.right);
    }

非递归方法：也可以看作用栈实现中序遍历

1、当指针不为空，或栈不为空都要继续进行 *** 作

2、利用while将当前指向的节点左子节点进栈，直到再无左子树

      此指针为空，或进栈到再无左子树。进行出栈（此时对出栈节点 *** 作与递归的一致）

3、将指针指向当前出栈节点的右孩子，

        因为此时此节点的左孩子一定已经进行过 *** 作，下一个要 *** 作的是右孩子

即每次都遍历到此节点最左， *** 作完成，指向当前节点右孩子，循环往复。 

public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)
            return null;
        TreeNode head = null;
        TreeNode pre = null;
        Stack stack = new Stack();
        while(pRootOfTree!=null||!stack.isEmpty()){
           while(pRootOfTree!=null){
               stack.push(pRootOfTree);
               pRootOfTree = pRootOfTree.left;
           }
            TreeNode node = stack.pop();
            if(pre==null)
                head = node;
            else{
                pre.right = node;
                node.left = pre;
            }
            pre = node;
            pRootOfTree = node.right;
        }
        return head;
    }

（14） 字符串的排列

一种更为简便的方法，利用字符串的子串获取与拼接。

递归传到现在的新串，剩余的字母，ArrayList

这里注意，ArrayList在函数中传递是地址的拷贝，不是仅仅参数的拷贝

 public ArrayList Permutation(String str) {
        ArrayList result = new ArrayList();
        if(str==null||str.length()==0)
            return null;
        newString(str,"",result);
        return result;
    }
    public void newString(String str,String newstr,ArrayList result){
        if(str.length()==0){
            if(!result.contains(newstr.toString()))
                result.add(newstr.toString());
            return ;
        }
        for(int i = 0;i

  /*
    这里采用优先队列的思想（大顶堆）
    维护一个大顶堆，每次加入元素后如果多余k个就删除最大的
    所有加入一遍后就剩下了k个最小的。
    PriorityQueue的用法
    大顶堆 new PriorityQueue((o1,o2)->(o2-o1));
    小顶堆 new PriorityQueue< >();
    自定义 Queue priorityQueue = new PriorityQueue<>(new Comparator() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2.compareTo(o1);
                }
            });
    */
    public ArrayList GetLeastNumbers_Solution(int [] input, int k){
        ArrayList res = new ArrayList();
        if(input.length==0||k==0)
            return res;
        Queue queue = new PriorityQueue((o1,o2)->(o2-o1));
        for(int i=0;i

 private ArrayList res = new ArrayList();
    public void Insert(Integer num) {
        int index = 0;
        if(res.isEmpty())
            res.add(num);
        else{
            while(index