【Leetcode 做题学算法周刊】第七期

首发于微信公众号《前端成长记》,写于 2020.01.15

背景

本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:

  • 题目分析设想
  • 编写代码验证
  • 查阅他人解法
  • 思考总结

目录

  • 121.买卖股票的最佳时机
  • 122.买卖股票的最佳时机Ⅱ
  • 125.验证回文串
  • 136.只出现一次的数字
  • 141.环形链表

Easy

121.买卖股票的最佳时机

题目地址

题目描述

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题目分析设想

这道题,我的第一反应有点像求最大子序和,只不过这里不是求连续,是求单个,转换为增益的思想来处理。当然也可以使用两次遍历的笨办法来求解。我们分别来验证一下。

编写代码验证

Ⅰ.两次遍历

代码:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length < 2) return 0
    // 因为是利润,所以不考虑负数
    let profit = 0
    for(let i = 0; i < prices.length; i++) {
        for(let j = i + 1; j < prices.length; j++) {
            profit = Math.max(prices[j] - prices[i], profit)
        }
    }
    return profit
};

结果:

  • 200/200 cases passed (384 ms)
  • Your runtime beats 25.89 % of javascript submissions
  • Your memory usage beats 19.85 % of javascript submissions (35.9 MB)
  • 时间复杂度 O(n^2)

Ⅱ.增益思想

代码:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length < 2) return 0
    // 因为是利润,所以不考虑负数
    let profit = 0
    let last = 0
    for(let i = 0; i < prices.length - 1; i++) {
        // 这里其实可以转换为每两项价格相减后,再求最大子序和
        // prices[i + 1] - prices[i] 就是增益,和0比较是因为求利润,不是求连续和
        last = Math.max(0, last + prices[i + 1] - prices[i])
        profit = Math.max(profit, last)
    }
    return profit
};

结果:

  • 200/200 cases passed (64 ms)
  • Your runtime beats 94.53 % of javascript submissions
  • Your memory usage beats 19.85 % of javascript submissions (35.9 MB)
  • 时间复杂度 O(n)

查阅他人解法

这里看到两种不同的思考,一种是理解为波峰和波谷,找到波谷后的下一个波峰,判断每个波峰与波谷差值的大小。另外一种是基于状态机的动态规划,也就是说把可能性都前置运算后,再进行比较。

Ⅰ.波峰波谷

代码:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length < 2) return 0
    // 波谷
    let min = Infinity
    // 因为是利润,所以不考虑负数
    let profit = 0
    for(let i = 0; i < prices.length; i++) {
        if (prices[i] < min) {
            min = prices[i]
        } else if (prices[i] - min > profit) {
            // 这里是当前这个波峰和波谷的差值与历史的进行比较
            profit = prices[i] - min
        }
    }
    return profit
};

结果:

  • 200/200 cases passed (68 ms)
  • Your runtime beats 86.75 % of javascript submissions
  • Your memory usage beats 21.34 % of javascript submissions (35.8 MB)
  • 时间复杂度 O(n)

Ⅱ.动态规划

代码:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length < 2) return 0
    // 动态初始数组
    let dp = new Array(prices.length).fill([])
    // 0:用户手上不持股所能获得的最大利润,特指卖出股票以后的不持股,非指没有进行过任何交易的不持股
    // 1:用户手上持股所能获得的最大利润
    // 状态 dp[i][0] 表示:在索引为 i 的这一天,用户手上不持股所能获得的最大利润
    // 状态 dp[i][1] 表示:在索引为 i 的这一天,用户手上持股所能获得的最大利润
    // -prices[i] 就表示,在索引为 i 的这一天,执行买入操作得到的收益
    dp[0][0] = 0
    dp[0][1] = -prices[0]

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

结果:

  • 200/200 cases passed (72 ms)
  • Your runtime beats 75.01 % of javascript submissions
  • Your memory usage beats 12.43 % of javascript submissions (36.7 MB)
  • 时间复杂度 O(n)

这个思路还有一系列的优化过程,可以点击这里查看

思考总结

很多问题都可以转换成动态规划的思想来解决,但是我这里还是更推荐使用增益思想,也可以理解为差分数组。但是如果题目允许多次买入卖出,我会更推荐使用动态规划来解决问题。

122.买卖股票的最佳时机Ⅱ

题目地址

题目描述

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

javascript 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。javascript

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题目分析设想

上面刚刚做了算最大收益的,这题明显是算累计收益的,所以可以按以下几个方向:

  • 一次遍历,直接遍历,不断比较前后两天价格,如果后一天收益高,则差值加到利润,可以理解为贪心算法。
  • 波峰波谷,找到所有波峰波谷,差值相加即可
  • 动态规划

