スーパーパラダイム
66238 ワード
これは一連のleetcode解決説明の一部です.あなたがこの解決が好きであるか、それが役に立つとわかるならば、このポストとmy solution post on Leetcode's forums .
Leetcode Problem #906 (Hard): Super Palindromes
説明
にジャンプします.Solution Idea || コードJavaScript | Python | Java | C++ )
例:
制約
考え
にジャンプします.Problem Description || コードJavaScript | Python | Java | C++ )
私たちがこの問題について理解することができなければならない最初のことは、それが大きなpalindromeから始まって、それをsquarerootingしているよりむしろ小さいPalindromeから、そして、それを正方形から始めるのがより簡単であるということです.これは、大規模なpalindromeの制約は、小さなpalindromeは9桁まで行くことができることを意味18桁まで行くので、特に便利です.
より小さいpalindromeから始めて、我々は簡単に文字列がpalindromeであるかどうかテストするために関数ispal ()を簡単に作成することができます.これは、制約に到達する前に、微妙な結果になりますが、小さなpalindromesについての興味深い情報を見つけるために使用することができます.
「1」と「9999999999999」の間にある小さなpalindrome値を考えてみましょう.
上記の有効な数値をもう少し詳しく見ると、さらにいくつかのことがわかります. 2は、値のエッジまたは奇数長の値の中間位置にのみ存在できます. エッジが2 sであるならば、唯一の他の変化は奇数長さ値の中央の1です. これらの観測を使用して、これらの規則にマッチする文字列を構築するために関数を変更することができます.これらの規則に従うようにしようとすると、Base 3ショートカットを防ぐために、より手動操作で文字列を構築する必要がありますが、それはまた、反復カウントをさらに減らすために、私たちがPalindromesを構築しているだけであることを保証する機会を利用することができます.
実際、我々がこれらの規則に従うならば、我々は実際に最大74の値を通して繰り返すだけです.
JavaScriptコード
にジャンプします.Problem Description || Solution Idea )
建物の教壇
Base 3反復
Pythonコード:
にジャンプします.Problem Description || Solution Idea )
建物の教壇
Base 3反復
Javaコード:
にジャンプします.Problem Description || Solution Idea )
建物の教壇
Base 3反復
C++コード:
にジャンプします.Problem Description || Solution Idea )
建物の教壇
Base 3反復
Leetcode Problem #906 (Hard): Super Palindromes
説明
にジャンプします.Solution Idea || コードJavaScript | Python | Java | C++ )
Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.
Given two positive integers
leftandrightrepresented as strings, return the number of super-palindromes integers in the inclusive range[left, right].
例:
Example 1: Input: left = "4", right = "1000" Output: 4 Explanation: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.
Example 2: Input: left = "1", right = "2" Output: 1
制約
1 <= left.length, right.length <= 18leftandrightconsist of only digits.leftandrightcannot have leading zeros.leftandrightrepresent integers in the range[1, 1018].leftis less than or equal toright.
考え
にジャンプします.Problem Description || コードJavaScript | Python | Java | C++ )
私たちがこの問題について理解することができなければならない最初のことは、それが大きなpalindromeから始まって、それをsquarerootingしているよりむしろ小さいPalindromeから、そして、それを正方形から始めるのがより簡単であるということです.これは、大規模なpalindromeの制約は、小さなpalindromeは9桁まで行くことができることを意味18桁まで行くので、特に便利です.
より小さいpalindromeから始めて、我々は簡単に文字列がpalindromeであるかどうかテストするために関数ispal ()を簡単に作成することができます.これは、制約に到達する前に、微妙な結果になりますが、小さなpalindromesについての興味深い情報を見つけるために使用することができます.
「1」と「9999999999999」の間にある小さなpalindrome値を考えてみましょう.
[1, 2, 3, 11, 22, 101, 111, 121, 202, 212, 1001, 1111, 2002, 10001, 10101,
10201, 11011, 11111, 11211, 20002, 20102, 100001, 101101, 110011, 111111,
200002, 1000001, 1001001, 1002001, 1010101, 1011101, 1012101, 1100011,
1101011, 1102011, 1110111, 1111111, 2000002, 2001002]
上記の有効な数値をもう少し詳しく見ると、さらにいくつかのことがわかります.
実際、我々がこれらの規則に従うならば、我々は実際に最大74の値を通して繰り返すだけです.
JavaScriptコード
にジャンプします.Problem Description || Solution Idea )
建物の教壇
var superpalindromesInRange = function(left, right) {
let ans = 9 >= left && 9 <= right ? 1 : 0
const isPal = str => {
for (let i = 0, j = str.length - 1; i < j; i++, j--)
if (str.charAt(i) !== str.charAt(j)) return false
return true
}
for (let dig = 1; dig < 10; dig++) {
let isOdd = dig % 2 && dig !== 1,
innerLen = (dig >> 1) - 1, innerLim = Math.max(1, 2 ** innerLen),
midPos = dig >> 1, midLim = isOdd ? 3 : 1
for (let edge = 1; edge < 3; edge++) {
let pal = new Uint8Array(dig)
pal[0] = edge, pal[dig-1] = edge
if (edge === 2) innerLim = 1, midLim = Math.min(midLim, 2)
for (let inner = 0; inner < innerLim; inner++) {
if (inner > 0) {
let innerStr = inner.toString(2).padStart(innerLen, '0')
for (let i = 0; i < innerLen; i++)
pal[1+i] = innerStr[i], pal[dig-2-i] = innerStr[i]
}
for (let mid = 0; mid < midLim; mid++) {
if (isOdd) pal[midPos] = mid
let palin = ~~pal.join(""),
square = BigInt(palin) * BigInt(palin)
if (square > right) return ans
if (square >= left && isPal(square.toString())) ans++
}
}
}
}
return ans
};
Base 3反復
var superpalindromesInRange = function(left, right) {
let ans = 9 >= left && 9 <= right ? 1 : 0
const isPal = str => {
for (let i = 0, j = str.length - 1; i < j; i++, j--)
if (str.charAt(i) !== str.charAt(j)) return false
return true
}
for (let i = 1; i < 19684; i++) {
let num = i.toString(3)
if (isPal(num)) {
let square = BigInt(num) * BigInt(num)
if (square > right) return ans
if (square >= left && isPal(square.toString())) ans++
}
}
return ans
};
Pythonコード:
にジャンプします.Problem Description || Solution Idea )
建物の教壇
class Solution:
def superpalindromesInRange(self, left: str, right: str) -> int:
ans = 1 if 9 >= int(left) and 9 <= int(right) else 0
def isPal(s: str) -> bool:
return s == s[::-1]
for dig in range(1, 10):
isOdd = dig % 2 and dig != 1
innerLen = (dig >> 1) - 1
innerLim = max(1, 2 ** innerLen)
midPos = dig >> 1
midLim = 3 if isOdd else 1
for edge in range (1, 3):
pal = [0] * dig
pal[0], pal[-1] = edge, edge
if edge == 2: innerLim, midLim = 1, min(midLim, 2)
for inner in range(innerLim):
if inner > 0:
innerStr = list(bin(inner)[2:].zfill(innerLen))
pal[1:1+innerLen] = innerStr
pal[-innerLen-1:-1] = reversed(innerStr)
for mid in range(midLim):
if isOdd: pal[midPos] = mid
palin = int("".join([str(n) for n in pal]))
square = palin * palin
if square > int(right): return ans
if square >= int(left) and isPal(str(square)): ans += 1
return ans
Base 3反復
class Solution:
def superpalindromesInRange(self, left: str, right: str) -> int:
ans = 1 if 9 >= int(left) and 9 <= int(right) else 0
def isPal(s: str) -> bool:
return s == s[::-1]
def base3(n: int, num: str) -> str:
if not n: return num
n, r = divmod(n, 3)
return base3(n, str(r) + num)
for i in range(1, 19684):
num = base3(i, "")
if isPal(num):
square = int(num) * int(num)
if square > int(right): return ans
if square >= int(left) and isPal(str(square)): ans += 1
return ans
Javaコード:
にジャンプします.Problem Description || Solution Idea )
建物の教壇
class Solution {
public int superpalindromesInRange(String left, String right) {
int ans = 9 >= Long.parseLong(left) && 9 <= Long.parseLong(right) ? 1 : 0;
for (int dig = 1; dig < 10; dig++) {
boolean isOdd = dig % 2 > 0 && dig != 1;
int innerLen = (dig >> 1) - 1,
innerLim = Math.max(1, (int)Math.pow(2, innerLen)),
midPos = dig >> 1, midLim = isOdd ? 3 : 1;
for (int edge = 1; edge < 3; edge++) {
char[] pal = new char[dig];
Arrays.fill(pal, '0');
pal[0] = (char)(edge + 48);
pal[dig-1] = (char)(edge + 48);
if (edge == 2) {
innerLim = 1;
midLim = Math.min(midLim, 2);
}
for (int inner = 0; inner < innerLim; inner++) {
if (inner > 0) {
String innerStr = Integer.toString(inner, 2);
while (innerStr.length() < innerLen)
innerStr = "0" + innerStr;
for (int i = 0; i < innerLen; i++) {
pal[1+i] = innerStr.charAt(i);
pal[dig-2-i] = innerStr.charAt(i);
}
}
for (int mid = 0; mid < midLim; mid++) {
if (isOdd) pal[midPos] = (char)(mid + 48);
String palin = new String(pal);
long square = Long.parseLong(palin) * Long.parseLong(palin);
if (square > Long.parseLong(right)) return ans;
if (square >= Long.parseLong(left) && isPal(Long.toString(square))) ans++;
}
}
}
}
return ans;
}
private boolean isPal(String str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--)
if (str.charAt(i) != str.charAt(j)) return false;
return true;
}
}
Base 3反復
class Solution {
public int superpalindromesInRange(String left, String right) {
int ans = 9 >= Long.parseLong(left) && 9 <= Long.parseLong(right) ? 1 : 0;
for (int i = 1; i < 19684; i++) {
String num = Integer.toString(i, 3);
if (isPal(num)) {
long square = Long.parseLong(num) * Long.parseLong(num);
if (square > Long.parseLong(right)) return ans;
if (square >= Long.parseLong(left) && isPal(Long.toString(square))) ans++;
}
}
return ans;
}
private boolean isPal(String str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--)
if (str.charAt(i) != str.charAt(j)) return false;
return true;
}
}
C++コード:
にジャンプします.Problem Description || Solution Idea )
建物の教壇
class Solution {
public:
int superpalindromesInRange(string left, string right) {
int ans = 9 >= stol(left) && 9 <= stol(right) ? 1 : 0;
for (int dig = 1; dig < 10; dig++) {
bool isOdd = dig % 2 && dig != 1;
int innerLen = (dig >> 1) - 1,
innerLim = max(1, (int)pow(2, innerLen)),
midPos = dig >> 1, midLim = isOdd ? 3 : 1;
for (int edge = 1; edge < 3; edge++) {
string pal(dig, '0');
pal[0] = (char)(edge + 48);
pal[dig-1] = (char)(edge + 48);
if (edge == 2) innerLim = 1, midLim = min(midLim, 2);
for (int inner = 0; inner < innerLim; inner++) {
if (inner > 0) {
string innerStr = bitset<3>(inner).to_string();
innerStr = innerStr.substr(3 - innerLen);
for (int i = 0; i < innerLen; i++) {
pal[1+i] = innerStr[i];
pal[dig-2-i] = innerStr[i];
}
}
for (int mid = 0; mid < midLim; mid++) {
if (isOdd) pal[midPos] = (char)(mid + 48);
long square = stol(pal) * stol(pal);
if (square > stol(right)) return ans;
if (square >= stol(left) && isPal(to_string(square))) ans++;
}
}
}
}
return ans;
}
bool isPal(string str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--)
if (str[i] != str[j]) return false;
return true;
}
};
Base 3反復
class Solution {
public:
int superpalindromesInRange(string left, string right) {
int ans = 9 >= stol(left) && 9 <= stol(right) ? 1 : 0;
for (int i = 1; i < 19684; i++) {
string num = base3(i);
if (isPal(num)) {
long square = stol(num) * stol(num);
if (square > stol(right)) return ans;
if (square >= stol(left) && isPal(to_string(square))) ans++;
}
}
return ans;
}
string base3(int n, string num="") {
if (!n) return num;
div_t divres = div(n, 3);
return base3(divres.quot, (char)(divres.rem + 48) + num);
}
bool isPal(string str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--)
if (str[i] != str[j]) return false;
return true;
}
};
Reference
この問題について(スーパーパラダイム), 我々は、より多くの情報をここで見つけました https://dev.to/seanpgallivan/solution-super-palindromes-30dテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol