C语言

一、二进制和位运算——异或的高端操作

### 问题导入：

袋子里一共有a个白球，b个黑球，每次从袋子里拿2个球，每个球每次被拿出的机会均等，如果拿出的是2个白球、或者2个黑球，那么就往袋子中重新放入一个白球，如果拿出的是1个白球和1个黑球，那么就往袋子中重新放入1个黑球。那么最终袋子中一定只会有1个球，请问最终的球是黑球的概率是多少？用a和b来表达这个概率。

答案：

==若原始黑球数量为偶数，则最终的球是黑球的概率为0%，若原始黑球数量为奇数，则最终的球是黑球的概率为100%。完全和白球的数量无关，通过异或运算的性质解决。==

1.异或运算性质：

1)异或运算就是无进位相加，即1与0异或为1，0与0、1与1异或为0例：(8位)A:01101110 B:10011101 则C=A ^ B:11110011

2)异或运算满足交换律、结合律,即同一批数字，无论异或顺序如何，结果都一致。

3)0 ^ n=n,n ^ n=0

4)整体异或和(所有数字异或的结果)如果为x,若整体其中某个部分的异或和为y,则剩下部分的异或和为x ^ y,例：c=a ^ b,a=c ^ b,b=a ^ c

==性质4在算法中的用处较多==

2.题解：

将白球看作0，黑球看作1。即0与1相遇产生1，0与0、1与1相遇均产生0，即为异或运算。则问题根据异或运算的性质，问题可以转化为，a个0同b个1作异或运算的结果。因此当b为偶数时，最终异或结果为0，为白球，概率为0%；当b为奇数时，最终异或结果为1，为黑球，概率为100%。

3.异或运算的骚操作：

1).交换两个数：

//前提：a和b各有各自不同的内存空间，比如：数组中的交换，若i！=j则方法成立，否则方法不成立，得到的交换结果始终为0.
int a=10;
int b=20;
a=a^b;
b=a^b;
a=a^b;

2).不用任何判断语句和比较操作，返回两个数的最大值：

int flip(int n){
    return n^1;
}
//非负数返回1
//负数返回0
int sign(int n){ 
    flip((unsigned int)n>>31);
    //保证无符号右移
}//获取某一个数的符号位的数字
int getMax(int a,int b){
    //c可能溢出
    int c=a-b;
    //a的符号
    int signa=sign(a);
    //b的符号
    int signb=sign(b);
    //c的符号
    int signc=sign(c);
    //判断a与b的符号是否相同
    int is_diffab=signa^signb;
    int is_sameab=flip(is_diffab);
    //return a；只存在两种情况
    //1.a、b不一样时，a为非负数，即is_diffab为1时signa同时也为1
    //2.a、b一样时，c为非负数，即is_sameab为1的同时signc也为1，
    //也即数字逻辑电路中的与或门的组合
    int returna=is_diffab*signa+is_sameab*signc;//返回部分中a数所占的比例
    int returnb=flip(returna);//返回部分中b数所占的比例
    return a*returna+b*returnb;
}

3). 找到缺失的数字:

0到10，11个数中缺一个数，求缺失的数字是多少？

运用异或的运算性质，==总异或和去异或数组中有的数字的异或和==得到的结果即为所缺的那一个数字。

4).找出数组中唯一出现奇数次的数字:

遍历整个数组的同时用一个变量ans（初始化为0）存储数组中按序异或即最终异或和，该数即为所求。运用到了==异或的偶消奇留==的性质。

5).骚操作

①Brian Kernighan算法——提取出二进制状态中最右侧的1

n&(~n+1)或(n&(-n))

②数组中有2种数出现了奇数次，其他的数都只出现了偶数次，返回这2种出现了奇数次的数：a、b（a！=b，显然）

先用eor1将数组全部数字异或和存储得到的数即为a ^ b,根据a ^ b最右侧的1(假定为第i位)(采用Brian Kernighan算法)将数组中的数分为第i位为1和第i位为0的两个阵营，再遍历一遍数组，用eor2将第i位为1的数的异或和储存下来，则eor2为a和b中的一个数，用eor1去异或eor2则可得到另一个数。

code：

void findoddnum(int *nums,int len){
         int eor1=0;
         int i=0;
         for(i;i<len;i++){
             //nums中分别有a和b有奇数个，其他数均为偶数个`
             eor1^=nums[i];
         }
         //提取出最右侧的1
         int rightOne=eor1&(-eor1);
         int eor2=0;
         for(i=0;i<len;i++){
            if(nums[i]&rightOne==0){
               eor2^=nums[i]; 
            }
         } 
         printf("%d %d",eor2,eor1^eor2);
}

6).找出数组中唯一的出现次数小于m的数：

将数组中的数以二进制表示后将每一位的数相加并用一个数组储存每一位数相加和，最终在变量ans(初始化为0)上储存数组中每一位数相加和为m的整数倍的位上置0，不为m整数倍的位上置1，即可得到最终的数。

原理：

==数组一共有a1、a2、……an个数（去重后的），则记ai只出现了l次(l<m),其余的数都出现了m次，则在二进制表现下除了ai的其余数的1位相加得到必定为m的整数倍，由于ai只出现了l次，则最终二进制下所有位按位相加，ai出现1的位上的相加和不能整除m，会余l，因此在该位上ans置1，而相加和为0(所有数该位都为0)以及m的整数倍的位都代表ai在该位上为0，因此在该位上ans置0==。

code：

int findsmallnum(int * nums,int m,int len){
            int cnt[32]={0};
            //cnt[i]表示第i位上有多少个1
            int i=0;
            for(i;i<len;i++){
                int j;
                for(j=0;j<32;j++){
                    cnt[j]+=(nums[i]>>j)&1;
                    //将nums[i]的每一位都加到cnt中
                }
            }
            int ans=0;
            for(i=0;i<32;i++){
                if(cnt[i]%m!=0){
                    ans|=(1<<i);
                    //不是m的整数倍的位上置1，其余位上置0
                }
            }
            return ans;
}

二、位运算的骚操作

1.判断一个整数是否为2的幂：

借由Brian Kernighan算法，当n与二进制数只有n最右侧的1的位置上有1的数相同时，n为2的幂，且n要大于0：

code:

1
2
3

int is_twospow(int n){
	return n>0 && (n==n&(-n));
}

