ES6的JavaScript数据结构实现之分而治之，动态规划，贪心算法和回溯算法

目的：ES6标准下的JS算法的一些实现代码。（作为记录和启发）

内容：分而治之，动态规划，贪心算法，回溯算法及其著名算法问题。（未完成，待继续）

所有源码在我的Github上（如果觉得不错记得给星鼓励我哦）：ES6的JavaScript算法思想实现之分而治之，动态规划，贪心算法和回溯算法（分别在divide and rule、dynamic programming、greedy、backtracking目录下）

一、基础算法

1、分而治之

概念：分而治之算法可以分为三个部分。1、分解原问题为多个子问题（原问题的多个小实例）；2、解决子问题，用返回解决子问题的方式的递归算法。递归算法的基本情形可以用来解决子问题；3、组合这些子问题的解决方式，得到原问题的解。

分而治之的二分搜索算法如下：

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

const DOES_NOT_EXIST = -1;

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}
function partition(array, left, right, compareFn) {
  const pivot = array[Math.floor((right + left) / 2)];
  let i = left;
  let j = right;

  while (i <= j) {
    while (compareFn(array[i], pivot) === Compare.LESS_THAN) {
      i++;
    }
    while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j);
      i++;
      j--;
    }
  }
  return i;
}
function quick(array, left, right, compareFn) {
  let index;
  if (array.length > 1) {
    index = partition(array, left, right, compareFn);
    if (left < index - 1) {
      quick(array, left, index - 1, compareFn);
    }
    if (index < right) {
      quick(array, index, right, compareFn);
    }
  }
  return array;
}
function quickSort(array, compareFn = defaultCompare) {
  return quick(array, 0, array.length - 1, compareFn);
}

function binarySearchRecursive(array, value, low, high, compareFn = defaultCompare) {
  if (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const element = array[mid];
    if (compareFn(element, value) === Compare.BIGGER_THAN) {
      return binarySearchRecursive(array, value, low, mid -1, compareFn);
    }
    if (compareFn(element, value) === Compare.LESS_THAN) {
      return binarySearchRecursive(array, value, mid + 1, high, compareFn);
    }
    return mid;
  }
  return DOES_NOT_EXIST;
}

function binarySearch(array, value, compareFn = defaultCompare){
  const sortedArray = quickSort(array);
  const low = 0;
  const high = sortedArray.length - 1;
  return binarySearchRecursive(array, value, low, high, compareFn);
}


const array = [8,7,6,5,4,3,2,1];
console.log(array);
console.log(binarySearch(array,2));
console.log(binarySearch(array,16));

binarySearch

2、动态规划

概念：动态规划（dynamic programming，DP）是一种将复杂问题分解成更小的子问题来解决的优化技术（分而治之方法是把问题分解成相互独立的子问题，然后组合它们的答案；而动态规划是将问题分解成相互依赖的子问题）。用动态规划解决问题时，要遵循三个重要步骤：1、定义子问题；2、实现要反复执行来解决子问题的部分（考虑递归）；3、识别并求解出基线条件。

动态规划能解决一些著名算法问题：

2.1 背包问题

描述：给出一组项，各自有值和容量，目标是找出总值最大的项的集合。这个问题的限制是，总容量必须小于等于“背包”的容量。

function knapSack(capacity, weights, values, n) {
  const kS = [];
  for (let i = 0; i <= n; i++) {
    kS[i] = [];
  }
  for (let i = 0; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if ( i === 0 || w === 0) {
        kS[i][w] = 0;
      } else if (weights[i - 1] <= w) {
        const a = values[i - 1] + kS[i - 1][w - weights[i - 1]];
        const b = kS[i - 1][w];
        kS[i][w] = a > b ? a : b;
      } else {
        kS[i][w] = kS[i - 1][w];
      }
    }
  }
  findValues(n, capacity, kS);
  return kS[n][capacity];
}

function findValues(n, capacity, kS) {
  let i = n;
  let k = capacity;
   console.log('Items that are part of the solution:');
  while (i > 0 && k > 0) {
    if (kS[i][k] !== kS[i - 1][k]) {
       console.log(
        'item ' + i + ' can be part of solution w,v: ' + weights[i - 1] + ',' + values[i - 1]
        );
      i--;
      k -= kS[i][k];
    } else {
      i--;
    }
  }
}


const values = [3,4,5];
const weights = [2,3,4];
const capacity = 5;
const n = values.length;

console.log(knapSack(capacity, weights, values, n));

knapSack

2.2 最长公共子序列

描述：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变余下元素的顺序而得到）。最长子序列是指，在两个字符串序列中以相同顺序出现，但不要求连续（非字符串子串）的字符串序列。

