資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中的超級迴文數
假設我們有一個正整數N，如果它是一個迴文數，並且也是一個迴文數的平方，則稱它為超級迴文數。現在考慮我們有兩個正整數L和R，我們需要找到[L, R]區間內超級迴文數的數量。
因此，如果輸入像L = 5，R = 500，則輸出為3，超級迴文數為9、121、484。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式helper()，它將接收x、m、M、lb、ub作為引數。
如果x > ub，則：
返回
如果x >= lb並且(x * x)是迴文數，則：
(將ans增加1)
從i := 1開始初始化，當m + 2 * i <= M時，更新(i增加1)，執行：
W := 10^(m + 2 * i - 1)
w := 10^i
從z := 1開始初始化，當z <= 9時，更新(z增加1)，執行：
helper(z * W + x * w, m + 2 * i, M, lb, ub)
在主方法中，執行以下操作：
lb := L的平方根，ub := R的平方根
M := 執行ub以10為底的對數 + 1
從z := 0開始初始化，當z <= 9時，更新(z增加1)，執行：
helper(z, 1, M, lb, ub)
helper(11 * z, 2, M, lb, ub)
返回ans
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
int ans = 0;
public:
int superpalindromesInRange(string L, string R){
long double lb = sqrtl(stol(L)), ub = sqrtl(stol(R));
int M = log10l(ub) + 1;
for (int z = 0; z <= 9; z++) {
helper(z, 1, M, lb, ub);
helper(11 * z, 2, M, lb, ub);
}
return ans;
}
private:
void helper(long x, int m, int M, long double lb, long double ub){
if (x > ub)
return;
if (x >= lb && is_palindrome(x * x))
ans++;
for (int i = 1; m + 2 * i <= M; i++) {
long W = powl(10, m + 2 * i - 1) + 1;
long w = powl(10, i);
for (int z = 1; z <= 9; z++)
helper(z * W + x * w, m + 2 * i, M, lb, ub);
}
}
bool is_palindrome(long x){
if (x == 0)
return true;
if (x % 10 == 0)
return false;
long left = x, right = 0;
while (left >= right) {
if (left == right || left / 10 == right)
return true;
right = 10 * right + (left % 10), left /= 10;
}
return false;
}
};
main(){
Solution ob;
cout << (ob.superpalindromesInRange("5", "500"));
}輸入
"5", "500"
輸出
3
更新於：2020年6月4日
430 次瀏覽
廣告