2.判断一个整数是否为3的幂（int范围内）：

code:

//如果一个数是3的幂，那么这个数一定只含有3这一个质数因子
//1162261467是int型范围内最大的3的幂，是3的19次幂
//因此1162261467只含有3这个质数因子，如果n也是只含有3这个质数因子，那么1162261467%n==0
//反之如果1162261467%n！=0，说明一定有其他的因子
int is_threespow(int n){
	return n>0 && 1162261467%n==0;
}

3.已知n为非负数，返回大于等于n的最小的2的幂：

code:

int minPoweroftwo(int n){
	if(n<=0){
	   return 1;
	   //2的幂从0开始算起，即从1开始
	}
    //若n大于0，则核心是得到n二进制最左边的一位的左侧一位置1，其余置0的数即可
    n--;//防止n刚好就是2的幂的情况
    n|=((unsigned int)n>>1);
	n|=((unsigned int)n>>2);
	n|=((unsigned int)n>>4);
	n|=((unsigned int)n>>8);
	n|=((unsigned int)n>>16);//将n-1的最左边的1右侧均置为1 
	return n+1;//最后通过加1进位得到所求答案
}

4.将区间[left,right]中的数全部&的结果：

code:

int AllAnd(int left,int right){
	while(left<right){
		  right-=right&(-right);
          //只要[left,right]区间上满足可使right最右位1改变该位上的1都会被&成0 
	}
	return right; 
}

5.将一个数按照其二进制逆序翻转得到新的数：

code:

int reverse(int n){
	n=((unsigned int)(n & 0xaaaaaaaa)>>1) | ((n & 0x55555555)<<1);
    //1对1交换次序，以8位为例：该步操作实现了：abcdefgh->badcfehg,((unsigned int)(n & 0xaaaaaaaa)>>1)得到0a0c0e0g;((n & 0x55555555)<<1)得到了b0d0f0h0
	n=((unsigned int)(n & 0xcccccccc)>>2) | ((n & 0x33333333)<<2);
    //2对2交换次序，以8位为例：该步操作实现了：badcfehg->dcbahgfe,((unsigned int)(n & 0xcccccccc)>>2)得到00ba00fe;((n & 0x33333333)<<2)得到了dc00hg00
	n=((unsigned int)(n & 0xf0f0f0f0)>>4) | ((n & 0x0f0f0f0f)<<4);
    //4对4交换次序，以8位为例：该步操作实现了：dcbahgfe->hgfedcba,((unsigned int)(n & 0xf0f0f0f0)>>4)得到0000dcba;((n & 0x0f0f0f0f)<<4)得到了hgfe0000
	n=((unsigned int)(n & 0xff00ff00)>>8) | ((n & 0x00ff00ff)<<8);//8对8交换同理 
	n=((unsigned int)n>>16) | (n<<16);//16对16交换同理
	return n;
}

6.求一个数的二进制表现形式有几个1:

code:

int searchnumone(int n){
	n=(n & 0x55555555)+((unsigned int)n>>1 & 0x55555555);
    //以8位为例：abcdefgh,(n & 0x55555555)得到0b0d0f0h,((unsigned int)n>>1 & 0x55555555)得到0a0c0e0g,二者相加得到每两位中以二进制形式表示这两位中原来的1的数目，例如如果a=1,b=1,则原来ab位上为11，处理后得到10为二进制形式 
	n=(n & 0x33333333)+((unsigned int)n>>2 & 0x33333333);
    //以8位为例：abcdefgh,(n & 0x33333333)得到00cd00gh,((unsigned int)n>>2 & 0x33333333)得到00ab00ef,同理得到4位形式的4位中的1的数量 
	n=(n & 0x0f0f0f0f)+((unsigned int)n>>4 & 0x0f0f0f0f);//同理 
	n=(n & 0x00ff00ff)+((unsigned int)n>>8 & 0x00ff00ff);//同理 
    n=(n & 0x0000ffff)+((unsigned int)n>>16 & 0x0000ffff);//同理，最终得到32位计算形式的1的数量 
	return n; 
}

三、位运算——位图

### 原理：

用bit组成的数组来存放值，用bit状态1、0代表存在、不存在，取值和存值操作都用位运算。限制是==必须为连续范围且不能过大==，好处是==极大的节省空间==，因为1个数字只占用1个bit的空间。

位图的实现：

Bitset(int n):初始化位图的大小，只支持0~n-1所有数字的增删查改

void add(int num):将num加入到位图中

void remove(int num):将num从位图中删除

void reverse(int num):如果位图里没有num，就加入：如果有就删除

int contains(int num):查询num是否在位图中

code:

//位图，利用1个整型数字的二进制位的0、1状态表示每32个数字是否在数组中，有点变相物理索引的感觉
int *arr=NULL;
int ones;//位图中所有1的个数
int zeros;//位图中所有0的个数 
int size;//位图大小 
bool is_reverse;//通过is_reverse变量控制是否翻转，当第一次翻转后，1表示不存在，而0表示存在 
void Bitset(int n){
 	 arr=(int *)malloc(sizeof(int)*((n+31)/32));
 	 int i;
     for(i=0;i<((n+31)/32);i++){
 		 arr[i]=0;
	 }
return ;
}
void add(int n){
 	 arr[n/32] |=1<<(n%32);
}
void remove0(int n){
	 arr[n/32] &=~(1<<(n%32));
}
void reverse(int n){
	 arr[n/32] ^=1<<(n%32);
}
int contains(int n){
	return ((((unsigned int)arr[n/32])>>(n%32))&1==1);
}
void fix(int i){
     int index=i/32;
     int rebit=i%32;
     if(!is_reverse){
    	//位图所有位维持原始含义
		//即0表示不存在，1表示存在
    	if((arr[index] & (1<<rebit))==0){
    		zeros--;
    		ones++;
    	    arr[index] |=(1<<rebit);
		}
		else{
			 if((arr[index] & (1<<rebit))!=0){
				 zeros--;
				 ones++;
				 arr[index] ^=(1<<rebit);
			  }
		     }
	  }
	  return ;
}
void unfix(int i){
	int index=i/32;
	int rebit=i%32;
	if(!is_reverse){
		if((arr[index] & (1<<rebit))!=0){
			ones--;
			zeros++;
			arr[index] ^=(1<<rebit);
		}
	}else{
		if((arr[index] & (1<<rebit))==0){
			ones--;
			zeros++;
			arr[index] |=(1<<rebit);
		}
	}
}
void flip(){
     is_reverse=!is_reverse;
     ones=ones^zeros;
     zeros=ones^zeros;
     ones=ones^zeros;
} 
int isAllone(){
		return ones==size;
}
int isleastone(){
		return (ones>=1);
}
int count(){
		return ones;
}

