题集

最小路径和

思路

核心思路：

DP 方程

当前项最小路径和 = 当前项值 + 上项或左项中的最小值 grid[i][j] += Math.min( grid[i - 1][j], grid[i][j - 1] )
边界处理

grid 的第一行与第一列分别没有上项与左项故单独处理计算起项最小路径和计算第一行

for (let j = 1; j < col; j++) grid[0][j] += grid[0][j - 1]

计算第一列

for (let i = 1; i < row; i++) grid[i][0] += grid[i - 1][0]

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  let row = grid.length,
    col = grid[0].length

  // calc boundary
  for (let i = 1; i < row; i++)
    // calc first col
    grid[i][0] += grid[i - 1][0]

  for (let j = 1; j < col; j++)
    // calc first row
    grid[0][j] += grid[0][j - 1]

  for (let i = 1; i < row; i++) for (let j = 1; j < col; j++) grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])

  return grid[row - 1][col - 1]
}

大数相加

let a = '9007199254740991'
let b = '1234567899999999999'

function add(a, b) {
  //取两个数字的最大长度
  let maxLength = Math.max(a.length, b.length)
  //用0去补齐长度
  a = a.padStart(maxLength, 0) //"0009007199254740991"
  b = b.padStart(maxLength, 0) //"1234567899999999999"
  //定义加法过程中需要用到的变量
  let t = 0
  let f = 0 //"进位"
  let sum = ''
  for (let i = maxLength - 1; i >= 0; i--) {
    t = parseInt(a[i]) + parseInt(b[i]) + f
    f = Math.floor(t / 10)
    sum = (t % 10) + sum
  }
  if (f == 1) {
    sum = '1' + sum
  }
  return sum
}

买股票最佳时机

只能交易一次的

暴力解决

var maxProfit = function (prices) {
  var maxprofit = 0
  for (var i = 0; i < prices.length; i++) {
    for (var j = i + 1; j < prices.length; j++) {
      var profit = prices[j] - prices[i]
      if (profit > maxprofit) maxprofit = profit
    }
  }
  return maxprofit
}

只关心 i 前面元素里最小的 minprice 是多少，然后迭代当前 price[i] - minprice 得到最大值

let maxProfit = function (prices) {
  let max = 0,
    minprice = prices[0]
  for (let i = 1; i < prices.length; i++) {
    minprice = Math.min(prices[i], minprice)
    max = Math.max(max, prices[i] - minprice)
  }
  return max
}

可交易多次的

var maxProfit = function (prices) {
  let money = 0
  let buy = prices[0]
  for (let price of prices) {
    if (price > buy) {
      money += price - buy
    }
    buy = price
  }
  return money
}

数组题

[1,1,3,3,2,2,4] 找出重复的数字

https://johnzhu12.github.io/easy/Array/只出现一次的数字.html

[0,0,0,1,1,1,2,2,3,3,4] 找出不重复的数字有多少个，并把数组前 N 项改成不重复的数字

var findSingle = function (arr) {
  var len = arr.length,
    sum = 0
  if (!arr || len == 0) return 0
  var sum = 0
  var numMap = {}
  for (var i = 0; i < len; i++) {
    //有重复
    if (numMap[arr[i]] !== undefined) {
      numMap[arr[i]]++
    } else {
      //没有重复
      numMap[arr[i]] = 1
    }
  }
  for (var key in numMap) {
    if (numMap[key] == 1) {
      arr[sum] = key
      sum++
    }
  }
  //把数组前N个改成不重复的数字
  console.log(arr)
  return sum
}
var src = [0, 0, 0, 1, 1, 1, 2, 5, 2, 3, 3, 4]
var res = findSignle(src)
console.log(res)

数组分成和等值的两个数组

数组可否分成和相等的三个数组

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canThreePartsEqualSum = function (arr) {
  let sum = arr.reduce((a, b) => a + b)
  let num = 3
  let temp = 0
  for (let a of arr) {
    temp += a
    if (temp === sum / 3) num--, (temp = 0)
  }
  return num <= 0
}

那两个就是把 num 改成 2

八皇后问题

class Queen {
  constructor(num) {
    this.num = num
    this.arr = []
    this.result = []
    this.initList()
    this.buildList(this.arr, 0)
  }

  initList() {
    let num = this.num
    for (let i = 0; i < num; i++) {
      this.arr[i] = []
      for (let j = 0; j < num; j++) {
        this.arr[i][j] = 0
      }
    }
    console.log(this.arr)
  }

  buildList(list, row) {
    // 递归中止条件,找到一个解缓存起来
    if (row === list.length) {
      this.result.push(JSON.parse(JSON.stringify(list)))
      return
    }
    for (let col = 0, len = list.length; col < len; col++) {
      if (this.isSafe(list, row, col)) {
        list[row][col] = 1
        this.buildList(list, row + 1)
        // 走到这里，说明该次递归已经结束，不管找没找到，都需要重置
        list[row][col] = 0
      }
    }
  }

