回文数：数学和字符串拼接回文数，求解《9. 回文数》《866. 回文素数》《479. 最大回文数乘积》《906. 超级回文数》

回文数是什么数，用数学和字符串两种方法拼接回文数，求解《9. 回文数》《866. 回文素数》《479. 最大回文数乘积》《906. 超级回文数》

回文数

• 正读倒读都一样的数
• 是自然数（非负整数），最小是0

平方回文数

• 是回文数
• 是某数的平方

步骤

• 根据数据范围，确定回文数一半 left 的范围
• 回文数一半 left 可拼成 奇数 / 偶数 位两种回文数
• 拼接方法
  • 按 BigInt 拼接

    // 奇数位
    const n = BigInt((left + '').length)
    const palindrome = left * 10n ** (n - 1n) + reverse(left / 10n) // reverse(left / 10 | 0)
    // 偶数位
    const n = BigInt(left + '').length)
    const palindrome = left * 10n ** n + reverse(left)

  • 按字符串拼接

    // 奇数位
    const s = left
    let palindrome = s
    for (let i = s.length - 1; i--;) palindrome += s[i]<br>
    // 偶数位
    const s = left
    let palindrome = s
    for (let i = s.length; i--;) palindrome += s[i]

例题

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 例如，121 是回文，而 123 不是。

答案

var isPalindrome = function(x) {
  if (x < 0) return false
  let n = x, y = 0
  while (n) {
    y = y * 10 + n % 10
    n /= 10
    n |= 0
  }
  return x === y
};

func isPalindrome(x int) bool {
  if x < 0 {
    return false
  }
  n, y := x, 0
  for n > 0 {
    y = y * 10 + n % 10
    n /= 10
  }
  return x == y
}

866. 回文素数

求出大于或等于 N 的最小回文素数。 回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。 例如，2，3，5，7，11 以及 13 是素数。 回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。 例如，12321 是回文数。

答案

数学

var primePalindrome = function(n) {
  for (let len = 1; len <= 5; len++) {
    for (let left = 10 ** (len - 1); left < 10 ** len; left++) {
      const N = (left + '').length
      const palindrome = left * 10 ** (N - 1) + reverse(left / 10 | 0)
      if (palindrome >= n && isPrime(palindrome)) return palindrome 
    }
    for (let left = 10 ** (len - 1); left <= 10 ** len; left++) {
      const N = (left + '').length
      const palindrome = left * 10 ** N + reverse(left)
      if (palindrome >= n && isPrime(palindrome)) return palindrome 
    }
  }
  return 2 * 10 ** 8
};
const reverse = n => {
  let r = 0
  while (n) {
    r = r * 10 + n % 10
    n /= 10
    n |= 0
  }
  return r
};
const isPrime = n => {
  if (n <= 1) return false
  let x = 2
  while (x * x <= n) {
    if (n % x === 0) return false
    x++
  }
  return true
};

func primePalindrome(n int) int {
  for len := 1; len <= 5; len++ {
    for left := math.Pow10(len - 1); left < math.Pow10(len); left++ {
      palindrome := int(left * math.Pow10(len - 1)) + reverse(int(math.Floor(left / 10)))
      if palindrome >= n && isPrime(palindrome) {
         return palindrome
      }
    }
    for left := math.Pow10(len - 1); left < math.Pow10(len); left++ {
      palindrome := int(left * math.Pow10(len)) + reverse(int(left))
      if palindrome >= n && isPrime(palindrome) {
        return palindrome
      }
    }
  }
  return -1
}
func reverse(n int) int {
  r := 0
  for n > 0 {
    r = r * 10 + n % 10
    n /= 10
  }
  return r
}
func isPrime(n int) bool {
  if (n < 2) {
    return false
  }
  for i := 2; i * i <= n; i++ {
    if n % i == 0 {
      return false
    }
  }
  return true
}

字符串

