leetcode_1. Two Sum

前言:

这段时间开始敲leetcode。我认为这并不仅仅只是为了应付笔试,面试。而是确实有着一定的意义。

尤其,你提交代码后,网站会多方面验证你的答案。

另外,提交成功后,你可以查看自己的运行时间,以及别人的运行时间。

最最关键的是,这之后,你可以查看别人的优秀代码。

这还不算,其中讨论模块,解决方案模块。

虽然以前在大学,玩过ACM。但是,体验和leetcode差很多。

所以,我是比较推荐的。

之前,我都是按照题目的序号来进行解题。

不过,其中hard难度的题目,确实对于现在的我来说有一定难度。

尤其是做到一篇寻找最长回文串的midium难度后,又做了一个判断是否为回文串的easy难度题目。

所以,我决定从简单的题目开始做起来。

我应该只会将一些midium难度的题目发布上来。以及一些有着不错亮点的easy题目。

一,问题:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [, , , ], target = ,

Because nums[] + nums[] =  +  = ,
return [, ].

翻译:

函数的输入是一个int数组以及一个目标值。通过在数组中选择两个int整数,来凑出目标值。

我们可以假设每个输入只有一个解决方案。并且数组中的每个元素只能使用一次。

(貌似,现在已经有了leetcode中文版。但是一方面,我希望锻炼一下自己的专业英文,另一方面,中文版的功能支持还不完善)

二,思路:

1.暴力法:通过双重循环,来遍历所有可能性,判断是否与目标值相等,如果相等,输入该循环内的两个数。

  优化:类比于排序算法的优化,外层循环遍历的nums[i]与内层循环遍历的nums[j],完全没必要再通过外层循环的nums[j]与内层循环的nums[i]这样来重复。

2.针对法:通过单次循环获取数组中每一个元素nums[i],再通过找寻数组内是否存在nums[j]使得nums[j]==target-nums[i],因为许多语言,内置了相关的搜搜索函数。如js的indexof.

三,代码:

我之后的这些题目都将采用go语言来实现。

V1:

func twoSum(nums []int, target int) []int {
result := make([]int, )
for k, v := range nums {
for k2, v2 := range nums[k+:] {
if v+v2 == target {
result = append(result, k,k2+k+)
return result
}
}
}
return result
}

由于并没有在go中找到相关的类似indexof的函数,所以,我便采用了暴力解法。

Runtime:80ms,6.40%

这里,我对于go的slice产生了一些疑惑,这导致我增添了一个无用的result变量。所以,我需要修改一下。

V2:

func twoSum(nums []int, target int) []int {
for k, v := range nums {
for k2, v2 := range nums[k+:] {
if v+v2 == target {
return []int{k, k+k2+}
}
}
}
return []int{}
}

PS:我们完全可以通过一句    return []int{k, k+k2+1}  来新建并返回一个匿名的slice。

Runtime:36ms,39.93%

相对与V1版本有了进步,但是仍然与TOP1的差很多。

从语法的角度,改进的空间已经不是很大了。那么只能从算法的结构上来提升。

虽然,go语言没有indexof。但是go语言还有map。

我曾今见过一两个通过map来提升速度的函数。但是,轮到自己来设计,还真是有些不适应。尤其,我对map还不是那么的熟悉,这导致我无法了解它的原理,从而降低耗时。

所以,我只能先试一试。直接先将所有的值都放在Map上,然后通过map间接性的实现indexof功能。

V3:

func twoSum(nums []int,target int) []int {
m:=make(map[int]int)
for k,v:=range nums{
m[v]=k
}
for k,v:=range nums{
another:=target-v
k2,ok:=m[another]
if ok== true &&k!=k2{
return []int{k,k2}
}
}
return nil
}

PS:这算是最无脑,直接的map算法。

Runtime:32ms,40.19%

即使这个算法非常无脑,只是非常僵硬地使用了map。但是依旧比v2快速。并且,这个方法从代码的角度依旧可以改进嘛。

起码两次循环遍历,完全是可以避免的。

V4:

 func twoSum(nums []int,target int) []int {
m:=make(map[int]int)
for k,v:=range nums{
another:=target-v
k2,ok:=m[another]
if ok== true &&k!=k2{
return []int{k,k2}
}
m[v]=k
}
return nil
}

PS:这里有一个非常关键的地方,那就是第9行的m[v]=k必须在第5行的k2,ok:=m[another]前。这样就避免了数组内有相同元素3,target=6,而导致的k2=k的情况。因为在map中相同键值的value值会后者覆盖前者的。