四、位运算——实现加减乘除：

### 加法：

利用每一步无进位相加即异或运算的结果 + 进位的结果（先作与运算再左移一位，即得到进位信息）不停计算，递归直到进位消失

code:

int oriadd(int x,int y){
	int ans=x;
	while(y!=0){
		ans=x^y;
		y=(x&y)<<1;
		x=ans;
	}
	return ans;//非递归版本 
}

减法：

code：

int neg(int n){//返回n的相反数 
	return oriadd(~n,1);
} 
int orisub(int x,int y){//x-y<==>x+(-y),-y:~y+1<==>oriadd(~y,1)
	return oriadd(x,neg(y));
}

乘法：

类似于小学的乘法过程

code:

int orimul(int x,int y){
	int ans=0;
	while(y!=0){
		if(y&1!=0){
			ans=oriadd(ans,x);
		}
		y=(unsigned int)y>>1;
		x<<=1;
	}
	return ans;
}

除法：

通过一位一位判断x是否含有y乘以2的i次方，来一位一位给ans置1，进而得到答案

code:

//需保证x和y都不是整数最小值即近似负无穷 
int oridiv(int x,int y){//x/y,允许x和y为负数 
	int signx=(x<0) ? neg(x):x;
	int signy=(y<0) ? neg(y):y; 
	int ans=0;
	int i;
	//为了规避溢出风险，y左移i位同x的比较，可以转化为x右移i位同y比较，这样做不存在溢出问题 
	for(i=30;i>=0;i=orisub(i,1)){
		if((unsigned int)signx>>i>=signy){
			signx=orisub(signx,(signy<<i));
			ans|=1<<i;
		}
	}
	return (x>0)^(y>0) ? neg(ans):ans;//ans表示x整除y的结果 
}

        ``}``  
 4.最大频率栈：
    栈的压入同一般栈相同，弹出时弹出离栈顶最近，且在栈中频率最大的值。次频表统计值在栈中一共出现的次数并且用一个栈数组来分层存储进入栈的值，加入进来的值存在栈数组中该值压入前在栈中的次数的位置，弹出时弹出最大出现次数的栈顶即可。
    code：
        `#define Maxsize 3240`
        `typedef struct node{`
            `int data;`
            `struct node * pNext;`
        `}NODE,*PNODE;`
        `typedef struct stack{`
            `PNODE pTop;`
            `PNODE pBottom;`
        `}STACK,*PSTACK;`
        `int maxnum=0;`
        `STACK array[Maxsize];//栈数组，用来实现按频率存储以及按频率弹出` 
        `int foo[Maxsize];//次频表，出现频率，frequency of occurrence` 
        `void initStack(PSTACK);`
        `void push(PSTACK,int);`
        `int pop();`
        `void initStack(PSTACK pS){`
            `pS->pTop=(PNODE)malloc(sizeof(NODE));`
            `pS->pBottom=pS->pTop;`
            `return ;`
        `}`
        `void push(PSTACK pS,int val){`
            `PNODE pNew=(PNODE)malloc(sizeof(NODE));`
            `pNew->data=val;`
            `pNew->pNext=pS->pTop;`
            `pS->pTop=pNew;`
            `return ;`
        `}`
        `int pop(){`
            `if(array[maxnum].pBottom==array[maxnum].pTop){`
                `if(maxnum>0){`
                    `maxnum--;`
                    `int hold=array[maxnum].pTop->data;`
                    `PNODE del=array[maxnum].pTop;`
                    `array[maxnum].pTop=del->pNext;`
                    `free(del);`
                    `return hold;`
                `}`
                `else{`
                    `return -1;`
                `}`
            `}`
            `else{`
                    `int hold=array[maxnum].pTop->data;`
                    `PNODE del=array[maxnum].pTop;`
                    `array[maxnum].pTop=del->pNext;`
                    `free(del);`
                    `return hold;`
                `}` 
        `}`

五、链表高频问题：

//用到的链表的结构体定义

typedef struct node{
	int data;
	struct node *pNext;
}NODE,*PNODE;

1.返回两个无环链表相交的第一个节点，若不相交则返回null

判断两个链表h1、h2(头结点)的走到尾结点e1、e2是否相等，相等即返回返回第一个相交的结点(利用长链表减去两链表长度差值，再同步移动h1、h2，判断h1与h2是否相同，第一个相同的即为第一个相交的节点)，不相等返回null。
#### code:

PNODE getIntersec(PNODE h1,PNODE h2){//h1、h2两个头结点 
	if(h1==NULL || h2==NULL){
		return NULL;
	}
	PNODE p=h1;
	PNODE q=h2;
	PNODE e1,e2;
	int len1=0;
	int len2=0;
	while(p!=NULL){
		e1=p;
		p=p->pNext;
		len1++;
	}
	while(q!=NULL){
		e2=q;
		q=q->pNext;
		len2++;
	}
	if(e1!=e2){
		return NULL;
	}
	else{
		while(len1>len2){
			h1=h1->pNext;
			len1--;
		} 
		while(len2>len1){
			h2=h2->pNext;
			len2--;
		}
		while(h1!=h2){
			h1=h1->pNext;
			h2=h2->pNext;
		}
		return h1;
	}
}

 ### 2.从链表头结点每k个一组翻转链表：

        #### code:

