資料結構
網路
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 次瀏覽
廣告