資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中計算範圍內數字個數，其中數字不包含超過 K 個非零數字
給定一個整數範圍，從變數（例如 start）開始到變數（例如 end）結束，以及一個變數 k，任務是計算該範圍內數字的個數，這些數字不包含超過 'k' 個非零數字。
例如
輸入 - int start = 50, end = 100 且 K = 2;
輸出 - 範圍內數字個數，其中數字不包含超過 K 個非零數字：50
解釋 - 範圍從 50 到 100，k 為 2。我們可以看到，50 到 100 之間的所有數字都是兩位數，這使得它們不可能包含超過 2 個非零數字，除了數字 100，它是一個三位數，但它也只有 2 個零，不多於 2 個，因此計數為 50。
輸入 - int start = 50, end = 100 且 K = 1;
輸出 - 範圍內數字個數，其中數字不包含超過 K 個非零
數字：5
解釋 - 範圍從 50 到 100，k 為 1。我們可以看到，50 到 100 之間的所有數字都是兩位數，因此不超過 1 或 k 個非零數字的數字是 50、60、70、80 和 90，因此計數為 5。
下面程式中使用的方案如下
- 建立一個從變數 start 到變數 end 的整數數字範圍，並宣告 k 並輸入值。將資料傳遞給函式以進行進一步處理。
- 建立一個向量型別的變數，例如 vec。
- 啟動迴圈，直到變數 start 中的值。現在，在迴圈內部，將值作為 val % 10 推入向量，並將 val 設定為 val / 10。
- 透過將 vec.begin() 和 vec.end() 作為引數傳遞給它，呼叫 STL 中的 reverse 函式。
- 使用 memset 將陣列中的值設定為 -1。
- 返回 check_val(0, 0, 0, vec)，這是一個將檢查數字是否為非零的函式。
- 在 check_val 函式內部 -
- 檢查 IF place 等於向量的 size，然後檢查 IF temp <= k，則返回 1 或返回 0。
- 檢查 IF arr[place][temp][set_val] 不等於 -1，則返回 arr[place][temp][set_val] 中的值。
- 宣告一個變數來儲存結果並將其設定為 0。
- 宣告一個變數 val 並將其設定為 9，如果 set_val 等於 1，否則將其設定為 i++
- 從 0 到 val 值啟動 FOR 迴圈
- 在迴圈內部，將 temp_2 設定為 temp 並檢查 IF 1 不等於 0，則將 temp_2 的值增加 1 並將 temp_3 設定為 set_val 並檢查 i 小於 vec[place]，然後將 temp_3 設定為 1
- 將 count 的值設定為對函式 check_val(place + 1, temp_2, temp_3, vec) 的遞迴呼叫
- 返回 arr[place][temp][set_val] 等於 count。
示例
#include <bits/stdc++.h>
using namespace std;
int arr[20][20][2];
int K;
int check_val(int place, int temp, int set_val, vector < int > vec) {
if (place == vec.size()) {
if (temp <= K) {
return 1;
}
return 0;
}
if (arr[place][temp][set_val] != -1) {
return arr[place][temp][set_val];
}
int count = 0;
int val = (set_val ? 9 : vec[place]);
for (int i = 0; i <= val; i++) {
int temp_2 = temp;
if (i != 0) {
temp_2++;
}
int temp_3 = set_val;
if (i < vec[place]) {
temp_3 = 1;
}
count += check_val(place + 1, temp_2, temp_3, vec);
}
return arr[place][temp][set_val] = count;
}
int Not_more_k(int val) {
vector < int > vec;
while (val) {
vec.push_back(val % 10);
val = val / 10;
}
reverse(vec.begin(), vec.end());
memset(arr, -1, sizeof(arr));
return check_val(0, 0, 0, vec);
}
int main() {
int start = 50, end = 100;
K = 2;
int count = Not_more_k(end) - Not_more_k(start);
cout << "Count of Numbers in Range where the number does not contain more than K non zero digits are: " << count;
return 0;
}如果我們執行以上程式碼，它將生成以下輸出 -
輸出
Count of Numbers in Range where the number does not contain more than K non zero digits are: 50
更新於: 2021年1月29日
285 次瀏覽
廣告