力扣练习——两数之和(python语言)_力扣两数之和python-程序员宅基地

技术标签: python  两数之和  力扣练习  

恍然间才发现把笔记记录在网上比记在本子上更方便,所以记录一次小小的尝试。

问题描述

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum

思路和提示

个人思路

从给定列表中依次不放回的取出一个数字,取一个新列表(mirror)存放这个数字,用target减去该数字,看差值是否在所给列表中。若在,将差值也存放在mirror中,然后找出这两个值在给定列表中的位置并输出;若不在,将mirror中的数字弹出(我用的remove),继续下一个数字。相当于遍历的方法。

官方提示

1.A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it’s best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.

2.So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value - x, where value is the input parameter. Can we change our array somehow so that this search becomes faster?

3.The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

总结:前两条是解决办法,大概和我个人的思路相一致。第三条中的 hash map目前还不知道是什么意思…

代码及描述

代码

class Solution(object):
    def twoSum(self, nums, target):
        twopos=[]
        mirror=nums[:]
        for i in nums:
            mirror.remove(i)
            twopos.append(i)
            x=target-i
            if x in mirror :
                twopos.append(x)
                if len(set(nums)) != len(nums):
                    one=nums.index(twopos[0])
                    nums[nums.index(twopos[0])]=''
                    two=nums.index(twopos[1])
                    return [one,two]
                else:
                    return[nums.index(twopos[0]), nums.index(twopos[1]) ]
            else:
                twopos.pop(0)

编写过程(这里是学习过程)

刚看完题感觉比较简单,很快就写好了代码,之道反复修改了几次之后才发现,事情并没有那么简单…
列两个比较典型的问题:

第一次出现的问题:

mirror=nums
'''这种方法中mirror和nums用的相同的存储空间'''

相当于mirror和nums共用了一个列表,所以对mirror的操作对nums也有相同的影响,最后return的时候从nums里找不到数值了…

第二次出现的问题:
少了一次判断,当nums=[3,3],target=6时,应该输出[0,1],所以加上一次判断

if len(set(nums)) != len(nums):
                    one=nums.index(twopos[0])
                    nums[nums.index(twopos[0])]=''
                    two=nums.index(twopos[1])
                    return [one,two]
'''这种方法直接改变了给定列表,但是最后能解决问题了就没有改(´▽`) '''

修改好之后,代码终于能成功运行了

结果:

执行用时 :560 ms, 在所有 python 提交中击败了 49.83% 的用户
内存消耗 :13.1 MB, 在所有 python 提交中击败了 15.65% 的用户

自己用的也就是暴力破解法,时间复杂度应该是O(n2),但是看有人用暴力破解法耗时 1636ms,所以不太确定,此处存疑。
关于算法复杂度:算法的时间复杂度和空间复杂度-总结

1636ms的代码:

def twoSum(nums, target):
    lens = len(nums)
    j=-1
    for i in range(lens):
        if (target - nums[i]) in nums:
            if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):
            #如果num2=num1,且nums中只出现了一次,说明找到是num1本身。
                continue
            else:
                j = nums.index(target - nums[i],i+1) 
                #index(x,i+1)是从num1后的序列后找num2                
                break
    if j>0:
        return [i,j]
    else:
        return []

#作者:lao-la-rou-yue-jiao-yue-xiang
#链接:https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-#jie-fa-by-lao-la-rou-yue-j/
#来源:力扣(LeetCode)
#著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

总结

可以看出用的都是简单的语句(再难一些自己都看不懂了),变量的命名和语句很糙,写的也很慢,经验太少了。

代码优化

1.命名变量时缺少经验,比如两数之和的两数,可以用num1, num2表示。
2.如果存在相同的两数,最后判定时,直接修改了给定列表中的值,这种做法很不好…

参考代码

找了一个简洁,自己又看得懂的代码:
用到了提示3中的 hash map。

class Solution(object):
    def twoSum(self, nums, target):
        hashmap = {
    }
        for index, num in enumerate(nums):
            another_num = target - num
            if another_num in hashmap:
                return [hashmap[another_num], index]
            hashmap[num] = index
        return None

