数据算法 腾讯50题

Leetcode 腾讯50题 day3

今天因为在做上一期pandas的综合测试题，第三题三数之和还没有写出更好的实现思路，暂时贴了官方题解的答案，主要和大家分享一些利用时间复杂度进行解题的技巧，在No.11盛最多水的容器的题解中分享

No.11 盛最多水的容器

题目描述

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
提示：
n = height.length
2 <= n <= 3 * 10000
0 <= height[i] <= 3 * 10000

解题思路

时间复杂度是算法题中一个重要概念，不但可以用来对比算法的效率优劣，还可以当做前提条件引导自己寻找更好的算法。
刚开始练习算法的时候，首先想到的都是基本的暴搜的思路，因此这道题我们先看一下用暴搜怎么解决。循环两次，遍历每两个点作为容器的边，并与当前最大值对比，最终求出最大值。显然暴搜使用了两次循环，时间复杂度为O(n²)。

题目中除了题目描述以外还有一个重要的信息，就是题目数据的边界，每道题都应仔细审视边界，这道题中数据为10⁴，在这种情况下，使用O(n²)的算法大多会暴时（备注：小技巧，数据范围10³使用O(n²)一定不会暴时，10⁵使用O(n²)一定会暴时）

因此，我们的目标就是寻找比O(n²）更好的算法，可以比较自然地想到有O(nlgn)以及O(n)，在数组、字符串相关的题目中，O(nlgn)通常意味着排序，（备注：在图、树的题目中通常O(lgn)是对树的搜索），这道题如果先排序能不能做呢？想想看感觉是比较困难的，因此可以想到使用O(n)的方法来做，而对一个数组只用O(n)的复杂度遍历，通常可以想到的方法有一次遍历、多次遍历、两边向中心遍历、中心向两边遍历。通常一次遍历可能是采用贪心的方法，两边向中心遍历就是双指针的方法，因此这道题可以想到用双指针来做。

我这里就不贴双指针的做法具体的思路是什么了，可以在leetcode官方题解中找到很好的讲解，我希望能从时间复杂度的角度，帮助大家认识到时间复杂度不仅是题目的限制，也是题目给出的提示，是帮助我们寻找更优算法的一个指引。也帮助大家想明白“我怎么才知道这道题应该用双指针来做”。

另外，在做公司招聘笔试题的时候，大多数平台是会按照测试样例的比例给分的，因此，如果想不出进阶算法，也应该先试试暴搜的思路，一方面写出暴搜才能给自己明确这个题解题的过程是怎样的，哪些地方可以优化，另一方面也可以答对测试样例中的部分样例，获得一部分分数。

这里我举一个我以前做笔试题的时候遇到的一道题，就是借助时间复杂度的提示完成的。题目是给出了一个图，图的结点非常非常多(10⁶)，因此如果用一个邻接矩阵存储图就是不现实的，但是这个图中的边的数量很少(10³)，因此就提示了我们应该根据边进行操作，而不是按照通常的邻接矩阵操作。

代码

class Solution:
    def maxArea(self, height: List[int]) -> int:
        p, q = 0, len(height)-1
        _max = 0
        while p<q:
            _max = max(_max, min(height[p], height[q])*(q-p))
            if height[p]<height[q]:
                p += 1
            else:
                q -= 1
        return _max

No.14 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

输入：strs = ["flower","flow","flight"]
输出："fl"
提示：
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

解题思路

这道题因为我使用Python做的，所以用了个Python的小技巧zip函数，zip函数可以将一个可迭代对象如列表打包，依次同时取出来列表中的元素。zip通常要与*操作联合使用。在这道题中strs参数是一个列表，里面包含了多个字符串，使用*strs就代表了解开这个列表，表示多个字符串，然后zip(*strs)就代表了将这多个字符串打包，依次同时取出其第一个元素作为一个元组，再取出所有字符串的第二个元素作为元组…zip函数默认取所有可迭代对象中最短的对象为边界，因此刚好符合这道题的题目要求。

代码

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ''
        if len(strs)==0:
            return ''
        for l in zip(*strs):
            for i in range(len(l)-1):
                if l[i]!=l[i+1]:
                    return res
            else:
                res = res + l[0]
        return res

No.15 三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        for first in range(n):
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            third = n - 1
            target = -nums[first]
            for second in range(first + 1, n):
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans

本文地址：https://blog.csdn.net/qq_32844743/article/details/112597877