Python Leetcode練習(4.23/4.25宿題)

3680 ワード

いくつかの理由で、今回の宿題は一日遅れて書きました.申し訳ございません.
11. Container With Most Water
a_をあげる1, a_2, ..., a_n合計n個の非負の整数で、一対のa_を求めるi、a_j(i解決策
S_を覚えてもいいですij = min(a_i, a_j)*(j - i). 証明できる:a_i < a_jの場合、必ずS_があるij > S_ik ( i < k < j). 証明は以下の通りである:a_i < a_j,だからS_ij = a_i*(j-i)a_の場合k <= a_i,明らかにS_があるij > S_ik,そしてa_k > a_i,S_ik = a_i * (k - i) < a_i * (j - i).証明が終わる
同様に、a_がi > a_jの場合、必ずS_があるij > S_kj ( i < k < j). そしてa_i = a_jの場合,前の2つのケースのいずれかに分類できる.
上記の結論から,1令i=1,j=n 2をa_からi, a_jの小さい方が反復を開始します.もしa_i <= a_j,kを(i+1)からS_が見つかるまでインクリメントするkj > S_ijの場合、i=kとし、その後②を繰り返すか、k>jの場合、③若a_i > a_j,kを(j-1)から減算し,S_を見つけることを知る.ik > S_ijの場合、j=kとして、②を繰り返すか、k時間複雑度O(n)
以下はソースコードである:(ソースコードにおける実装は上述した実装と完全に一致しないが、全体的に考え方は同じである)

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

120. Triangle
概要:数値三角形を指定し、上から下までの最短パスを見つけます.各ステップは、1行から次の行の真下に隣接する2つの要素の1つになります.たとえば、次の数値三角形を指定します.

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

最も短いルートの長さは11(2+3+5+1=11)です.
解決策
動的計画例題.記F[i,j]は、i行j番目の要素まで歩いたときに最も短いパス長である.遷移方程式は,F[i,j]=min(F[i−1,j−1],F[i−1,j])+a[i,j]境界条件はF[0,0]=a[0,0]配列境界条件の判断に注意する.答えはmin(F[n,i])(1<=i<=n)(三角形にn層があると仮定)時間複雑度O(n^2)、nは三角形層数以下がソースコード:(ソースコードにスクロール配列が使用されている)

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        f = [triangle[0][0]]
        g = []
        for i in range(1, len(triangle)):
            g.append(f[0] + triangle[i][0])
            for j in range(1, i):
                g.append(min(f[j - 1], f[j]) + triangle[i][j])
            g.append(f[len(f) - 1] + triangle[i][i])
            f = g
            g = []
        return min(f)

153. Find Minimum in Rotated Sorted Array
テーマ概要:あるインクリメンタルシーケンスが回転した結果を与えて、このインクリメンタルシーケンスの中で最も小数を求める.(このシーケンスには同じ2つの要素がないと仮定します).(回転とは?概ね、任意のキーi(pivot)を選択し、シーケンス中のi~n個の要素をシーケンスの前n-i+1ビットに、シーケンス中の0~(i-1)個の要素をシーケンスの後iビットに置くことを意味する)
解決策
キーiが0でない(すなわち回転がない)場合、回転後のシーケンスは必ず以下の条件を満たす:j(≠0)が1つ存在し、a[j]a[right]の場合、ターゲット値が2パーティション間の右半分(midを除く)にある場合、left=mid+1が更新されます.a[mid]

class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left = 0
right = len(nums) - 1
while (right > left):
mid = int((left + right) / 2)
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[right]

railsのプロセスを停止させる

luaとcのインタラクション