Day24 剪绳子 II + 1～n 整数中 1 出现的次数 +

TODO：

1. 都不大会做重新做一遍吧
2. 手动写堆排序

剑指 Offer 14- II. 剪绳子 II(中等)

两个要点: ①快速幂 ②找到最优解的模式

class Solution {
public:
    int cuttingRope(int n) {
        if(n == 2) return 1;
        else if(n==3) return 2;
        if(n==4) return  4;
        int t1 = n/3;
        int t2 = n%3;
        int b = t1 -1;
        long res = 1;
        long k =3;
        while(b){
            if(b%2 == 1){
                res = (res*k)%1000000007;
            }
            b = b/2;
            k = k %1000000007;
            k = (k*k)%1000000007;
        }
        if(t2 == 0) return (res*3)%1000000007;
        else if(t2 == 1) return (res*4)%1000000007;
        else return (res*3*2)%1000000007;     
    }
};

class Solution {
public:
    int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        long result = 1;
        while(n > 4){
            n -=3;
            result*=3;
            result%=1000000007;
        }
        return (int)(n*result%1000000007);
     
    }
};

剑指 Offer 43. 1～n 整数中 1 出现的次数(困难)

想了一会发现是1出现的次数，也就是11表示1有出现2次...直接看题解好了。很有趣的一道题！！！
这个代码很简洁

class Solution {
public:
    int countDigitOne(int n) {
        if(n == 0) return 0;
        int high = n/10;
        int cur = n%10;
        int low = 0;
        long digit = 1;
        int res = 0;
        while(high || cur){
            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 = high/10;
            digit = digit*10;
        }
        return res;
    }
};

剑指 Offer 44. 数字序列中某一位的数字(中等)

不会做看的题解。

class Solution {
public:
    int findNthDigit(int n) {
        int digit =1;
        long start =1, count = 9;
        while( n > count){
            n -= count;
            start*=10;
            digit+=1;
            count = 9*start*digit;
        }
        int num = start + (n-1)/digit;
        string snume = to_string(num);
        return snume[(n-1)%digit]-'0';
    }
};