高度なプログラミング技術(Python)ジョブ12

LeetCode 11.最大水を盛る容器は、n個の非負の整数a 1,a 2,...,anを与え、各数は座標の1つの点(i,ai)を表す.垂直線iの2つの端点がそれぞれ(i,ai)と(i,0)になるようにn本の垂直線を引く.x軸と共に構成された容器が最も多くの水を収容できるように、その中の2本の線を探し出す.
注意:容器を傾けてはいけません.nは少なくとも2です.
Solution:

class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        maxSpace = 0
        i = 0
        j = len(height) - 1
        while(i <= j):
            length = j - i
            if (height[i] < height[j]):
                h = height[i]
                i += 1
            else:
                h = height[j]
                j -= 1
            maxSpace = maxSpace if maxSpace > h * length else h * length    
        return maxSpace

考え方:面積は高さの小さい端点に依存するので、両端から高さを取り、毎回小さい高さに距離を乗じて面積を計算し、前の最大面積と比較して最大面積を保存し、小さい端点は中間に2つの端点が重なるまで移動します.
62.異なる経路のロボットがm x nメッシュの左上隅に位置する(開始点は下図で「Start」と表記される).
ロボットは毎回、下または右に1歩しか移動できません.ロボットはメッシュの右下隅に到達しようとします(下図では「Finish」と表記されています).
全部で何本の違う経路がありますか?
説明:mとnの値はいずれも100を超えない.例1:

  : m = 3, n = 2
  : 3
  :
      ，    3           。
1.    ->    ->   
2.    ->    ->   
3.    ->    ->   

例2:

  : m = 7, n = 3
  : 28

Solution:

class Solution:
    def factorial(self, num):
        if (num == 1 or num == 0):
            return 1
        else:
            return num * self.factorial(num-1)

    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        x = min(m, n) - 1
        y = m + n - 2
        return int(self.factorial(y) / (self.factorial(x) * self.factorial(y - x)))

考え方:再帰計算階乗を用いて,その後組合せ数を用いて問題を解決する.配列を使用して階乗結果を保存して最適化できます.本題のデータは小さく、使用しなくてもいいです.
217.所定の整数配列が重複して存在し、重複要素が存在するか否かを判定する.
任意の値が配列に少なくとも2回現れる場合は、関数はtrueを返します.各要素が異なる場合はfalseを返します.
Solution:

class Solution:
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if(len(nums) > 0):
            if (len(nums) != len(set(nums))):
                return True
            else:
                return False
        return False

考え方:set関数を使用してリスト内の重複要素を削除し、前後のリスト長が同じかどうかを比較します.私は最初pythonを使ってhash表を書いて繰り返し要素を判断し、提出して合格したが、時間がかかりすぎて、後で他の人のコードを見て、setがこのような問題を解決できることを発見したが、pythonのsetの実現は実はhash表を通じて実現した.