leetcode数学思想

剑指offer 43 1~n整数中1出现的次数: 数学的思想,不太理解 

面试题43. 1~n 整数中 1 出现的次数(清晰图解) - 1~n 整数中 1 出现的次数 - 力扣(LeetCode)

剑指offer 44 数字序列中某一位的数字(迭代 + 求整 / 求余,清晰图解) 数学的思想,找规律,也不太懂

面试题44. 数字序列中某一位的数字(迭代 + 求整 / 求余,清晰图解) - 数字序列中某一位的数字 - 力扣(LeetCode)

剑指offer14- I. 剪绳子(数学推导 / 贪心思想),也有数学的思想,还可以用动态规划来做

//方法一
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;
        return (int)Math.pow(3, a) * 2;
    }
}
//方法二
class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[]dp=new int[n+1];
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<=i-j;j++){
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已,
                //并且,在本题中,我们分析 dp[0], dp[1]都是无意义的,
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ,再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }
}


版权声明:本文为weixin_40728070原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。