专栏首页王漂亮NSum及股票系列
原创

NSum及股票系列

NSum系列

1. 2Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

1. 一边Dict

2. 排序,双指针,Onlogn

15. 3Sum

3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路 排序+双指针,On2,固定一个i,l,r从左右开始扫描

18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution

和3Sum思路一样,固定两个再双指针,On3

股票系列

算法:买卖股票系列

// 第i天的没有股票的状态 = Max(前一天就没有,前一天有但今天卖出了) 
profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]); 
// 第i天的有股票的状态 = Max(前一天就有了,前一天没有今天买了) 
profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]);

121. 买卖股票的最佳时机

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution

维护最小值,不断更新最大收益

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        
        dp = [0]*len(prices)
        min_v = prices[0]
        
        for i in range(1, len(prices)):
            min_v = min(min_v, prices[i])
            dp[i] = prices[i] - min_v
            
        return max(dp)

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

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Solution

只要后一天比前一天大,就交易

ab

123. 买卖股票的最佳时机 III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Solution

dp[i][s],i为天数,s为状态

ab

188. 买卖股票的最佳时机 IV

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Solution

dp[i][s],i为天数,s为状态

ab

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 狗家算法面试高频题汇总

    Google 面试题 | Data Stream Median - Python版

    王脸小
  • 各种字符串问题

    总结:所有题目都已做,有些Easy没有做第二遍,有两道没有accept,请戳 link-en, link-cn

    王脸小
  • 亚麻BQ

    Leaders start with the customer and work backward. They work vigorously to earn ...

    王脸小
  • [剑指offer][Java]旋转数组的最小数字

    链接:https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba ...

    后端技术漫谈
  • Python3 + django2.0 + apache2 + ubuntu14部署网站上线

    希希里之海
  • Ubuntu 16.04 Install OpenCV

    ---- 安装opencv有很多种方式,我列出了两种方式。并针对第二种方式进行了详细的安装解释。 从Ubuntu源安装opencv sudo apt-get i...

    BrianLv
  • 用户管理下

    第1章 批量添加3个用户stu01-stu03,设置密码为123456. 1.1 预备知识 前的产生的命令通过管道后可以交给bash运行 [root@znix ...

    惨绿少年
  • 深度学习让人脸识别准确率不断提升

      人脸识别、图像分类、语音识别是最早的深度学习取得突破的主要几个技术方向。在2014年前后,多家技术公司纷纷宣布其利用深度学习在LFW上取得的最新成果,此为深...

    人工智能的秘密
  • CSS 侧边栏在小屏设备中进行隐藏

    侧边栏的作用应该就不用多说了吧,能够很方便我们回到网页的指定位置,在大屏设备中,侧边栏往往是悬浮于屏幕右侧,很方便用户的使用,但在小屏设备中,屏幕空间有限,所以...

    Nian糕
  • 学界 | 我们还缺多少基础理论,才能在高中开设深度学习课程?

    AI 科技评论按:这篇文章来自资深机器学习专家、NIPS 2017 「时间检验奖」( Test of Time Award ) 获得者 Ali Rahimi。上...

    AI科技评论

扫码关注云+社区

领取腾讯云代金券