//从当前的p结点往下数k个找到当前组的结束结点并返回 
PNODE getEnd(PNODE pS,int k){
	PNODE p=pS; 
	while(p->pNext!=NULL && --k!=0){//先判断结点的next域是否为NULL，若为NULL则不进循环直接退出NULL前的一个结点便于后续r1或者r2的寻找；反之，若不为NULL则先--k,得到判断k-1后与0的关系，k为1时仍为该指针--k==0，跳出循环成立 
		p=p->pNext;
	}
	return p;
}
void reverse(PNODE p,PNODE q){
	PNODE pre=NULL;
	PNODE next=NULL;
	PNODE cur=p;
	PNODE nexth=q->pNext; 
	while(cur!=nexth){
		next=cur->pNext;//next指针始终指向当前讨论结点的下一个结点，便于cur结点的转移 
		cur->pNext=pre;//把cur结点的指针域翻转 
		pre=cur;//将cur用pre赋,这一个循环的cur结点就是下一个结点的pre 
		cur=next;//cur结点的转移 
	}
	p->pNext=nexth;//将这一组翻转后的尾结点同下一组的头结点连接起来 
	return ; 
}
PNODE reverseKgroup(PNODE head,int k){
	PNODE start=head;
	PNODE end=getEnd(start,k);
	if(end==NULL){
		return head;
	}//不足k个一组直接按原序返回 
	//第一组是比较特殊的，因为涉及到了换头的问题 
	head=end;
	reverse(start,end);
	//翻转后start变成了该组的尾结点 
	PNODE lastGroupEnd=start;//衔接翻转后头尾颠倒的问题 
	while(lastGroupEnd->pNext!=NULL){
		start=lastGroupEnd->pNext;
		end=getEnd(start,k);
		if(end==NULL){
			return head;
		}
		reverse(start,end);
		lastGroupEnd->pNext=end;
		lastGroupEnd=start;
	}//循环多次每次k个一组 
	return head; 
}

###  3.复制带有random指针的链表：

code：

typedef struct node{
	int data;
	struct node *pNext;
	struct node *random;//random指针可以是指向链表中任意结点的指针，也可以为NULL 
}NODE,*PNODE;//带随机指针的链表的结构体表达形式
PNODE initNode(PNODE p){
	if(p==NULL){
		p=(PNODE)malloc(sizeof(NODE));
		return p;
	}
	return p;
}
PNODE copyList(PNODE head){
	if(head==NULL){
		return NULL;
	}
	//采用将复制的结点加入到对应结点的next指针上的方式创建便于random指针域复制的索引
	PNODE cur=head;
	PNODE next=NULL;
	//将1->2->3->…变成1->1`->2->2`->3->3`->… 
    while(cur!=NULL){
     next=cur->pNext;
	 cur->pNext=initNode(cur->pNext);
	 cur->pNext->pNext=next;
	 cur=next;	
	}
	cur=head;
	PNODE copy=NULL;
	//利用创建的新老节点之间的结构关系，设置每一个新复制的结点的random指针 
	while(cur!=NULL){
		next=cur->pNext->pNext;
		copy=cur->pNext;
		copy->random=(cur->random==NULL)?NULL:(cur->random->pNext);
		cur=next;
	}
	PNODE ans=head->pNext;
	cur=head;
	//新老链表分离：老节点重新连在一起，新节点重新连在一起 
	while(cur!=NULL){
		next=cur->pNext->pNext;//next始终指向老链表中cur所指向节点的下一个节点 
		copy=cur->pNext;//copy指针为新链表中cur对应的复制节点 
		cur->pNext=next;
		copy->pNext=(cur->pNext==NULL)?NULL:(next->pNext);
		cur=next;
	}
	//返回新链表的头结点
	return ans; 
}

 ### 4.判断链表是否为回文结构：

       #### 技巧：

快慢指针求中点：慢指针和快指针一开始都指向头结点，慢指针一次跳一个，快指针一次跳两个，当快指针的next域为NULL或快指针为空时停止，此时慢指针指在近似中点的节点位置
#### code:

int is_Palidrome(PNODE head){
	//特判head为空和链表只有一个节点的情况，此时一定为回文结构 
	if(head==NULL || head->pNext==NULL){
		return 1;//1代表是回文结构 
	}
	PNODE slow=head;
	PNODE fast=head;
	//利用快慢指针的方法寻找链表的类似中点
	while(fast->pNext!=NULL && fast->pNext->pNext!=NULL){
		slow=slow->pNext;
		fast=fast->pNext->pNext;
	}
	//现在slow为链表的类似中点，从中点开始往后的结点开始逆序
	PNODE pre=slow;
	PNODE cur=pre->pNext;
	PNODE next=NULL;
	pre->pNext=NULL;
	while(cur!=NULL){
		next=cur->pNext;
		cur->pNext=pre;
		pre=cur;
		cur=next;
	} 
	//上述过程已完成了链表左右侧均向中间指
	//head……slow……pre 
	PNODE left=head;
	PNODE right=pre;
	int ans=1;
	while(left!=NULL && right!=NULL){
		if(left->data!=right->data){
			ans=0;//0代表不是回文结构 
            break;		
 		}
		left=left->pNext;
		right=right->pNext;
	}
	//将原链表调整辉原来的样子 
	cur=pre->pNext;
	pre->pNext=NULL;
	next=NULL;
	while(cur!=NULL){
		next=cur->pNext;
		cur->pNext=pre;
		pre=cur;
		cur=next;
	} 
	return ans; 
}

5.找链表的第一个入环节点，如果不存在环结构，就返回NULL：

code:

//仍采用快慢指针的方法，如果快指针的next域或者快指针的next域的next域为空，则返回NULL即无环结构；否则，当快慢指针相遇时，将快指针拨回链表头结点，快慢指针一起一步一步移动，再次相遇即为对应第一个入环的节点。（数学证明）
PNODE getEntercirnode(PNODE head){
    if(head==NULL || head->pNext==NULL || head->pNext->pNext==NULL){
    	return NULL;
	}
	PNODE slow=head;
	PNODE fast=head;
	while(slow!=fast){
		if(fast->pNext==NULL || fast->pNext->pNext==NULL){
			return NULL;
		}
		slow=slow->pNext;
		fast=fast->pNext->pNext;
	}
	fast=head;
	while(slow!=fast){
		slow=slow->pNext;
		fast=fast->pNext;
	}
	return slow;
}

6.在链表上排序。要求时间复杂度O(n*logn),额外空间复杂度O(1),还要求排序有稳定性，（在数组层面上不能实现）

code:

