剑指 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。
输入: 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

思路

代码实现 

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

思路

代码实现 

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的哪一数位
    }
}