leetcode660 remove 9

思路1：

二分+数位dp。

实现：

 1 class Solution 
 2 {
 3 public:
 4     int dfs(int now, bool ok, bool flag, int dp[][2], int num[])
 5     {
 6         if (now == 0) return ok;
 7         if (!flag && dp[now][ok] != -1)
 8             return dp[now][ok];
 9         int res = 0;
10         int u = flag ? num[now] : 9;
11         for (int i = 0; i <= u; i++)
12         {
13             res += dfs(now - 1, ok || (i == 9), flag && i == u, dp, num);
14         }
15         return flag ? res : dp[now][ok] = res;
16     }
17     int newInteger(int n) 
18     {
19         long long l = n, r = 5e9, res = n;
20         int dp[15][2], num[15]; 
21         while (l <= r)
22         {
23             long long m = (l + r) >> 1;
24             memset(dp, -1, sizeof dp);
25             memset(num, 0, sizeof num);
26             int sum = 0;
27             long long tmp = m;
28             while (tmp)
29             {
30                 num[++sum] = tmp % 10;
31                 tmp /= 10;
32             }
33             int ans = dfs(sum, 0, true, dp, num);
34             if (m - ans < n) l = m + 1;
35             else 
36             {
37                 r = m - 1;
38                 if (m - ans == n)
39                     res = m;
40             }
41         }
42         return res;
43     }
44 };

思路2：

去掉包含9的数之后实际上就是变成了9进制。

实现：

 1 class Solution 
 2 {
 3 public:
 4     int newInteger(int n) 
 5     {
 6         int sum = 0, x = 1;
 7         while (n)
 8         {
 9             sum += n % 9 * x;
10             n /= 9;
11             x *= 10;
12         }
13         return sum;
14     }
15 };