0%

【编程起跑线】03 数组和字符串

数组和字符串作为最基本的元素,涉及的知识点非常多,许多高级的应用如堆,栈,队列,动态规划等都可以基于数组,这一讲我们主要还是集中在数组本身性质的习题上。


更新历史

  • 2019.08.05:编入新系列
  • 2016.01.22:完成初稿

题目分类与解题策略

原本以为这一章内容不会很多,但是整理资料的时候发现,我把不少稍微有些『难度』的题目,也放到了这个类别下,不过也没有问题,万事开头难,熬过这一波就好了。

基本解题策略

  • 判断元素是否出现:哈希表 或者 bitset
  • 统计元素出现次数:哈希表

重要知识点

  • 越界问题
  • 支持随机访问,修改读取 O(1)
  • 插入删除 O(n)
  • 哈希表,插入 O(1),查找 O(1)
  • 哈希表解决冲突的方式:链接法(chaining)和开放地址法(open addressing)

常见容器

  • Vector / ArrayList
  • HashSet, HashTable
  • Map / Dictionary

我们先来分析一下具体的题目类型,因为很多题目万变不离其宗,只要抓住解题思路,剩下的就是时间问题了(具体的题目列表在最后的附录中),下面是几个大类的问题及对应的思路:

次数统计

这类题目就是哈希表大显身手的时候了,比方说找唯一出现的字母或数字,或者是统计元素出现的次数,都可以用哈希表来快速完成。因为哈希表可以做到 O(1) 时间的检索,所以效率会很高。看一次这个分类下的题目就会发现,问题的突破口往往就是找到对应的建立哈希表的方式。

哈希表(Hash Table)几乎是最为重要的数据结构,主要用于基于“键(key)”的查找,存储的基本元素是键-值对(key-value pair)。逻辑上,数组可以作为哈希表 的一个特例:键是一个非负整数。注意,通常哈希表会假设键是数据的唯一标识,相同的键默认表示同一个基本存储元素。

哈希表的本质是当使用者提供一个键,根据哈希表自身定义的哈希函数(hash function),映射出一个下标,根据这个下标决定需要把当前的元素存储在什么位置。在一些合理的假设情况下,查找一个元素的平均时间复杂度是O(1),插入一个元素的平摊(amortized)时间复杂度是O(1)。

当对于不同的键,哈希函数提供相同的存储地址时,哈希表就遇到了所谓的冲突(collision)。解决冲突的方式有链接法(chaining)和开放地址法(open addressing)两种。简单来说,链接法相当于利用辅助数据结构(比如链表),将哈希函数映射出相同地址的那些元素链接起来。而开放地址法是指以某种持续的哈希方式继续哈希,直到产生的下标对应尚未被使用的存储地址,然后把当前元素存储在这个地址里。

通常而言,链接法实现相对简便,但是可能需要附加空间,并且利用当前空间的效率不如开放地址法高。开放地址法更需要合理设计的连续哈希函数,但是可以获得更好的空间使用效率。需要注意的是,过于频繁的冲突会降低哈希表的搜索效率,此时需要哈希表的扩张。

比较有特点的题目是:

特定模式

这个类型的题目比较多变化,比方说,找回文串,子串匹配,或者是两个数组中相差最小的两个元素,又或者是字符串按照一定规则变成数字。这类问题有一个特点,就是可以很容易想出暴力解法,但是暴力解法会有很多重复运算,效率不高,于是需要进一步进行优化。具体的优化方式有很多,比方说找回文串,如果比较复杂一点的 manacher 算法没办法保证百分百写对的话,那么以每个字符为中心开始延展的方式,也是不错的做法。

具体来说,就是一定要清楚地知道,具体在操作的元素是哪个,以及对应的匹配关系,一开始可能会比较慢,但是熟悉了之后就好了。比较有特点的题目是:

区间问题

区间问题的复杂性在于,需要处理多种情况,如果不事先想好的话,很容易出错。另外就是处理区间取数的问题,会涉及到一些动态规划的思想,当然,有些问题也可以用哈希表来解决。解决问题的关键在于,一定要意识到多种情况的可能,并且在代码中做对应的处理。比较有特点的题目是:

矩阵相关

矩阵就是二维数组,具体来说,难度在于,怎么处理好两个维度的问题。具体来说,就是要看题目中有没有给出一些明显的信息,比方说排好序。写关键代码的时候,一定要列好前条件和后条件,保证不出问题。比较有特点的题目是:

逻辑操作

这个类别包括的题目千奇百怪,理论上来说很难总结一个普适的规律,因为实际上就是根据特定的逻辑规则来进行操作。比方说以特定格式输出,旋转,排序,交换,合并,堆等等。因为变化太多,所以这里只能给出一个比较通用的建议:列出前条件后条件,注意每一步操作及可能带来的副作用,善于利用数据结构本身的能力。比较有特点的题目有:

附录