几道算法题

算法

1.假设有一个数，这个数的每一位数都不同，且每一位都不能为0，每一位数相加得到s。现在要求输入s，输出这个数的最大值。
即对于某个数s，s=a+b+c+d，其中a≠b≠c≠d≠0，求出abcd的最大值。
如此时程序输入s=9，则输出126。

实现思路：当位数最大时，此值最大；如果位数最大时不满足s=a+b+c+d，则位数减一，寻找满足条件的最大值。
因此，分两步进行，第一步寻找最大位数；
若第一步没有找到满足条件的值，位数减一，继续寻找。

代码实现：

function findNum(s) {
  if (s < 1 || s > 42) {
    return
  }
  var numArr = [1];
  var bit = 1;
  var numPlus = 1;
  while (numPlus < s) {
    numArr[bit] = ++bit;
    numPlus = bit * (1 + bit) / 2;
  }
  if (numPlus == s) {
    return parseInt(numArr.reverse().join(''));
  } else if (numPlus > s) {
    numArr.pop();
    var index = bit - 2;
    findNumStep2(index);
    return parseInt(numArr.reverse().join(''));
  }
  function findNumStep2(index) {
    var digit = index + 1;
    while (sumArr(numArr) !== s) {
      numArr[index] = ++digit;
      if (digit >= 9) {
        break;
      }
    }
    if (sumArr(numArr) !== s) {
      findNumStep2(--index);
    }
    return
  }
  function sumArr(arr) {
    var sum = 0;
    for (var i = 0; i < arr.length; i++) {
      sum += arr[i];
    }
    return sum
  }
}
// 假设s = 20
findNum(20)  // 95321

1. 寻找既是回文数又是素数的数。
   如12321、1551的数称为回文数。

实现思路：一开始自己写得比较复杂，导致程序内存溢出了。后来优化下，也拆分代码，分别做回文判断和素数判断。
目前用的素数判断是比较粗暴拙劣的方法，在上网查了下关于素数判断的方法，有很多值得学习的算法（如费马小定理），有时间继续深究。

代码实现：

function isPP (min, max) {
  let result = []
  while (min < max) {
    if (isPalindrome(min) && isPrime(min)) {
      result.push(min)
    }
    min++
  }
  return result
}
function isPalindrome (num) {
  let str1 = num.toString()
  let str2 = str1.split('').reverse().join('')
  if (str1 === str2) {
    return true
  } else {
    return false
  }
}
function isPrime (num) {
  if (num < 2) return false
  if (num !== 2 && num % 2 === 0) return false
  let sqrtNum = Math.sqrt(num);
  for (let i = 3; i <= sqrtNum; i += 2) {
    if (num % i === 0) return false
  }
  return true
}

3.对于给定字符串如'aaaabbcccd'，其字符串价值为字符出现次数的平方和，即为4 * 4 + 2 * 2 + 3 * 3 + 1 * 1。输入字符串和整数k，k为可移除字符串中某一字符的次数。求出最小字符串价值。

实现思路：毫无疑问，被移除的字符一定是出现次数最大的字符。思路是构建二维数组，数组元素为字符和字符出现的次数。然后进行删除字符操作和统计字符串价值。

代码实现：

function strValue (s, k) {
    let result = 0
    let sArr = [...new Set(s)]   // 去重的字符数组
    let count = []
    // 构建二维数组
    for (var i = 0;i < sArr.length; i++) {
        let n = s.match(new RegExp(sArr[i], 'g')).length
        count[i] = [sArr[i], n];
    }
    // 二维数组的元素根据出现次数排序
    count.sort((a, b) => {
        return b[1] - a[1]
    })
    // 移除出现次数最多的字符，执行k次
    while (k--) count.shift()
    // 计算价值
    for (var j = 0; j < count.length; j++) {
        result += Math.pow(count[j][1], 2)
    }
  return result
}