编写代码验证

Ⅰ.一次遍历

代码:

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

结果:

  • 201/201 cases passed (68 ms)
  • Your runtime beats 77.02 % of javascript submissions
  • Your memory usage beats 13.55 % of javascript submissions (35.7 MB)
  • 时间复杂度 O(n)

Ⅱ.波峰波谷

代码:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (!prices.length) return 0
    let profit = 0
    // 波峰波谷
    let min = max = prices[0]
    let i = 0
    while (i < prices.length - 1) {
        while(prices[i] >= prices[i + 1]) {
            i++
        }
        min = prices[i]
        while(prices[i] <= prices[i + 1]) {
            i++
        }
        max = prices[i]
        profit += max - min
    }
    return profit
};

结果:

  • 201/201 cases passed (68 ms)
  • Your runtime beats 77.02 % of javascript submissions
  • Your memory usage beats 14.4 % of javascript submissions (35.7 MB)
  • 时间复杂度 O(n)

Ⅲ.动态规划

代码:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length < 2) return 0
    // 动态初始数组
    let dp = new Array(prices.length).fill([])
    // 0:用户手上不持股所能获得的最大利润,特指卖出股票以后的不持股,非指没有进行过任何交易的不持股
    // 1:用户手上持股所能获得的最大利润
    // 状态 dp[i][0] 表示:在索引为 i 的这一天,用户手上不持股所能获得的最大利润
    // 状态 dp[i][1] 表示:在索引为 i 的这一天,用户手上持股所能获得的最大利润
    // -prices[i] 就表示,在索引为 i 的这一天,执行买入操作得到的收益
    dp[0][0] = 0
    dp[0][1] = -prices[0]

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

结果:

  • 201/201 cases passed (76 ms)
  • Your runtime beats 37.68 % of javascript submissions
  • Your memory usage beats 5.13 % of javascript submissions (36.7 MB)
  • 时间复杂度 O(n)

查阅他人解法

这里看到了动态规划的优化版,主要是降低空间复杂度。其他的思路都区别不大。

Ⅰ.动态规划优化版

代码:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length < 2) return 0
    // cash 表示持有现金
    // hold 表示持有股票
    let cash = new Array(prices.length).fill(null)
    let hold = new Array(prices.length).fill(null)

    cash[0] = 0
    hold[0] = -prices[0]

    for(let i = 1; i < prices.length; i++) {
        cash[i] = Math.max(cash[i - 1], hold[i - 1] + prices[i])
        hold[i] = Math.max(hold[i - 1], cash[i - 1] - prices[i])
    }
    return cash[prices.length - 1]
};

结果:

  • 201/201 cases passed (68 ms)
  • Your runtime beats 77.02 % of javascript submissions
  • Your memory usage beats 9.7 % of javascript submissions (36 MB)
  • 时间复杂度 O(n)

还可以进一步进行状态压缩

代码:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length < 2) return 0
    // cash 表示持有现金
    // hold 表示持有股票
    // 加了两个变量来存储上一次的值
    let cash = tempCash = 0
    let hold = tempHold = -prices[0]

    for(let i = 1; i < prices.length; i++) {
        cash = Math.max(tempCash, tempHold + prices[i])
        hold = Math.max(tempHold, tempCash - prices[i])

        tempCash = cash
        tempHold = hold
    }
    return tempCash
};

结果:

  • 201/201 cases passed (72 ms)
  • Your runtime beats 58.45 % of javascript submissions
  • Your memory usage beats 10.55 % of javascript submissions (35.8 MB)
  • 时间复杂度 O(n)

思考总结

就这道题而言,我会推荐使用一次遍历的方式,也就是贪心算法,理解起来会十分清晰。当然,动态规划的解决范围更广,基本上可以解决这类型的所有题目。增益也是一个比较常见的手段。总体而言,这两道股票题还比较简单。

125.验证回文串

题目地址

题目描述

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例:

输入: "A man, a plan, a canal: Panama"
输出: true

输入: "race a car"
输出: false

题目分析设想

这道题我有两个方向,一是改变原输入串,二是不改变原输入串。

  • 改变原输入串,可以去掉非字母和数字的字符后,反转判断或者双指针判断或者单指针
  • 不改变原输入串,直接双指针判断

主要作答方法就是反转判断,双指针法以及二分法。

编写代码验证

Ⅰ.反转判断

代码:

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    // 正则去除不满足条件的字符
    let str = s.toLowerCase().replace(/[^0-9a-z]/g, '')
    return str === str.split('').reverse().join('')
};

结果:

  • 476/476 cases passed (72 ms)
  • Your runtime beats 95.33 % of javascript submissions
  • Your memory usage beats 47.7 % of javascript submissions (38.1 MB)
  • 时间复杂度: O(1)

Ⅱ.双指针法(预处理字符)

代码:

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    // 正则去除不满足条件的字符
    let str = s.toLowerCase().replace(/[^0-9a-z]/g, '')
    let len = str.length
    let l = 0
    let r = len - 1
    while(l < r) {
        if (str.charAt(l) !== str.charAt(r)) {
            return false
        }
        l++
        r--
    }
    return true
};

结果:

  • 476/476 cases passed (76 ms)
  • Your runtime beats 89.25 % of javascript submissions
  • Your memory usage beats 70.96 % of javascript submissions (37.4 MB)
  • 时间复杂度: O(n)

Ⅲ.单指针法(预处理字符)

代码:

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    // 正则去除不满足条件的字符
    let str = s.toLowerCase().replace(/[^0-9a-z]/g, '')
    let len = str.length
    // 最多需要判断的次数
    let max = len >>> 1
    let i = 0
    while(i < max) {
        if (len % 2) { // 奇数
            if (str.charAt(max - i - 1) !== str.charAt(max + i + 1)) {
                return false
            }
        } else { // 偶数
            if (str.charAt(max - i - 1) !== str.charAt(max + i)) {
                return false
            }
        }
        i++
    }
    return true
};

结果:

  • 476/476 cases passed (72 ms)
  • Your runtime beats 95.33 % of javascript submissions
  • Your memory usage beats 56.02 % of javascript submissions (38 MB)
  • 时间复杂度: O(n)

Ⅳ.双指针法

代码:

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let len = s.length
    let l = 0
    let r = len - 1
    while (l < r) {
        if (!/[0-9a-zA-Z]/.test(s.charAt(l))) {
            l++
        } else if (!/[0-9a-zA-Z]/.test(s.charAt(r))) {
            r--
        } else {
            if(s.charAt(l).toLowerCase() !== s.charAt(r).toLowerCase()) {
                return false
            }
            l++
            r--
        }

    }
    return true
};

结果:

  • 476/476 cases passed (76 ms)
  • Your runtime beats 89.25 % of javascript submissions
  • Your memory usage beats 13.06 % of javascript submissions (42 MB)
  • 时间复杂度: O(n)

查阅他人解法

这里看到一种利用栈的思路,先进后出,推一半入栈然后进行比较。

Ⅰ.利用栈

代码:

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    // 正则去除不满足条件的字符
    let str = s.toLowerCase().replace(/[^0-9a-z]/g, '')
    let mid = str.length >>> 1
    let stack = str.substr(0, mid).split('')
    // 起始位置如果字符个数为奇数则跳过中间位
    for(let i = str.length % 2 ? mid + 1 : mid; i < str.length; i++) {
        const last = stack.pop()
        if (last !== str.charAt(i)) {
            return false
        }
    }
    return true
};

结果:

  • 476/476 cases passed (84 ms)
  • Your runtime beats 65.67 % of javascript submissions
  • Your memory usage beats 71.81 % of javascript submissions (37.4 MB)
  • 时间复杂度: O(n)

思考总结

总体而言,判断回文字符或者相关的题目,我更推荐采用双指针法,思路非常清晰。这里头尾递归比较也可以作答,就不在这里列举了。

136.只出现一次的数字

题目地址

题目描述

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

输入: [2,2,1]
输出: 1

输入: [4,1,2,1,2]
输出: 4

题目分析设想

这题说明了线性时间复杂度,所以最多一次遍历。很容易想到用 Hash 表或者其他方式对各数字出现次数做个统计来求解,但是需要考虑如何不适用额外空间。这里很明显就指向了离散数学中的异或运算。

  • Hash 法,需要额外 O(n) 的空间
  • 异或运算

编写代码验证

Ⅰ.Hash 法

代码:

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let hash = {}
    for(let i = 0; i < nums.length; i++) {
        if (hash[nums[i]]) {
            hash[nums[i]] = false
        } else if (hash[nums[i]] === undefined) {
            hash[nums[i]] = true
        }
    }
    for(let i in hash) {
        if(hash[i]) {
            return parseInt(i)
        }
    }
};

结果:

  • 16/16 cases passed (72 ms)
  • Your runtime beats 68.39 % of javascript submissions
  • Your memory usage beats 5.49 % of javascript submissions (38.6 MB)
  • 时间复杂度: O(n)

Ⅱ.异或运算

简单列一下几条运算规则,利用这规则,发现很容易作答这道题。

  • 交换律: a^b^c = a^c^b
  • 任何数和 0 异或为本身:a^0 = a
  • 相同的数异或为 0:a^a = 0

代码:

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let n = 0
    for(let i = 0; i < nums.length; i++) {
        n ^= nums[i]
    }
    return n
};

结果:

  • 16/16 cases passed (60 ms)
  • Your runtime beats 95.77 % of javascript submissions
  • Your memory usage beats 74.07 % of javascript submissions (35.3 MB)
  • 时间复杂度: O(n)

查阅他人解法

没有发现其他不同方向的解法。

思考总结

这里的话第一想法大多都是借助哈希表来实现,但是由于有补充说明,所以更推荐使用异或算法。纯粹是数学公式的应用场景之一,没有什么太多好总结的地方。

141.环形链表

题目地址

题目描述

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

题目分析设想

这道题的本质其实就是对象的比较,而对应的相等应当是引用同样的内存,可以想象成数组中找到同样的元素。所以第一个想法就是哈希表,当然也可以使用快慢指针来做处理。由于哈希表需要额外的内存,所以可以做优化,比如直接改变原对象,做特殊标识或者其他方式。

  • 哈希表,直接利用哈希表存储,也可以使用 Map/Set 等等,直接判断对象相等即可
  • 特殊标识,哈希表需要额外空间,可以直接在原对象上打标识,或者置为空等等特殊标识均可
  • 双指针法,一快一慢,如果是环,那必然会存在相等的时候,如果不是环,那快的先走完

编写代码验证

Ⅰ.哈希表

代码:

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let hashArr = []
    // val 可能为 0 ,所以不能直接 !head
    while (head !== null) {
        if (hashArr.includes(head)) {
            return true
        } else {
            hashArr.push(head)
            head = head.next
        }
    }
    return false
};

结果:

  • 17/17 cases passed (116 ms)
  • Your runtime beats 12.03 % of javascript submissions
  • Your memory usage beats 5.05 % of javascript submissions (38.5 MB)
  • 时间复杂度: O(n)

Ⅱ.特殊标识法

代码:

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    while (head && head.next) {
        if (head.FLAG) {
            return true
        } else {
            head.FLAG = true
            head = head.next
        }
    }
    return false
};

结果:

  • 17/17 cases passed (76 ms)
  • Your runtime beats 78.6 % of javascript submissions
  • Your memory usage beats 16.32 % of javascript submissions (37.5 MB)
  • 时间复杂度: O(n)

Ⅲ.双指针法

代码:

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (head && head.next) {
        let slow = head
        let fast = head.next
        while(slow !== fast) {
            if (fast && fast.next) {
                // 快指针需要比慢指针移动速度快,才能追上,所以是 .next.next
                fast = fast.next.next
                slow = slow.next
            } else {
                // 快指针走到头了,所以必然不是环
                return false
            }
        }
        return true
    } else {
        return false
    }
};

结果:

  • 17/17 cases passed (76 ms)
  • Your runtime beats 78.6 % of javascript submissions
  • Your memory usage beats 56.97 % of javascript submissions (36.6 MB)
  • 时间复杂度: O(n)

查阅他人解法

这里发现一个有意思的思路,通过链路导致。如果是环,那么倒置后的尾节点等于倒置前的头节点。如果不是环,那么就是正常的倒置不相等。

Ⅰ.倒置法

代码:

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (head === null || head.next === null) return false
    if (head === head.next) return true
    let p = head.next
    let q = p.next
    let x = head
    head.next = null
    // 相当于每遍历一个链表,就把后面的指向前面一项,这样当循环的时候,会反方向走出环形
    while(q !== null) {
        p.next = x
        x = p
        p = q
        q = q.next
    }
    return p === head
};

结果:

  • 17/17 cases passed (72 ms)
  • Your runtime beats 90.05 % of javascript submissions
  • Your memory usage beats 35.91 % of javascript submissions (36.8 MB)
  • 时间复杂度: O(n)

思考总结

一般去重或者找到重复项用哈希的方式都能解决,但是在这题里,题目期望空间复杂度是 O(1),要么是改变原数据本身,要么是使用双指针法。这里我比较推荐双指针法,当然倒置法也比较巧妙。

(完)


本文为原创文章,可能会更新知识点及修正错误,因此转载请保留原出处,方便溯源,避免陈旧错误知识的误导,同时有更好的阅读体验
如果能给您带去些许帮助,欢迎 ⭐️star 或 ✏️ fork
(转载请注明出处:https://chenjiahao.xyz)

你可能感兴趣的