大数据BigData

[zhangsong246]

准备大数据面试笔试相关 http://www.hawstein.com/posts/ctci-solutions-contents.html

[zhangsong246]

1.字符串是否出现的重复字符

首先要考虑字符的编码，是26个字母还是ASCII字符(256)个？ 用bool值表征每个字符的出现，遍历字符串，判断是否重复出现

bool mem[256]; memset(mem, 0, sizeof(mem)); int len = str.length(); for(int i = 0; i < len; i++){ if(mem[(int)str[i]]){ return true; }else{ mem[i] = true; } return true; }

位运算，节省空间，256个bool变量，可以使用8长度的int数组 除32得到数组下标，取余得到数组元素中int相应的位

int mem[8]; memset(mem, 0, sizeof(mem)); int len = str.length(); for(int i = 0; i < len; i++){ int index = ((int)str[i])/32; int bit = ((int)str[i])%32; if(mem[i] & (1 << bit)){ return true; }else{ mem[i] |= (1 << bit); } return true; }

如果是字母，只需一个整形数即可

This is because the post-increment operator (i.e., itr++) is more expensive than pre-increment operator (i.e., ++itr). The underlying implementation of the post-increment operator makes a copy of the element before incrementing it and then returns the copy.

[zhangsong246]

2.C风格字符串反转

考虑C风格字符串末尾的结束符'\0' 交换使用三次^异或等于

void swap(char &a, char &b){ a ^= b; b ^= a; a ^= b; } void reverse(char* s){ if(!s)return; char _p = s, q = s; while(q)++q; --q; while(p < q){ swap(_p++, q++); } }

或者根据长度来交换：

void swap(char &a, char &b){ a ^= b; b ^= a; a ^= b; } void reverse(char* s){ int len = strlen(s); for(int i = 0; i < len/2; i++) swap(s[i], s[len-i-1]); }

[zhangsong246]

3.不开辟数组，移除重复字符

不允许开辟数组，是指不能做数组的拷贝，还是能开辟一个与问题规模无关的数组 O(n^2 )的代码：