//从当前的p结点往下数k个找到当前组的结束结点并返回 
PNODE getEnd(PNODE pS,int k){
	PNODE p=pS; 
	while(p->pNext!=NULL && --k!=0){//先判断结点的next域是否为NULL，若为NULL则不进循环直接退出NULL前的一个结点便于后续r1或者r2的寻找；反之，若不为NULL则先--k,得到判断k-1后与0的关系，k为1时仍为该指针--k==0，跳出循环成立 
		p=p->pNext;
	}
	return p;
}
PNODE start;//每组排序后的头结点 
PNODE end;//每组排序后的尾结点 
//l1……r1->NULL:有序的左部分
//l2……r2->NULL:有序的右部分 
//整体merge在一起，并且保证有序
//将全局变量start设置为整体的头结点，全局变量end设置为整体的尾结点 
void merge(PNODE l1,PNODE r1,PNODE l2,PNODE r2){
	PNODE pre=NULL;
	//第一次比较同样特别处理，要将start指到整体的最小值节点上去 
	if(l1->data<=l2->data){
		start=l1;
		pre=l1;
		l1=l1->pNext;
	}else{
		start=l2;
		pre=l2;
		l2=l2->pNext;
	}
	while(l1!=NULL && l2!=NULL){
		if(l1->data<=l2->data){
			pre->pNext=l1;
			pre=l1;
			l1=l1->pNext;
		}else{
            pre->pNext=l2;
			pre=l2;
			l2=l2->pNext;		
		} 
	}
	if(l1!=NULL){
		pre->pNext=l1;
		end=r1;
	}//左部分更长，直接将已经排好序的接在末尾即可，并且是以r1作为尾结点end的 
	else{
		pre->pNext=l2;
		end=r2;
	}//右部分更长，直接将已经排好序的接在末尾即可，并且是以r2作为尾结点end的
	return ;
}
//为了使额外空间复杂度为O(1),不能使用递归，因为mergeSort递归需要O(logn)的额外空间 
PNODE perfectSort(PNODE head){
	int len=0;//获得链表长度 
	PNODE cur=head;
	while(cur!=NULL){
		len++;
		cur=cur->pNext;
	}
	//l1……r1 每组的左部分
	//l2……r2 每组的右部分
	//next 下一组的头结点
	//lastGroupEnd 上一组的尾结点
	PNODE l1,r1,l2,r2,next,lastGroupEnd;
	int step=1;
	for(step;step<len;step<<=1){
		//第一组很特殊，因为要决定整个链表的头结点，所以要单独处理
		l1=head;
		r1=getEnd(l1,step);
		l2=r1->pNext;
		r2=getEnd(l2,step);
		next=r2->pNext;
		r1->pNext=NULL;
		r2->pNext=NULL;
		merge(l1,r1,l2,r2);
		head=start;
		lastGroupEnd=end;
		while(next!=NULL){
			l1=next;
			r1=getEnd(l1,step);
			l2=r1->pNext;
			if(l2==NULL){
				lastGroupEnd->pNext=l1;
				break;
			}
			r2=getEnd(l2,step);
			next=r2->pNext;
			r1->pNext=NULL;
			r2->pNext=NULL;
			merge(l1,r1,l2,r2);
			lastGroupEnd->pNext=start;
			lastGroupEnd=end;
		} 
	}
	return head;
}

六、数据结构设计高频题：

 ### 1.LRU缓存：

最近最少使用缓存约束的数据结构

使用哈希表和双向链表实现

2.插入、删除、元素等概率随机获取时间复杂度均为O(1)的结构:

哈希map记录加入值和其在动态数组中的下标，随机获取时在哈希map中随机获取下标，得到相应的随机值

删除操作时用最后一个数去填删除的数来保证下标的连续，保证删除之后随机获取的随机性

若允许重复数字的加入，那可以采用哈希map中value采用集合的形式存储key在动态数组中一共出现过的下标，相应的remove时再删除的值同动态数组的最后一个值不同时，用动态数组中最后一个数值，来到删除位置，并在哈希mapvalue集合中进行下标的删除和插入；相同时，删除最后一个值即可。若remove后该值value集合已为空，那么应该在哈希map里删除该键值对。

3.快速获取数据流的中位数：

堆实现：大根堆加上小根堆，希望较小的一半都在大根堆里，而较大的一半都在小根堆里。若两个堆都为空，新来数字进大根堆。若至少一个不为空，则新来数字若小于等于大根堆的顶，其进入大根堆，反之进入小根堆。大小根堆大小差值大于等于2时，较小的一方应弹出堆顶进入另一个堆，两个堆大小之和为偶数时，中位数为两个堆堆顶数的平均数；为奇数时，中位数为大小为偶数一方的堆顶。
#### code:

#define Maxsize 3240
int bigHeap[Maxsize];
int smallHeap[Maxsize];
int bigSize;
int smallSize;
double midnum;//数据流的中位数 
void swap(int *array,int i,int j){
	int temp=array[i];
	array[i]=array[j];
	array[j]=temp;
	return ;
} 
void heapInsert(int *array,int i,int key){//堆的插入操作,key为1是为大根堆，key为2是为小根堆 
	if(key==1){
	while(array[i]>array[(i-1)/2]){//直到不比父节点的值大停止向上交换 
		swap(bigHeap,i,(i-1)/2);
		i=(i-1)/2;
	}
}
if(key==2){
	while(array[i]<array[(i-1)/2]){//直到不比父节点的值小停止向上交换 
		swap(smallHeap,i,(i-1)/2);
		i=(i-1)/2;
	}
}
	return ;
}
//i位置上的数发生变化后，堆的自我调整形成大顶堆或小顶堆 
void heapAdjust(int *array,int i,int key){
	if(key==1){
	int hold=i*2+1;//i结点的左孩子 
	while(hold<bigSize){
		int bigger=(hold+1<bigSize && array[hold+1]>array[hold])?(hold+1):hold;//右孩子存在且比左孩子大的情况下作为最大的孩子 
		bigger=array[bigger]>array[i]?bigger:i;
		if(bigger==i){
			heapInsert(bigHeap,i,1); 
			return ;
		}
	swap(bigHeap,i,bigger);
		i=bigger;
		hold=i*2+1;
	}
}
if(key==2){
	int hold=i*2+1;//i结点的左孩子 
	while(hold<smallSize){
		int smaller=(hold+1<smallSize && array[hold+1]<array[hold])?(hold+1):hold;//右孩子存在且比左孩子大的情况下作为最大的孩子 
		smaller=array[smaller]<array[i]?smaller:i;
		if(smaller==i){
			heapInsert(smallHeap,i,2); 
			return ;
		}
	swap(smallHeap,i,smaller);
		i=smaller;
		hold=i*2+1;
	}
}
	return ;
}
int pop(int *array,int size,int key){
    int hold=array[0];
	swap(array,0,size-1);
	size--;
	heapAdjust(array,0,key);
	return hold;	
}
int main()
{
	int n;
	scanf("%d",&n);
	int i=0;
	int x; 
	for(i;i<n;i++){
		scanf("%d",&x);
		if(bigSize==0 && smallSize==0){
			bigHeap[bigSize]=x;
			heapInsert(bigHeap,bigSize++,1);
			midnum=x;
		}else{
			if(x<=bigHeap[0]){
				bigHeap[bigSize]=x;
			heapInsert(bigHeap,bigSize++,1);
			}else{
				smallHeap[smallSize]=x;
				heapInsert(smallHeap,smallSize++,2);
			}
			if(bigSize-smallSize>=2){
				int temp=pop(bigHeap,bigSize,1);
				smallHeap[smallSize]=temp;
				heapInsert(smallHeap,smallSize++,2);
			}
			if(smallSize-bigSize>=2){
				int tempp=pop(smallHeap,smallSize,2);
					bigHeap[bigSize]=tempp;
			heapInsert(bigHeap,bigSize++,1);
			}
			if((bigSize+smallSize)%2==0){
				midnum=(double)(bigHeap[0]+smallHeap[0])/2;
			}
			else{
				midnum=(bigSize>smallSize)?bigHeap[0]:smallHeap[0];
			}
		}
		printf("%lf ",midnum);
	} 
	return 0;
}