var primePalindrome = function(n) {
  for (let len = 1; len <= 5; len++) {
    for (let left = 10 ** (len - 1); left < 10 ** len; left++) {
      const s = left + ''
      let palindrome = s
      for (let i = s.length - 1; i--;) palindrome += s[i]
      if (palindrome >= n && isPrime(palindrome)) return palindrome
    }
    for (let left = 10 ** (len - 1); left < 10 ** len; left++) {
      const s = left + ''
      let palindrome = s
      for (let i = s.length; i--;) palindrome += s[i]
      if (palindrome >= n && isPrime(palindrome)) return palindrome
    }
  }
};
const isPrime = n => {
  if (n < 2) return false
  let x = 2
  while (x * x <= n) {
    if (n % x === 0) return false
    x++
  }
  return true
}

func primePalindrome(n int) int {
  for len := 1; len <= 5; len++ {
    for left := math.Pow10(len - 1); left < math.Pow10(len); left++ {
      s := strconv.FormatFloat(left, 'f', -1, 32)
      palindrome := s
      for i := len - 2; i >= 0; i-- {
        palindrome += string(s[i])
      }
      palindromeInt, _ := strconv.Atoi(palindrome)
      if palindromeInt >= n && isPrime(palindromeInt) {
        return palindromeInt
      }
    }
    for left := math.Pow10(len - 1); left < math.Pow10(len); left++ {
      s := strconv.FormatFloat(left, 'f', -1, 32)
      palindrome := s
      for i := len - 1; i >= 0; i-- {
        palindrome += string(s[i])
      }
      palindromeInt, _ := strconv.Atoi(palindrome)
      if palindromeInt >= n && isPrime(palindromeInt) {
        return palindromeInt
      }
    }
  }
  return -1
}
func isPrime(n int) bool {
  if (n < 2) {
    return false
  }
  for i := 2; i * i <= n; i++ {
    if n % i == 0 {
      return false
    }
  }
  return true
}

479. 最大回文数乘积

给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余 。

答案

数学

var largestPalindrome = function(n) {
  if (n === 1) return 9
  n = BigInt(n)
  for (let left = 10n ** n - 1n; left >= 10n ** (n - 1n); left--) {
    const palindrome = left * 10n ** n + reverse(left)
    for (let multi = 10n ** n - 1n; multi * multi >= palindrome; multi--) {
      if (palindrome % multi === 0n) return palindrome % 1337n
    }
  }
};
const reverse = n => {
  let r = 0n
  while (n) {
    r = r * 10n + n % 10n
    n /= 10n
  }
  return r
}

func largestPalindrome(n int) int {
  if n == 1 {
    return 9
  }
  for left := math.Pow10(n) - 1; left >= math.Pow10(n - 1); left-- {
    palindrome := int(left * math.Pow10(n)) + reverse(int(left))
    for multi := int(math.Pow10(n) - 1); multi * multi >= palindrome; multi-- {
      if palindrome % multi == 0 {
        return palindrome % 1337
      }
    }
  }
  return -1
}
func reverse(n int) int {
  r := 0
  for n > 0 {
    r = r * 10 + n % 10
    n /= 10
  }
  return r
}

字符串

var largestPalindrome = function(n) {
  if (n === 1) return 9
  for (let left = 10 ** n - 1; left >= 10 ** (n - 1); left--) {
    const s = left + ''
    let palindrome = s
    for (let i = s.length; i--;) palindrome += s[i]
    const palindromeInt = BigInt(palindrome)
    for (let multi = BigInt(10 ** n - 1); multi * multi >= palindromeInt; multi--) {
      if (palindromeInt % multi === 0n) return palindromeInt % 1337n
    }
  }
  return -1
};

func largestPalindrome(n int) int {
  if n == 1 {
    return 9
  }
  for left := math.Pow10(n) - 1; left >= math.Pow10(n - 1); left-- {
    s := strconv.Itoa(int(left))
    palindrome := s
    for i := len(s) - 1; i >= 0; i-- {
      palindrome += string(s[i])
    }
    palindromeInt, _ := strconv.Atoi(palindrome)
    for multi := int(math.Pow10(n) - 1); multi * multi >= palindromeInt; multi-- {
      if palindromeInt % multi == 0 {
        return palindromeInt % 1337
      }
    }
  }
  return -1
}

906. 超级回文数

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数的数目。

答案

数学

