兩個(gè)有序數(shù)組求并集：
1.? NSArray*array1 =@[@"1",@"2",@"3"];
? ? NSArray*array2 =@[@"1",@"5",@"6"];
? ? NSMutableSet *set1 = [NSMutableSet setWithArray:array1];
? ? NSMutableSet *set2 = [NSMutableSet setWithArray:array2];
? ? [set1 intersectSet:set2];
2.?使用兩個(gè)指針分別指向數(shù)組A和數(shù)組B，指向數(shù)據(jù)小的指針往前繼續(xù)移動(dòng)，保存兩個(gè)指針指向相同數(shù)據(jù)的值，直到兩個(gè)指針都指向數(shù)組末尾，該算法的時(shí)間復(fù)雜度為O(m+n)。
? void GetIntersectionSet(int ABuffer[],int ALength,int BBuffer[],int BLength,int*des)
? ? {
? ? ? ? intpointerA =0;
? ? ? ? intpointerB =0;
? ? ? ? inttemp =0;
? ? ? ? while(pointerA < ALength && pointerB < BLength)
? ? ? ? {
? ? ? ? ? ? if(ABuffer[pointerA] < BBuffer[pointerB])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? pointerA++;
? ? ? ? ? ? }
? ? ? ? ? ? else if(BBuffer[pointerB] < ABuffer[pointerA])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? pointerB++;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? des[temp] = ABuffer[pointerA];
? ? ? ? ? ? ? ? temp++;
? ? ? ? ? ? ? ? pointerA++;
? ? ? ? ? ? ? ? pointerB++;
? ? ? ? ? ? }
? ? ? ? }
? ? }
3.使用二分法，由于A和B數(shù)組都是有序數(shù)組，使用二分法查找B數(shù)組的每個(gè)成員是否在A數(shù)組中，時(shí)間復(fù)雜度為O(n*lgm)。如果n比m大，則查找A數(shù)組的成員是否在B數(shù)組中，時(shí)間復(fù)雜度為O(m*lgn)。?
4.利用哈希
? NSArray*aArray=@[@3,@4,@6,@8,@10];
? ?NSArray*bArray =@[@4,@8,@11,@20];
? ? for (NSNumber*numinaArray) {
? ? ? ? if([bArraycontainsObject:num]){
? ? ? ? ? ? NSLog(@"%@",num);
? ? ? ? };
? ? }，或者用nsset
2.計(jì)算a的n次方
int test3(int a,int n){
? ? if(n==0)
? ? return 1;
? ? else
? ? return a*test3(a,n-1);
}
3.二叉樹遍歷
//輸出數(shù)據(jù)和層數(shù)
void operation2(int ch,int level)
{
? ? ? cout << ch <<"在第"<< level <<"層"<< endl;
}
前序遍歷二叉樹：
voidPreOrderTraverse(BiTree *T,int level){
? ? if(T == NULL)
? ? ? ? return;
/*此處表示對(duì)遍歷的樹結(jié)點(diǎn)進(jìn)行的操作，根據(jù)你自己的要求進(jìn)行操作，這里只是輸出了結(jié)點(diǎn)的數(shù)據(jù)*///
????operation1(T->data);operation2(T->data, level);//輸出了層數(shù)? ?
?????PreOrderTraverse(T->lchild, level +1);
? ? PreOrderTraverse(T->rchild, level +1);
}
中序遍歷二叉樹:
void InOrderTraverse(BiTree *T,int level){
????if(T==NULL)
????????return;
????InOrderTraverse(T->lchild,level+1);
????operation2(T->data, level);//輸出了層數(shù) ? ? ? ? ? ? ? ? ? ? ??
? ? InOrderTraverse(T->rchild,level+1);
}
后序遍歷二叉樹：
void????PostOrderTraverse(BiTree *T,int level){
????if(T==NULL)????return;
????PostOrderTraverse(T->lchild,level+1);
????PostOrderTraverse(T->rchild,level+1);
????operation2(T->data, level);//輸出了層數(shù)
}
4.二叉樹交換左右結(jié)點(diǎn)：
void exchange(BTree *T){
BTree *temp =?NULL;
if(rt->lchild ==?NULL?&& rt->rchild ==?NULL)
????return;
else{
????temp = T->lchild;
????T->lchild = T->rchild;
????T->rchild = temp;
}
if(T->lchild)
????exchange(T->lchild);
????if(T->rchild)
????????exchange(T->rchild);
}
判斷鏈表是否有環(huán)
bool exitLoop(Node *head){
? ? Node *fast,*slow;
? ? slow = fast = head;
? ? while(slow !=NULL&fast->next!=NULL){
? ? ? ? ? ? slow = slow ->next;
? ? ? ? ? ? fast = fast->next->next;
? ? ? ? ? ? if(slow == fast){
? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }????
? ? }
? ? return false;
}
交換相鄰的兩個(gè)結(jié)點(diǎn)：
//根據(jù)結(jié)點(diǎn)的data來尋找這個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
List FindPrevious( ElementType x, List Head)
{
List ?P;
P = Head;
while( P->next != NULL && P->next->x != x )
{
P = P->next;
}
if ( P->next == NULL )
return NULL;
else
return P;
}?
void SwapAdjacentElements( List Head, List p1, List p2 )
{
if ( p1->next != p2 ){
printf("不是相鄰的節(jié)點(diǎn)");
return;
}
else{
Position p0;
p0 = FindPrevious( p1->x, L );
p1->next = p2->next;
p2->next = p1;
p0->next = p2;
return;
}
}
字符串按單詞逆序算法
例如，給定字符串“I am a student”按單詞逆序輸出為“student a am I”
//指定兩個(gè)位置front指針在首端，end指針在末尾，對(duì)里面的元素進(jìn)行逆序
思路：對(duì)于字符串I am a student”采用先單詞內(nèi)部局部逆序，字符串變?yōu)?I ma a tneduts",然后再將整個(gè)字符串逆序得到最終字符串變?yōu)椤皊tudent a am I”。
void ReverseWord(char*front,char*end)
{
? ? while(front
? ? {
? ? ? ? chartemp=*front;
? ? ? ? *front++=*end;
? ? ? ? *end--=temp;
? ? }
}
char* Reverse(char*s)
{
? ? char*pre=s;
? ? char*current=s;
? ? //pre和current兩個(gè)指針代表要逆序的范圍，current是大的那一個(gè)指針
? ? while(*current!='\0')
? ? {
? ? ? ? if(*current==' ')
? ? ? ? {
? ? ? ? ? ? ReverseWord(pre,current-1);
? ? ? ? ? ? current++;
? ? ? ? ? ? pre=current;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? current++;
? ? ? ? }
? ? }
? ? ReverseWord(pre,current-1); //由于最后一位不是空格，所以還需要特殊逆序一下
? ? ReverseWord(s,current-1);
? ? return s;
}
字符串轉(zhuǎn)數(shù)字
int strToInt(char*string){
? ? if(string==NULL) {
? ? ? ? return0;
? ? }
? ? intnumber =0;
? ? while(*string!=0) {
? ? ? ? number = number*10+*string-'0';
? ? ? ? ++string;
? ? }
? ? returnnumber;
}
斐波那契數(shù)列:
int qbnx(int n){
?if(n<1) {
? ? ? ? return0;
? ? }
? ? else if(n==1) {
? ? ? ? return 1;
? ? }
? ? else if(n==2) {
? ? ? ? return 1;
? ? }
? ? int val =qbnx(n-1)+qbnx(n-2);
? ? return val;
}
? for(int i=1; i<=6; i++) { //輸出斐波那契數(shù)列
? ? ? ? printf("%d",qbnx(i));
? ? }
