进制下中数字出现的次数,记作。例如,因为三进制为,数字出现了次。牛牛现在给你和,他想知道,最小的是多少呢。请你返回的值。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @param k int整型 * @return long长整型 */ public long minM (int n, int k) { // write code here int len = getBits(n, k); // 计算n是几位数 // k进制数的左右边界 long left = 1; long right = (long)Math.pow(k, len + 1); // 二分法找最小的m long lowestM = right; while(left <= right){ long m = left + ((right - left) >> 1); if(caculateOnes(m, k) < n){ left = m + 1; }else{ lowestM = m; right = m - 1; } } return lowestM; } // 计算k进制下1~m有多少个1 private long caculateOnes(long num, int k) { int len = getBits(num, k); if(len <= 1){ return len; } long offset = (long)Math.pow(k, len - 1); long first = num / offset; long curOne = first == 1 ? (num % offset) + 1 : offset; long restOne = first * (len - 1) * (offset / k); return curOne + restOne + caculateOnes(num % offset, k); } // 计算num有多少位 private int getBits(long num, int radix) { int len = 0; while(num > 0){ num /= radix; len++; } return len; } }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param n int整型 # @param k int整型 # @return long长整型 # class Solution: def minM(self , n , k ): def find(m, k): if m==0: return 0 if m < k: return 1 # 找0-m(含) k进制有多少1 a = [] mm = m while mm: a.append(mm % k) mm //= k p = len(a) - 1 t = 1 s = [0] * (p+1) while t <= p: s[t] = k * s[t - 1] + k ** (t - 1) t += 1 if a[p] == 1: ans = m - k ** p + 1 + s[p] + find(m - k ** p, k) else: ans = a[p] * s[p] + k ** p + find(m - a[p] * k ** p, k) return ans if n==1: return 1 p = 1 while p*k**(p-1)<n: p+=1 st = k**(p-1) ed = k**p while st<ed-1: mid = (st+ed)>>1 if find(mid, k)<n: st = mid else: ed = mid if find(st+1, k)>=n: return st+1 else: return st+2