数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的令人困惑的数字 II
假设我们有一个数字，现在如果我们将该数字旋转 180 度以形成新的数字。当 0、1、6、8、9 旋转 180 度时，它们分别变成 0、1、9、8、6。但是当 2、3、4、5 和 7 旋转 180 度时，它们变得无效。
令人困惑的数字是一个数字，当旋转 180 度时会变成一个新数字。因此，如果我们有一个正整数 N，我们必须找到 1 到 N（包括 1 和 N）之间令人困惑的数字的数量。
因此，如果输入类似于 20，则输出将为 6
为了解决这个问题，我们将遵循以下步骤 -
定义一个映射 map
定义一个数组 valid
定义一个函数 solve()，它将接收 num、rotate、digit、N，
如果 rotate 不等于 num，则 -
（将 ret 增加 1）
对于初始化 i := 0，当 i < valid 的大小，更新（将 i 增加 1），执行 -
dig := valid[i]
如果 num * 10 + dig > N，则
退出循环
solve(num * 10 + dig, 定义一个映射，digit * 10, N)
从主方法执行以下操作 -
ret := 0
valid := { 0, 1, 6, 8, 9 }
mapping[0] := 0
mapping[1] := 1
mapping[6] := 9
mapping[9] := 6
mapping[8] := 8
solve(1, 1, 10, N)
solve(6, 9, 10, N)
solve(9, 6, 10, N)
solve(8, 8, 10, N)
返回 ret
让我们看看以下实现以获得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int ret;
map <int, int> mapping;
vector <int> valid;
void solve(lli num, lli rotate, lli digit, lli N){
if (rotate != num) {
ret++;
}
for (int i = 0; i < valid.size(); i++) {
int dig = valid[i];
if (num * 10 + dig > N) {
break;
}
solve(num * 10 + dig, mapping[dig] * digit + rotate, digit * 10, N);
}
}
int confusingNumberII(int N) {
ret = 0;
valid = { 0, 1, 6, 8, 9 };
mapping[0] = 0;
mapping[1] = 1;
mapping[6] = 9;
mapping[9] = 6;
mapping[8] = 8;
solve(1, 1, 10, N);
solve(6, 9, 10, N);
solve(9, 6, 10, N);
solve(8, 8, 10, N);
return ret;
}
};
main(){
Solution ob;
cout << (ob.confusingNumberII(20));
}输入
20
输出
6
更新于: 2020年7月11日
752 次浏览
广告