#作者:lao-la-rou-yue-jiao-yue-xiang
#链接:https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-#jie-fa-by-lao-la-rou-yue-j/
#来源:力扣(LeetCode)
#著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

结果:

执行用时 :40ms, 在所有 python 提交中击败了 87.30% 的用户
内存消耗 :13.1 MB, 在所有 python 提交中击败了 15.26% 的用户

时间复杂度是O(n)。

学到的语句

1.enumerate 函数

python 自带的 enumerate 语句:

enumerate英文翻译为枚举的意思。 可以将一个可遍历的数据对象组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中。

如:

 >>> product = [ "Mac pro","iPhone","iWatch"]
 >>> for index,item in enumerate(product):
          print(index,item)

 '''得到结果如下:'''
 0    Mac pro
 1    iPhone
 2    iWatch

具体请参考Python中的enumerate函数介绍

2.permutations 函数

该函数从python自带的库 itertools 中引入:

>>> import itertools
>>> s = [1, 2, 3]
>>> print(itertools.permutations(s,2))
<itertools.permutations object at 0x000002C49B0283A8>
>>> n=itertools.permutations(s,2)
>>> for i in n:
	print(i)

'''得到结果如下:'''	
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)

3.combinations 函数

该函数同样从python自带的库 itertools 中引入:

>>> import itertools
>>> s = [1, 2, 3]
>>> t=list(itertools.combinations(s, 2))
>>> print(t)
[(1, 2), (1, 3), (2, 3)]

>>> t=list(itertools.combinations(s, 3))
>>> print(t)
[(1, 2, 3)]

即:
permutations和combinations都是得到一个迭代器。
combinations方法重点在组合,permutations方法重在排列。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45182000/article/details/103409842

智能推荐

TC刷题记_tc 刷题-程序员宅基地

文章浏览阅读323次。先挖个坑,会不断更新。1.SRM658 Div1 850 DancingForever题意:n个男孩和n个女孩,每个男孩喜欢至少一个女孩。你需要给出一种配对方案,满足至少有一对,且每个配对的男孩和他喜欢的女孩配对且他喜欢的其他女孩都被配了对,输出任意一组解。我们考虑直接二分图匹配。对于每个男孩,若你已经找不到增广路,那么肯定已经存在了一组可行解。为什么呢,我们考虑这个男孩找不到增广路,那就说明了他喜_tc 刷题

基础巩固(五)Android通过WebView与Js交互_android webview与js交互-程序员宅基地

文章浏览阅读2.4k次,点赞5次,收藏8次。WebView是一个基于webkit引擎、展现web页面的控件。Android的Webview在低版本和高版本采用了不同的webkit版本内核,4.4后直接使用了Chrome。显示和渲染web界面直接使用html文件(网络上或者本地asset)作为布局可与JavaScript交互调用WebView控件功能强大,除了具有一般View的属性和设置外,还可以对url请求、页面加载、渲染、页面交互进行强大的处理。_android webview与js交互

ListView异步加载图片,完美实现图文混排_qt listview 放入图片-程序员宅基地

文章浏览阅读409次。ListView加载文本数据都是很简单的,即使是异步获取文本数据。但是异步加载图片就稍微有一点麻烦,既要获得一个比较好的用户体验,还要防止出现图片错位等各种不良BUG,其实要考虑的东西还是挺多的。好了,我们先来看一下我们今天要实现的一个效果图: 看起来似乎并不难,确实,我们今天的核心问题只有一个,就是怎么异步加载图片,并且没有违和感。好了,废话不多说,先来看主布局文_qt listview 放入图片

python 中:NameError: name 'array' is not defined-程序员宅基地

文章浏览阅读1.5w次,点赞16次,收藏16次。必须执行:&gt;&gt;&gt; from numpy import array即使执行:&gt;&gt;&gt; import numpy也不能解决问题_name 'array' is not defined

时光煮雨 Unity3D让物体动起来③—UGUI DoTween&Unity Native2D实现-程序员宅基地