4.最大频率栈：

栈的压入同一般栈相同，弹出时弹出离栈顶最近，且在栈中频率最大的值。次频表统计值在栈中一共出现的次数并且用一个栈数组来分层存储进入栈的值，加入进来的值存在栈数组中该值压入前在栈中的次数的位置，弹出时弹出最大出现次数的栈顶即可。

code:

#define Maxsize 3240
typedef struct node{
	int data;
	struct node * pNext;
}NODE,*PNODE;
typedef struct stack{
	PNODE pTop;
	PNODE pBottom;
}STACK,*PSTACK;
int maxnum=0;
STACK array[Maxsize];//栈数组，用来实现按频率存储以及按频率弹出 
int foo[Maxsize];//次频表，出现频率 
void initStack(PSTACK);
void push(PSTACK,int);
int pop();
void initStack(PSTACK pS){
	pS->pTop=(PNODE)malloc(sizeof(NODE));
	pS->pBottom=pS->pTop;
	return ;
}
void push(PSTACK pS,int val){
	PNODE pNew=(PNODE)malloc(sizeof(NODE));
	pNew->data=val;
	pNew->pNext=pS->pTop;
	pS->pTop=pNew;
	return ;
}
int pop(){
	if(array[maxnum].pBottom==array[maxnum].pTop){
		if(maxnum>0){
		maxnum--;
		int hold=array[maxnum].pTop->data;
		PNODE del=array[maxnum].pTop;
		array[maxnum].pTop=del->pNext;
		free(del);
		return hold;
	}
	else{
		return -1;
	}
	}
	else{
		int hold=array[maxnum].pTop->data;
		PNODE del=array[maxnum].pTop;
		array[maxnum].pTop=del->pNext;
		free(del);
		return hold;
	} 
}

七、二叉树高频题：

1.bfs的两种实现方式：

①队列加哈希表（表记录弹出结点的层数），根据哈希表中的数值与对应层数的关系在链表数组中进行处理。

②一次处理一层的方式：

1)拿当前队列的长度size

2)如下行为重复size遍：

（1）弹出队首结点放入其所在层的链表中。

（2）有左节点加左节点;有右节点加右节点

code:

#define Maxsize 3240
typedef struct btnode{
	int data;
	struct btnode *left,*right;
}BTNODE,*PBTNODE;
typedef struct list{
	int length;
	int array[Maxsize];
}LIST,*PLIST;
int l;
int r;
int count;
BTNODE queue[Maxsize];
PLIST linkList[Maxsize];
PBTNODE initBTree(PBTNODE pT,int val){
	if(pT==NULL){
		pT=(PBTNODE)malloc(sizeof(BTNODE));
		pT->data=val;
		pT->left=NULL;
		pT->right=NULL;
	}else{
		if(pT->data>=val){
			pT->left=initBTree(pT->left,val);
		}else{
			pT->right=initBTree(pT->right,val);
		}
	}
	return pT;
} 
void bfs(PBTNODE pRoot){
	if(pRoot!=NULL){
		l=r=0;//用[l,r)的左闭右开区间代表队列中的结点分布情况，l代表队首，r代表队尾的下一个结点 
        queue[r++]=*pRoot;
		count=1;//代表结点所在的层数
		while(l<r){
			int size=r-l;//队列长度
			int i=0;
			for(i;i<size;i++){//重复队列长度次可以将该层的所有结点都弹出 
			if(i==0){
				linkList[count]=(PLIST)malloc(sizeof(LIST));
			}
				BTNODE hold=queue[l++];
				printf("%d ",hold.data);
				linkList[count]->array[i]=hold.data;
				if(hold.left!=NULL){
					queue[r++]=*hold.left;
				}
				if(hold.right!=NULL){
					queue[r++]=*hold.right;
				}
			}
			linkList[count]->length=size;
			count++; 
		}		
	}
	return ;
}
int main()
{
	int n;
	PBTNODE PROOT=NULL;
	scanf("%d",&n);
	int i,x;
	for(i=0;i<n;i++){
		scanf("%d",&x);
		PROOT=initBTree(PROOT,x);
	}
	bfs(PROOT);
	printf("\n");
	int j;
	for(i=1;i<count;i++){
		for(j=0;j<linkList[i]->length;j++){
			printf("%d ",linkList[i]->array[j]);
		}
	}
	return 0;
 }

若要求锯齿状层次遍历二叉树，即相邻的两层的遍历左右次序不同，则队列加入结点的方式同上，弹出结点的方式改为如下：

 #####       code：

bool reverse=false;
//reverse == false,左->右:i+=1,l…r-1,收集size-1个
//reverse == true,右->左:i-=1,r-1…l,收集size-1个 
int i,j,k;
for(i=(reverse)?(r-1):l,j=(reverse)?(-1):1,k=0;k<size;i+=j,k++){
	BTNODE hold=queue[i];
	linkList[count]->array[i]=hold.data;
}
//每一层遍历结束后将reverse翻转即
reverse=!reverse;

