@luminous/docs
搜索 K

Appearance

On this page

刷题笔记2 ​

90 子集 II ​

本题目的关键在于对子集中的元素进行去重, 关键点是要在for循环内部去重

js
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    const result = []
    nums.sort((a,b)=>a-b)
    function backtrack(start, cur) {
        result.push([...cur])
        for (let i=start; i<nums.length;i++) {
            // for循环里去重, 在树形结构上表现为对同一层的元素进行去重
            if (i>start && nums[i-1]===nums[i]) continue
            cur.push(nums[i])
            // 每一次递归相当于树形结构更深一层
            backtrack(i+1, cur)
            cur.pop()
        }
    }
    backtrack(0, [])
    return result
};

121 买卖股票最佳时机 ​

js
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let minProfit = prices[0],
        maxProfit = 0
    for (let i=0; i<prices.length; i++) {
        // 价格上涨
        if (prices[i]>minProfit) {
            maxProfit = (maxProfit>prices[i]-minProfit) ? maxProfit : (prices[i]-minProfit)
        }
        // 价格下跌
        else {
            minProfit = prices[i]
        }
    }
    return maxProfit
};

122 买卖股票最佳时机 II ​

原理类似, 甚至更加简单

js
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length===0) return 0
    let profit = 0,
        i = 0,
        curMin = prices[0],
        curMax = prices[0]
    while (i<prices.length-1) {
        while (prices[i]>=prices[i+1]) {
            (i<prices.length-1) && i++
        }
        curMin = prices[i]
        while (prices[i]<=prices[i+1]) {
            (i<prices.length-1) && i++
        }
        curMax = prices[i]
        profit += curMax - curMin
    }
    return profit
};

123 买卖股票最佳时机 III⭐ ​

动态规划 image.png

js
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
//   变量初始化
  if (prices.length === 0) {
    return 0;
  }
  const dp = Array.from(Array(3), () => new Array(prices.length));
// 填上第一行和第一列
  for (let i = 0; i < prices.length; i++) {
    dp[0][i] = 0;
  }
  for (let i = 0; i < 3; i++) {
    dp[i][0] = 0;
  }
// 填上其他位置的数
  for (let i = 1; i < 3; i++) {
    let maxProfit = -prices[0];
    for (let j = 1; j < prices.length; j++) {
      dp[i][j] = Math.max(dp[i][j - 1], prices[j] + maxProfit);
      // 更新maxProfit
      maxProfit = Math.max(maxProfit, dp[i - 1][j] - prices[j]);
    }
  }
// 返回dp表的右下角元素
  return dp[2][prices.length - 1];
};

188 买卖股票的最佳时机 IV⭐ ​

解法同上

js
var maxProfit = function (k, prices) {
  if (prices.length === 0) {
    return 0;
  }
  const dp = Array.from(Array(k+1), () => new Array(prices.length));
  // 填上第一行和第一列
  for (let i = 0; i < prices.length; i++) {
    dp[0][i] = 0;
  }
  for (let i = 0; i < k+1; i++) {
    dp[i][0] = 0;
  }
// 填上其他位置的数
  for (let i = 1; i < k+1; i++) {
    let maxProfit = -prices[0];
    for (let j = 1; j < prices.length; j++) {
      dp[i][j] = Math.max(dp[i][j - 1], prices[j] + maxProfit);
      // 更新maxProfit
      maxProfit = Math.max(maxProfit, dp[i - 1][j] - prices[j]);
    }
  }
// 返回dp表的右下角元素
  return dp[k][prices.length - 1];
};

125 验证回文串 ​

利用正则表达式 移除所有非字母数字字符

js
var isPalindrome = function (s) {
  s = s.toLowerCase().replace(/[\W_]/g, "");

  if (s.length < 2) {
    return true;
  }

  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
};

134 加油站 ​

O(N)的时间复杂度, 很巧妙的题解

js
/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
    let totalGas = 0,
        totalCost = 0
    for (let i=0; i<gas.length; i++) {
        totalGas += gas[i]
        totalCost += cost[i]
    }
    if (totalGas<totalCost) return -1

    let start = 0,
        curGas = 0
    for (let i=0; i<gas.length; i++) {
        curGas += gas[i] - cost[i]
        if (curGas<0) {
            curGas = 0
            start = i+1
        }
    }
    return start
};

152 乘积最大子数组 ​

双DP数组

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    // 两个DP数组
    const maxProductDp = []
    const minProductDp = []
    maxProductDp[0] = nums[0]
    minProductDp[0] = nums[0]
    let max = nums[0] // 返回最大乘积

    for (let i=1; i<nums.length; i++) {
        maxProductDp[i] = Math.max(nums[i], nums[i]*maxProductDp[i-1], nums[i]*minProductDp[i-1])
        minProductDp[i] = Math.min(nums[i], nums[i]*maxProductDp[i-1], nums[i]*minProductDp[i-1])
        max = Math.max(max, maxProductDp[i])
    }
    return max
};

