剑指offer刷题(中等等级)

()(1)二维数组中的查找

(2)重建二叉树

利用Arrays.copyOfRange(n,from,to)进行数组截取，实现起来更简便。

public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int pren = pre.length;
        int vinn = vin.length;
        if(pren==0 || vinn==0)
            return null;
        int node = pre[0];
        TreeNode root = new TreeNode(node);
        for(int i = 0;i<vin.length;i++)
            if(vin[i]==node){
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pren),Arrays.copyOfRange(vin,i+1,vinn));
                break;
            }
        return root;
    }

(3)二叉树的下一个结点 

(4)矩阵中的路径

更简便的代码：
1、将矩阵路径经过时改为‘.’，使用完再回复为原值。来代替flag矩阵记1

2、关于i，j是否超届的判断均放到最开始的if中用，超届则直接false；

3、易错点，到index最后一位匹配上就直接给true

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(deepPath(matrix,i,j,word,0))
                    return true;
            }
        }
        return false;
        
    }
    public boolean deepPath(char[][] m,int i,int j,String word,int index){
        //不需要进行m[i][j]=='.'置false的判断，因为只有和word中值匹配上才会通过，其已包含在m[i][j]!=word.charAt(index)判断中
        if(i<0||i>=m.length||j<0||j>=m[0].length||m[i][j]!=word.charAt(index))
            return false;
        if(index==word.length()-1)
            return true;
        char t = m[i][j];
        m[i][j] = '.';
        boolean res = deepPath(m,i-1,j,word,index+1)||
            deepPath(m,i+1,j,word,index+1)||
            deepPath(m,i,j-1,word,index+1)||
            deepPath(m,i,j+1,word,index+1);
        m[i][j]=t;
        return res;
    }

(5)剪绳子 

动态规划的思想是一定要从最小子问题开始求解，之后更大的问题可以应用其子问题的结果。

若该子问题出现多次，只需计算一次。

1、本题n=2和n=3与裁成了2和3的值不同。

因为n=2和n=3必须进行裁剪故对应1，2。但裁的段中有2和3时不需要继续裁最大为2，3.

其他的可以依次便利或得（不必排除裁成长度为1的段，因为肯定不如其他的值大）

public int cutRope (int n) {
        // write code here
        if(n==2)
            return 1;
        if(n==3)
            return 2;
        int[] max = new int[n+1];
        max[1] = 1;
        max[2] = 2;
        max[3] = 3;
        for(int i = 4;i<=n;i++){
            for(int j=1;j<i;j++){
               max[i] = Math.max(max[i],max[j]*max[i-j]);
            }
        }
        return max[n]; 
    }

(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<TreeNode> 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)栈的压入、弹出序列

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

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

 public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length==0)
            return true;
        int pushIndex = 0,top=-1,popIndex=0;
        while(popIndex<popA.length){
            if(top>=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)二叉树中和为某一值的路径(二)

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

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

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<TreeNode> 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;
    }

（13） 字符串的排列

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

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

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

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

（14）最小的K个数

本题可利用三种方法实现：堆排序，有控制的快排，冒泡

对于堆排序思想：要用大顶推，因为堆顶的值是方便获取的，每次要看是不是前4小，就要看是不是比目前进堆的最大值还小，故要用大顶堆。

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

（15） 数据流中的中位数

提议目的理解清楚

ArrayList的add可以在对应位置添加（即插入元素）

 private ArrayList<Integer> res = new ArrayList();
    public void Insert(Integer num) {
        int index = 0;
        if(res.isEmpty())
            res.add(num);
        else{
            while(index<res.size()){
                if(num<=res.get(index)){
                    //如果在这里添加，当要出入的是末尾时则无法插入，因为不会进入if
                    //res.add(i,num);
                    break;
                }
                index++;
            }
            res.add(index,num);
        } 
    }

    public Double GetMedian() {
        if(res.size()%2==0){
            int index1 = res.size()/2;
            int index2 = index1-1;
            return (res.get(index1)*1.0+res.get(index2))/2;
        }
        else{
           return (double)res.get(res.size()/2) ;
        }
    }

（16） 整数中1出现的次数（从1到n整数中1出现的次数）

计算每一位上1出现的次数做计算

分成两部分 ，假设此数位12345，计算百位上数字base=100

1、百位前为12则有12个100~199故有12*100个一。(n/(base*10))*base

2、百位后包括百位为345(n%(base*10))，即计算包含100~199之间多少个数。

  故n%(base*10)<base   0个

     base<=  n%(base*10)  <base*2  有n%(base*10)-base+1 eg：123有23+1个100~123

     n%(base*10) >= base*2  即包含了100~199 有base个

 public int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        int index = 1, flag = 10;
        while(n/index!=0){
            sum+=n/flag*index;
            if(n%flag>=index&&n%flag<index*2)
                sum+= n%flag - index +1;
            else if(n%flag>=index*2)
                sum+=index;
            index*=10;
            flag*=10;
        }
        return sum;
    }

（17） 把数组排成最小的数

时间复杂度：O(nlog2n)，可利用自带的快排

思想：进行数组的排序；这里排序的规则，即最小的无论谁放在其前面，都没有其放在前面小。

