[关闭]
@smilence 2016-09-02T20:02:18.000000Z 字数 5071 阅读 1845

第四部分:数组和字符串

算法面试指南


4.1 知识解析

array, hashtable和字符串,从结构形式来说,这三个是一种东西。array是特殊的hashtable,key是连续的index,例如当key是char的时候就可以一一对应。比如有一些字符,我们需要做一些预处理来检索一些信息(每个字符出现的数量)。我们应该用hashtable还是array呢?(分布是密集还是稀疏)

  1. Open hashing (Separate Chaining) & Closed hashing (Open Addressing)

  2. 特别地,Hash table还可以用Balanced BST来实现,如std::map, lookup的时间由增长为,但可能节省space cost ,且可以按照key的值有序输出pairs。

  3. 使用hashtable时,key没有预设hash function情况下的语言细节:

    对于C++,
    map<Key,Val,key_comp> table ,对于严格弱序判断的不同定义,可以通过重载<操作符或者定义functor class实现。
    注意对于map无需重载==运算符,因为 A==B 等效于 !(A<B)&&!(B<A)

    对于unordered_map<Key,Val>则更加复杂,需要定义:
    (1) A hash function, 用于确定Index即hash值;(2) 重载==操作符,用于区分hash值相同的不同key。
    详见:http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key

    对于JAVA,需要对HashMap重定义equals()hashCode()

    e.g Find a line which passes the most number of points.

  4. 使用hashtable分类的问题,往往也可以用排序来解决,取决于对时间复杂度和空间复杂度的要求。sorting(排序)即分类。

  5. string的语言细节 ( Java: StringBuilder, stringBufferString )
  6. reverse string or array (经常用到的piece of code)
    (1) 用头尾两个指针,相向遍历,swap元素 (不适用于数据流)
    (2) 顺序遍历元素,push入stack,再依次pop。(或者递归)

  7. String matching (推荐使用Rabin-Karp算法)
    将每一个匹配子串映射为一个hash值。例如,将子串看做一个多进制数,计算它的值与目标字符串的hash值比较,如果相同,再比较两个字符串是否相同。顺序shift过程中,可以增量计算hash值(扣除最高位,增加最低位)。因此能在average case下做到O(m+n)。

  8. 2-D array, 总是推荐用collection(vector of vector) 而不是C-style

4.2 数组与哈希表问题

1.统计一个元素集中元素出现的次数,用Hash Table,即std::unordered_map或std::map。只统计元素出现与否的问题,可以用bitvector即bitset,二进制数来记录。

e.g. 1 Implement an algorithm to determine if a string has all unique characters. (也可以用排序)
e.g. 2 Write a method to decide if one string is a permutation of the other. (也可以用sorting,不仅把相等的放在一起,更会有序地把相近地放到一起)
e.g. 3 Given a newspaper and message as two strings, check if the message can be composed using letters in the newspaper.(Google interview)
(只需要找到match_cnt == count(message)就可以了)

2. 处理vectorarray或string问题的几点细节:

a.数组或string内前驱subproblem推出problem的问题,总是以为范围,检索前驱节点 求解当前节点 。如果只是检索特定的value,则可以用将当前value作为key建立hash table(value取决于你需要什么前驱子问题的信息),使得后驱节点每次检索的复杂度降低到。实际上类似于dynamic programming的思维方式,记录前驱节点的信息,用空间换取重新扫描需要的时间。

e.g.1 Given an array of integers, find two numbers such that they add up to a specific number.(Leetcode: 2Sum) (也可以用排序)

  1. sum = 6
  2. [1, 3, 5, 7, 6]

e.g.2 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. (Leetcode: Longest Consecutive Sequence)

  1. Given [6, 4, 8, 1, 3, 27],
  2. The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

