agl codeing

[zhangzheng-zz]

https://juejin.cn/post/6844904175562653710

[zhangzheng-zz]

dp

// 爬梯子
// 1:1 2:2  3 = 1+2 = 3 结果来看只有两种
var climbStairs = function (n) {
  let dp = []
  dp[0] = 0
  dp[1] = 1
  dp[2] = 2
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}
// console.log(climbStairs(5))

// 打家劫舍
// [1,3,5,6,1,3,100,2]
// [1,3,6,9,9,12,109,109]
var rob = function (arr) {
  let dp = []
  if(arr.length === 0) return 0
  if(arr.length === 1) return arr[0]
  if(arr.length === 2) return arr[1]
  if(arr.length === 3) return Math.max(arr[1], arr[0] + arr[2])
  dp[0] = arr[0]
  dp[1] = Math.max(arr[0], arr[1])
  dp[2] = Math.max(arr[1], arr[0] + arr[2])

  const l = arr.length
  for (let i = 3; i < l; i++) {
    dp[i] = Math.max(dp[i-1], arr[i] + dp[i-2]) // 第 n 房最大的金额
  }
  console.log(dp)
  // 要返回的是整最大金额不是某个房的?
  return dp[l - 1]
  // return Math.max(dp[l-1],dp[l-2])
}
// console.log(rob([1,3,5,6,1,3,100,2]))

// 最大正方形 0 1组成找到最大的由1组成
// 1 0 1 1 1
// 1 1 1 1 1
// 1 1 1 1 1
// 1 0 0 1 1
let arr = [[1, 0, 1, 1, 1],[1, 1, 1, 1, 1],[1, 1, 1, 1, 1],[1, 0, 0, 1, 1]]
// dp[i][j] 保存以这个点为右下的最大边长
const maximalSquare = (matrix) => {
  if(!matrix.length) return 0
  // 保存最大边长
  let maxsqlen = 0
  let rowL = matrix.length, colL = matrix[0].length
  for (let i = 0; i < rowL; i++) {
    for (let j = 0; j < colL; j++) {
     if(matrix[i][j] == 1) {
       if(i !=0 && j!=0) {
        matrix[i][j] = Math.min(matrix[i-1][j],matrix[i][j-1], matrix[i-1][j-1]) + 1 // 相邻三个点的最小的那一个加一
       }
       // 每次遍历完都更新以下结果
       maxsqlen = Math.max(maxsqlen, matrix[i][j])
     }
    }
  }
  return maxsqlen**2
}
// console.log(maximalSquare(arr))

// 零钱兑换
const coins = [1,3,5]
const amount = 30 // 2
// 按金额暴力穷举每个面额所需最少硬币 return dp[amount]
var coinChange = function(coins, amount) {
  let dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0
  // 从 1 元开始穷举
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if(coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1) // 要不就是自己 要不就是自己减去某个硬币加1
      }
    }
  }
  console.log(dp)
  // 有可能不存在
  return dp[amount] === Infinity ? -1 : dp[amount]
}
console.log(coinChange(coins, amount))

// 不同路径
// 以 4 * 4 为例子 造一个二维数组保存路的数量
// 0 1 1 1
// 1
// 1
// 1
var uniquePaths = function (m,n) {
    if(m === 1 && n === 1) return 1
    let data = [], rows = [0]
    for(let i = 0;i < n-1;i++){
      rows.push(1)
    }
    data.push(rows)
    for(let i = 0;i < m-1;i++){
        data.push([1]);
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
           data[i][j] = data[i][j-1] + data[i-1][j]
        }
    }
    // console.log(data)
    return data[m-1][n-1]
}
console.log(uniquePaths(10,4))

[zhangzheng-zz]

贪心

// 剪绳子
var cuttingRope = function(number) {
  if (number === 1) return 1
  if (number === 2) return 1
  if (number === 3) return 2
  if (number === 4) return 4
  // 大于等于 5 的数拆分后相乘肯定大于原来的数字所以尽可能拆分 且可以拆成 2、3组合（1不考虑）
  // ( n - 2 ) * 2 < ( n - 3 ) * 3 所以尽可能分成 3 的组合
  const a = number % 3
  const b = parseInt(number / 3)
  // 1、凑成一个 4 因为 4 拆成 2 * 2 结果也一样
  if (a === 1) {
    return 4 * (3 ** (b - 1))
  }
  // 2、直接乘 2
  if (a === 2) {
    return 2 * (3 ** b)
  }
  // 3、3
  return 3 ** b
}
// console.log(cuttingRope(12))

// 跳跃游戏
// 只考虑能不能到本位置 可以的话就把最远值保存起来最后对比
const c1 = [2,3,1,1,4] , c2 =  [4,2,1,0,4]
var canJump = function (arr) {
  let maxL = 0
  for (let i = 0; i < arr.length; i++) {
    if (maxL < i) {
      return false
    }
    // 有可能前面的直接越过他了
    maxL = Math.max(i + arr[i], maxL)
  }
  return maxL >= (arr.length - 1)
}
console.log(canJump(c1))

[zhangzheng-zz]

二分

// 统计数组出现次数
const data = [1,3,5,5,5,5,5,5,5,6,6,7,7,7,8,10]
const k = 5
function GetNumberOfK (data, k) {
  let left = 0, right = data.length - 1, pos, count = 0
  while(left < right) {
     mid = Math.floor((left + right) >> 1)
     if (data[mid] === k) {
        pos = mid
        break
     }
     if (data[mid] > k) {
        right = mid - 1
     }
     if (data[mid] < k) {
        left = mid + 1
     }
  }
  left = pos, right = pos
  // 找出位置之后前后排查
  if(pos !== undefined) {
    count++ 
    while(left--) {
     if(data[left] === k){
        count++
     }else {
         break
      }
    }
    while(right++) {
     if(data[right] === k){
         count++
      }else {
         break
      }
    }
  }

  return count
}
console.log(GetNumberOfK(data, k))
// 0 ~ n-1 缺失数字
const data = [0,1,2,3,4,5,6,7,8,10]
function missingNumber (data) {
  let left = 0, right = data.length - 1, result
  while(left <= right) {
    mid = Math.floor((left + right) >> 1)
    if (mid === data[mid]) {
       left = mid + 1
    }
    if (data[mid] > mid) {
      right = mid - 1
    }
  }
  return left
}
console.log(missingNumber(data))

// 最长增长子序列 
const data = [8,1,2,3,4,5,9,6,7,8,10]
function lengthOfLis (data) {
   const n = data.length
   if(n === 1) {
     return data
   }
   let tail = [data[0]]
   for (let i = 1; i < n - 1; i++) {
      if (data[i] >= tail[tail.length - 1]) {
          tail.push(data[i])
      } else {
        let left = 0, right = tail.length - 1, mid
        while(left < right) {
          mid = Math.floor((left + right) >> 1)
          if(tail[mid] < data[i]) {
            left = mid + 1
          }
          if(tail[mid] >= data[i]) {
            right = mid
          }
        }
        tail[left] = data[i]
      }
   }
   return tail
}
console.log(lengthOfLis(data))