javascript常见算法

一、数学算法

1.阶乘

5! = 5 * 4 * 3 * 2 * 1 = 120
4! = 4 * 3 * 2 * 1 = 24
/**
 * @param {number} number
 * @return {number}
 */
export default function factorial(number) {
  let result = 1;

  for (let i = 1; i <= number; i += 1) {
    result *= i;
  }

  return result;
}

2.斐波那契数

// Calculate fibonacci number at specific position using Dynamic Programming approach.
export default function fibonacci(numberPosition) {
  if (numberPosition === 1) {
    return 1;
  }

  let iterationsCounter = numberPosition - 1;

  // Calculated fibonacci number.
  let fib = null;
  // Previous fibonacci number.
  let fibPrev = 1;
  // Before previous fibonacci number.
  let fibPrevPrev = 0;

  while (iterationsCounter) {
    // Calculate current value using two previous ones.
    fib = fibPrev + fibPrevPrev;
    // Shift previous values.
    fibPrevPrev = fibPrev;
    fibPrev = fib;
    iterationsCounter -= 1;
  }

  return fib;
}

3.素数检测 (排除法)

/**
 * @param {number} number
 * @return {boolean}
 */
export default function trialDivision(number) {
  if (number <= 1) {
    // If number is less than one then it isn't prime by definition.
    return false;
  } else if (number <= 3) {
    // All numbers from 2 to 3 are prime.
    return true;
  }

  // If the number is not divided by 2 then we may eliminate all further even dividers.
  if (number % 2 === 0) {
    return false;
  }

  // If there is no dividers up to square root of n then there is no higher dividers as well.
  const dividerLimit = Math.sqrt(number);
  for (let divider = 3; divider <= dividerLimit; divider += 2) {
    if (number % divider === 0) {
      return false;
    }
  }

  return true;
}

4.欧几里得算法 - 计算最大公约数(GCD)

/**
 * @param {number} originalA
 * @param {number} originalB
 * @return {number|null}
 */
export default function euclideanAlgorithm(originalA, originalB) {
  const a = Math.abs(originalA);
  const b = Math.abs(originalB);

  if (a === 0 && b === 0) {
    return null;
  }

  if (a === 0 && b !== 0) {
    return b;
  }

  if (a !== 0 && b === 0) {
    return a;
  }

  // Normally we need to do subtraction (a - b) but to prevent
  // recursion occurs to often we may shorten subtraction to (a % b).
  // Since (a % b) is normally means that we've subtracted b from a
  // many times until the difference became less then a.

  if (a > b) {
    return euclideanAlgorithm(a % b, b);
  }

  return euclideanAlgorithm(b % a, a);
}

5.最小公倍数 (LCM)

4和6的最小公倍数是多少?

4的倍数有:

4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ...
6的倍数有:

6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...
所以4和6共同的倍数有:

12, 24, 36, 48, 60, 72, ....
所以他们的最小公倍数是12.

// euclideanAlgorithm就是上面计算最大公约数的算法
import euclideanAlgorithm from '../euclideanAlgorithm';

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */

export default function leastCommonMultiple(a, b) {
  if (a === 0 && b === 0) {
    return 0;
  }

  return Math.abs(a * b) / euclideanAlgorithm(a, b);
}

6.整数拆分

4可以拆分成以下5种:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
/**
 * @param {Number} number
 */
export default function integerPartition(number) {
  // Create partition matrix for solving this task using Dynamic Programming.
  const partitionMatrix = Array(number + 1).fill(null).map(() => {
    return Array(number + 1).fill(null);
  });

  // Fill partition matrix with initial values.

  // Let's fill the first row that represents how many ways we would have
  // to combine the numbers 1, 2, 3, ..., n with number 0. We would have zero
  // ways obviously since with zero number we may form only zero.
  for (let numberIndex = 1; numberIndex <= number; numberIndex += 1) {
    partitionMatrix[0][numberIndex] = 0;
  }

  // Let's fill the first row. It represents the number of way of how we can form
  // number zero out of numbers 0, 1, 2, ... Obviously there is only one way we could
  // form number 0 and it is with number 0 itself.
  for (let summandIndex = 0; summandIndex <= number; summandIndex += 1) {
    partitionMatrix[summandIndex][0] = 1;
  }

  // Now let's go through other possible options of how we could form number m out of
  // summands 0, 1, ..., m using Dynamic Programming approach.
  for (let summandIndex = 1; summandIndex <= number; summandIndex += 1) {
    for (let numberIndex = 1; numberIndex <= number; numberIndex += 1) {
      if (summandIndex > numberIndex) {
        // If summand number is bigger then current number itself then just it won't add
        // any new ways of forming the number. Thus we may just copy the number from row above.
        partitionMatrix[summandIndex][numberIndex] = partitionMatrix[summandIndex - 1][numberIndex];
      } else {
        // The number of combinations would equal to number of combinations of forming the same
        // number but WITHOUT current summand number plus number of combinations of forming the
        // previous number but WITH current summand.
        const combosWithoutSummand = partitionMatrix[summandIndex - 1][numberIndex];
        const combosWithSummand = partitionMatrix[summandIndex][numberIndex - summandIndex];

        partitionMatrix[summandIndex][numberIndex] = combosWithoutSummand + combosWithSummand;
      }
    }
  }

  return partitionMatrix[number][number];
}

二、集合

1.笛卡尔积-多集合结果