一个好的习惯是walkthrough这个test case观察自己的思维过程。
1. 前驱子问题的解 + 当前节点这个增量 => 新的子问题的解
2. 需要什么前驱子问题的信息?上界和下界

  1. struct Bound{
  2. int high;
  3. int low;
  4. Bound(int h = 0 , int l = 0){
  5. high = h;
  6. low = l;
  7. }
  8. };
  9. class Solution {
  10. public:
  11. int longestConsecutive(vector<int> &num) {
  12. // Note: The Solution object is instantiated only once and is reused by each test case.
  13. unordered_map<int,Bound> table;
  14. int local;
  15. int max_len = 0;
  16. for(int i = 0; i < num.size(); i++){
  17. if(table.count(num[i])) continue;
  18. local = num[i];
  19. int low = local, high = local;
  20. if(table.count(local-1))
  21. low = table[local-1].low;
  22. if(table.count(local+1))
  23. high = table[local+1].high;
  24. table[low].high = table[local].high = high; // 试一下如果第一条不赋值会怎么样 [1,2,0,1]
  25. table[high].low = table[local].low = low; // 再想一想,为什么我们只需要维护low和high这两条,而不用考虑这个范围内的value [1,2,3,4,,3]
  26. if(high - low + 1 > max_len)
  27. max_len = high - low + 1;
  28. }
  29. return max_len;
  30. }
  31. };

b.求最值或总和的问题,总是可以在update的过程中不断记录更新,而不用再次遍历。
也是一种从subproblem -> problem, 通过记录前驱子问题的解,而不需要再次遍历(只不过它只需要记录一个前驱子问题就可以了),就像上一个问题我们不需要再把这些bound重新遍历一遍

c.处理两个不等长的数组或string,总是可以以while( aIndex < aSize && bIndex < bSize )作为结束条件,再处理可能剩下的元素。

e.g. 1 Merge two sorted arrays into a new array

3.需要用数字或者bitset来映射/hash的情境, 可以利用进制数的正交性,即:数字的高位和低位是互相正交、独立的。或者反过来说,一个数用m进制来表示,只有唯一一种可能。

e.g. 1 Design a hash function that is suitable for words in a dictionary.

hash对象的特征是什么? 1. word不会很长 2.每一位的可能性非常有限且离散

e.g. 2 A hash function for the state of a chess game.

常识:对于一次transition,能够简单地转换hash ()

e.g. 3 Implement a method rand7() given rand5(). (课后思考)

4.3 字符串问题

1.对于要求in-place的删除或修改,可以用两个int变量分别记录新index与原index,观察:如果改动后size增大,则先resize(int),再倒序赋值;反之,则先顺序赋值,再resize.

e.g. 1 Given input "Mr John Smith", output "Mr%20John%20Smith"
e.g. 2 Given input "Mr%20John%20Smith" , output "Mr John Smith"
e.g. 3 Given two sorted arrays, merge B into A in sorted order.

2.对于简单修改长字符串的问题,通常可以顺序或倒序一次遍历,在O(n)内解决。对于分段处理的情况,则使用两个int变量记录段首、段尾Index来处理(slicing window)。 可以利用C++ string类的 += 操作符来增量输出结果。

e.g.1 Given input -> "I have 36 books, 40 pens2."; output -> "I evah 36 skoob, 40 2snep."

用begin和end去标记window的初始和终止点,这两个总是核心变量;建议用 while(end < str.size()) 作为循环形式而不是 for loop 因为begin和end每次的增量未必是1.

e.g.2 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). (Leetcode: Minimum Window Substring)
典型的将复杂问题划归为简单问题的思维过程:4.2中的newspaper -> message 问题以及最值问题的结合,总体上又是用分段策略

  1. string minWindow(string S, string T) {
  2. if(S.size() < T.size()) return string();
  3. unordered_map<char,int> table;
  4. int begin = 0, end = 0;
  5. int min_window = S.size()+1, min_begin;
  6. for(auto it = T.begin(); it != T.end(); ++it)
  7. ++table[*it];
  8. int cnt = 0;
  9. for(int end = 0; end < S.size(); end++){
  10. if( table.count(S[end]) == 0 ) continue;
  11. if( table[ S[end] ] > 0)
  12. cnt++;
  13. --table[ S[end] ];
  14. if( cnt == T.size() ){
  15. while( table.count(S[begin]) == 0 || table[ S[begin] ] < 0){ // 注意时间复杂度仍然是O(n)
  16. if(table.count(S[begin]) > 0 )
  17. ++table[ S[begin] ];
  18. // 处理字符串至少固定一端
  19. begin++;
  20. }
  21. // 最值的追踪
  22. if(end-begin+1 < min_window){
  23. min_begin = begin;
  24. min_window = end - begin +1;
  25. }
  26. }
  27. }
  28. if(min_window > S.size())
  29. return "";
  30. else
  31. return S.substr(min_begin, min_window);
  32. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注