因?yàn)橐恍┰颍?這次的作業(yè)晚了一天寫(xiě)。 很抱歉。
11. Container With Most Water
題目意思很簡(jiǎn)單： 給出a_1, a_2, ..., a_n總共n個(gè)非負(fù)整數(shù)，求出一對(duì)a_i、a_j(i < j)， 滿足min(a_i, a_j)*(j - i)是最大的。
解決思路
我們可以記S_ij = min(a_i, a_j)*(j - i)。
可以證明：當(dāng)a_i < a_j時(shí)， 一定有S_ij > S_ik ( i < k < j)。 證明如下：
因?yàn)閍_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)。證畢
類似地可以證得到: 當(dāng)a_i > a_j時(shí)， 一定有S_ij > S_kj ( i < k < j)。
且當(dāng)a_i = a_j時(shí)，可以歸入到前面兩種情況的任意一種中去。
有了上述結(jié)論，我們就可以得到一個(gè)解決的方法：
① 令i = 1， j = n
② 從a_i， a_j較小的那一邊開(kāi)始迭代。
若a_i <= a_j，則令k從(i+1)開(kāi)始遞增，直到找到S_kj > S_ij時(shí)， 令i = k，然后重復(fù)②，或k > j時(shí)，跳到③
若a_i > a_j， 則令k從(j-1)開(kāi)始遞減，知道找到S_ik > S_ij時(shí)，令j = k， 然后重復(fù)②， 或k < i時(shí)， 跳到③
③程序運(yùn)行結(jié)束， 答案就是S_ij。
時(shí)間復(fù)雜度為O(n)
以下為源代碼:
(源代碼中的實(shí)現(xiàn)與上述描述的實(shí)現(xià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
題目概述：給定一個(gè)數(shù)字三角形， 找到一條從頂至底的最短路徑，每一步可以從一行已到下一行正下方的相鄰兩個(gè)元素之一。例如， 給定下面的數(shù)字三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
最短的從頂至底的路徑長(zhǎng)度為11（2+3+5+1=11）。
解決思路
動(dòng)態(tài)規(guī)劃例題。記F[i, j]是走到第i行第j個(gè)元素時(shí)最短的路徑長(zhǎng)度。轉(zhuǎn)移方程為：
F[i, j] = min(F[i - 1, j - 1], F[i - 1, j]) + a[i, j]
邊界條件為F[0, 0] = a[0, 0]
注意判斷數(shù)組越界條件。
答案是min(F[n, i]) (1 <= i <= n) （假設(shè)三角形有n層）
時(shí)間復(fù)雜度為O(n^2)， n為三角形層數(shù)
以下為源代碼：
(源代碼中使用了滾動(dòng)數(shù)組)
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
題目概述：給定某個(gè)遞增序列旋轉(zhuǎn)后的結(jié)果， 求出這個(gè)遞增序列中最小數(shù)。（假定這個(gè)序列沒(méi)有相同的兩個(gè)元素）。（什么是旋轉(zhuǎn)？ 大概意思就是指選定任意一位關(guān)鍵位i(pivot)， 把序列中i~n個(gè)元素放到序列的前n-i+1位， 把序列中0~(i-1)個(gè)元素放到序列的后i位中）
解決思路
若關(guān)鍵位i不為0（即沒(méi)有旋轉(zhuǎn)），則旋轉(zhuǎn)后的序列一定滿足以下條件:
存在一個(gè)j(≠0)， 滿足a[j] < a[j + 1] < ... < a[n] < a[0] < a[1] < ... < a[j - 1]
我們的目標(biāo)就是要找到這個(gè)j，答案就是a[j]。
有了這個(gè)條件，可以考慮使用二分法來(lái)解決這個(gè)問(wèn)題：
① 初始化二分區(qū)間邊界left = 0, right = n
② 取二分區(qū)間的中值mid = (left + right)/2。
若a[mid] > a[right]，目標(biāo)值在二分區(qū)間的右半部分(不包括mid)，更新left = mid + 1。
若a[mid] < a[right]，目標(biāo)值在二分區(qū)間的左半部分(包括mid)，更新right = mid。
時(shí)間復(fù)雜度為O(logn)
源代碼:
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]
