「剑指Offer」Day31：数学（困难）
剑指 Offer 14- II. 剪绳子 II
题目描述
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36🔗题目链接：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof
思路
这道题与剑指 Offer 14- I. 剪绳子大体相同，不同在于本题目涉及 “大数越界情况下的求余问题”，采用之前的动态规划没办法很好地进行求余，可能导致越界，这里采用另一种解法。
代码实现
有价值的因子只有2和3，因为4 =
2+2=2*2分不分都一样了，而5以后的数都需要进一步做分解才更优。而且同样的n，分出3比分出2更优（比如3*3大于2*2*2），所以尽可能分出更多的3就是解法，当分出若干3后，n≤4时，此时n若为2，为3，为4，直接乘就都是最优解了。
class Solution {
public int cuttingRope(int n) {
if(n == 2)
return 1;
if(n == 3)
return 2;
long res = 1;
while(n > 4){
res *= 3;
res = res % 1000000007;
n -= 3;
}
return (int)(res * n % 1000000007);
}
}
剑指 Offer 43. 1～n 整数中 1 出现的次数
题目描述
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
🔗题目链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
🔗题目链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
思路
代码实现
class Solution {
public int countDigitOne(int n) {
int high = n; //高位
int low = 0; //低位
int cur = 0; //当前位
int sum = 0;
int base = 1;
while (high > 0) {
cur = high % 10;
high /= 10;
if (cur == 0){
sum += high * base;
}else if (cur == 1){
sum += high * base + low + 1;
}else{
sum += (high + 1) * base;
}
low = cur * base + low;
if (high > 0){
base *= 10;
}
}
return sum;
}
}
剑指 Offer 44. 数字序列中某一位的数字
题目描述
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。
输入：n = 11 输出：0🔗题目链接：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof
思路
🔗参考题解：（LeetCode K神）https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6/
代码实现
class Solution {
public int findNthDigit(int n) {
int digit = 1;
long start = 1;
long count = 9;
while (n > count) { //确定n所在数字的数位
n -= count;
digit += 1;
start *= 10;
count = digit * start * 9;
}
long num = start + (n - 1) / digit; //确定n所在的数字
return Long.toString(num).charAt((n - 1) % digit) - '0'; //确定n在num的哪一数位
}
}
查看11道真题和解析
