15道简单算法题

2014-6-9 15:37| 发布者: joejoe0332| 查看: 5888| 评论: 0|原作者: 陈太汉|来自: jobbole.com

摘要: 这15道大部分来自《剑指Offer》，作者的博客之前看过几次，感觉写得很好，但看这本书时却没有那个感觉了，可能是因为看过博客的原因吧，没有了之前的那种惊喜。自己就试着实现里面的一些算法题目，基本上是简单的思 ...

12:判断一个字符串是否是另一个字符串的子串;

　　我这里就是暴力的对比

//判断一个字符串是否是另一个字符串的子串
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;
}

13:把一个int型数组中的数字拼成一个串，这个串代表的数字最小;

　　先将数字转换成字符串存在数组中，在通过qsort排序，在排序用到的比较函数中，将要比较的两个字符串进行组合，如要比较的两个字符串分别是A,B，那么组合成，A+B，和B+A，在比较A+B和B+A，返回strcmp(A+B, B+A)，经过qsort这么一排序,数组就变成从小到大的顺序了，组成的数自然是最小的。

//把一个int型数组中的数字拼成一个串，是这个串代表的数组最小
#define MaxLen 10 
int Compare(const void* str1,const void* str2)
{
    char cmp1[MaxLen*2+1];
    char cmp2[MaxLen*2+1];
    strcpy(cmp1,*(char**)str1);
    strcat(cmp1,*(char**)str2);
 
    strcpy(cmp2,*(char**)str2);
    strcat(cmp2,*(char**)str1);
    return strcmp(cmp1,cmp2);
}  
void GetLinkMin(int a[],int len)
{
    char** str=(char**)new int[len];
    for (int i=0;i<len;i++)
    {
        str[i]=new char[MaxLen+1];
        sprintf(str[i],"%d",a[i]); 
    }
 
    qsort(str,len,sizeof(char*),Compare);
    for (int i=0;i<len;i++)
    {
        cout<<str[i]<<" ";
        delete[] str[i] ;
    }
    delete[] str;
} 
void GetLinkMinTest()
{
    int arr[]={123,132,213,231,321,312};
    GetLinkMin(arr,sizeof(arr)/sizeof(int));
}

14:输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）;

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

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);
    } 
}
 
void TreeClassTest()
{
    NodeT* root=new NodeT(8);
    NodeT* n1=new NodeT(6);
    NodeT* n2=new NodeT(10);
    NodeT* n3=new NodeT(5);
    NodeT* n4=new NodeT(7);
    NodeT* n5=new NodeT(9);
    NodeT* n6=new NodeT(11);
    root->left=n1;
    root->right=n2;
    n1->left=n3;
    n1->right=n4;
    n2->left=n5;
    n2->right=n6;
    PrintTree(root);
    cout<<endl;
    TreeClass( root );
    PrintTree(root);
    cout<<endl;
}

15:输入两个链表，找到它们第一个公共节点;

　　如果两个链表有公共的节点，那么第一个公共的节点及往后的节点都是公共的。从后往前数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;
    }
}