function printSolution(solution, wordX, m, n) {
  let a = m;
  let b = n;
  let x = solution[a][b];
  let answer = '';
  while (x !== '0') {
    if (solution[a][b] === 'diagonal') {
      answer = wordX[a - 1] + answer;
      a--;
      b--;
    } else if (solution[a][b] === 'left') {
      b--;
    } else if (solution[a][b] === 'top') {
      a--;
    }
    x = solution[a][b];
  }
  return answer;
}
export function lcs(wordX, wordY) {
  const m = wordX.length;
  const n = wordY.length;
  const l = [];
  const solution = [];
  for (let i = 0; i <= m; i++) {
    l[i] = [];
    solution[i] = [];
    for (let j = 0; j <= n; j++) {
      l[i][j] = 0;
      solution[i][j] = '0';
    }
  }
  for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
      if (i === 0 || j === 0) {
        l[i][j] = 0;
      } else if (wordX[i - 1] === wordY[j - 1]) {
        l[i][j] = l[i - 1][j - 1] + 1;
        solution[i][j] = 'diagonal';
      } else {
        const a = l[i - 1][j];
        const b = l[i][j - 1];
        l[i][j] = a > b ? a : b; // max(a,b)
        solution[i][j] = l[i][j] === l[i - 1][j] ? 'top' : 'left';
      }
    }
    // console.log(l[i].join());
    // console.log(solution[i].join());
  }
  return printSolution(solution, wordX, m, n);
}

LCS

2.3 矩阵链相乘

描述：给出一系列矩阵，目标是找到这些矩阵相乘的最高效办法（计算次数尽可能少）。相乘运算不会进行，解决方案是找到这些矩阵各自相乘的顺序（由于矩阵乘法结合律的原因）。

function matrixChainOrder(p) {
  const n = p.length;
  const m = [];
  const s = [];
  for (let i = 1; i <= n; i++) {
    m[i] = [];
    m[i][i] = 0;
  }
  for (let i = 0; i <= n; i++) {
    s[i] = [];
    for (let j = 0; j <= n; j++) {
      s[i][j] = 0;
    }
  }
  for(let l = 2; l < n; l++) {
    for (let i = 1; i <= (n - l) + 1; i++) {
      const j = (i + l) - 1;
      m[i][j] = Number.MAX_SAFE_INTEGER;
      for (let k = i; k <= j - 1; k++) {
        const q = m[i][k] + m[k + 1][j] +((p[i - 1] * p [k]) * p[j]);
        if (q < m[i][j]) {
          m[i][j] = q;
          s[i][j] = k; 
        }
      } 
    }
  }
  printOptimalParenthesis(s, 1, n - 1);
  return m[1][n - 1];
}
function printOptimalParenthesis(s, i, j) {
  if (i === j) {
    console.log('A[' + i + ']');
  } else {
    console.log('(');
    printOptimalParenthesis(s, i, s[i][j]);
    printOptimalParenthesis(s, s[i][j] + 1, j);
    console.log(')');
  }
}
const p = [10, 100, 5, 50, 1];
console.log(matrixChainOrder(p));

matrixChainOrder

2.4 硬币找零

描述：给出面额为d1,…,dn的一定数量的硬币和要找零的钱数，找出有多少种找零的方法。

我们来研究一下最少硬币找零问题。（找出最少硬币个数的方案）

function minCoinChange(coins, amount) {
  const cache = [];

  const makeChange = (value) => {
    if(!value) {
      return [];
    }
    if (cache[value]) {
      return cache[value];
    }
    let min = [];
    let newMin;
    let newAmount;
    for (let i = 0; i < coins.length; i++) {
      const coin = coins[i];
      newAmount = value - coin;
     // console.log(coin);
      if (newAmount >= 0) {
        newMin  = makeChange(newAmount);
      }
      if (
        newAmount >= 0 
        && (newMin.length < min.length - 1 ||!min.length)
        && (newMin.length || !newAmount)
        ) {
        min = [coin].concat(newMin);
      console.log('new Min ' + min + ' for ' + amount);
      }
    }
    return (cache[value] = min);
  };
  return makeChange(amount);
}

console.log(minCoinChange([1, 3, 4], 6));

minCoinChange

2.5 图的全源最短路径

描述：对所有顶点对（u，v），找出从顶点u到顶点v的最短路径。

用Floyd-Warshall算法：

