問題一：
給定一個最多包含40億個隨機排列的32位整數(shù)的順序文件，找出一個不在文件中的32位整數(shù)。在具有足夠內(nèi)存的情況下，如何解決該問題？如果有幾個外部的“臨時”文件可用，但是僅有幾百字節(jié)的內(nèi)存，又該如何解決該問題？
先考慮有足夠的內(nèi)存，我們可以采用位圖技術(shù)，即使用536870912個8位字節(jié)形成的位圖來表示已看到的整數(shù)。最后再對位圖遍歷一遍，找到某個位為0即可。實現(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;
}
然而，該問題還問到在僅有幾百個字節(jié)內(nèi)存和幾個稀疏順序文件的情況下如何找到缺失的整數(shù)？我們從表示每個整數(shù)的32位的視角來考慮二分搜索。算法的第一趟（最多）讀取40億個輸入整數(shù)，并把起始位為0的整數(shù)寫入一個順序文件，并把起始位為1的整數(shù)寫入另一個順序文件為1寫入另一個順序文件。這兩個文件中，有一個文件最多包含20億個整數(shù)，我么接下來將該文件用作當前輸入并重復(fù)探測過程，但這次探測的是第二個位。如果原始的輸入文件包含n個元素，那么第一趟將讀取n個整數(shù)，第二趟最多讀取n/2個整數(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)) { //將當前位為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;
}
問題二
將一個n元一維向量向左旋轉(zhuǎn)i個位置。例如，當n=8且i=3時，向量abcdefgh旋轉(zhuǎn)為defghabc。
方法一：
首先移動x[0]到臨時變量t，然后移動x[i]至x[0]，x[2i]至x[i]，依次類推(x中的所有下標對n取模)，直至返回到取x[0]中的元素，此時改為從t取值然后終止過程。如果該過程沒有移動全部元素，就從x[1]開始再次進行移動，直到所有的元素都已經(jī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其實就是交換向量ab的兩端，得到向量ba。這里a表示x中的前i個元素。假設(shè)a比b短。將b分為bl和br，使得br具有與a相同的長度。交換a和br，也就是將ablbr轉(zhuǎn)換為brbla。序列a此時已經(jīng)處于其最終的位置，因此現(xiàn)在的問題就集中到交換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中獲取對應(yīng)的存放位置。因為存放位置可能有多個，我們需要每個都去判斷是不是屬于它的存放位置。參考代碼如下：
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); //計算對應(yīng)的hash值
unordered_map<int, vector<int>>::iterator pos;
unordered_map<int, vector<int>>::iterator end = mapper.end();
//若沒有找到，則將其放在列表的最后一個位置
if ((pos = mapper.find(hashVal)) == end) {
putInEnd(result, mapper, hashVal, str);
} else {
//找到后需要逐個判斷是否屬于它的存放位置
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;
}
};
方法二
我們可以標識字典里的每一個詞，使得在相同變味詞類中的單詞具有相同的標識。然后，將具有相同標識的單詞集中在一起。這將原始的變味詞問題簡化為兩個子問題：選擇標識和集中具有相同的單詞。
對于第一個問題，我們可以使用基于排序的標識：將單詞中的字母表順序排列。"deposit"的標識就是"deiopst"，這也是"dopiest"和其他任何該類單詞的標識。要解決第二個問題，我們將所有的單詞按照其標識的順序排序。
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;
}
