首页 > 代码库 > 算法小思路(一)

算法小思路(一)

  • 合并排序,将两个已经排序的数组合并成一个数组,其中一个数组能容下两个数组的所有元素

并排序一般的思路都是创建一个更大数组C,刚好容纳两个数组的元素,先是一个while循环比较,将其中一个数组A比较完成,将另一个数组B中所有的小于前一个数组A的数及A中所有的数按顺序存入C中,再将剩下的数存入C中,空间复杂度高

但是目前是这个数组:

int a[]={2,4,6,8,10,0,0,0,0,0};int b[]={1,3,5,7,9};

解决思路是:

void MergeArray(int a[],int alen,int b[],int blen){    int len=alen+blen-1;     alen--;    blen--;    while (alen>=0 && blen>=0)    {        if (a[alen]>b[blen])        {            a[len--]=a[alen--];        }else{            a[len--]=b[blen--];         }    }     while (alen>=0)    {        a[len--]=a[alen--];    }     while (blen>=0)    {        a[len--]=b[blen--];    } }

倒着遍历和比较数组,都是从key=4开始,比较之后放到从key=9开始的位置。

  • 合并两个单链表

新建单链表,然后分别比较两个单链表的值,再放入新链表中。

//合并两个单链表NodeL* MergeList(NodeL* head1,NodeL* head2){    if (head1==NULL)        return head2;    if (head2==NULL)        return head1;     NodeL* head=NULL;     if (head1->value<head2->value)    {        head=head1;        head1=head1->next;    }else{        head=head2;        head2=head2->next;    }    NodeL* tmpNode=head;    while (head1 && head2)    {        if (head1->value<head2->value)        {            head->next=head1;            head1=head1->next;        }else{            head->next=head2;            head2=head2->next;        }        head=head->next;    }    if (head1)    {        head->next=head1;    }    if (head2)    {        head->next=head2;    }     return tmpNode;}
  • 倒序打印一个单链表

递归实现,先递归在打印就变成倒序打印了,如果先打印在调用自己就是顺序打印了。

//倒序打印一个单链表void ReversePrintNode(NodeL* head){    if (head)    {        ReversePrintNode(head->next);        cout<<head->value<<endl;    } }
  • 通过两个栈实现一个队列

插入的话先放入栈1,如果要取出,则判断栈2是否有元素,没有的话将栈1中的元素全部放入栈2,栈2再弹出。

  • 二分查找

二分查找记住几个要点就行了,start=0,end=数组长度-1,while(start<=end),注意溢出。

//二分查找int binarySearch(int a[],int len,int val){    int start=0;    int end=len-1;    int index=-1;    while (start<=end)    {        index=start+(end-start)/2;        if (a[index]==val)        {            return index;        }else if (a[index]<val)        {            start=index+1;        }else        {            end=index-1;        }    }    return -1;}
  • 快速排序

1.先从数列中取出一个数作为基准数(一般都为第一个数)。

2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。(两个指针,i在第一个的位置,j在第二个位置,j向前找,找到比基数小的,交换,然后i向后找,找到比技术大的,交换,知道i>=j,把i、j归位,再确定基数,再继续执行)。

3.再对左右区间重复第二步,直到各区间只有一个数。

