欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

数据算法 腾讯50题

程序员文章站 2022-03-15 14:54:19
Leetcode 腾讯50题 day3今天因为在做上一期pandas的综合测试题,第三题三数之和还没有写出更好的实现思路,暂时贴了官方题解的答案,主要和大家分享一些利用时间复杂度进行解题的技巧,在No.11盛最多水的容器的题解中分享No.11 盛最多水的容器题目描述给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容...

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(n2)。

题目中除了题目描述以外还有一个重要的信息,就是题目数据的边界,每道题都应仔细审视边界,这道题中数据为104,在这种情况下,使用O(n2)的算法大多会暴时(备注:小技巧,数据范围103使用O(n2)一定不会暴时,105使用O(n2)一定会暴时)

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

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

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

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

代码

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