数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告