文章浏览阅读53次。本文首发蛮牛,次发博客园。接系列 第一篇,第二篇,本文为第三篇,再次感谢“武装三藏”在前两篇无私且精彩的问题解答写在最前,时光煮雨,为了怀念以下引用曾今读过的一些教程文章 其实这3种动画都有它特定的使用场合。 第一种动画适合创建简单的对象位移及直接性质的属性更改(在后面的教程中,我还将更深入的挖掘Storyboard动画的潜力,动态创建更复杂的基于KeyFra..._unity3d物体动起来

docker docker-compose volumes数据卷挂载问题_volumes no such file docker-程序员宅基地

文章浏览阅读3.3k次,点赞2次,收藏2次。docker数据卷挂载之后,导致no such file or directory...._volumes no such file docker

随便推点

缓存数据Key设置过期自动失效_baseresponse response=new baseresponse(statauscode-程序员宅基地

文章浏览阅读310次。内容:其实就是Expire命令的使用setex userOrderInfo 10 :设置10s的时间ttluserOrderInfoAPI的使用KeyExpireController.java@RestController@RequestMapping("key/expire")public class KeyExpireController extends AbstractController{ @Autowired private RedisTemplate r._baseresponse response=new baseresponse(statauscode.sucess)

FFmpeg 交叉编译libx264、libx265、libfdk-aac流程_libx264 交叉编译-程序员宅基地

文章浏览阅读4.9k次。背景FFmpeg 是一款强大的音视频处理工具,它是一种可插拔的架构设计。当需要使用某个编解码器、容器格式、网络协议时,只需要在编译文件中打开、配置,就可以在FFmpeg中使用。在播放器、推流器、视频编辑中经常都会使用到FFmpeg交叉编译第三方库,FFmpeg交叉编译第三方库可以说是音视频入门的基础知识,也是最重要的。通过学习了交叉编译的过程,加深对FFmpeg架构的设计。编译第三方库FFmpeg 最常使用的第三方库就是libx264、libx265、libfdk-aac。这里就介绍下libx264、_libx264 交叉编译

信号完整性之阻抗匹配与端接方法_传输线的阻抗匹配和端接方式-程序员宅基地

文章浏览阅读9.4k次,点赞15次,收藏98次。信号完整性之阻抗匹配与端接方法1. 前言随着电子技术的发展,电路的规模越来越大,单个器件集成的功能越来越多,速率越来越高,而器件的尺寸越来越小。由于器件尺寸的减小,器件引脚信号变化沿的速率变得越来越高,导致SI问题越来越突出。SI (Signal Integrity,信号完整性)与以下几个因素有关:反射、串扰、辐射。反射是由信号传输路径上的阻抗不连续造成的;串扰与信号的间距有关;辐射则与高速器件自身以及PCB设计均有关。2. 信号的阻抗匹配信号的阻抗匹配是影响信号完整性最主要的._传输线的阻抗匹配和端接方式

Ae 入门系列之一:了解 Ae 及工作流程-程序员宅基地

文章浏览阅读1.7k次,点赞2次,收藏5次。Adobe After Efftects(简称为 Ae )可以帮助用户高效且精确地创建无数种引人注目的动态图形和震撼人心的视觉效果,利用与其他 Adobe 软件紧密集成和高度灵活的二维和三..._ae视频渲染从入门到精通 csdn

Android进程间通信--消息机制及IPC机制实现_ipc机制和消息机制-程序员宅基地

文章浏览阅读479次。Android为了屏蔽进程的概念,利用不同的组件[Activity、Service]来表示进程之间的通信!组件间通信的核心机制是Intent,通过Intent可以开启一个Activity或Service,不论这个Activity或Service是属于当前应用还是其它应用的! _ipc机制和消息机制

mysql中文编码问题-程序员宅基地

文章浏览阅读38次。我比较推荐的方法是在创建数据库时便设置中文编码create database bp default character set utf8; #注意是utf8不是utf-8以下方法只适用于mysql5.5以上版本的(其实我的是mariadb5.5版本的) 编辑mysql配置文件[root@localhost ~]# cat /etc/my.cnf..._群晖 mysql5.6 中文乱码

推荐文章

热门文章

相关标签