算法小思路（一）-阿里云开发者社区

算法小思路（一）

2017-10-01 987

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

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

并排序一般的思路都是创建一个更大数组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://www.cnblogs.com/yydcdut/p/3859403.html，如需转载请自行联系原作者