leetcodeテンセント2018秋招精選(50題)Easy Part(3)

21.2つの秩序チェーンテーブルを結合する
2つの順序付きチェーンテーブルを新しい順序付きチェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます. 
例:

  ：1->2->4, 1->3->4
  ：1->1->2->3->4->4

考え方:2つのチェーンテーブルを再帰的に遍歴し、小さな数を前に置く(秩序チェーンテーブル)ことで、返される値がチェーンテーブルであることに注意してください.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        #     0
        res = ListNode(0)
        if l1.val < l2.val:
            #      
            res.val = l1.val
            res.next = self.mergeTwoLists(l1.next, l2)
        else:
            res.val = l2.val
            res.next = self.mergeTwoLists(l1, l2.next)
        return res

122.株の売買に最適なタイミングII
配列が与えられ、その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:

  : [1,2,3,4,5]
  : 4
  :    1  （     = 1）     ，   5   （     = 5）     ,            = 5-1 = 4 。
             1     2        ，        。
                    ，                 。

例3:

  : [7,6,4,3,1]
  : 0
  :       ,       ,         0。

構想:貪欲なアルゴリズム.毎回、後の値と前の値の最大差を取って加算します.

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        res = 0
        if not prices:
            return 0
        if len(prices) < 2:
            return 0
        for i in range(1, len(prices)):
            res += max(0, prices[i] - prices[i - 1])
        return res

155.最小スタック
push,pop,top操作をサポートし,定数時間で最小要素を取得できるスタックを設計した.

push(x)--要素xをスタックにプッシュします.

pop()--スタックトップの要素を削除します.

top()--スタックトップ要素を取得します.

getMin()--スタック内の最小要素を取得します.

例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   -->    -3.
minStack.pop();
minStack.top();      -->    0.
minStack.getMin();   -->    -2.

構想:通常スタックと最小値スタックを設定し、最小値スタックは最小値のみを格納し、定数時間に達して最小値を取得します.

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.stackMin = []
    
    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.stack.append(x)
        #             ，         
        if self.stackMin == [] or x < self.getMin():
            self.stackMin.append(x)
        else:
            self.stackMin.append(self.getMin())
    
    def pop(self):
        """
        :rtype: void
        """
        if self.stack == [] or self.stackMin == []:
            return None
        self.stack.pop()
        self.stackMin.pop()
    
    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.stackMin[-1]

121.株を売買する最良のタイミング
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.
最大1つの取引(株の購入と売却)しか許可されていない場合は、取得できる最大利益を計算するアルゴリズムを設計します.
株を買う前に株を売ってはいけないことに注意してください.
例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。

# -*- coding:utf-8 -*-
"""
    i     ，                  ？
    i-1            。          
    。     minPrice   i-1        ，
          minPrice             ，
              maxProfit       。
"""
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        res = 0
        if not prices:
            return 0
        if len(prices) < 2:
            return 0
        minPrice = prices[0]
        for i in range(1, len(prices)):
            res = max(prices[i] - minPrice, res)
            if prices[i] < minPrice:
                minPrice = prices[i]
        return res

217.重複する要素が存在する
整数配列を指定し、重複要素が存在するかどうかを判断します.
任意の値が配列に少なくとも2回現れる場合、関数はtrueを返します.配列内の各要素が異なる場合はfalseを返します.
例1:

  : [1,2,3,1]
  : true

例2:

  : [1,2,3,4]
  : false

例3:

  : [1,1,1,3,3,4,3,2,4,2]
  : true

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) <= 1:
            return False
        nums.sort()
        first = nums[0]
        for i in range(len(nums)):
            if nums[i] == first:
                return True
            first = nums[i]
        return False