大一那会偶然听说过leetcode,那时刚学算法感觉这玩意太高大上了…(其实是感觉好难)。 注册后就尘封了。
学到现在,终于感受到了算法的重要性…看来以后算法练习也要提上日程了QWQ !

第一题,两数和

题目:

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.

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

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

Example:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题思路

第一种方法:

遍历两遍数组,暴力破解。通过for循环的嵌套,每一个元素进行尝试,正确则返回。
代码如下:

1
2
3
4
5
6
7
8
9
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i+1,n):
if nums[i] + nums[j] == target:
return [i,j]

return None

分析:
当数组长度为n时,时间复杂度为O(n²)
关于时间和空间,两者相比之下我更愿意用空间来换取时间。当然,使用的空间也不能太过分。

第二种解法:

第一种方法的时间复杂度是 O(n²),这是因为遍历了两次数组,那如果我们只遍历一次数组,那么时间自然就降下来了->O(n)
我们知道x + y = target,我们遍历的时候已经获取到了X,则y = target - x。所以此时我们只需寻找满足Y值的数就可以了。
而判断Y值是否在数组中,我们可以用if语句来实现。但这有个问题,题目要求不能重复使用自己。如果target = X + X时则错误。
代码如下:

1
2
3
4
5
6
7
8
9
10
for index, num in enumerate(nums):
# 找到Y值
find_num = target - num
# 记录当前下标
my_index = index
# 判断数组中是否存在Y值
if find_num in nums :
fine_index = nums.index(find_num)
if fine_index != my_index: # 判断Y值的下标与X值是否一样
return [my_index, fine_index]

分析:
与其他语言相比,python的if语句无疑是走了捷径。

第三种解法:

既然第二种解法的时间复杂度是O(n),那如果是O(1)的话速度无疑会更快。
通过看大佬的解答得知一种数据结构hashmap,一种键值一一对应的数据结构。这让我联想到了python的 dict。
通过对字典的索引,无疑可以减少遍历带来的时间问题,因此我们把数组的下标 index 和数组的内容 value联系起来。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
# 把数组转换成字典
dict_nums = {}
for index, num in enumerate(nums):
dict_nums[num] = index

for index, num in enumerate(nums):
find_num = target - num
my_index = index
if find_num in dict_nums.keys():
if dict_nums[find_num] != my_index:
find_index = dict_nums[find_num]
return [my_index, find_index]

哈希表

这一题所涉及的知识点–哈希表
哈希表是一种数据结构,它使用哈希函数组织数据,以支持快速插入和快速搜索。

哈希表简介

哈希表(Hash Table,也叫散列表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做哈希函数,存放记录的数组称做哈希表。

一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表(即建立人名 xx 到首字母 F(x)F(x) 的一个函数关系),在首字母为 WW 的表中查找 “王” 姓的电话号码,显然比直接查找就要快得多。这里使用人名作为关键字,“取首字母” 是这个例子中哈希函数的函数法则 F()F(),存放首字母的表对应哈希表。关键字和函数法则理论上可以任意确定。

哈希表是使用 O(1)O(1) 时间进行数据的插入删除和查找,但是哈希表不保证表中数据的有序性,这样在哈希表中查找最大数据或者最小数据的时间是 O(N)O(N) 实现。

哈希表的原理

哈希表的关键思想是:

  • 存储
    1. 开创一块连续存储空间,通常是数组。(这块连续的空间称为散列表或哈希表)
    2. 把key通过固定的算法函数(哈希函数) 转换成一个整型数字
    3. 把该数字对数组长度进行取余,取余的结果则是数组(哈希表)下标。
    4. 将value的值存储在以该数字为下标的数组空间中

当读取时,过程与存储类似。

  • 读取
    1. 将key通过同样的过程进行转换
    2. 用转换后的值(即下标),去访问对应数组下标。

这样就能够快速的通过数组下标定位元素了!!!!! TQLLLLLL!

哈希表冲突

理想情况下,如果我们的哈希函数是完美的一对一映射,我们将不需要处理冲突。不幸的是,在大多数情况下,冲突几乎是不可避免的。因为余数的个数是有限的(0-9)。比如,哈希函数y = x % 5 中,1987和2 的余数都是2,这是一个冲突。

因此,哈希函数的设计就十分重要。冲突解决算法应该解决以下几个问题:

  • 如何组织在同一个桶中的值?
  • 如果为同一个桶分配了太多的值,该怎么办?
  • 如何在特定的桶中搜索目标值?

好的哈希函数的特点:

  1. 尽量使关键字对应的记录均匀分配在哈希表里面
  2. 关键字极小的变化可以引起哈希值极大的变化。

哈希冲突解决的办法有许多,我提一下用的比较多的链地址法。
上面说到,数组的空间是会用完的。链地址法的原理是:如果遇到冲突,他会在源地址新建一个空间,然后以链表结点的形式插入到该空间。

比如说我有一堆数据{1,12,26,337,353…},而我的哈希算法是H(key)=key mod 16,第一个数据1的哈希值f(1)=1,插入到1结点的后面,第二个数据12的哈希值f(12)=12,插入到12结点,第三个数据26的哈希值f(26)=10,插入到10结点后面,第4个数据337,计算得到哈希值是1,遇到冲突,但是依然只需要找到该1结点的最后链结点插入即可,同理353。

总结

不知道说什么,但算法真的好好好好好好好van!~~!