最长公共前缀 和 最大水量

lettcode 题目求解 Python

• Longest Common Prefix
  给定一个字符串，返回其最长前缀子串

例子 1：
Input: ["flower","flow","flight"]
Output: "fl"
例子 2：
Input: ["dog","racecar","car"]
Output: ""

思路：借鉴大神解法

def common_str(strs):
    if not strs:
        return ""
    for i, letter_group in enumerate(zip(*strs)):
        if len(set(letter_group)) > 1:
            return strs[0][:i]
    else:
        return min(strs)
# 注意 else 的用法 正常 for 循环结束后才会执行 else 语句，continue 也算正常语句
# 当有 break 语句执行后，并不会执行 else 语句
# 当然了，zip 的用法也非常有意思
def main():
    s = ["aower","flow","flight"]
    print common_str(s)

if __name__ == '__main__':
    main()

当前了，还有更大神的解法：

import os
 s = ["flwer","flow","flight"]
os.path.commonprefix(s)

来看一看 os 模块对其的解释：

Given a list of pathnames, returns the longest common leading component

只不过这个函数一般用来匹配路径前面的公共路径而已，只不过这里可以派上用场。其实一看 path 就知道用来匹配路径的了。

• Container With Most Water
  给定一个数组模拟水桶，计算其体积
  如[1, 2, 5, 2, 6, 3, 8]，计算在哪个区间的面积最大。比如 5 和 8，底是 8-5=3，高是 5，所以最大为 15

# 从两边开始遍历，维护一个最大值，每次和最大值比较即可
# 移动就是较小的那一条边即可
def maxArea(height):
    """
    :type height: List[int]
    :rtype: int
    """
    length = len(height)
    l, r = 0, length-1
    max_water = 0
    while l < r:
        max_water = max(max_water, min(height[l], height[r])*(r-l))
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
    return max_water

类似这样的过程

动图来源于网络