剑指 Offer 14- I. 剪绳子

数学

根据求导等数学公式可以得出，最好的情况是每一段相等其次是3的元素尽可能多。
image.png

  1. class Solution {
  2. public:
  3.     int cuttingRope(int n) {
  4.         if(n <= 3) return n-1;
  5.         int a = n / 3, b = n % 3;
  6.         if(b == 0) return pow(3, a);
  7.         if(b == 1) return pow(3, a-1)*4;
  8.         return pow(3, a)*2;
  9.     }
  10. };

动态规划的写法

  • 根据子集求更大集，找到子集与父集之间的规律。

  • 这里的dp[1], dp[2], dp[3]代表的是基本单元的意思，并不是长度为3的情况下最大值。

    1. class Solution {
    2. public:
    3.   int cuttingRope(int n) {
    4.       if( n <= 3)
    5.        return n-1;
    6.        vector<int> dp(n + 1);
    7.        dp[1] = 1, dp[2] = 2, dp[3] = 3;
    8.        for(int len = 4; len <= n; len++){
    9.            for(int k = 1; k < len; k++){
    10.                dp[len] = max(dp[len], dp[k] * dp[len - k]);
    11.            }
    12.        }
    13.        return dp[n];
    14.   }
    15. };

    剑指 Offer 14- II. 剪绳子 II

    本题与之前的剪绳子1大致相同，唯一不同就是要考虑大数越界情况下的求余问题。

  • 这一题不能够再使用dp求解，因为数值过大，需要取模。但是dp算法需要枚举多个值选最大的，而取模之后的大小不能反映真实的大小，以至于的不到正确的答案。

  • djp的时间复杂度为n方，本题的数据范围是1000以内不会超时，如果数据范围再次扩大肯定会超时
  1. public class Solution {
  2.     public int CuttingRope(int n) {
  3.         //处理特殊情况
  4.         if(n==2) return 1;
  5.         if(n==3) return 2;
  6.         if(n==4) return 4;
  7.         long ans = 1;
  8.         int mod = 1000000007;
  9.         //当大于4的时候，先分出一段长度为3的，直到长度小于等于4，则不再分
  10.         while(n>4)
  11.         {
  12.             ans=ans*3%mod;
  13.             n-=3;
  14.         }
  15.         return (int)(ans*n%mod);
  16.     }
  17. }

计算过程中爆int

这里出现了一个问题，有下面这样一个等式

  1. int mypow(long base, int consult, long mod) {
  2.         int ret = 1; // 返回值定义成 long 类型，防止溢出
  3.         for (int i = 0; i < consult; i++) {
  4.             ret = (ret * base) % 1000000007;
  5.         }
  6.         return ret;
  7.     }

其中看起来好像不会溢出，但是实际上确溢出了。我的猜测是计算过程中，就是不到取模那一步就会溢出，因为进行乘法运算时，运算结果会中间转存到一个int类型的空间。此时超出范围则溢出。

  1. long long mypow(long base, int consult, long mod) {
  2.         long long ret = 1; // 返回值定义成 long 类型，防止溢出
  3.         for (int i = 0; i < consult; i++) {
  4.             ret = (ret * base) % 1000000007;
  5.         }
  6.         return ret;
  7.     }

剑指 Offer 43. 1～n 整数中 1 出现的次数

  • 这里 注意0LL代表longlong类型的0，主要是为了匹配max函数；
  • 先计算出每个位置上有多少1，然后把剩下来的部分单独计算。
  • 比如每个百分位，对于数字来说都会出现 n/1000 * 100个1，然后计算剩下的部分

  • 剩下的部分<100则百分位出现1的次数是0， 如果在100到200之间就是 n%1000 - 100+1,如果大于200则固定为100；

    1. class Solution {
    2. public:
    3.   int countDigitOne(int n) {
    4.       // mulk 表示 10^k
    5.       // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
    6.       // 但为了让代码看起来更加直观，这里保留了 k
    7.       long long mulk = 1;
    8.       int ans = 0;
    9.       for (int k = 0; n >= mulk; ++k) {
    10.           ans += (n / (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0LL), mulk);
    11.           mulk *= 10;
    12.       }
    13.       return ans;
    14.   }
    15. };

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

    ```shell class Solution { public: int findNthDigit(int n) {

    1.   int section_cnt = 9;            //当前数长下，有多少个这样长的数
    2.   int num_len = 1;                //每个数的长度
    3.   while ((long)section_cnt * num_len < n)
    4.   {
    5.       n -= section_cnt * num_len;
    6.       section_cnt *= 10;
    7.       num_len ++;
    8.   }
    10.   section_cnt /= 9;               //比如是1000
    11.   int target_num = section_cnt + (n - 1) / num_len;   //比如1004
    12.   int idx = (n - 1) % num_len;    //比如1004
    13.   return to_string(target_num)[idx] - '0';

    } };

```