export default function cartesianProduct(setA, setB) {
  if (!setA || !setB || !setA.length || !setB.length) {
    return null;
  }

  const product = [];

  for (let indexA = 0; indexA < setA.length; indexA += 1) {
    for (let indexB = 0; indexB < setB.length; indexB += 1) {
      product.push([setA[indexA], setB[indexB]]);
    }
  }

  return product;
}

2.幂集 - 该集合的所有子集

export default function powerSet(originalSet) {
  const subSets = [];

  // We will have 2^n possible combinations (where n is a length of original set).
  // It is because for every element of original set we will decide whether to include
  // it or not (2 options for each set element).
  const numberOfCombinations = 2 ** originalSet.length;

  // Each number in binary representation in a range from 0 to 2^n does exactly what we need:
  // it shoes by its bits (0 or 1) whether to include related element from the set or not.
  // For example, for the set {1, 2, 3} the binary number of 010 would mean that we need to
  // include only "2" to the current set.
  for (let combinationIndex = 0; combinationIndex < numberOfCombinations; combinationIndex += 1) {
    const subSet = [];

    for (let setElementIndex = 0; setElementIndex < originalSet.length; setElementIndex += 1) {
      // Decide whether we need to include current element into the subset or not.
      if (combinationIndex & (1 << setElementIndex)) {
        subSet.push(originalSet[setElementIndex]);
      }
    }

    // Add current subset to the list of all subsets.
    subSets.push(subSet);
  }

  return subSets;
}

3.排列 (有/无重复)

有重复
**
 * @param {*[]} permutationOptions
 * @return {*[]}
 */
export default function permutateWithRepetitions(permutationOptions) {
  // There is no permutations for empty array.
  if (!permutationOptions || permutationOptions.length === 0) {
    return [];
  }

  // There is only one permutation for the 1-element array.
  if (permutationOptions.length === 1) {
    return [permutationOptions];
  }

  // Let's create initial set of permutations.
  let previousPermutations = permutationOptions.map(option => [option]);
  let currentPermutations = [];
  let permutationSize = 1;

  // While the size of each permutation is less then or equal to options length...
  while (permutationSize < permutationOptions.length) {
    // Reset all current permutations.
    currentPermutations = [];

    for (let permIndex = 0; permIndex < previousPermutations.length; permIndex += 1) {
      for (let optionIndex = 0; optionIndex < permutationOptions.length; optionIndex += 1) {
        let currentPermutation = previousPermutations[permIndex];
        currentPermutation = currentPermutation.concat([permutationOptions[optionIndex]]);
        currentPermutations.push(currentPermutation);
      }
    }

    // Make current permutations to be the previous ones.
    previousPermutations = currentPermutations.slice(0);

    // Increase permutation size counter.
    permutationSize += 1;
  }

  return currentPermutations;
}
无重复
/**
 * @param {*[]} permutationOptions
 * @return {*[]}
 */
export default function permutateWithoutRepetitions(permutationOptions) {
  if (permutationOptions.length === 1) {
    return [permutationOptions];
  }

  // Init permutations array.
  const permutations = [];

  // Get all permutations for permutationOptions excluding the first element.
  const smallerPermutations = permutateWithoutRepetitions(permutationOptions.slice(1));

  // Insert first option into every possible position of every smaller permutation.
  const firstOption = permutationOptions[0];

  for (let permIndex = 0; permIndex < smallerPermutations.length; permIndex += 1) {
    const smallerPermutation = smallerPermutations[permIndex];

    // Insert first option into every possible position of smallerPermutation.
    for (let positionIndex = 0; positionIndex <= smallerPermutation.length; positionIndex += 1) {
      const permutationPrefix = smallerPermutation.slice(0, positionIndex);
      const permutationSuffix = smallerPermutation.slice(positionIndex);
      permutations.push(permutationPrefix.concat([firstOption], permutationSuffix));
    }
  }

  return permutations;
}

4. 组合(有/无重复)

有重复

/**
 * @param {*[]} comboOptions
 * @param {number} comboLength
 * @return {*[]}
 */
export default function combineWithRepetitions(comboOptions, comboLength) {
  if (comboLength === 1) {
    return comboOptions.map(comboOption => [comboOption]);
  }

  // Init combinations array.
  const combos = [];

  // Eliminate characters one by one and concatenate them to
  // combinations of smaller lengths.
  comboOptions.forEach((currentOption, optionIndex) => {
    const smallerCombos = combineWithRepetitions(
      comboOptions.slice(optionIndex),
      comboLength - 1,
    );

    smallerCombos.forEach((smallerCombo) => {
      combos.push([currentOption].concat(smallerCombo));
    });
  });

  return combos;
}
无重复

/**
 * @param {*[]} comboOptions
 * @param {number} comboLength
 * @return {*[]}
 */
export default function combineWithoutRepetitions(comboOptions, comboLength) {
  if (comboLength === 1) {
    return comboOptions.map(comboOption => [comboOption]);
  }

  // Init combinations array.
  const combos = [];

  // Eliminate characters one by one and concatenate them to
  // combinations of smaller lengths.
  comboOptions.forEach((currentOption, optionIndex) => {
    const smallerCombos = combineWithoutRepetitions(
      comboOptions.slice(optionIndex + 1),
      comboLength - 1,
    );

    smallerCombos.forEach((smallerCombo) => {
      combos.push([currentOption].concat(smallerCombo));
    });
  });

  return combos;
}

评论已关闭