[数据结构与算法]剑指Offer31

剑指Offer第三十一天

数学（困难）

题1：剪绳子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。

剪绳子的题目，解法就是尽可能拿更多的3，直到4的时候，因为2x2 > 3x1，不能再拿3了

class Solution {
    final int DEL = 1000000007;
    public int cuttingRope(int n) {
        if(n<2)return 0;
        if(n==2)return 1;
        if(n==3) return 2;
        //尽可能要更多的3，但是2*2 > 3*1
        //定义返回res
        long res = 1;
        while(n > 4){
            res *= 3;
            res %= DEL;
            n -= 3;
        }
        return (int)(res * n % DEL);
    }
}

题2：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/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/

class Solution {
    public int countDigitOne(int n) {
        //找规律的题目，copy的。。
        //当前位数
        int digit = 1;
        //n中1的个数
        int res = 0;
        //高位的标志位
        int high = n/10;
        //当前digit位对应的值
        int cur = n % 10;
        //低位值，初始化为0
        int low = 0;
        while(high != 0 || cur != 0){
            //找的规律。。唉这种题我服了
            if(cur == 0){
                res += high * digit;
            }else if(cur == 1){
                res += high * digit + low + 1;
            }else {
                res += (high + 1) * digit;
            }
            //更新标志符
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

题3：数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

不用考虑越界问题

/* 数字范围    数量  位数    占多少位
    1-9        9      1       9
    10-99      90     2       180
    100-999    900    3       2700
    1000-9999  9000   4       36000  ...

    现在我要找2901位上是什么，所以从1000开始第12位
    例如 2901 = 9 + 180 + 2700 + 12 即一定是4位数,第12位   n = 12;
    数据为 = 1000 + (12 - 1)/ 4  = 1000 + 2 = 1002
    定位1002中的位置 = (n - 1) %  4 = 3    s.charAt(3) = 2;
*/
class Solution {
    public int findNthDigit(int n) {
        int digit = 1;   // n所在数字的位数
        long start = 1;  // 数字范围开始的第一个数
        long count = 9;  // 占多少位
        while(n > count){
            n -= count;
            digit++;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit;
        return Long.toString(num).charAt((n - 1) % digit) - '0';
    }
}