資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告