void Qsort(int a[],int low,int high){     if(low>=high)     {         return;     }     int first=low;     int last=high;     int key=a[first];//用字表的第一个记录作为枢轴     while(first<last)     {         while(first<last && a[last]>=key )--last;         a[first]=a[last];//将比第一个小的移到低端         while(first<last && a[first]<=key )++first;         a[last]=a[first];//将比第一个大的移到高端    }     a[first]=key;//枢轴记录到位     Qsort(a,low,first-1);     Qsort(a,last+1,high);}
  • 获得一个int型的数中二进制中的个数

核心实现就是while (num= num & (num-1)),通过这个数和比它小1的数的二进制进行&运算,将二进制中1慢慢的从后往前去掉,直到没有。

int Find1Count(int num){    if (num==0)    {        return 0;    }    int count=1;    while (num= num & (num-1))    {        count++;    }    return count;}
  • 输入一个数组,实现一个函数,让所有奇数都在偶数前面

两个指针,一个从前往后,一个从后往前,前面的指针遇到奇数就往后走,后面的指针遇到偶数就往前走,只要两个指针没有相遇,就奇偶交换。

void RecordOddEven(int A[],int len){    int i=0,j=len-1;    while (i<j)    {        while (i<len && A[i]%2==1)             i++;          while (j>=0 && A[j]%2==0)             j--;          if (i<j)        {            A[i]^=A[j]^=A[i]^=A[j];         }    }}
  • 判断一个字符串是否是另一个字符串的子串
//判断一个字符串是否是另一个字符串的子串int substr(const char* source,const char* sub){    if (source==NULL || sub==NULL)    {        return -1;    }    int souLen=strlen(source);    int subLen=strlen(sub);    if (souLen<subLen)    {        return -1;    }     int cmpCount=souLen-subLen;    for (int i=0;i<=cmpCount;i++)    {        int j=0;        for (;j<subLen;j++)        {            if (source[i+j]!=sub[j])            {                break;            }        }        if (j==subLen)        {            return i ;        }    }    return -1;}
  • 输入一颗二叉树,输出它的镜像(每个节点的左右子节点交换位置)

递归实现,只要某个节点的两个子节点都不为空,就左右交换,让左子树交换,让右子树交换。

struct NodeT{    int value;    NodeT* left;    NodeT* right;    NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}}; //输入一颗二叉树,输出它的镜像(每个节点的左右子节点交换位置)void TreeClass(NodeT* root){    if( root==NULL || (root->left==NULL && root->right==NULL) )         return;     NodeT* tmpNode=root->left;    root->left=root->right;    root->right=tmpNode;    TreeClass(root->left);    TreeClass(root->right); } void PrintTree(NodeT* root){    if(root)    {        cout<<root->value<<" ";        PrintTree(root->left);        PrintTree(root->right);    } }
  • 输入两个链表,找到它们第一个公共节点

如果两个链表有公共的节点,那么第一个公共的节点及往后的节点都是公共的。从后往前数N个节点(N=短链表的长度节点个数),长链表先往前走K个节点(K=长链表的节点个数-N),这时两个链表都距离末尾N个节点,现在可以一一比较了,最多比较N次,如果有两个节点相同就是第一个公共节点,否则就没有公共节点。

//输入两个链表,找到它们第一个公共节点int GetLinkLength(NodeL* head){     int count=0;    while (head)    {        head=head->next;        count++;    }    return count;} NodeL* FindFirstEqualNode(NodeL* head1,NodeL* head2){    if (head1==NULL || head2==NULL)        return NULL;    int len1=GetLinkLength(head1);    int len2=GetLinkLength(head2);    NodeL* longNode;    NodeL* shortNode;    int leftNodeCount;    if (len1>len2)    {        longNode=head1;        shortNode=head2;        leftNodeCount=len1-len2;    }else{        longNode=head2;        shortNode=head1;        leftNodeCount=len2-len1;    }    for (int i=0;i<leftNodeCount;i++)    {        longNode=longNode->next;    }    while (longNode && shortNode && longNode!=shortNode)    {        longNode=longNode->next;        shortNode=shortNode->next;    }    if (longNode)//如果有公共节点,必不为NULL    {        return longNode;    }    return NULL;  } void FindFirstEqualNodeTest(){    NodeL* head1=new NodeL(0);    NodeL* head2=new NodeL(0);    NodeL* node1=new NodeL(1);    NodeL* node2=new NodeL(2);    NodeL* node3=new NodeL(3);    NodeL* node4=new NodeL(4);    NodeL* node5=new NodeL(5);    NodeL* node6=new NodeL(6);    NodeL* node7=new NodeL(7);     head1->next=node1;    node1->next=node2;    node2->next=node3;    node3->next=node6;//两个链表相交于节点node6     head2->next=node4;    node4->next=node5;    node5->next=node6;//两个链表相交于节点node6    node6->next=node7;     NodeL* node= FindFirstEqualNode(head1,head2);    if (node)    {        cout<<node->value<<endl;    }else{        cout<<"没有共同节点"<<endl;    }}

我是天王盖地虎的分割线                                                              

参考:http://blog.jobbole.com/70599/