2.最大特殊宽度：

code:

#define Maxsize 3240
typedef struct btnode{
	int data;
	struct btnode *left,*right;
}BTNODE,*PBTNODE;
int l;
int r;
int ans;
BTNODE nodeQueue[Maxsize];
int idQueue[Maxsize];
PBTNODE initBTree(PBTNODE pT,int val){
	if(pT==NULL){
		pT=(PBTNODE)malloc(sizeof(BTNODE));
		pT->data=val;
		pT->left=NULL;
		pT->right=NULL;
	}else{
		if(pT->data>=val){
			pT->left=initBTree(pT->left,val);
		}else{
			pT->right=initBTree(pT->right,val);
		}
	}
	return pT;
} 
void bfsOFfindbigspecialwidth(PBTNODE pT){
	ans=1;
	l=r=0;
	nodeQueue[r]=*pT;
	idQueue[r++]=1;
	while(l<r){
		int size=r-l;
		ans=(ans>(idQueue[r-1]-idQueue[l]+1))?ans:(idQueue[r-1]-idQueue[l]+1);
		int i=0;
		for(i;i<size;i++){
			BTNODE hold=nodeQueue[l];
			printf("%d ",hold.data);
			int id=idQueue[l++];
			if(hold.left!=NULL){
				nodeQueue[r]=*hold.left;
				idQueue[r++]=id*2;
			}
			if(hold.right!=NULL){
				nodeQueue[r]=*hold.right;
				idQueue[r++]=id*2+1;
			}
		}
	}
}

             ### 3.二叉树的最小高度（从头结点到所有叶节点的高度中的最小值）：

code：

#define Maxsize 3240 //以3240来代表数值范围内的最大值，以题目数据范围为准
typedef struct btnode{
	    int data;
	    struct btnode *left,*right;
}BTNODE,*PBTNODE;
int minDepth(PBTNODE pRoot){
	if(pRoot==NULL){
	//当前的树为空树 
	   return 0;
    }
    if(pRoot->left==NULL && pRoot->right==NULL){
	//pRoot指向叶节点
	   return 1; 
	}
	int ldeep=Maxsize;
	int rdeep=Maxsize;
	if(pRoot->left!=NULL){
	   ldeep=minDepth(pRoot->left);
	}
	if(pRoot->right!=NULL){
	   rdeep=minDepth(pRoot->right);
	}
	return ((ldeep<=rdeep)?ldeep:rdeep)+1;
}

4.二叉树的先序序列化和反序列化

要求将一棵二叉树的按照序列遍历转换成一串字符串，其中空结点由占位符”#”占用，再提供反序列化的方法。

code：

#define MAX_SIZE 1000

int count, index;
char preOrderStr[MAX_SIZE];

typedef struct BTNode {
    char val;
    struct BTNode* left;
    struct BTNode* right;
} BTNode, *PBTNode;

