LeetCode

发布时间: 2018-07-27 10:40:14

第一题

  • 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        min_price = 299999999
        max_profit = 0

        for i in range(len(prices)):
            if prices[i]<=min_price:
                min_price=prices[i]

            if prices[i] -min_price>=max_profit:
                max_profit = prices[i] - min_price

        return max_profit

思路总结

  • 类似动态规划的感觉,遍历价格的时候同时更新最小价格和最大利润,这样就可以在O(N)的时间内完成.如何采用双重循环的方式O(N*N-(N/2(N-1)))的时间复杂度.

第二题

  • 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit =0
        for i in range(1,len(prices)):
            if prices[i]>prices[i-1]:
                profit += prices[i]-prices[i-1]
        return profit

思路总结

  • 这题算法不难,理解题目意思就可以了,最大利润那我只需要比前一天的价格高就卖出这样就可以得到最大的利润

第三题

  • 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        m = dict()
        for i in range(len(nums)):
            if target-nums[i] in m.keys():
                return [m[target-nums[i]],i]
            else:
                m[nums[i]]=i

思路总结

  • 遍历的同时把之前遍历的值和对应的索引保存在dict中,然后之后遍历的同时判断一下是否相等就可以了.这题因为是升序排列的数组,还可以使用首尾指针的方式.

第四题

  • 给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。 你找到的子数组应是最短的,请输出它的长度。

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        snum = sorted(nums)
        start = 0
        end = len(nums)
        for i in range(len(nums)):
            if nums[i]!=snum[i]:
                start = i
                break

        for i in range(len(nums)-1,0,-1):
            if nums[i]!=snum[i]:
                end = i
                break
        return end - start + 1 if end > start else 0

思路总结

  • 重新排序得到一个新的数组,然后对比前后找到变化了的位置.