golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-21 23:22:40

func newInteger(n int) int {
	if n == 0 {
		return 0
	}
	return newInteger(n/9)*10 + n%9
}

cpp 解法, 执行用时: 0 ms, 内存消耗: 6.5 MB, 提交时间: 2023-10-21 23:22:01

class Solution {
public:
    int newInteger(int n) {
        long cnt = 1;
        int exp = 1;
        int dp[15]={0};
        //用于判断这个数是几位数字
        while(pow(10,exp)-1-cnt<n){
            dp[exp] = cnt;//exp位数的情况下9的个数
            cnt = cnt*9+pow(10,exp);
            exp++;
        }
        int ans = 0;
        for(int i = exp;i>0;i--){//总共有exp位数
            //还需要计算后续的数字，高位固定后，低位全填零还比目标数小（即不大于目标数的个数不足）
            if(n>0){
                //最高位单独判断，不能为0，其余的可以
                int j = exp==i?1:0;//遍历该位置上的数
                for( ;j<=9;j++){//
                    //总的数减去9的个数
                    int num = j*pow(10,i-1)-j*dp[i-1];
                    //找到刚好满足的数字
                    if(num<n)
                        continue;
                    //比这个数小的数字个数刚好满足目标n，后面就不用计算了，直接填0
                    if(num==n){
                        ans = ans*10+j;
                        n = 0;
                    //否则，还得计算后面应该为什么数
                    }else{
                        ans = ans*10+(j-1);
                        n-=(j-1)*pow(10,i-1)-(j-1)*dp[i-1];
                    }
                    
                    break;
                }
            //n为0,直接填零，即没有比这个数（高位固定）小的数
            }else{
                ans*=10;
            }
        }
        return ans;
    }
};

cpp 解法, 执行用时: 28 ms, 内存消耗: 11.1 MB, 提交时间: 2023-10-21 23:21:49

#define LL long long

class Solution {
public:
    vector<int> i2v(int i) {
        vector<int> res;
        while (i) {
            res.push_back(i%10);
            i /= 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
    
    LL lessOrEqual(unordered_map<LL, LL>& memo, LL n, bool zero) {
        if (memo.find(n*2+zero) != memo.end()) return memo[n*2+zero];
        if (n < 10) {
            LL res = (n == 9 ? 8 : n);
            if (!zero) res++;
            return res;
        }
        auto v = i2v(n);
        LL res = 0;
        for (int first = 0; first < 9; first++) {
            if (first < v[0]) {
                res += lessOrEqual(memo, pow(10, v.size()-1)-1, zero && first == 0);
            } else if (first == v[0]) {
                res += lessOrEqual(memo, n - first*pow(10, v.size()-1), zero && first == 0);
            }
        }
        return memo[n*2+zero] = res;
    }
    
    int newInteger(int n) {
        LL l = 1;
        LL r = INT_MAX;
        LL res = r;
        unordered_map<LL, LL> memo;
        while (l <= r) {
            LL m = l + (r - l) / 2;
            LL le =lessOrEqual(memo, m, true);
            if (le >= n) {
                res = min(res, m);
                r = m - 1;
            } else l = m + 1;
        }
        return res;
    }
};

python3 解法, 执行用时: 36 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-21 23:21:13

class Solution:
    def newInteger(self, n: int):
        ans = ''
        while n:
            ans = str(n%9) + ans
            n //= 9
        return int(ans)

java 解法, 执行用时: 0 ms, 内存消耗: 38.5 MB, 提交时间: 2023-10-21 23:20:31

class Solution {
    public int newInteger(int n) {
        return Integer.parseInt(Integer.toString(n, 9));
    }
}