void replace(char s[]){ int len = strlen(s); if(len < 2)return; int p = 0; for(int i = 0; i < len; ++i){ if(s[i] != '\0'){//避开'\0'字符 s[p++] = s[i];//对之前的'\0'位置重新赋值 for(int j = i+1; j < len; ++j){ if(s[i] == s[j])s[j] = '\0';//对之后的重复位置赋'\0'值 } } s[p] = '\0';//最后一个有效位置'\0' } }

开辟数组的方法：

void removeDuplicate(char s[]) { int len = strlen(s); if(len < 2) return; bool c[256]; memset(c, 0, sizeof(c)); int p = 0; for(int i=0; i < len; ++i) { if(!c[s[i]]) { s[p++] = s[i]; c[s[i]] = true; } } s[p] = '\0';
}

O(n)时间复杂度，使用int替代bool数组

void removeDuplicate(char s[]) { int len = strlen(s); if(len < 2) return; int check = 0, p = 0; for(int i=0; i < len; ++i) { int v = (int)(s[i]-'a'); if((check & (1 << v))==0) { s[p++] = s[i]; check |= (1 << v); } } s[p] = '\0'; }

[zhangsong246]

4.判断两个字符串是否是变位词(字符出现相同，位置不同)

O(nlogn)+O(n)时间 先排序O(nlogn)，然后比较O(n)

bool isAnagram(string s1, string t){ if(s=="" || t=="") return false; if(s.length() != t.length()) return false; sort(s.begin(), s.end());
sort(t.begin(), t.end());
if(s == t) return true; else return false; }

O(n)时间 统计字符串中字符出现的次数，各个字符出现的次数一样是变位词，开辟一个辅助数组来保存

bool isAnagram(string s, string t){ if(s=="" || t=="") return false; if(s.length() != t.length()) return false; int len = s.length(); int c[256]; memset(c, 0, sizeof(c)); for(int i = 0; i < len; ++i){ ++c[(int)s[i]] --c[(int)t[i]]; } for(int i=0; i<sizeof(c); ++i) if(c[i] != 0) return false; return true; }

[zhangsong246]

5.字符串空格字符替换为多个字符

遍历字符串，得到替换后的串长度，然后从后往前进行替换

char* replace1(char _c){ if(c == NULL) return NULL; int len = strlen(c); if(len == 0) return NULL; int cnt = 0; for(int i=0; i<len; ++i) { if(c[i] == ' ') ++cnt; } char *cc = new char[len + 2_cnt + 1]; int p = 0; for(int i=0; i<len; ++i) { if(c[i] == ' ') { cc[p] = '%'; cc[p+1] = '2'; cc[p+2] = '0'; p += 3; } else { cc[p] = c[i]; ++p; } } cc[p] = '\0'; return cc; }

void replace2(char _c){ if(c == NULL) return; int len = strlen(c); if(len == 0) return; int cnt = 0; for(int i=0; i<len; ++i) { if(c[i] == ' ') ++cnt; } int p = len + 2_cnt; c[p--] = '\0';//the space must be allocated first. for(int i=len-1; i>=0; --i) { if(c[i] == ' ') { c[p--] = '0'; c[p--] = '2'; c[p--] = '%'; } else { c[p] = c[i]; --p; } } }

[zhangsong246]

6.图像N*N矩阵就地旋转90度

分两步，第一步交换主对角线元素，第二步交换第i行和第n-i-1行元素

void swap(int &a, int &b){ int t = a; a = b; b = t; } void transpose(int a[][4], int n){ for(int i=0; i<n; ++i) for(int j=i+1; j<n; ++j) swap(a[i][j], a[j][i]); for(int i=0; i<n/2; ++i) for(int j=0; j<n; ++j) swap(a[i][j], a[n-i-1][j]); } int main(){ int a[4][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} }; for(int i=0; i<4; ++i){ for(int j=0; j<4; ++j) cout<<a[i][j]<<" "; cout<<endl; } cout<<endl; transpose(a, 4); for(int i=0; i<4; ++i){ for(int j=0; j<4; ++j) cout<<a[i][j]<<" "; cout<<endl; } return 0; }

[zhangsong246]

矩阵零元素所在的行和列都置零

开辟两个数组，纪录零元素出现的行号和列号

void zero(int **a, int m, int n){ bool row[m], col[n];
memset(row, false, sizeof(row)); memset(col, false, sizeof(col));
for(int i=0; i<m; ++i) for(int j=0; j<n; ++j) if(a[i][j] == 0){ row[i] = true; col[j] = true; } for(int i=0; i<m; ++i) for(int j=0; j<n; ++j) if(row[i] || col[j]) a[i][j] = 0; }

[zhangsong246]

8.借助存在的subString函数一次，判断一个字符串是否是另一个字符串的旋转字符串

如果进行旋转，每次都要调用subString判断，不进行旋转，考虑将a串变长，才能使用subString，而s1+s1符合要求：如果s2是s1+s1的子串，则s2是s1的旋转字符串

bool isSubstring(string s1, string s2){ if(s1.find(s2) != string::nops)return true; else return false; } bool isRotation(string s1, string s2){ if(s1.length() != s2.length() || s1.length()<=0) return false; return isSubstring(s1+s1, s2); }

int main(){ string s1 = "apple"; string s2 = "pleap"; cout<<isRotation(s1, s2)<<endl; //cout<<string::npos<<endl; return 0; }

[zhangsong246]

9. 从一个未排序的链表中移除重复的项，如果不使用临时缓存，如何解决？

使用hash，可以用一个数组模拟，数组要开的很大，可能会造成空间浪费。

void removedulicate(node head){ if(head==NULL) return; node p=head, q=head->next; hash[head->data] = true; while(q){ if(hash[q->data]){ node t = q; p->next = q->next; q = p->next; delete t; } else{ hash[q->data] = true; p = q; q = q->next; } } } 不使用临时缓存的方法： 时间复杂度O(n^2 )，两个指针，两层遍历

void removedulicate1(node head){ if(head==NULL) return; node p, q, c = head; while(c){ p = c; q = c->next; int d = c->data; while(q){ if(q->data==d){ node *t = q; p->next = q->next; q = q->next; delete t; } else{ p = q; q = q->next; } } c = c->next; } }

[zhangsong246]

10.求单链表倒数第n个节点

node pp; int nn; void findNthToLast1(node head){ if(head==NULL) return; findNthToLast1(head->next); if(nn==1) pp = head; --nn; }

定义两个指针，距离为n，在单链表上移动

node* findNthToLast(node head, int n){ if(head==NULL || n < 1) return NULL; node p=head, *q=head; while(n>0 && q){ q = q->next; --n; } if(n > 0) return NULL; while(q){ p = p->next; q = q->next; } return p; }

[zhangsong246]

11.仅有指向该节点的指针，实现一个算法删除单链表的节点

不能直接删除c，就只有删除后面的d节点，同时将d节点的数据赋值给c 考虑1-头节点，2-中间节点，3-尾节点，4-空

bool remove(node c){ if(c==NULL || c->next==NULL)return false; node q = c->next; c->data = q->data; c->next = q->next; delete q; return true; }

[zhangsong246]

12.由单链表逆序表示的数，每一个节点表示一位，写一个函数返回相加结果，同样表示方式

include

using namespace std;

typedef struct node{ int data; node *next; }node;

node* init(int a[], int n){ node head=NULL, p; for(int i=0; i<n; ++i){ node *nd = new node(); nd->data = a[i]; if(i==0){ head = p = nd; continue; } p->next = nd; p = nd; } return head; }

node* addlink(node p, node q){ if(p==NULL) return q; if(q==NULL) return p; node res = NULL, pre ＝ NULL; int c = 0; while(p && q){ int t = p->data + q->data + c; node r = new node(); r->data = t%10; if(pre){ pre->next = r; pre = r; } else pre = res = r; c = t/10; p = p->next; q = q->next; } while(p){ int t = p->data + c; node r = new node(); r->data = t%10; pre->next = r; c = t/10; pre = r; p = p->next; } while(q){ int t = q->data + c; node r = new node(); r->data = t%10; pre->next = r; pre = r; c = t/10; q = q->next; } if(c>0){//当链表一样长，而又有进位时 node r = new node(); r->data = c; pre->next = r; r->next = NULL; } return res; }

void print(node *head){ while(head){ cout<data<<" "; head = head->next; } cout<<endl; }

int main(){ int n = 4; int a[] = { 1, 2, 9, 3 }; int m = 3; int b[] = { 9, 9, 2 };

node p = init(a, n); node q = init(b, m); node *res = addlink(p, q); if(p) print(p); if(q) print(q); if(res) print(res); return 0; }

[zhangsong246]

13.寻找链表中出现环的节点

第一种方法比较tricky，需要复杂的数学演算 第二种方法使用map作为hash表，将节点放入map，map是由RB-tree组织

map<node, bool> hash; node* loopstart1(node head){ while(head){ if(hash[head])return head; else{ hash[head] = true; head = head->next; } } return head; }

[zhangsong246]

14.用一个数组实现三个栈

class stack3{ public: stack3(int size = 300){ buf = new int[size_3]; ptop[0]=ptop[1]=ptop[2]=-1; this->size = size; } ~stack3(){ delete[] buf; } void push(int stackNum, int val){ int idx = size_stackNum + ptop[stackNum] + 1; buf[idx] = val; ++ptop[stackNum]; } void pop(int stackNum){ --ptop[stackNum]; } int top(int stackNum){ int idx = stackNum*size + ptop[stackNum]; return buf[idx]; } bool empty(int stackNum){ return ptop[stackNum] == -1; }

private: int *buf; int ptop[3]; int size; };

[zhangsong246]

15.实现一个栈，还能实现min函数，时间复杂度都是O(1)

最直接的反应是用一个变量来保存当前栈的最小值，但是一个变量没法解决这个问题，增加变量，每个节点除了保存当前的值，再保存当前节点到栈底节点的最小值。

const int MAX_INT = ~(1<<31);//2147483647

typedef struct node{ node():val(0),min(MAX_INT){} int val, min; }node;

class StackWithMin{ public: StackWithMin(int size=1000){ buf = new node[size]; cur = 0; } ~StackWithMin(){ delete[] buf; } void push(int val){ buf[++cur].val = val; if(val < buf[cur].min) buf[cur].min = val; else buf[cur].min = buf[cur-1].min; } void pop(){ --cur; } int top(){ return buf[cur].val; } bool empty(){ return cur==0; } int min(){ return buf[cur].min; }

private: node *buf; int cur; };

充分减少拷贝的方法：

class stack{ public: stack(int size=1000){ buf = new int[size]; cur = -1; } ~stack(){ delete[] buf; } void push(int val){ buf[++cur] = val; } void pop(){ --cur; } int top(){ return buf[cur]; } bool empty(){ return cur==-1; }

private: int *buf; int cur; };

class StackWithMin1{ public: StackWithMin1(){

}
    ~StackWithMin1();
void push(int val){
    s1.push(val);
    if(val<=min())
        s2.push(val);
}
void pop(){
    if(s1.top()==min())
        s2.pop();
    s1.pop();
}
int top(){
    return s1.top();
}
bool empty(){
    return s1.empty();
}
int min(){
    if(s2.empty()) return MAX_INT;
    else return s2.top();
}

private: stack s1, s2; };