  isSafe(list, row, col) {
    const len = list.length
    // 同一列
    for (let i = 0; i < len; i++) {
      if (list[i][col] === 1) return false
    }
    // 斜右上方
    for (let i = row - 1, j = col + 1; i >= 0 && j < len; i--, j++) {
      if (list[i][j] === 1) return false
    }
    // 斜左上方
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (list[i][j] === 1) return false
    }
    return true
  }
}
const queen = new Queen(8)
console.log(queen.result)

-优化

其实解法跟之前一样，上面用了二维矩阵来记录位置，因为已经确定同一行不可能存在 2 个皇后实际上只用一维数组就表示：list[row] = col;减少空间消耗

isSafe 判断和之前不同

isSafe(row) {
  for (let i = 0; i < row; i++) {
    // 判断列
    if (this.arr[i] === this.arr[row]) return false;
    // 判断对角线
    if (Math.abs(this.arr[row] - this.arr[i]) === row - i) return false;
  }
  return true;
}

完整代码

class Queen {
  constructor(num) {
    this.num = num
    this.arr = []
    this.result = []
    this.initList()
    this.buildList(0)
  }

  initList() {
    let num = this.num
    for (let i = 0; i < num; i++) {
      this.arr[i] = 0
    }
  }

  buildList(row) {
    // 递归中止条件,找到一个解缓存起来
    if (row === this.num) {
      this.result.push(JSON.parse(JSON.stringify(this.arr)))
      return
    }
    for (let col = 0; col < this.num; col++) {
      this.arr[row] = col
      if (this.isSafe(row)) {
        this.buildList(row + 1)
      }
    }
  }

  isSafe(row) {
    for (let i = 0; i < row; i++) {
      // 判断列
      if (this.arr[i] === this.arr[row]) return false
      // 判断对角线
      if (Math.abs(this.arr[row] - this.arr[i]) === row - i) return false
    }
    return true
  }
}

const queen = new Queen(8)
console.log(queen.result)

二分法递归

var search = function (arr, low, high, key) {
  if (high < low) {
    return '无值'
  }
  var index = Math.floor((low + high) / 2)
  //console.log(typeof index);
  if (key == arr[index]) {
    return index
  } else if (key > arr[index]) {
    return search(arr, index + 1, high, key)
  } else if (key < arr[index]) {
    return search(arr, low, index - 1, key)
  }
}

生成随机数组

function genArray(n) {
  let a = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] //生成的随机数的集合
  let res = []
  for (let i = 0; i < n; i++) {
    let index = parseInt(Math.random() * a.length) //生成一个的随机索引，索引值的范围随数组a的长度而变化
    res.push(a[index])
    a.splice(index, 1) //已选用的数，从数组a中移除， 实现去重复
  }
  return res
}

改下：

function genArray(n) {
  let arr = []
  for (var i = 1; i <= n; i++) {
    arr.push(i)
  }
  let res = []
  for (let i = 0; i < n; i++) {
    let index = parseInt(Math.random() * arr.length) //生成一个的随机索引，索引值的范围随数组a的长度而变化
    res.push(arr[index])
    arr.splice(index, 1) //已选用的数，从数组a中移除， 实现去重复
  }
  return res
}

输入 n 和 m，找出 1-n 中所有相加等于 m 的可能

function findSumEq(n, m) {
  if (n == 0) return
  let arr = []
  for (var i = 1; i <= n; i++) {
    arr.push(i)
  }
  // ??
}

var res = findSumEq(4, 5)

射击气球

https://leetcode-cn.com/problems/burst-balloons/solution/dong-tai-gui-hua-js312-chuo-qi-qiu-by-fe-lucifer/

回溯法模板

var maxCoins = function (nums) {
  let n = nums.length
  // 添加两侧的虚拟气球
  let points = [1, ...nums, 1]
  let dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0))
  // 最后一行开始遍历,从下往上
  for (let i = n; i >= 0; i--) {
    // 从左往右
    for (let j = i + 1; j < n + 2; j++) {
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.max(dp[i][j], points[j] * points[k] * points[i] + dp[i][k] + dp[k][j])
      }
    }
  }
  return dp[0][n + 1]
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

题集.md

题集.md

题集

最小路径和

思路

大数相加

买股票最佳时机

只能交易一次的

可交易多次的

数组题

数组分成和等值的两个数组

八皇后问题

二分法递归

生成随机数组

输入 n 和 m，找出 1-n 中所有相加等于 m 的可能

射击气球

暴力递归

Files

题集.md

Latest commit

History

题集.md

File metadata and controls

题集

最小路径和

思路

大数相加

买股票最佳时机

只能交易一次的

可交易多次的

数组题

数组分成和等值的两个数组

八皇后问题

二分法递归

生成随机数组

输入 n 和 m，找出 1-n 中所有相加等于 m 的可能

射击气球

暴力递归