[数据结构与算法]剑指offer 14Ⅰ.57Ⅱ.62. 数学(中等)

14Ⅰ.

题目:

剑指 Offer 14- I. 剪绳子https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

想法1:动态规划,每次选择剪掉j长度,然后剩下可以选择剪或者不剪,再求max

代码1:

class Solution {
    public int cuttingRope(int n) {
        // 下标2->n存储每个数的最大乘积
        int[] dp = new int[n+1];
        // n>1并且m>1 
        // dp[1]=1; 
        // 不初始化则dp[1]=0, 当i-j==1时,j*dp[i-j],j*(i-j)中总有j*(i-j)=j更大,所以无需初始化
        dp[2]=1;
        for(int i=3;i<=n;i++){
            // 依次选择不同长度的j剪
            for(int j=1;j<i-1;j++){
                // 转移方程如下:
                // 1.剪掉长度为j的绳子之后,继续剪或者不剪,都可以.
                // 2.当j不同时，求出最大的dp[i]
                dp[i]=Math.max( dp[i],Math.max(j*dp[i-j],j*(i-j)) );
            }
        }
        return dp[n];
    }
}

想法2:数学 长度为2或3时不剪更好,长度为4时剪成2.2比1.3好,长度为5及以上时剪比不剑剪好.

代码2:

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        //if(b == 2)
        return (int)Math.pow(3, a) * b;
    }
}

结果:

?

57Ⅱ.

题目:

剑指 Offer 57 - II. 和为s的连续正数序列https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

?想法1:因为要求连续的正数序列,想到滑窗,从第一个和第二个开始,用sum表示窗内数字的和.具体见代码.

代码1:

class Solution {
    public int[][] findContinuousSequence(int target) {
        //定义s为滑窗和
        int left=1,right=2,sum=3;
        List<int[]> res = new ArrayList<>();
        while(left<right){
            if(sum==target){
                //找到一组连续数字和为target
                int[] tmp = new int[right-left+1];
                for(int i=left;i<=right;i++){
                    tmp[i-left]=i;
                }
                res.add(tmp);
                // sum-=left;
                // left++;
            }
            if(sum<target){
                //连续数字和<target,应将right右移,继续往后找
                right++;
                //right右移后,sum加上新right的值
                sum+=right;
            }else{ //if(sum>=target)
                //left右移前,sum减去旧left的值
                sum-=left;
                //连续数字和<target,应将left右移,继续往后找
                left++;
            }
        }
        //这里也可以写new int[0][]
        return res.toArray(new int[res.size()][]);
    }
}

结果1:

想法2:每次从头遍历i,滑动右边界j.计算窗内数字和.

代码2:

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        for(int i=1;i<=target;i++){
            int sum=0;
            int cnt=0;
            for(int j=i;j<=target;j++){
                sum+=j;
                cnt++;
                if(sum==target && cnt!=1){
                    int[] tmp= new int[j-i+1];
                    for(int k=i;k<=j;k++){
                        tmp[k-i]=k;
                    }
                    res.add(tmp);
                    break;
                }
                if(sum>target)
                    break;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

结果2:

62.

题目:

?剑指 Offer 62. 圆圈中最后剩下的数字https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

?

?想法参考:讲的好清晰!力扣https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/

写出动规代码 使用dp[] 或者不使用也可以

//只用公式 不使用dp[]
class Solution {
    public int lastRemaining(int n, int m) {
        // 最后的幸存者在数组中的下标一定是0
        int pos = 0;
        for (int i = 2; i <= n; i++) {
            pos = (pos + m) % i;
        }
        return pos;
    }
}

//动规 使用dp[]
class Solution {
    public int lastRemaining(int n, int m) {
        int[] dp = new int[n+1];
        dp[1]=0;
        for(int i=2;i<=n;i++){
            dp[i]=(dp[i-1]+m)%i;
        }
        return dp[n];
    }
}

结果:

?