常见算法学习

求和

问题： 给定一个整数无序数组和变量sum，如果存在数组中任意两项和使等于sum的值，则返回true。否则返回false。例如，数组[3,5,1,4]和sum = 9，函数应该返回true，因为4 + 5 = 9 解：

const findSum = (arr, val) => {
  let searchValues = new Set();
  searchValues.add(val - arr[0]);
  for (let i = 1, length = arr.length; i < length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.has(arr[i])) {
      return true;
    } else {
      searchValues.add(searchVal);
    }
  };
  return false;
};

阶乘

// 尾递归优化
const factorial2 = (n, total = 1) => {
  if (n <= 1) return total
  return factorial2(n - 1, total * n)
}

斐波那契数列

function fib(n) {
  let a = 0;
  let b = 1;
  let c = a + b;
  for (let i = 3; i < n; i++) {
    a = b;
    b = c;
    c = a + b;
  }
  return c;
}

如何判断一个字符串是否另一个字符串的子序列

描述： 比如给定 a = apple, b = axpfxplle; 那么a就是b的子序列。 你也可以这么理解，在b中删除零个或多个字符，如果可以使得a和b相等，那么说明a就是b的子序列。

function isSequence(a, b) {
  let i = 0;
  let j = 0;

  while(i < a.length && j < b.length) {
    if (a[i] === b[j]) i++;
    j++;
  }

  return i === a.length;
}

最少硬币找零

class MinCoinChange {
  constructor(coins) {
    this.coins = coins
    this.cache = {}
  }
  makeChange(amount) {
    if (!amount) return []
    if (this.cache[amount]) return this.cache[amount]
    let min = [], newMin, newAmount
    this.coins.forEach(coin => {
      newAmount = amount - coin
      if (newAmount >= 0) {
        newMin = this.makeChange(newAmount)
      }
      if (newAmount >= 0 && 
        (newMin.length < min.length - 1 || !min.length) && 
        (newMin.length || !newAmount)) {
        min = [coin].concat(newMin)
      }
    })
    return (this.cache[amount] = min)
  }
}
const rninCoinChange = new MinCoinChange([1, 2, 5, 10])
console.log(rninCoinChange.makeChange(120))

小红包免费领

小礼物走一走