leetCode刷题

https://github.com/guojingwen/leetcode/tree/master/ts

汉诺塔

KMP算法

举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？

// 暴力破解
const str = "BBC ABCDAB ABCDABCDABDE"
const subStr = 'ABCDABD'
function strIndexOf(str, substr) {
  if(substr.length > str.length) return false
  for(let i = 0; i <= str.length - substr.length; i++) {
    if(str.substr(i, substr.length) === substr) {
      return i
    }
  }
  return -1
}
console.log(strIndexOf(str, subStr))
// KMP算法
function KMPSearch (str1, str2) {
  const kmpNext = createKMPNext(str2)
  for (let i = 0, j = 0; i < str1.length; i++) {
    while (j > 0 && str1[i] !== str2[j]) {
      j = kmpNext[j - 1]
    }
    if (str1[i] === str2[j]) {
      j++
    }
    if (j === str2.length) {
        return i - j + 1
    } 
  }
  return -1
}
function createKMPNext (str2) {
  const arr = [0]
  for (let i = 1, j = 0; i < str2.length; i++) {
      while(j > 0 && str2[i] !== str2[j]){
        j = arr[j - 1]
    }
    if (str2[i] === str2[j]) {
        j++
    }
    arr[i] = j
  }
  return arr
} 
KMPSearch("BBC ABCDAB ABCDABCDABDE", "ABCDABD")

八皇后问题

function run(N) {
  let count = 0;
  const chess = Array.from(
    {length: N},
    () => Array.from(
      {length: N},
      () => 0,
      ),
    );
  putQueenByRow(chess, 0);
  function putQueenByRow(chess, row){
    if(row === chess.length) {
      count++;
      console.log(`the ${count} solution:`, chess);
      return
    }
    const chessTemp = JSON.parse(JSON.stringify(chess));
    for(let i = 0; i<N; i++){
      chessTemp[row].forEach((it, index) => {
        chessTemp[row][index] = 0;
      });
      chessTemp[row][i] = 1;
      if(checkIsSafe(chessTemp, row, i)) {
        putQueenByRow(chessTemp, row+1)
      }
    }
  }
  function checkIsSafe(chess, row, col){
    let step = 1;
    if(row >= 1 && chess[row -1][col] === 1) return false;
    if(col >= 1 && row >= 1 && chess[row -1][col - 1] === 1) return false;
    if(row >= 1 && col < chess.length && chess[row -1][col + 1] === 1) return false;
    return !chess.slice(0, row).some(rowArr => rowArr[col] === 1);
  }
}

骑士周游问题

数据结构和算法的重要性
1）算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算
2) 一般来讲程序会使用了内存计算框架(比如Spark)和缓存技术(比如Redis等)来优化程
序,再深入的思考一下，这些计算框架和缓存技术，它的核心功能是哪个 部分呢?
3) 拿实际工作经历来说,在Unix下开发服务器程序，功能是要支持上千万人同时在
线，在上线前，做内测，一切OK,可上线后，服务器就支撑不住了，公司的CTO对代
码进行优化，再次上线，坚如磐石。你就能感受到程序是有灵魂的，就是算法。
4) 目前程序员面试的门槛越来越高，很多一 线IT公司，都会有数据结构和算法面试题
(负责的告诉你，肯定有的)
5) 如果你不想永远都是代码工人，那就花时间来研究下数据结构和算法

最长回文字符串

// 暴力破解
function longestPalindrome(str) {
  let res = str[0];
  if(str.length < 2) return str[0];
  for(let i=0; i<str.length; i++) {
    for(let j=i; j<=str.length; j++) {
      const subStr = str.substring(i, j);
      if(isHuiWen(subStr) && subStr.length > res.length) {
        res = subStr
      }
    }
  }
  return res;
}
function isHuiWen(subStr){
  return subStr === [...subStr].reverse().join('');
}
// 双指针移动
longestPalindrome2('abacab')
function longestPalindrome2(str){
  let longSubStr = str[0];
  run(str);
  function run(str){
    let i =0, j = str.length - 1;
    for(;;) {
      if (i >= j) {
        if(longSubStr.length < str.length) {
          longSubStr = str;
        }
        return;
      }
      if (str[i] === str[j]) {
        i++;
        j--;
      } else {
        run(str.substring(0, str.length - 1));
        run(str.substring(1, str.length));
        return;
      }
    }
  }
  console.log(longSubStr)
}

动态规划解法
abbacbca 中
dp[i][j] 表示第 i到j(包含j)个字符串是否是回文

从上图可以得出规律

• dp[j][i] 如果 i > j 开始位置不能比结束位置大，
• i === j 填充dp[j][i] = 1
• j - i === 1 的时候 填充 dp[j][i] 依据 str[j] === str[j-1]
• j - i === 2 的时候 填充 dp[j][i] 依据 dp[j-1][i+1] 为 1 且 str[j] === str[j-2] 成立则为1
• 类推 如果 j - i > = 2 设 step = j-i 填充 dp[j][i] 依据 dp[j-1][j-step+1] 为 1 且 str[j] === str[j-step] 成立则为1

• 找出最长回文字符串

  // 动态规划
  // 以 "abbacbca"为例子
  function longestPalindrome2 (str) {
  if(str.length < 2) return str[0]
  // dp[j][i] 表示第 i到j(包含j)个字符串是否是回文
  const dp = Array(str.length).fill(' ').map(item => Array(str.length).fill(' '))
  // i === j   填充dp[j][i] = 1
  for(let i = 0; i < str.length; i++) {
    dp[i][i] = 1
  }
  // j - i === 1 的时候 填充 dp[j][i] 依据 str[j] === str[j-1]
  for(let j = 1; j < str.length; j++) {
    dp[j][j - 1] = (str[j] === str[j-1]) ? 1 : 0
  }
  // console.log(dp.map(items => items.join()).join("\n"))
  // j - i > 1的时候
  // 如果 j-i===2 时 填充 dp[j][i] 依据 dp[j-1][i+1] 为 1 且 str[j] === str[j-2] 成立则为1
  // 如果 j - i > = 2 设 step = j-i 填充 dp[j][i] 依据 dp[j-1][j-step+1] 为 1 且 str[j] === str[j-step] 成立则为1
  let step = 2 //  j-i === 2 回文串长度为3  str.substring(i, j + 1)
  while (step < str.length) {
    for(let j = step; j < str.length; j++) {
      // i = j - step
      // console.log(`${j-step}:${j}：${dp[j-1][j-step+1]}   `, str.substring(j- step, j + 1), `${str[j-step]}:${str[j]}`)
      if(dp[j-1][j-step+1] && (str[j-step] === str[j])) {
        dp[j][j-step] = 1
      } else {
        dp[j][j-step] = 0
      }
    }
    step++
  }
  console.log(dp.map(items => items.join()).join('\n'))
  // 找出最长回文字符串
  for(let step2 = str.length; step2 > 0; step2--) {
    for(let j = step2; j < str.length; j++) {
      const i = j - step2;
      console.log(i,j, str.substring(i, j+1))
      if(dp[j][i]) {
        let result = str.substring(i, j+1)
        // console.log(result)
        return result
      }
    }
  }
  }
  longestPalindrome2('abbacbca')

马拉车算法，后面在学 https://www.bilibili.com/video/BV1rg4y1b71i?p=3

商品规格算法

https://static.warmplace.cn:10443/suanfa/sku.html