目录

三个月算法进阶-day7

2020-08-30 约 298 字预计阅读 1 分钟次阅读

目录

python的for…else…或while…else可以用于跳出外层循环

python的any()与all()

横向扫描与纵向扫描

两两求解

分治法与递归

两个规模差不多的子问题

二分查找

查找最终值

记录

leetcode第14题

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        start = 0
        while start < min([len(i) for i in strs]):
            tmp = strs[0][start]
            for i in strs:
                if i[start] != tmp:
                    start -= 1
                    break
            else:
                start += 1
                continue
            break
        else:
            start -= 1
        if start == -1:
            return ""
        else:
            return strs[0][:start+1]

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        length, count = len(strs[0]), len(strs)
        for i in range(length):
            c = strs[0][i]
            if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
                return strs[0][:i]
        
        return strs[0]

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def isCommonPrefix(length):
            str0, count = strs[0][:length], len(strs)
            return all(strs[i][:length] == str0 for i in range(1, count))

        if not strs:
            return ""

        minLength = min(len(s) for s in strs)
        low, high = 0, minLength
        while low < high:
            mid = (high - low + 1) // 2 + low
            if isCommonPrefix(mid):
                low = mid
            else:
                high = mid - 1

        return strs[0][:low]