# Chapter 1: Collections ## 知识解析 {% hint style="info" %} 本文将 **array, hash table, string** 统称为collections。 array可以看作 "key是从0开始的连续整数的hash table"，string可以看作是character组成的array。注意这里说的都是抽象意义上的array和string概念，与具体语言中的`class Array`和 `class String`相区别。 {% endhint %} ### **1.1 Hash Table as ADT** **Hash table的功能是基于"key"快速查找value (**$$O(1)$$**时间) ，存储的基本元素是key-value pair。** {% hint style="info" %} Hash table 是一种“归类”的数据结构，由`hash_func(key)` 得到bucket number，把key, value pair 放入对应的bucket。整个hash table就是一组bucket。`hash_func就是`hash function，负责把 key 转换成尽可能少的整数，作为key对应的bucket index。【Cracking the Coding Interview】介绍了一种简单而普遍的实现方式。 如果不同的key出现在同一个bucket，就叫做hash table的collision。hash function的设计原则，就是collision越少越好。 Hash 函数的具体实现方法，可以参考open hashing 和 closed hashing的相关资料：[Meaning of open hashing and closed hashing](https://stackoverflow.com/questions/9124331/meaning-of-open-hashing-and-closed-hashing) {% endhint %} ![How keys allocated to different buckets via hash function ](https://2007902981-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2FfpP0CWaMnRlFhQ_R%2F-M2QPf5QwPm1k3D7iq1f%2F-M2QRqm7HH_ZJof4_zIp%2Fimage.png?alt=media\&token=2057e1eb-f888-4be5-87e8-844a70e8d5e7) 如果hash table的key的范围与连续的整数对应，比如keys是从`a` 到`z` , 或者数字`i` 到`j`，那么可以把array当做hashtable，index与真正的key一一对应。比如用`arr[0]` 表示 `key:a` 或`key:i`对应的value。这种情况具体选择专门的hash数据结构还是array，取决于key的分布是密集 (array) 还是稀疏 (hash)。 特别地，如果value是只有两种状态，比如`true` 或 `false` ，那么可以把二进制数或bit-vector作为hash table来记录。 特别地，Hash table还可以用Balanced BST来实现, **lookup的时间由** $$O(1)$$ **增长为** $$O(logn)$$**，但可能节省space cost , 且可以按照key的顺序输出。** {% hint style="warning" %} **正因为Hash Table是一种“归类”的数据类型，往往也可以用排序来解决，取决于问题对时间和空间复杂度的trade-off。排序（sorting）即归类，只不过是有序的归类。** {% endhint %} ### **1.2 Reverse array / string** 1. 用头尾两个pointer，相向遍历，交换元素直到指针相遇 `while l < r` ，但不适用于数据流 2. 顺序遍历元素，push入stack，再依次pop，也可以用递归 ### **1.3 String Matching 的常见算法 （在string中查找substring）** > 假定源string长度为m，需要查找的substring长度为n {% hint style="success" %} Brute-Force算法：遍历string，将每个`idx`为起点, `idx+n-1`为终点的匹配子串与substring比较 $$O(mn)$$ Rabin-Karp算法：遍历string，把每个`idx` 为起点，`idx+n-1` 为终点的匹配子串当做一个sliding window，为他们设计一种线性的hash function，使得这些匹配子串的hash值在window移动时只需要做 $$O(1)$$ 的操作：比如**把子串的每一位看作一个x进制数，每个字符对应每一位上的数字，这样每次window slide时，就可以快速增量计算hash的值**（扣除最高位，增加最低位）。而hash值与匹配对象substring不同时，无需每个字符进行比较，因此在average情况下能做到 $$O(m+n)$$ 。最差情况需要 $$O(mn)$$ ，在hash function的collision非常严重时发生。 {% endhint %} ## **模式识别** ### **1.4 在collection内检索和统计的问题** #### **1.4.1 统计一个元素集中元素出现的次数** {% hint style="success" %} 用Hash Table。只统计元素出现与否的问题，可以用bitvector即二进制数来记录。 {% endhint %} > *e.g. 1 Implement an algorithm to determine if a string has all unique characters. （Hint: 也可以用排序）*\ > \&#xNAN;*e.g. 2 Write a method to decide if one string is a permutation of the other. （Hint: 也可以用排序）*\ > \&#xNAN;*e.g. 3 Given a newspaper and message as two strings, check if the message can be composed using letters in the newspaper.* #### 1.4.2 检索某一类元素的问题 {% hint style="success" %} 检索(归类)某一类元素的问题，如果允许修改原来的array并且追求更低的空间复杂度，那么总是可以用排序来归类进而达到待检索元素group到一起的效果。 {% endhint %} > *e.g.1 Given an array of integers, find two numbers such that they add up to a specific number. (*[*Leetcode: 2Sum*](https://leetcode.com/problems/two-sum/)*)* > > *e.g.2 Find all unique triplets in the array which gives the sum of zero.(*[*Leetcode: 3Sum*](https://leetcode.com/problems/3sum/)*)* ### **1.5 处理array或string问题的几点细节** #### **1.5.1 数组或string内，问题的解与前驱子问题有递推关系** {% hint style="success" %} 总是以`[0, i]`为范围，检索前驱节点的信息求解当前子问题的解 。如果只是检索特定的`value`，则可以用将当前`value`作为`key`建立hash table（value取决于你需要什么前驱子问题的信息），使得后驱节点每次检索的复杂度降低到 $$O(1)$$ 。实际上类似于dynamic programming的思维方式，记录前驱节点的信息，用空间换取回头在范围内重新扫描需要的时间。 {% endhint %} > *e.g. Given an unsorted array of integers, find the length of the longest consecutive elements sequence. (*[*Leetcode: Longest Consecutive Sequence*](https://leetcode.com/problems/longest-consecutive-sequence/)*)* ```python # 1. 前驱子问题的最大长度 + 当前节点的影响 => 到当前节点为止的最大长度 # 2. 要求当前节点对最大长度的影响，就要知道当前节点所在序列的长度， # 就必须知道num-1和num+1所在序列的上界和下界 class Solution: def longestConsecutive(self, nums: List[int]) -> int: bounds = {} max_length = 0 for num in nums: if num in bounds: continue # extend the bound via neighbors low, high = num, num if num - 1 in bounds: low = bounds[num-1][0] if num + 1 in bounds: high = bounds[num+1][1] # future extension can only be from low and high so only they need correct bounds bounds[high] = bounds[low] = bounds[num] = (low, high) # maintain max_length if high - low + 1 > max_length: max_length = high - low + 1 return max_length ``` {% hint style="danger" %} 注意在处理每个节点时，首先检索得到当前子问题的解，其次再把用于当前节点检索的信息存入hash table。 {% endhint %} #### **1.5.2 求最值或总和的问题，其实就是1.5.1的最简单特例，只不过我们只需要了解之前紧邻的一个节点的解就能推导出当前解 :**`sum(n) = sum(n-1) + curr` **，在update的过程中用 `sum` 一个变量记录即可** **1.5.3 处理两个不等长的array或string，总是可以以`while aIdx < aLength and bIdx < bLength` 作为结束条件，再处理可能剩下的元素。** > *e.g Given two sorted arrays, merge B into A in sorted order. (*[*Leetcode: Merge Sorted Array*](https://leetcode.com/problems/merge-sorted-array/)*)* **1.5.4 array或string修改后长度变化的问题** {% hint style="success" %} 用两个pointer分别记录`old_index` 和 `new_index` ，如果改动后element增多，就先resize array，再倒序赋值；element减少，就先顺序赋值，再resize。这样就使得新数据不会覆盖旧数据。 {% endhint %} > *e.g. 1 Given input "Mr John Smith", output "Mr%20John%20Smith"* \ > \&#xNAN;*e.g. 2 Given input "Mr%20John%20Smith" , output "Mr John Smith"* ### **1.6\*\* Sliding Window 问题** ### **1.7 处理2D-Array的问题** {% hint style="success" %} 通常可以把2D-Array当做array of arrays，访问每一行，在每一行内再按列访问。对于外圈向内圈遍历，可以记录row和col的边界，循环时将上下左右的进程分开描述。 {% endhint %} > *e.g.1 Given an NxN matrix, rotate the matrix by 90 degrees. （从test case出发理解交换规律）*\ > \&#xNAN;*e.g.2 If mat\[i]\[j] is 0, then set the entire row and column to 0.* > *e.g.3 Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.* [*(LeetCode: Spiral Matrix)*](https://leetcode.com/problems/spiral-matrix/) ```python def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if len(matrix) == 0 or len(matrix[0]) == 0: return [] seq = [] row, col = 0, 0 row_l, col_l = 0,0 row_h, col_h = len(matrix), len(matrix[0]) while True: # right for col in range(col_l, col_h): seq.append(matrix[row_l][col]) row_l += 1 if row_l == row_h: return seq # down for row in range(row_l, row_h): seq.append(matrix[row][col_h-1]) col_h -= 1 if col_l == col_h: return seq # left for col in reversed(range(col_l, col_h)): seq.append(matrix[row_h-1][col]) row_h -= 1 if row_l == row_h: return seq # up for row in reversed(range(row_l, row_h)): seq.append(matrix[row][col_l]) col_l += 1 if col_l == col_h: return seq ``` ### 1.8 设计**数字来映射/hash的情境** {% hint style="success" %} 可以利用进制数的正交性，即：数字的高位和低位是互相正交、独立的（或者反过来说，一个数用m进制来表示，只有唯一一种可能），把每一个单元用一位数字来表示 {% endhint %} > *e.g. 1 Design a hash function that is suitable for words in a dictionary.(EPI: 12.1) (问题的特征: word不会很长，每一位的可能性有限且密集，可以对应0-25的整数）*\ > *e.g. 2 A hash function for the state of a chess game.(EPI: 12.2) (问题的特征: 对每一次transition需要很容易的变换hash）* > > *e.g. 3 Implement a method rand7() given rand5().(CtCI:17.11)* --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://smilence-yu.gitbook.io/coding/chapter-1-collections.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.