PBTNode createNode(PBTNode root, char val) {
    if (root == NULL) {
        PBTNode root = (PBTNode)malloc(sizeof(BTNode));
        root->val = val;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    else {
        if (root->val >= val) {
            root->left = createNode(root->left, val);
        }
        else {
            root->right = createNode(root->right, val);
        }
    }
} //建树的方式可以是题目所提供的，或者给一个根结点
void preOrder(PBTNode root) {
    if (root == NULL) {
        preOrderStr[count++] = '#';
        return;
    }
    preOrderStr[count++] = root->val;
    preOrder(root->left);
    preOrder(root->right);
}

PBTNode deserialize(PBTNode root) {
    if (preOrderStr[index] == '#') {
        index++;
        return NULL;
    }
    PBTNode newNode = (PBTNode)malloc(sizeof(BTNode));
    newNode->val = preOrderStr[index++];
    newNode->left = deserialize(newNode->left);
    newNode->right = deserialize(newNode->right);
    return newNode;
}

int main() {
    PBTNode root = NULL;
    char val;
    int i;
    int n;
    printf("Enter the number of nodes: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        printf("Enter the value of node %d: ", i+1);
        scanf(" %c", &val);
        root = createNode(root, val);
    }
    preOrder(root);
    printf("%s\n", preOrderStr);
    PBTNode newRoot = NULL;
    newRoot = deserialize(newRoot);
    count = 0;
    preOrder(newRoot);
    printf("%s\n", preOrderStr);
    return 0;
}

5.二叉树的按层次序列化和反序列化

给出树的根节点或者给出建树的方式

code

void bfs_order_serialize(PBTNode root) {
    if (root == NULL) {
        bfs_order[cnt++] = '#';
        return;
    }
    int front = 0;
    int rear = 0;
    queue[rear++] = *root;
    bfs_order[cnt++] = root->val;
    while (front < rear) {
        BTNode temp = queue[front++];
        if (temp.left != NULL) {
            queue[rear++] = *temp.left;
            bfs_order[cnt++] = temp.left->val;
        }
        else {
            bfs_order[cnt++] = '#';
        }
        if (temp.right != NULL) {
            queue[rear++] = *temp.right;
            bfs_order[cnt++] = temp.right->val;
        }
        else {
            bfs_order[cnt++] = '#';
        }
    }
    return;
}
PBTNode bfs_order_deserialize(PBTNode root, int index) {
    if (bfs_order[index - 1] == '#'){
        return NULL;
    }
    PBTNode newNode = (PBTNode)malloc(sizeof(BTNode));
    newNode->val = bfs_order[index - 1];
    newNode->left = bfs_order_deserialize(root, 2 * index);
    newNode->right = bfs_order_deserialize(root, 2 * index + 1);
    return newNode;
}

6.利用二叉树的先序序列和中序序列建树

#define MAX_SIZE 100

typedef struct BTNode {
    int data;
    struct BTNode* left;
    struct BTNode* right;
} BTNode, *PBTNode;

typedef struct node{
    int data;
    int num;
    struct node* next;
} NODE, *Pnode;

Pnode hashlinkedlist[13];

char preorder[MAX_SIZE];
char inorder[MAX_SIZE];
int int_preorder[MAX_SIZE];
int int_inorder[MAX_SIZE];
int count;

void createHashLinkedList(char *str) {
	int i;
    for (i = 0; i < 13; i++) {
        hashlinkedlist[i] = NULL;
    }
    int len = strlen(str);
    int cur = 0;
    for (i = 0; i < len; i++) {
        if (str[i] >= '0' && str[i] <= '9') {
            cur = cur * 10 + (str[i] - '0');
        }
        else {
            if (hashlinkedlist[cur % 13] == NULL) {
                Pnode PNode = (Pnode)malloc(sizeof(NODE));
                PNode->data = cur;
                PNode->num = count;
                PNode->next = NULL;
                hashlinkedlist[cur % 13] = PNode;
            }
            else {
                Pnode temp = hashlinkedlist[cur % 13];
                while (temp != NULL) {
                    temp = temp->next;
                }
                temp->num = count;
                temp->data = cur;
                temp->next = NULL;
            }
            count++;
            cur = 0;
        }
    }
    if (hashlinkedlist[cur % 13] == NULL) {
        Pnode PNode = (Pnode)malloc(sizeof(NODE));
        PNode->data = cur;
        PNode->num = count;
        PNode->next = NULL;
        hashlinkedlist[cur % 13] = PNode;
    }
    else {
        Pnode temp = hashlinkedlist[cur % 13];
        while (temp != NULL) {
            temp = temp->next;
        }
        temp->num = count;
        temp->data = cur;
        temp->next = NULL;
    }
    count++;
    return;
}

void adjust(char* str, int* int_str, int len) {
    int cur = 0;
    int cnt = 0;
    int i;
    for (i = 0; i < len; i++) {
        if (str[i] >= '0' && str[i] <= '9') {
            cur = cur * 10 + (str[i] - '0');
        }
        else {
            int_str[cnt++] = cur;
            cur = 0;
        }
    }
    int_str[cnt++] = cur; 
}

int fun(int c) {
    Pnode temp = hashlinkedlist[c % 13];
    while (temp->data != c) {
        temp = temp->next;
    }
    return temp->num;
}

PBTNode createBT(int * int_preorder, int * int_inorder, int pre_start, int pre_end, int in_start, int in_end) {
     if (pre_start > pre_end) {
        return NULL;
    }
    PBTNode pnewNode = (PBTNode)malloc(sizeof(BTNode));
    pnewNode->data = int_preorder[pre_start];
    int find = fun(int_preorder[pre_start]);
    pnewNode->left = createBT(int_preorder, int_inorder, pre_start + 1, pre_start + find - in_start, in_start, find - 1);
    pnewNode->right = createBT(int_preorder, int_inorder, pre_start + find - in_start + 1, pre_end, find + 1, in_end);
    return pnewNode;
}

7.判断完全二叉树

利用按层次遍历的方式，一次遍历每一层，对于每一个结点，如果有一个结点只有右孩子，但无左孩子，则该树必不为完全二叉树；若有一个结点孩子不全，则接下来的所有遍历的结点必须全为叶子节点，否则也不为完全二叉树。

8.计算完全二叉树的结点个数，要求复杂度小于O（n）

code：

int mostleftdown(PBTNode PNode, int level) {
    while(PNode != NULL) {
        PNode = PNode->left;
        level++;
    }
    return level - 1;
}
//PNode is the current node, 
//level is the current level, 
//h is the height of the original tree
int function(PBTNode PNode, int level, int h) {
    if (level == h) {
        return 1;
    }
    if (mostleftdown(PNode->right, level + 1) == h) {
        return ((1 << (h - level)) + function(PNode->right, level + 1, h));
    } else {
        return ((1 << (h - level - 1)) + function(PNode->left, level + 1, h));
    }
}

int count_complete_binary_trees(PBTNode root) {
    if (root == NULL) {
        return 0;
    }
    return function(root, 1, mostleftdown(root, 1));
}

C语言

一、二进制和位运算——异或的高端操作

答案：

1.异或运算性质：

2.题解：

3.异或运算的骚操作：

1).交换两个数：

2).不用任何判断语句和比较操作，返回两个数的最大值：

3). 找到缺失的数字:

4).找出数组中唯一出现奇数次的数字:

5).骚操作

①Brian Kernighan算法——提取出二进制状态中最右侧的1

②数组中有2种数出现了奇数次，其他的数都只出现了偶数次，返回这2种出现了奇数次的数：a、b（a！=b，显然）

code：

6).找出数组中唯一的出现次数小于m的数：

原理：

code：

二、位运算的骚操作

1.判断一个整数是否为2的幂：

2.判断一个整数是否为3的幂（int范围内）：

code:

3.已知n为非负数，返回大于等于n的最小的2的幂：

code:

4.将区间[left,right]中的数全部&的结果：

code:

5.将一个数按照其二进制逆序翻转得到新的数：

code:

6.求一个数的二进制表现形式有几个1:

code:

三、位运算——位图

位图的实现：

code:

四、位运算——实现加减乘除：

code:

减法：

code：

乘法：

code:

除法：

code:

五、链表高频问题：

1.返回两个无环链表相交的第一个节点，若不相交则返回null

code：

5.找链表的第一个入环节点，如果不存在环结构，就返回NULL：

code:

6.在链表上排序。要求时间复杂度O(n*logn),额外空间复杂度O(1),还要求排序有稳定性，（在数组层面上不能实现）

code:

六、数据结构设计高频题：

2.插入、删除、元素等概率随机获取时间复杂度均为O(1)的结构:

3.快速获取数据流的中位数：

4.最大频率栈：

code:

七、二叉树高频题：

1.bfs的两种实现方式：

①队列加哈希表（表记录弹出结点的层数），根据哈希表中的数值与对应层数的关系在链表数组中进行处理。

②一次处理一层的方式：

1)拿当前队列的长度size

2)如下行为重复size遍：

（1）弹出队首结点放入其所在层的链表中。

（2）有左节点加左节点;有右节点加右节点

code:

若要求锯齿状层次遍历二叉树，即相邻的两层的遍历左右次序不同，则队列加入结点的方式同上，弹出结点的方式改为如下：

2.最大特殊宽度：

code:

code：

4.二叉树的先序序列化和反序列化

code：

5.二叉树的按层次序列化和反序列化

code

6.利用二叉树的先序序列和中序序列建树

7.判断完全二叉树

8.计算完全二叉树的结点个数，要求复杂度小于O（n）

9.找一颗普通二叉树中两个不同结点的最近相同的祖先节点