153 寻找旋转排序数组中的最小值 ​

  • 如果数组长度为1, 返回唯一的数
  • 定义两个指针, 第一个left指向数组开头, 第二个right指向数组结尾
  • 检查数组是否被反转, 如果数组没有被反转, 则返回数组里的第一个数
  • 当left小于right时, 取中间位置作为mid进行二分搜索
    • 若mid左边一个数大于mid位置的数, 返回mid位置的数
    • 若mid大于mid右边一个数, 返回mid+1位置的数
    • 若nums[left]<nums[mid], 则left=mid+1(砍掉左半边), 否则right=mid-1(砍掉右半边)
js
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    if (nums.length<2) return nums[0]
    let mid = Math.floor(nums.length/2),
        left = 0,
        right = nums.length-1
    if (nums[left]<nums[right]) return nums[0]
    while (left<=right) {
        mid = Math.floor(left + (right-left) / 2)
        if (nums[mid-1]>nums[mid]) {
            return nums[mid]
        }
        if (nums[mid]>nums[mid+1]) {
            return nums[mid+1]
        }
        if (nums[left]<nums[mid]) {
            left = mid + 1
        }else {
            right = mid - 1
        }
    }
};

187 重复的DNA序列 ​

Map和Set两种方法, Map方法可以获得字符串的更多细节

js
/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function(s) {
    let map = new Map(),
        result = []
    for (let i=0; i<=s.length-10; i++) {
        let str = s.substring(i, i+10)
        // 开始判断
        if (!map.has(str)) {
            map.set(str, 1)
        }else {
            map.set(str, map.get(str)+1)
            // 仅当为2的时候加入结果, 防止重复加入
            if (map.get(str)===2) {
                result.push(str)
            }
        }
    }
    return result
};

198 打家劫舍 ​

动态规划

方程

  • dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1])

基本情况

  • dp[0] = nums[0]
  • dp[1] = Math.max(nums[0], nums[1])
js
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length===1) return nums[0]
    if (nums.length===2) return Math.max(nums[0], nums[1])
    const dp = []
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for (let i=2; i<nums.length; i++) {
        dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1])
    }
    return dp[nums.length-1]
};

200 岛屿数量 ​

下沉扩散 + 深度优先搜索

  • 遍历表格, 若检测到取值为"1"的点, 就将count++, 并将当前点的值设为"0", 也即下沉当前点
  • 使用深度优先搜索, 将当前点周围取值为"1"的点也设置为"0"
  • 继续遍历表格, 最后返回count
js
/**
 * @param {character[][]} grid
 * @return {number}
 */
// bfs 广度优先搜索
// dfs 深度优先搜索

var numIslands = function (grid) {

  let count = 0

  // 下沉函数
  function dfs (row, col) {
    // 边界判断
    if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] === '0') {
      return
    }
    // 下沉当前点
    grid[row][col] = '0'
    // 并使用深度优先搜索进行下沉扩散
    dfs(row - 1, col)
    dfs(row + 1, col)
    dfs(row, col - 1)
    dfs(row, col + 1)
  }
  // 遍历表格
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) {
      if (grid[row][col] === '1') {
        count++
        dfs(row, col)
      }
    }
  }
  return count
}

219 存在重复元素 II ​

利用map, 简单的遍历即可实现, 注意当不满足条件时要更新对应value的值

js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    
    let map = new Map()
    for (let i=0; i<nums.length; i++) {
        if (map.has(nums[i]) && Math.abs(i-map.get(nums[i]))<=k) {
            return true
        }else {
            map.set(nums[i], i)
        }
    }
    return false
};

220 存在重复元素III⭐ ​

桶排思想

js
var containsNearbyAlmostDuplicate = function(nums, k, t) {
    if(k<=0||!nums.length||t<0) return false
    // 方法一、借助桶排思想。构建容量为t的桶。同时桶的数目保持小于k。
    //只要同一个桶中出现两个元素或者相邻桶中的两个元素差的绝对值小于桶容量
    //那么就返回true
    let getBucketKey=(val)=>{
        return Math.floor(val/(t+1))
    }
    let buckets=new Map()
    for(let i=0;i<nums.length;i++){
        let key=getBucketKey(nums[i]) //求出元素i属于哪个桶里面
        if(buckets.has(key)){
            // 一个桶中包含了两个元素，这两个元素的差绝对值一定小于桶的容量t
            return true
        }else if(buckets.has(key-1)||buckets.has(key+1)){
            // 判断是否拥有相邻的桶
            if(buckets.has(key-1)&&nums[i]- buckets.get(key-1)<=t){
                return true
            }
            if(buckets.has(key+1)&&buckets.get(key+1)- nums[i]<=t){
                return true
            }
        }
        buckets.set(key,nums[i])

        // 为此桶的数量小于等于k
        if(i>=k){
            buckets.delete(getBucketKey(nums[i-k]))
        }

    }
    return false

};

238 除自身以外数组的乘积⭐ ​

不懂, 空间太极限了

js
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
     const result = Array(nums.length).fill(1)
     let product = 1
     for (let i=0; i<nums.length; i++) {
         result[i] *= product
         product *= nums[i]
     }
     product = 1
     for (let i=nums.length-1; i>=0; i--) {
         result[i] *= product
         product *= nums[i]
     }
     return result
};

上次更新于: