Day 19 | 78.子集、121.买卖股票的最佳时机

Leetcode 78.子集

题目：78.子集

初始思路

休息日，写两题练练。

代码

var subsets = function (nums) {
    const res = []
    const dfs = (index, list) => {
        // 结束条件
        if (index === nums.length) {
            // 指针越界，加入题解
            res.push(list.slice())
            return
        }
        // 选择index所在的数
        list.push(nums[index])
        // 基于这个选择，继续递归
        dfs(index + 1, list)
        // 撤销这个选择,往上回溯
        list.pop()
        // 不选这个index,继续递归
        dfs(index + 1, list)
    }
    dfs(0, [])
    return res
};

感想

1. 回溯问题，没练过啊。
2. [1,2,3]的输出是：[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
3. 题解：https://leetcode.cn/problems/subsets/solution/shou-hua-tu-jie-zi-ji-hui-su-fa-xiang-jie-wei-yun-/

Leetcode 121.买卖股票的最佳时机

题目：121.买卖股票的最佳时机

初始思路

恩。。。之前做过贪心的

代码

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

感想

1. 这题实际上是要用动态规划做的，但是还没刷到那里。