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.

from job.

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]);
}

from job.

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';
}

from job.

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;
}

from job.

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;
}
}
}

from job.

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;
}

from job.

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

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

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;
}

from job.

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;
}

from job.

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;
}
}

from job.

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;
}

from job.

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;
}

from job.

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;
}

from job.

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;
}

from job.

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;
};

from job.

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;
};

from job.