問(wèn)題一：
給定一個(gè)最多包含40億個(gè)隨機(jī)排列的32位整數(shù)的順序文件，找出一個(gè)不在文件中的32位整數(shù)。在具有足夠內(nèi)存的情況下，如何解決該問(wèn)題？如果有幾個(gè)外部的“臨時(shí)”文件可用，但是僅有幾百字節(jié)的內(nèi)存，又該如何解決該問(wèn)題？
先考慮有足夠的內(nèi)存，我們可以采用位圖技術(shù)，即使用536870912個(gè)8位字節(jié)形成的位圖來(lái)表示已看到的整數(shù)。最后再對(duì)位圖遍歷一遍，找到某個(gè)位為0即可。實(shí)現(xiàn)代碼如下：
#define BITSPERWORD 32
#define SHIFT 32
#define MASK 0x1F
#define N 4000000000
int 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;
}
然而，該問(wèn)題還問(wèn)到在僅有幾百個(gè)字節(jié)內(nèi)存和幾個(gè)稀疏順序文件的情況下如何找到缺失的整數(shù)？我們從表示每個(gè)整數(shù)的32位的視角來(lái)考慮二分搜索。算法的第一趟（最多）讀取40億個(gè)輸入整數(shù)，并把起始位為0的整數(shù)寫入一個(gè)順序文件，并把起始位為1的整數(shù)寫入另一個(gè)順序文件為1寫入另一個(gè)順序文件。這兩個(gè)文件中，有一個(gè)文件最多包含20億個(gè)整數(shù)，我么接下來(lái)將該文件用作當(dāng)前輸入并重復(fù)探測(cè)過(guò)程，但這次探測(cè)的是第二個(gè)位。如果原始的輸入文件包含n個(gè)元素，那么第一趟將讀取n個(gè)整數(shù)，第二趟最多讀取n/2個(gè)整數(shù)，以此類推。參考代碼如下：
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<<bit)) { //將當(dāng)前位為0和1的整數(shù)分到不同的數(shù)組
b[biter++] = a[i];
} else {
c[citer++] = a[i];
}
}
if(biter <= citer) {
re += v;
t = a;
a = b;
b = t;
alen = biter;
} else {
t = c;
c = a;
a = t;
alen = citer;
}
}
return re;
}
問(wèn)題二
將一個(gè)n元一維向量向左旋轉(zhuǎn)i個(gè)位置。例如，當(dāng)n=8且i=3時(shí)，向量abcdefgh旋轉(zhuǎn)為defghabc。
方法一：
首先移動(dòng)x[0]到臨時(shí)變量t，然后移動(dòng)x[i]至x[0]，x[2i]至x[i]，依次類推(x中的所有下標(biāo)對(duì)n取模)，直至返回到取x[0]中的元素，此時(shí)改為從t取值然后終止過(guò)程。如果該過(guò)程沒有移動(dòng)全部元素，就從x[1]開始再次進(jìn)行移動(dòng)，直到所有的元素都已經(jīng)移動(dòng)為止。參考代碼如下：
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;
}
}
方法二：
旋轉(zhuǎn)向量x其實(shí)就是交換向量ab的兩端，得到向量ba。這里a表示x中的前i個(gè)元素。假設(shè)a比b短。將b分為bl和br，使得br具有與a相同的長(zhǎng)度。交換a和br，也就是將ablbr轉(zhuǎn)換為brbla。序列a此時(shí)已經(jīng)處于其最終的位置，因此現(xiàn)在的問(wèn)題就集中到交換b的兩部分。由于新問(wèn)題與原來(lái)的問(wèn)題具有相同的形式，我們可以遞歸得解決之。參考代碼如下：
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);
}
給定一個(gè)英語(yǔ)詞典，找出其中的所有變味詞集合。例如，"pots"、"stop"、"tops"互為變味詞，因?yàn)槊恳粋€(gè)單詞都可以通過(guò)改變其他單詞中字母的順序來(lái)得到。
方法一
我們可以計(jì)算每個(gè)單詞的hash值，如果是變味詞，可以保證hash值肯定相同。但并不能保證相同的hash值就一定是變味詞，有可能兩個(gè)單詞不是變味詞，但恰好具有相同的hash值，這個(gè)時(shí)候就需要解決沖突，類似于散列表中的散列沖突。我們可以用一個(gè)map的key來(lái)保存單詞的hash值，value保存該hash值的單詞保存的位置。因?yàn)槟硞€(gè)hash值可能存在多種變味詞，因此value本身是一個(gè)列表。比如有個(gè)單詞A，首先計(jì)算A的hash值，然后用hash值從map中獲取對(duì)應(yīng)的存放位置。因?yàn)榇娣盼恢每赡苡卸鄠€(gè)，我們需要每個(gè)都去判斷是不是屬于它的存放位置。參考代碼如下：
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<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<int, vector<int>> mapper;
vector<vector<string>> result;
for (string &str : strs) {
int hashVal = caculateHashVal(str); //計(jì)算對(duì)應(yīng)的hash值
unordered_map<int, vector<int>>::iterator pos;
unordered_map<int, vector<int>>::iterator end = mapper.end();
//若沒有找到，則將其放在列表的最后一個(gè)位置
if ((pos = mapper.find(hashVal)) == end) {
putInEnd(result, mapper, hashVal, str);
} else {
//找到后需要逐個(gè)判斷是否屬于它的存放位置
vector<int> &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<string> &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<vector<string>> &result, unordered_map<int, vector<int>> &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;
}
};
方法二
我們可以標(biāo)識(shí)字典里的每一個(gè)詞，使得在相同變味詞類中的單詞具有相同的標(biāo)識(shí)。然后，將具有相同標(biāo)識(shí)的單詞集中在一起。這將原始的變味詞問(wèn)題簡(jiǎn)化為兩個(gè)子問(wèn)題：選擇標(biāo)識(shí)和集中具有相同的單詞。
對(duì)于第一個(gè)問(wèn)題，我們可以使用基于排序的標(biāo)識(shí)：將單詞中的字母表順序排列。"deposit"的標(biāo)識(shí)就是"deiopst"，這也是"dopiest"和其他任何該類單詞的標(biāo)識(shí)。要解決第二個(gè)問(wèn)題，我們將所有的單詞按照其標(biāo)識(shí)的順序排序。
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] ar = s.toCharArray();
Arrays.sort(ar);
String sorted = String.valueOf(ar);
List<String> list = map.get(sorted);
if (list == null) list = new ArrayList<String>();
list.add(s);
map.put(sorted, list);
}
List<List<String>> res = new ArrayList<>();
for (List<String> l : map.values()) {
Collections.sort(l);
res.add(l);
}
return res;
}
