leetcode 5.04-5.10

2020-05-05

001 两数之和
231 2的幂

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

https://leetcode-cn.com/explore/interview/card/tencent/221/array-and-strings/894/

方法一：双循环，两次遍历，$O(n^2)$，太慢了

使用python list, 列表由方括号扩起，括号内逗号分割值，list.append用于向列表添加元素，len获取长度

方法二：排序，首尾双指针，$O(n\log{n})+O(n) = O(n\log{n})$，但结果要求的是返回数组下标，想了一下有点麻烦，没写

方法三：参考提交中执行速度较快的代码，利用字典存已经遍历过的元素，每次访问新元素查询字典中有没有target-num的值，字典的查询时间是$O(1)$ ，遍历一遍是$O(n)$。

dic = {}
for index, num in enumerate(nums):
  another = target - num
  if another in dic:
    return [dic[another], index]
  else:
    dic[num] = index
return []

231. 2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

1
2
3

输入: 1
输出: true
解释: 2^0 = 1

示例 2:

1
2
3

输入: 16
输出: true
解释: 2^4 = 16

示例 3:

1 2	输入: 218 输出: false

https://leetcode-cn.com/explore/interview/card/tencent/223/math-and-numbers/942/

2的幂次方实际上是二进制表达中只有一个1的数，那么题目转换成数二进制表达中有几个1的问题

方法一：暴力，1左移，按位与

方法二：n & n-1 会将该数最右的1置为0，那么如果n&(n-1)==0就说明这个数只有一个1，需要注意n=0的情况

1 2	def isPowerOfTwo(n): return n > 0 and (n & (n-1)) == 0

Reference

python list 菜鸟教程 https://www.runoob.com/python/python-lists.html
python range() 菜鸟教程 https://www.runoob.com/python/python-func-range.html