《剑指offer》每日三题

这里使用的是题库：
https://leetcode.cn/problem-list/xb9nqhhg/?page=1

剑指 Offer 07. 重建二叉树

递归思想：

代码

class Solution {
   
    int pPre=0;//用于遍历preorder数组
    public TreeNode build(int[] preorder, int[] inorder,int start,int end){
   
        //建立完成返回
        if(pPre==preorder.length){
   
            return null;
        }
        //代表该子树为空
        if(end<start){
   
            return null;
        }
        //获取在pPre指向位置的中序遍历内的下标
        int index=-1;
        for(int i=start;i<=end;i++){
   
            if(preorder[pPre]==inorder[i]){
   
                index=i;
                break;
            }
        }
        TreeNode root=new TreeNode(preorder[pPre]);
        pPre++;
        if(end-start==0){
   //如果子树只有一个结点，直接返回
            return root;
        }
        root.left=build(preorder,inorder,start,index-1);
        root.right=build(preorder,inorder,index+1,end);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
   
       return build(preorder,inorder,0,preorder.length-1);
    }
}

 

  
 

剑指 Offer 14- I. 剪绳子

代码实现：

class Solution {
   
    public int cuttingRope(int n) {
   
        //判断特殊情况
        if(n==2)return 1;
        if(n==3)return 2;
        int[] dp=new int[n+1];
        //放置初始值
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        //递归求解
        return lengthest(dp,n);
    }

    private int lengthest(int[] dp,int n){
   
        //如果dp数组中该位置有计算好的值直接返回
        if(dp[n]!=0){
   
            return dp[n];
        }
        //计算最大值--默认不切割
        int max=n;
        //开始切割
        for(int i=2;i<=n/2;i++){
   
            if(lengthest(dp,i)*lengthest(dp,n-i)>max){
   
                max=lengthest(dp,i)*lengthest(dp,n-i);
            }
        }9
        dp[n]=max;
        return max;
    }
}

 

  
 

剑指 Offer 14- II. 剪绳子 II

与上一题的区别是n的范围更大了，有溢出的可能。再利用前面的动态规划就不好处理了，这里得采用一些数学的推理。我是推不出来，看了一下其他大佬的解析，得到了以下三点：
切分规则：
最优： 3 。把绳子尽可能切为多个长度为 33 的片段，留下的最后一段绳子的长度可能为 0,1,20,1,2 三种情况
次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1
最差： 1 。若最后一段绳子长度为 1；则应把一份 3 + 1替换为 2 + 2
切分规则有了，这里最大的问题就变成了如何取模
只要在每一次累乘时判断一下，超过了就取模1000000007，值得注意的是这里使用的类型是long，因为int类型最大值为21亿多，乘3很容易就溢出了。

代码实现：
return的（）都要加，因为强制类型转换执行优先级更高，例如这样就会出错：
return (int)max*2%1000000007;

class Solution {
   
    public int cuttingRope(int n) {
   
        if(n==2)return 1;
        if(n==3)return 2;
        long max=1;
        while(n>4){
   
            n-=3;
            max=(max*3)%1000000007;
        }
        if(n==4){
   
            return (int)(max*4%1000000007);
        }else if(n==3){
   
            return (int)(max*3%1000000007);
        }else{
   //n==2 不会存在n=1的情况
            return (int)(max*2%1000000007);
        }
    }
}

 

  
 

共勉