Runtime:8ms,85.92%

这可以说是一个非常喜人的结果了。从最后的结果分析图来看,只有一种算法要超过V4算法。

但是,我在尝试了几次代码上map的优化,还是没有办法。我甚至想是不是从内存的角度解决的。但是感觉可能性不大。

最后,简化出一个版本。

V5:

 func twoSum(nums []int,target int) []int {
m:=make(map[int]int)
for k,v:=range nums{
another:=target-v
if k2,ok:=m[another]; ok {
return []int{k,k2}
}
m[v]=k
}
return nil
}

Runtime:8ms,85.92%

虽然,简化了内存和判断条件。但是运算时间依然没有提高。甚至在一次改进中还出现时间增加到12ms的情况。

所以这应该是我提交的最终版本了。

四,他人代码:
1.最佳代码:

无论如何,也要看看完成最佳的代码是如何实现的。

 func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for i := ; i < len(nums); i++ {
comp := target - nums[i]
if _, ok := m[comp]; ok {
return []int {m[comp], i}
}
m[nums[i]] = i
}
return nil
}

Runtime:4ms,100%

2.分析:

从这个代码来看,其结构基本和我的最终版V5类似了。区别在于1,他没有使用range函数;2,他第5行没有接受key值,在第6行中采用map[key]来获取所需的value值。

那么究竟是哪个造成这4ms的差距。

但从理论上分析,我确实无法做到。但是我可以一个个去尝试嘛。

3.结果:

然而,在测试过程中,我发现了很尴尬的情况。那就是我的V5算法和TOP算法会跳动。有时候4ms,100%,有时候8ms,85.92%。

结果,另外一次提交:

请注意,下面的代码部分是完全一摸一样的。。。

表示这种情况也是有些尴尬。

不过,两者的算法应该差距不大了。

五,总结:

1,任何问题的第一要求是解决问题。不管是什么方法,想想出来一个解决问题。再谈优化。

2.任何函数都需要各种各样的测试,如溢出等。这样才可以令函数更具健壮性。

3.很多时候,go可以通过map来实现其他语言indexof的功能。而且性能很好。

4.算法结构解决完了,更可以优化代码结构。

PS:V4中解决键值冲突,只需要简单的换个位置就可以了。

PS2:map通过键值找不到的值,会返回相关零值。如果需要判断到底是否存在,请使用ok接收。

如有更正,请指出。谢谢。

(话说,for循环中到底是用i好呢,还是用range更好呢。)

最新文章

  1. NotePad++中JSLint的使用
  2. csharp: Oracle Stored Procedure DAL using ODP.NET
  3. 特许金融分析师 (CFA) 持证人现在一般在做什么工作?职业分布是怎样的?
  4. ui-router中的锚点问题(angular中的锚点问题)
  5. ligerui_实际项目_001:利用ligerLayout、ligerAccordion实现可折叠的菜单效果
  6. Flume OG 与 Flume NG 的区别
  7. SAP BW 通过视图创建数据源(无单位)
  8. HDOJ 1312 (POJ 1979) Red and Black
  9. Python:urllib和urllib2的区别(转)
  10. chrome_php logger 的实现原理
  11. java socket解析和发送二进制报文工具(附java和C++转化问题)
  12. JSON以及Java转换JSON的方法(前后端常用处理方法)
  13. AngularJS1.X学习笔记11-服务
  14. 零基础如何自学java开发?
  15. go [第一篇]初识
  16. 对讲解OS文献的反思
  17. 第三部分:Android 应用程序接口指南---第二节:UI---第十一章 样式和主题
  18. script 页面在指定位置加载
  19. Leetcode 78
  20. 【Linux】LVM逻辑卷管理和RAID

热门文章

  1. How to Enable Trace or Debug for APIs executed as SQL Script Outside of the Applications ?
  2. Android群英传笔记——第十二章:Android5.X 新特性详解,Material Design UI的新体验
  3. Java-Iterator总结
  4. Memcached学习笔记 — 第四部分:Memcached Java 客户端-gwhalin(1)-介绍及使用
  5. TCP 的那些事儿(上)(转)
  6. 苹果新的编程语言 Swift 语言进阶(十六)--泛型
  7. MDX的实例讲解(排名前15的小例子)
  8. Xcode中iOS模拟器程序中的plist路径
  9. Linux变量键盘读取、数组与声明: read, array, declare
  10. ThreadPoolExecutor运行机制