每一位都如此控制，则最终组合最小。

 public String PrintMinNumber(int [] numbers) {
        if(numbers.length==0)
            return "";
        ArrayList<String> res = new ArrayList();
        String result = "";
        for(int i = 0;i < numbers.length;i++){
            res.add(Integer.toString(numbers[i]));
        }
        res.sort(new Comparator<String>(){
            public int compare(String s1,String s2){
                return (s1+s2).compareTo(s2+s1);
            }
        });
        for(String str:res){
            result+=str;
        }
        return result;
    }

（18）把数字翻译成字符串

思想见代码：

public int solve (String nums) {
        if(nums==null||nums.length()==0||nums.charAt(0)=='0')
            return 0;
        //先排除特殊情况即若中间出现了30、60，不为10，20则直接不可编译。因为0必须要和前一个数结合
        for(int i = 1;i<nums.length();i++){
            if(nums.charAt(i)=='0'&&nums.charAt(i-1)!='1'&&nums.charAt(i-1)!='2')
                return 0;
        }
        //此处预留0，方便计算第二个字符位置有集中可能
        int[] kinds = new int[nums.length()+1];
        Arrays.fill(kinds,1);
        for(int i =2;i<kinds.length;i++){
            //因为kinds 下标1对应的是nums下标0，故i-2，i-1
            //若与前一位组合后范围在11~19，21~26
            if((nums.charAt(i-2)=='1'&&nums.charAt(i-1)!='0')||(nums.charAt(i-2)=='2'&&nums.charAt(i-1)!='0'&&nums.charAt(i-1)<'7'))
                kinds[i] = kinds[i-1]+kinds[i-2];
            else//无法组合或组合为10，20是等于前一位结果
                kinds[i] = kinds[i-1];
        }
        return kinds[kinds.length-1];
    }

(19) 礼物的最大价值

 本次主要是时间复杂度。为了使时间复杂度更小，用sum去记录右上到此格的最大值。若此出已有值则不向下递归。

1、递归实现

 public int maxValue (int[][] grid) {
        int[][] sum = new int[grid.length][grid[0].length];
        sumcount(grid,grid.length-1,grid[0].length-1,sum);
        return sum[sum.length-1][sum[0].length-1];
    }
    public int sumcount(int[][] g ,int i, int j,int[][] sum){
       if(i==0&&j==0){
           sum[0][0] = g[0][0];
           return sum[0][0];
       }
       if(sum[i][j]==0){
           //以下i==0 和 j==0的判断为保证不越界访问。
           if(i==0)
            sum[i][j] = sumcount(g,i,j-1,sum)+g[i][j];
           else if(j==0)
            sum[i][j] = sumcount(g,i-1,j,sum)+g[i][j];
           //不存在i==0或j==0则不会越界，可向下递归计算
           else
           sum[i][j] = g[i][j]+Math.max(sumcount(g,i-1,j,sum),sumcount(g,i,j-1,sum));
       }
       return sum[i][j];   
    }

2、非递归方法：因为每个位置要都是获取其上，左的做大值。使固定的。可从晓的开始依次累加计算。

 public int maxValue (int[][] grid) {
         if(grid==null||(grid.length==0&&grid[0].length==0))
             return 0;
         
         for(int i = 0;i<grid.length;i++){
             for(int j = 0;j<grid[0].length;j++){
                 if(i==0&&j==0)
                    continue;
                 if(i==0)
                     grid[i][j] += grid[i][j-1];
                 else if(j==0)
                     grid[i][j] += grid[i-1][j];
                 else
                     grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
             }
         }
         return grid[grid.length-1][grid[0].length-1];
    }

(20) 最长不含重复字符的子字符串

思想：利用Hashmap 实现字典

如果map中已有此字符，且在f,l之间（因为此时l为当前位置故只用判断是否大于等于f）则重复。f 变为与当前重复的位置+1

右边界一直移动，长度变大就更新

public int lengthOfLongestSubstring (String s) {
        // write code here
        if(s==null)
            return 0;
        Map<Character,Integer> map = new HashMap();
        int max = Integer.MIN_VALUE;
        int f = 0,l = -1;
        for(int i = 0;i<s.length();i++){
            if(map.get(s.charAt(i))!=null&&map.get(s.charAt(i))>=f){      
                f = map.get(s.charAt(i))+1;
            }
            l++;
            if(l-f+1>max)
                max=l-f+1;
            map.put(s.charAt(i),i);
        }
        return max;
    }

（21） 丑数

1、非递归思路，用最小堆，每次弹出最小的数。（即为当前低i个抽数）再将min*2、min*3，min*5入队（前提此数在堆中不存在，用一个HashMap辅助判断）

中间加入的值可能出现long类型超过int

public int GetUglyNumber_Solution(int index) {
        if(index==0)
            return 0;
        Queue<Long> queue = new PriorityQueue();
        Map<Long,Integer> map = new HashMap();
        long num=0;
        int sum=0;
        queue.add(1L);
        map.put(1L,1);
        while(sum<index){
            num = queue.poll();
            sum++;
            if(!map.containsKey(num*2)){
                queue.add(num*2);
                map.put(num*2,1);
            }
            if(!map.containsKey(num*3)){
                queue.add(num*3);
                map.put(num*3,1);
            }
            if(!map.containsKey(num*5)){
                queue.add(num*5);
                map.put(num*5,1);
            }
        }
        return (int)num;
    }

