数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究可找到小于或等于 M 数值的不同进制表示方式
假设我们有一个数字字符串 S 和另一个数字 M。令 d 为 S 中最大的数字。我们需要找出可以通过选择一个不小于 d+1 的整数 n，并将 S 视为 n 进制数字，得到多少个不同的不大于 M 的整数？
因此，如果输入类似于 S = "999"; M = 1500，那么输出将为 3，因为 S 作为 10 进制数字，我们得到 999，作为 11 进制数字，我们得到 1197，作为 12 进制数字，我们得到 1413。这三个值是我们唯一可以获得且不大于 1500 的值。
步骤
要解决这个问题，我们将按照以下步骤操作 −
if size of S is same as 1, then: if numeric value of S <= M, then: return 1 Otherwise return 0 d := 0 for each character c in S, do d := maximum of d and (c - ASCII of '0') left := d right := M + 1 while right - left > 1, do: mid := (left + right) / 2 v := 0 for each character c in S, do if v > M / mid, then: v := M + 1 Otherwise v := v * mid + (c - ASCII of '0') if v <= M, then: left := mid Otherwise right := mid return left - d
示例
让我们看看以下实现以更好地理解 −
#include <bits/stdc++.h>
using namespace std;
int solve(string S, int M){
if (S.size() == 1){
if (stoi(S) <= M)
return 1;
else
return 0;
}
int d = 0;
for (char c : S)
d = max(d, int(c - '0'));
long left = d;
long right = M + 1;
while (right - left > 1){
long mid = (left + right) / 2;
long v = 0;
for (char c : S){
if (v > M / mid)
v = M + 1;
else
v = v * mid + (c - '0');
}
if (v <= M)
left = mid;
else
right = mid;
}
return left - d;
}
int main(){
string S = "999";
int M = 1500;
cout << solve(S, M) << endl;
}输入
"999", 1500
输出
3
更新时间： 03-Mar-2022
130 次浏览
广告