const floydWarshall = graph => {
  const dist = [];
  const {length} = graph;
  for (let i = 0; i < length; i++) {
    dist[i] = [];
    for (let j = 0; j < length; j++) {
      if (i === j) {
        dist[i][j] = 0;
      } else if (!isFinite(graph[i][j])) {
        dist[i][j] = Infinity;
      } else {
        dist[i][j] = graph[i][j];
      }
    }
  }
  for (let k = 0; k < length; k++) {
    for(let i = 0; i < length; i++) {
      for (let j = 0; j < length; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
};

const INF = Infinity;
const graph = [
  [INF, 2, 4, INF, INF, INF],
  [INF, INF, 2, 4, 2, INF],
  [INF, INF, INF, INF, 3, INF],
  [INF, INF, INF, INF, INF, 2],
  [INF, INF, INF, 3, INF, 2],
  [INF, INF, INF, INF, INF, INF]
];

dist = floydWarshall(graph);
let s = '';
for (let i = 0; i < dist.length; i++) {
  s = '';
  for (let j = 0; j < dist.length; j++) {
    if (dist[i][j] === INF) {
      s += 'INF ';
    } else {
      s += dist[i][j] + ' ';
    }
   
  }
  console.log(s);
}

floydWarshall

FloydWarshall

3、贪心算法

概念：贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），从而达到全局的最优（全局最优解）。它不像动态规划算法那那样计算更大的格局。

3.1最少硬币找零问题

function minCoinChangeGreedy (coins, amount) {
  const change = [];
  let total = 0;
  for (let i = coins.length; i >= 0; i--) {
    const coin = coins[i];
    while (total + coin <= amount) {
      change.push(coin);
      total += coin;
    }
  }
  return change;
}




console.log(minCoinChangeGreedy([1, 5, 10], 15)); // [5, 10]
console.log(minCoinChangeGreedy([1, 3, 4], 6)); //not the best

minCoinChangeGreedy

3.2 分数背包问题

概念：在分数背包问题中，可以装入分数的物品。

function knapSackGreedy(capacity, weights, values) {
  const n = values.length;
  let load = 0;
  let val = 0;
  for (let i = 0; i < n && load < capacity; i++) {
    if (weights[i] <= capacity - load) {
      val += values[i];
      load += weights[i];
    } else {
      const r = (capacity - load) / weights[i];
      val += r*values[i];
      load += weights[i]; 
    }
  }
  return val;
}



const values = [3,4,5];
const weights = [2,3,4];
const capacity = 5;

console.log(knapSackGreedy(capacity, weights, values));

knapSackGreedy

4、回溯算法

概念：回溯是一种渐进式寻找并构建问题解决方式的策略。从一个可能的动作开始并试着用这个动作解决问题。如果不能解决，就回溯并选择另一个动作直到问题解决为止。根据这种行为，回溯算法会尝试所有可能的动作（如果更快找到了解决办法就尝试较少的次数）来解决问题。可用回溯解决的著名问题有：骑士巡逻问题，N皇后问题，迷宫老鼠问题，数独解问题。

4.1 迷宫老鼠问题

function ratInAMaze(maze) {
  const solution = [];
  for (let i = 0; i < maze.length; i++) {
    solution[i] = [];
    for (let j = 0; j < maze[i].length; j++) {
      solution[i][j] = 0;
    }
  }
  if (findPath(maze, 0, 0, solution) === true) {
    return solution;
  }
  return 'NO PATH FOUND';
}

function findPath(maze, x, y, solution) {
  const n = maze.length;
  if (x === n - 1 && y === n -1) {
    solution[x][y] = 1;
    return true;
  }
  if (isSafe(maze, x, y) === true) {
    solution[x][y] = 1;
    if (findPath(maze, x + 1, y, solution)) {
      return true;
    }
    if (findPath(maze, x, y + 1, solution)) {
      return true;
    }
    solution[x][y] = 0;
    return false;    
  }
  return false;
}

function isSafe(maze, x, y) {
  const n = maze.length;
  if (x >= 0 && y >= 0 && x < n && y < n && maze[x][y] !== 0) {
    return true;
  }
  return false;
}

const maze = [
  [1, 0, 0, 0],
  [1, 1, 1, 1],
  [0, 0, 1, 0],
  [0, 1, 1, 1]
];

console.log(ratInAMaze(maze));

ratInAMaze

4.2 数独解问题

function sudokuSolver(matrix) {
  if (solveSudoku(matrix) ===  true) {
    return matrix;
  }
  return 'NO SOLUTION';
}
const UNASSIGNED = 0;

function solveSudoku(matrix) {
  let row = 0;
  let col = 0;
  let checkBlankSpaces = false;
  for (row = 0; row < matrix.length; row++) {
    for (col = 0; col < matrix[row].length; col++) {
      if (matrix[row][col] === UNASSIGNED) {
        checkBlankSpaces = true;
        break;
      }
    }
    if (checkBlankSpaces === true) {
      break;
    }
  }
  if (checkBlankSpaces === false) {
    return true;
  }
  for (let num = 1; num <= 9; num++) {
    if (isSafe(matrix, row, col, num)) {
      matrix[row][col] = num;
      if (solveSudoku(matrix)) {
        return true;
      }
      matrix[row][col] = UNASSIGNED;
    }
  }
  return false;
}

function isSafe(matrix, row, col, num) {
  return (
    !usedInRow(matrix, row, num) 
    && !usedInCol(matrix, col, num) 
    && !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
  );
}
function usedInRow(matrix, row, num) {
  for (let col = 0; col < matrix.length; col++) {
    if (matrix[row][col] === num) {
      return true;
    }
  }
  return false;
}

function usedInCol(matrix, col, num) {
  for (let row = 0; row < matrix.length; row++) {
    if (matrix[row][col] === num) {
      return true;
    }
  }
  return false;
}

function usedInBox(matrix, boxStartRow, boxStartCol, num) {
  for (let row = 0; row < 3; row++) {
    for (let col = 0; col < 3; col++) {
      if (matrix[row + boxStartRow][col + boxStartCol] === num) {
        return true;
      }
    }
  }
  return false;
}
const sudokuGrid = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]
];

console.log(sudokuSolver(sudokuGrid));

sudokuSolver