2、递归方式

(22)数组中的逆序对

import java.util.*;
public class Solution {
    public int InversePairs(int [] array) {
      if(array.length<=0)
          return 0;
      return merge(array,0,array.length-1);
    }
    public int merge(int[] arr,int l, int r ){
        if(l>=r)
            return 0;
        int m = (r+l)/2;
        int sum = merge(arr,l,m)+merge(arr,m+1,r);
        int[] t = new int[r-l+1];
        int lindex = l,rindex=m+1;
        for(int k = 0;k<t.length;k++){
        //右侧归完，则一定不会再出现逆序对
            if(rindex>r){
                t[k]=arr[lindex++];    
            }
            //还能入for循环说明，左右一定有一侧未归完.即rindex>m则lindex一定不大于l
            //arr[lindex]<arr[rindex]可能此时rindex已大于r故要作为第二个判断
            else if(lindex>m||arr[lindex]<arr[rindex])
                t[k] = arr[rindex++];
            else{
                sum=(sum+(r-rindex+1))%1000000007;
                t[k] = arr[lindex++];
            }
        }
        int k = 0;
        for(int i = l;i<=r;i++)
            arr[i] = t[k++];
        return sum;
        
    }
}

(23)二叉搜索树的第k个节点

这里其实运用的是中序遍历的思想，故用栈实现中序遍历是关键

/*
    当前
        指向节点不为null（即还有内容待入栈）
        栈不为空（即还有节点未出栈）
        进入循环
            每次循环入栈到当前节点的最左（指针变空则最左完成）
            出栈顶为当前遍历元素
            因出栈元素左边一定已经入栈（入的时候入到了最左），故再指向其右边
            （若右边是空的，进入下一个循环就不会执行入栈，直接出下一个）
    
    */
    public int KthNode (TreeNode proot, int k) {
        if(proot==null||k<=0)
            return -1;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = proot;
        while(node!=null||!stack.isEmpty()){
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            k--;
            node = stack.pop();
            if(k==0)
                return node.val;
            node = node.right;
           
        }
        return -1;
    }

(24)数组中只出现一次的两个数字

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 的方法思路

异或运算满且相同的数字作异或会被抵消掉，相同为0 不同为1.a^x^y^z^c^x^y^z^c^b=a^b

（1）想分别得到a，b则需要把输入内容分成两组。已知a与b不同，一定至少有一位异或结果为1。故可利用此位是否为0来区分。（可从a^b的低位开始寻找，找到第一个为1的位）

（2）此为是否为0可以把输入内容划分为两组.a^x^y^x^y=a;b^z^c^z^c=b

则分别对这两组内容异或可得a和b。

public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        int ab = 0;
        for(int i = 0;i<array.length;i++){
            ab^=array[i];
        }
        int k = 1;
        while((ab & k) == 0)
            k = k << 1;
        int[] num = new int[2];
        for(int i = 0;i<array.length;i++){
            if((array[i] & k) == 0)
                num[0]^=array[i];
            else
                num[1]^=array[i];
        }
        if(num[0]>num[1]){
            int t = num[0];
            num[0] =num[1];
            num[1]=t;
        }
        return num;
        
    }

 （25）和为S的两个数字

时间复杂度更小的方法

方法一：

        思路：sum - a 即为当前数对应的另一个数。若在此数组中则可输出此对。

                   要想快速定位在不在可用HashMap存储，这样计算包不包含比较快。

        注意：可能出现[1445]8,[1456]8。故不可以见简单的先把数存入哈希，再从头遍历

                  不然 [1456]8中，4包含但是是自己，若通过下标判断是否为自己，则 [1445]8 中存入key4，前将后覆盖。

故应该边存边，比较。当前的与之前的比较。 

        若与其匹配的数之前存在则输入数对；若不存在则存入hash表。则可排除上边两种意外。

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res = new ArrayList();
        if(array.length<=1)
            return res;
        Map<Integer,Integer> map = new HashMap();
        for(int i = 0;i<array.length;i++){
            if(map.containsKey(sum-array[i])){
                res.add(array[i]);
                res.add(sum-array[i]);
                return res;
            }
            else{
                map.put(array[i],i);
            }
        }
        return res;
    }

  方法二：充分利用数组的有序。可以一个指针指向最小值即开始，一个指针指向最大值即结束。

当两数和大于sum，说明需要指向更小的，故右指针移动。

当两数和小于sum，说明需要指向更大的，故左指针移动。

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res = new ArrayList();
        if(array.length<=1)
            return res;
        int l = 0, r = array.length-1;
        while(l<r){
            if(array[l]+array[r]>sum)
                r--;
            else if(array[l]+array[r]<sum)
                l++;
            else{
                res.add(array[l]);
                res.add(array[r]);
                return res;
            }
        }
        return res;
    }

(26)左旋转字符串

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