leetcode 第11、14、15題 Python

1. 盛最多水的容器

   給你 n 個非負整數 a1，a2，…，an，每個數代表坐标中的一個點 (i, ai) 。在坐标内畫 n 條垂直線，垂直線 i 的兩個端點分别為 (i, ai) 和 (i, 0) 。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。

   說明：你不能傾斜容器

   思路：設定左右兩個指針left 和 right，盛水容量由矮的高度決定，每次移動矮的高度

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l = 0
        r = len(height)-1
        if not height or len(height) == 1 :
            return 0
        res = (r-l)*(height[l] if height[l] < height[r] else height[r])
        
        while l < r:
            if height[l] < height[r] :
                res = res if res > height[l]*(r-l) else height[l]*(r-l)
                l += 1
            else :
                res = res if res > height[r]*(r-l) else height[r]*(r-l) 
                r -=1
        return res
           

1. 最長公共字首

   編寫一個函數來查找字元串數組中的最長公共字首。

   如果不存在公共字首，傳回空字元串 “”。

   示例 1：

   輸入：strs = [“flower”,“flow”,“flight”]

   輸出：“fl”

   示例 2：

   輸入：strs = [“dog”,“racecar”,“car”]

   輸出：""

   解釋：輸入不存在公共字首。

   暴力方法好像會逾時，但是看到下面這個暴力循環方法，不逾時。

   循環對比第一個字母，初始t為""，若首位全相同則追加至t并對比下一位，不相同則傳回t

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs)==0:
            return ""
        t=""
        flag=0
        strs=sorted(strs,key=lambda x:len(x))
        for n in range(len(strs[0])):
            temp=strs[0][n]
            for i in strs[1::]:
                if i[n]==temp:
                    continue
                else:
                    flag=1
                    break
            if flag!=1: 
                t+=temp
        return t
           

另一個思路：取第一個字元串并與接下來的字元串循環對比，利用find()比對查找，若傳回索引不為0則去掉待比對字元串最後一個字母，直到為空。運作時間和記憶體消耗都更優！

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        
        if len(strs) == 0:
            return ""
        
        prefix = strs[0]
 
        for s in strs[1:]:
            while s.find(prefix) != 0:
                prefix = prefix[0:len(prefix) - 1]
                if prefix == "":
                    return prefix
        return prefix
           

正常思路：

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len (strs) == 1:
            return strs[0]
        if strs == []:
            return ""
    
        temp = self.__firstmatch(strs[0],strs[1])
        if temp =="":
            return ""
        result = temp
        for i in range(len(strs)-1):
            temp = self.__firstmatch(temp,strs[i+1])
            if temp =="":
                return ""
            if len (temp)<len(result):
                result = temp
        return result
                
    def __firstmatch(self,a,b):
        result=""
        for i in range(len(a)):
            if i>len(b)-1 or a[i] != b[i] or i>len(b) :
                break
            result +=a[i]
        return result
           

1. 三數之和

   給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重複的三元組。

   注意：答案中不可以包含重複的三元組

   思路：通過先對list進行排序，後周遊所有滿足要求的三元組，隻是在避免三元組重複的問題上，使用了字典作為判斷條件。具體思路是将所有符合要求的三元組的最大值和最小值組合成元組，将這個元組作為key儲存在字典中，根據字典的key的唯一性，就可保證三元組的唯一性。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        list_ret = []
        d = {} 
        num = len(nums)
        nums.sort()
        for i in range(num): 
            if i == 0 or nums[i]>nums[i-1]: ##避免出現重複三元組 
                l = i+1
                r = num-1            
                while(l < r):
                    s = nums[i] + nums[l] + nums[r]
                    if s == 0:                        
                        col = [nums[i],nums[l],nums[r]]
                        max_e = max(col)
                        min_e = min(col)   
                        if((max_e,min_e)  not in d):
                            list_ret.append(col)                     
                            d[(max_e,min_e)] = 1 ###字典用來最終避免三元組重複
                        r -= 1
                        l += 1                   
                    elif s > 0:
                        r -= 1
                    else:
                        l += 1

        return list_ret

           

借鑒了好多人的解題思路，進行了嘗試。算法小白在龜速學習中，非原創。特此感謝！