JS中数字是否为回文的最佳验证

Question

过去几天我遇到了一个问题。

我想写一个最佳的（在 JS 中）程序来验证一个数字是否是回文。

我目前的做法：

function isPalidrom2(pali){
//MOST time consuming call - I am splitting the digit into char array. 
  var digits = (""+pali).split("");
//To get the length of it. 
  var size = digits.length;
  var isPali = true;
  for(var i = 0; i<Math.floor(size/2); i++){
    //I am comparing digits (first vs last, second vs last-1, etc.) one by one, if ANY of the pars is not correct I am breaking the loop. 
    if(parseInt(digits[i]) != parseInt(digits[size-i-1])){
      isPali = false;
      break;
    }
  }
  return isPali;
}

这不是最佳选择。我最浪费的时间是从 INT 到 STRING 的变化。

我没主意了 - 我试图理解 BIT 运算符，但我做不到。 - 我试图 google 并寻找替代方法 - 但我找不到任何东西。 - 我尝试使用不同的算法 - 但这个算法是我能够应用的最快的。

简而言之 - 我的问题是： "how can I make it faster?"

编辑：

所以我要解决的任务：

Find all of the prime numbers within the range of all five digit numbers. Among all of the multiplies (i*j) they are between them, find the most significant palindrome.

我目前的做法：

function isPrime(number){
  var prime = true;
  var i
  for(i = 2; i<= number/2; i++){
if((number%i)==0){
  prime = false;
  break;
}
  }
  return prime;
}

function get5DigitPrimeNr(){
  var a5DigitsPrime = [];
  var i;
  for(i = 10000; i<100000; i++){
if(isPrime(i)){
  a5DigitsPrime.push(i)
}
  }
  return a5DigitsPrime;
}

function isPalidrom(pali){
  var digits = (""+pali).split("");
  //we check if first and last are the same - if true, we can progress
  size = digits.length;
  return
(digits[0]==digits[size-1]) &&
(parseInt(digits.slice(1, Math.floor(size/2)).join("")) ==
  parseInt(digits.reverse().slice(1, Math.floor(size/2)).join("")))
}

function isPalidrom2_48s(str) {
  var str = str.toString();
  const lower = str.substr(0, Math.floor(str.length / 2));
  const upper = str.substr(Math.ceil(str.length / 2));
  return lower.split("").reverse().join("") === upper;
}

function isPalidrom_22s(pali){
  var digits = (""+pali).split("");
  var size = digits.length;
  for(var i = 0; i<Math.floor(size/2); i++){
//console.log("I am comparing: "+i+", and "+(size-i-1)+" elements in array")
//console.log("I am comparing digit: "+digits[i]+", and "+digits[(size-i-1)]+"")
if(digits[i] !== digits[size-i-1]){
  //console.log('nie sa rowne, koniec')
  return false;
}
  }
  return true;
}

function isPalidrom2_80s(pali){
  return parseInt(pali) == parseInt((""+pali).split("").reverse().join(""))
}

function runme(){
  var prime5digits = get5DigitPrimeNr();
  var size = prime5digits.length;
  var max = 0;
  var message = "";
  for(var i = 0; i<size; i++){
for(var j = 0; j<size; j++){
  var nr = prime5digits[i]*prime5digits[j];
  if(nr>max && isPalidrom2(nr)){
    max = nr;
    message = 'biggest palidrome nr: '+nr+', made from numbers: '+prime5digits[i]+' x '+prime5digits[j];
  }
}
  }
  console.log(message)
}

function timeMe(){
  var t0 = performance.now();
  runme();
  var t1 = performance.now();
  console.log("Function took " + millisToMinutesAndSeconds(t1 - t0) + " s to find the perfect palindrom.")
}

//helper functons:

function millisToMinutesAndSeconds(millis) {
  var minutes = Math.floor(millis / 60000);
  var seconds = ((millis % 60000) / 1000).toFixed(0);
  return minutes + ":" + (seconds < 10 ? '0' : '') + seconds;
}

Answer 1

最快的可能是依赖javascript原生方法：

 function isPalindrome(str) {
   const lower = str.substr(0, Math.floor(str.length / 2));
   const upper = str.substr(Math.ceil(str.length / 2));

   return lower.split("").reverse().join("") === upper;
}

或者从您的代码中删除所有不必要的对话：

function isPlaindrome(str) {
  const half = str.length / 2;
  for(var i = 0; i < half; i++)
    if(str[i] !== str[str.length - i - 1])
       return false;
  return true;
}

Answer 2

为了保持代码的精神，您可以使用 return 而不是 break 退出循环并直接使用字符串而不转换为数组。作为数组，字符串可以通过索引访问单个字符。

function isPalidrom2(value) {
    var digits = value.toString(),
        length = digits.length,
        i, l;

    for (i = 0, l = length >> 1; i < l; i++) {
        if (digits[i] !== digits[length - i - 1]) {
            return false;
       }
    }
    return true;
}

console.log(isPalidrom2(1));
console.log(isPalidrom2(12));
console.log(isPalidrom2(1221));
console.log(isPalidrom2(123));

Answer 3

如果您想加快速度，可以通过优化 isPrime(n) 函数来再缩短几秒钟。

您不需要检查每个因子，只检查小于 sqrt(n)
如果你按升序检查从 2 到 99999 的每个数字，你可以随时存储结果，所以你不需要不断地重新计算之前的素数列表

像这样：

var savedPrimes = [2]

function isPrime(n){
    // call this method with increasing values of n (starting at 2), saving primes as we go,
    // so we can safely assume that savedPrimes contains all primes less than n
    for(var i=0; i<savedPrimes.length; i++)
    {
        var f = savedPrimes[i];
        if ((n % f) == 0)
            return false; // found a factor
        if (f*f>=n)
            break; // stop checking after f >= sqrt(n)
    }
    // no prime factors - we found a new prime
    savedPrimes.push(n);
    return true;
}


function get5DigitPrimeNr(){
    var a5DigitsPrime = [];
    var i;

    // first find all the primes less than 10000
    for(i = 3; i<10000; i++){
        isPrime(i);
    }

    // now find (and keep) the rest of the primes up to 99999
    for(i = 10000; i<100000; i++){
        if(isPrime(i)){
            a5DigitsPrime.push(i)
        }
    }
    return a5DigitsPrime;
}

EDIT - 当我用这种方法运行你的代码时，我得到的时间是 10 秒

Answer 4

代码：

您可以使用多种方法（不知道它们是否最佳）：

Palindrom = _ => (_=''+_) === [..._].sort(_=>1).join``

还有一些：

let isPalindrome = __ => (_=(__=__+'').length)==0||_==1?!0:__[0]==__.slice(-1)?isPalindrome(__.slice(1,-1)):!1

let isPalindrome = (s,i) => (i=i||0)<0||i>=(s=''+s).length>>1||s[i]==s[s.length-1-i]&&isPalindrome(s,++i);

let isPalindrome = (str) => {
  var len = ~~((str=str+'').length / 2);
  for (var i = 0; i < len; i++)
    if (str[i] !== str[str.length - i - 1])
      return false;
  return true;
}

Updated 现在将数字作为输入

JS中数字是否为回文的最佳验证

Optimal verification if a number is Palindrom in JS

javascript

optimization

palindrome

代码：