锐客网

  1. 首页 > it技术 > >

《编程珠玑》第2章三个问题

问题一：

给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？
先考虑有足够的内存，我们可以采用位图技术，即使用536870912个8位字节形成的位图来表示已看到的整数。最后再对位图遍历一遍，找到某个位为0即可。实现代码如下：
#define BITSPERWORD 32 #define SHIFT 32 #define MASK 0x1F #define N 4000000000int a[1 + N / BITSPERWORD]; void set(int i) { a[i >> SHIFT] |= (1 << (i & MASK)); }void clr(int i) { a[i >> SHIFT] &= ~(1 << (i & MASK)); }int test(int i) { return a[i >> SHIFT] & (i << (i &MASK)); }int main(void) { int i; for (i = 0; i < N; i++) { clr(i); } while (scanf("%d", &i) != EOF) { set(i); } for (i = 0; i < N; i++) { if (test(i)) { printf("%d\n", i); } } return 0; }

然而，该问题还问到在仅有几百个字节内存和几个稀疏顺序文件的情况下如何找到缺失的整数？我们从表示每个整数的32位的视角来考虑二分搜索。算法的第一趟（最多）读取40亿个输入整数，并把起始位为0的整数写入一个顺序文件，并把起始位为1的整数写入另一个顺序文件为1写入另一个顺序文件。这两个文件中，有一个文件最多包含20亿个整数，我么接下来将该文件用作当前输入并重复探测过程，但这次探测的是第二个位。如果原始的输入文件包含n个元素，那么第一趟将读取n个整数，第二趟最多读取n/2个整数，以此类推。参考代码如下：
int split(int* a, int* b, int*c, int alen, int bit) { int biter, citer, i; int v=0, re = 0, *t; while(bit--){ //bit从32开始 v = (1 << bit); for(i=biter=citer=0; i < alen; i++) { if(a[i] & (1<

【《编程珠玑》第2章三个问题】问题二
将一个n元一维向量向左旋转i个位置。例如，当n=8且i=3时，向量abcdefgh旋转为defghabc。
方法一：
首先移动x[0]到临时变量t，然后移动x[i]至x[0]，x[2i]至x[i]，依次类推(x中的所有下标对n取模)，直至返回到取x[0]中的元素，此时改为从t取值然后终止过程。如果该过程没有移动全部元素，就从x[1]开始再次进行移动，直到所有的元素都已经移动为止。参考代码如下：
void rotate(int *nums, int len, int rotdist) { int i; for (i = 0; i < gcd(rotdist, len); i++) { int t = nums[i]; int j = i; while (true) { int k = (j + rotdist) % len; if (k == i) { break; } nums[j] = nums[k]; j = k; } nums[j] = t; } }

方法二：
旋转向量x其实就是交换向量ab的两端，得到向量ba。这里a表示x中的前i个元素。假设a比b短。将b分为bl和br，使得br具有与a相同的长度。交换a和br，也就是将ablbr转换为brbla。序列a此时已经处于其最终的位置，因此现在的问题就集中到交换b的两部分。由于新问题与原来的问题具有相同的形式，我们可以递归得解决之。参考代码如下：
void swap(string &str, int leftBegin, int rightBegin, int count) { while (count--) { char temp = str[leftBegin]; str[leftBegin] = str[rightBegin]; str[rightBegin] = temp; leftBegin++; rightBegin++; } }void rotate(string &str, int rotdis) { int len = (int) str.size(); int i = rotdis; int p = rotdis; int j = len - rotdis; while (i != j) { if (i > j) { swap(str, p - i, p, j); i -= j; } else { swap(str, p - i, p + j - i, i); j -= i; } } swap(str, p - i, p, i); }

给定一个英语词典，找出其中的所有变味词集合。例如，"pots"、"stop"、"tops"互为变味词，因为每一个单词都可以通过改变其他单词中字母的顺序来得到。
方法一
我们可以计算每个单词的hash值，如果是变味词，可以保证hash值肯定相同。但并不能保证相同的hash值就一定是变味词，有可能两个单词不是变味词，但恰好具有相同的hash值，这个时候就需要解决冲突，类似于散列表中的散列冲突。我们可以用一个map的key来保存单词的hash值，value保存该hash值的单词保存的位置。因为某个hash值可能存在多种变味词，因此value本身是一个列表。比如有个单词A，首先计算A的hash值，然后用hash值从map中获取对应的存放位置。因为存放位置可能有多个，我们需要每个都去判断是不是属于它的存放位置。参考代码如下：
class Solution { private: int prime[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}; public: vector groupAnagrams(vector& strs) { unordered_map> mapper; vector result; for (string &str : strs) { int hashVal = caculateHashVal(str); //计算对应的hash值 unordered_map>::iterator pos; unordered_map>::iterator end = mapper.end(); //若没有找到，则将其放在列表的最后一个位置 if ((pos = mapper.find(hashVal)) == end) { putInEnd(result, mapper, hashVal, str); } else { //找到后需要逐个判断是否属于它的存放位置 vector &v = pos->second; bool isExist = false; for (int index : v) { string &str1 = result[index][0]; if (isSameGroup(str1, str)) { result[index].push_back(str); isExist = true; break; } } if (!isExist) { putInEnd(result, mapper, hashVal, str); }}} for (vector &v : result) { sort(v.begin(), v.end()); } return result; }int caculateHashVal(string &str) { int result = 0; for (char c : str) { int num = c - 'a'; result += num * prime[num]; } return result; }void putInEnd(vector &result, unordered_map> &mapper, int hashVal, string &str) { int len = result.size(); result.resize(len + 1); mapper[hashVal].push_back(len); result[len].push_back(str); }bool isSameGroup(string &str1, string &str2) { int len = str1.size(); if (str2.size() == len) { int flags[26]; memset(flags, 0, sizeof(int) * 26); for (char c : str1) { flags[c - 'a']++; } for (char c : str2) { flags[c - 'a']--; } for (int i = 0; i < 26; i++) { if (flags[i] != 0) { return false; } } return true; } return false; }};

方法二
我们可以标识字典里的每一个词，使得在相同变味词类中的单词具有相同的标识。然后，将具有相同标识的单词集中在一起。这将原始的变味词问题简化为两个子问题：选择标识和集中具有相同的单词。
对于第一个问题，我们可以使用基于排序的标识：将单词中的字母表顺序排列。"deposit"的标识就是"deiopst"，这也是"dopiest"和其他任何该类单词的标识。要解决第二个问题，我们将所有的单词按照其标识的顺序排序。
public List groupAnagrams(String[] strs) { HashMap> map = new HashMap<>(); for (String s : strs) { char[] ar = s.toCharArray(); Arrays.sort(ar); String sorted = String.valueOf(ar); List list = map.get(sorted); if (list == null) list = new ArrayList(); list.add(s); map.put(sorted, list); } List res = new ArrayList<>(); for (List l : map.values()) { Collections.sort(l); res.add(l); } return res; }

    推荐阅读


    上一篇：上海深夜食堂

    下一篇：技术实务（第一篇|技术实务：第一篇 消防基础知识 第三章 爆炸）