var superpalindromesInRange = function(L, R) {
  let ans = 0
  for (let len = 1n; len <= 5n; len++) {
    for (let left = 10n ** (len - 1n); left < 10n ** len; left++) {
      const palindrome = left * 10n ** (len - 1n) + reverse(left / 10n)
      const multi = palindrome * palindrome
      if (multi > R) break
      if (multi >= L && multi === reverse(multi)) ans++
    }
    for (let left = 10n ** (len - 1n); left < 10n ** len; left++) {
      const palindrome = left * 10n ** len + reverse(left)
      const multi = palindrome * palindrome
      if (multi > R) break
      if (multi >= L && multi === reverse(multi)) ans++
    }
  }
  return ans
};
const reverse = n => {
  let r = 0n
  while (n) {
    r = r * 10n + n % 10n
    n /= 10n
  }
  return r
}

func superpalindromesInRange(L string, R string) int {
  Lmin, _ := strconv.Atoi(L)
  Rmax, _ := strconv.Atoi(R)
  ans := 0
  for len := 1; len <= 5; len++ {
    for left := math.Pow10(len - 1); left < math.Pow10(len); left++ {
      palindrome := int(left * math.Pow10(len - 1)) + reverse(int(left / 10))
      multi := palindrome * palindrome
      if multi > Rmax {
        break
      }
      if multi >= Lmin && multi == reverse(multi) {
        ans++
      }
    }
    for left := math.Pow10(len - 1); left < math.Pow10(len); left++ {
      palindrome := int(left * math.Pow10(len)) + reverse(int(left))
      multi := palindrome * palindrome
      if multi > Rmax {
        break
      }
      if multi >= Lmin && multi == reverse(multi) {
        ans++
      }
    }
  }
  return ans
}
func reverse(n int) int {
  r := 0
  for n > 0 {
    r = r * 10 + n % 10
    n /= 10
    n |= 0
  }
  return r
}

字符串

var superpalindromesInRange = function(L, R) {
  let ans = 0
  for (let len = 1; len <= 5; len++) {
    for (let left = 10 ** (len - 1); left < 10 ** len; left++) {
      const s = left + ''
      let palindrome = s
      for (let i = s.length - 1; i--;) palindrome += s[i]
      palindrome = BigInt(palindrome)
      const multi = palindrome * palindrome
      if (multi > R) break
      if (multi >= L && isPalindrome(multi)) ans++
    }
    for (let left = 10 ** (len - 1); left < 10 ** len; left++) {
      const s = left + ''
      let palindrome = s
      for (let i = s.length; i--;) palindrome += s[i]
      palindrome = BigInt(palindrome)
      const multi  = palindrome * palindrome
      if (multi > R) break
      if (multi >= L && isPalindrome(multi)) ans++
    }
  }
  return ans
};
const isPalindrome = s => {
  s = s.toString()
  let l = 0, r = s.length - 1
  while (l < r) {
    if (s[l] !== s[r]) return false
    l++
    r--
  }
  return true
}

func superpalindromesInRange(L string, R string) int {
  Lmin, _ := strconv.Atoi(L)
  Rmax, _ := strconv.Atoi(R)
  ans := 0
  for index := 1; index <= 5; index++ {
    for left := math.Pow10(index - 1); left < math.Pow10(index); left++ {
      s := strconv.Itoa(int(left))
      palindrome := s
      for i := len(s) - 2; i >= 0; i-- {
        palindrome += string(s[i])
      }
      palindromeInt, _ := strconv.Atoi(palindrome)
      multi := palindromeInt * palindromeInt
      if multi > Rmax {
        break
      }
      if multi >= Lmin && isPalindrome(multi) {
        ans++
      }
    }
    for left := math.Pow10(index - 1); left < math.Pow10(index); left++ {
      s := strconv.Itoa(int(left))
      palindrome := s
      for i := len(s) - 1; i >= 0; i-- {
        palindrome += string(s[i])
      }
      palindromeInt, _ := strconv.Atoi(palindrome)
      multi := palindromeInt * palindromeInt
      if multi > Rmax {
        break
      }
      if multi >= Lmin && isPalindrome(multi) {
        ans++
      }
    }
  }
  return ans
}
func isPalindrome(multi int) bool {
  s := strconv.Itoa(multi)
  for l, r := 0, len(s) - 1; l < r; l, r = l + 1, r - 1 {
    if s[l] != s[r] {
      return false
    }
  }
  return true
}