精华内容
下载资源
问答
  • 15道简单算法

    千次阅读 2018-06-25 18:05:53
    没事又做起了算法题目。好久没怎么写算法题了,感觉手气还不错,经常能一次就写对(编译通过,得到想要的结果,没怎么测试),可能是因为这些题目之前看过或是写过,或许就是自己进步了一点。这15道大部分来自《剑指...

    转载自http://www.cnblogs.com/hlxs/archive/2014/06/06/3772333.html

    最近在公司里基本处于打酱油的状态,工作正在交接中。没事又做起了算法题目。好久没怎么写算法题了,感觉手气还不错,经常能一次就写对(编译通过,得到想要的结果,没怎么测试),可能是因为这些题目之前看过或是写过,或许就是自己进步了一点。这15道大部分来自《剑指Offer》,作者的博客之前看过几次,感觉写得很好,但看这本书时却没有那个感觉了,可能是因为看过博客的原因吧,没有了之前的那种惊喜。自己就试着实现里面的一些算法题目,基本上是简单的思考一下,如果没什么思路,就看看作者是怎么想的,大概看一下他的思路或是代码,就开始自己实现。15道算法题如下:源码下载

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

    2:合并两个单链表;

    3:倒序打印一个单链表;

    4:给定一个单链表的头指针和一个指定节点的指针,在O(1)时间删除该节点;

    5:找到链表倒数第K个节点;

    6:反转单链表;

    7:通过两个栈实现一个队列;

    8:二分查找;

    9:快速排序;

    10:获得一个int型的数中二进制中的个数;

    11:输入一个数组,实现一个函数,让所有奇数都在偶数前面;

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

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

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

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

    下面简单说说思路和代码实现

    复制代码
    //链表节点
    struct NodeL 
    {
        int value;
        NodeL* next;
        NodeL(int value_=0,NodeL* next_=NULL):value(value_),next(next_){}
    }; 
    //二叉树节点
    struct NodeT
    {
        int value;
        NodeT* left;
        NodeT* right;
        NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}
    };
    复制代码

     

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

    合并排序一般的思路都是创建一个更大数组C,刚好容纳两个数组的元素,先是一个while循环比较,将其中一个数组A比较完成,将另一个数组B中所有的小于前一个数组A的数及A中所有的数按顺序存入C中,再将A中剩下的数存入C中,但这里是已经有一个数组能存下两个数组的全部元素,就不用在创建数组了,但只能从后往前面存,从前往后存,要移动元素很麻烦。

    复制代码
    //合并排序,将两个已经排序的数组合并成一个数组,其中一个数组能容下两个数组的所有元素
    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 (blen>=0)
        {
            a[len--]=b[blen--];
        } 
    }
    
    void MergeArrayTest()
    {
        int a[]={2,4,6,8,10,0,0,0,0,0};
        int b[]={1,3,5,7,9};
        MergeArray(a,5,b,5);
        for (int i=0;i<sizeof(a)/sizeof(a[0]);i++)
        {
            cout<<a[i]<<" ";
        }
    }
    复制代码

     

    2:合并两个单链表;

    合并链表和合并数组,我用了大致相同的代码,就不多少了,那本书用的是递归实现。

    复制代码
    //链表节点
    struct NodeL 
    {
        int value;
        NodeL* next;
        NodeL(int value_=0,NodeL* next_=NULL):value(value_),next(next_){}
    }; 
    
    //合并两个单链表
    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 MergeListTest()
    {
        NodeL* head1=new NodeL(1);
        NodeL* cur=head1;
        for (int i=3;i<10;i+=2)
        {
            NodeL* tmpNode=new NodeL(i);
            cur->next=tmpNode;
            cur=tmpNode;
        }
        NodeL* head2=new NodeL(2);
        cur=head2;
        for (int i=4;i<10;i+=2)
        {
            NodeL* tmpNode=new NodeL(i);
            cur->next=tmpNode;
            cur=tmpNode;
        }
        NodeL* head=MergeList(head1,head2);
        while (head)
        {
            cout<<head->value<<" ";
            head=head->next;
        }
    }
    复制代码

     

    3:倒序打印一个单链表;

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

    复制代码
    //倒序打印一个单链表
    void ReversePrintNode(NodeL* head)
    {
        if (head)
        {
            ReversePrintNode(head->next);
            cout<<head->value<<endl;
        } 
    } 
    void ReversePrintNodeTest()
    {
        NodeL* head=new NodeL();
        NodeL* cur=head;
        for (int i=1;i<10;i++)
        {
            NodeL* tmpNode=new NodeL(i);
            cur->next=tmpNode;
            cur=tmpNode;
        }
        ReversePrintNode(head);
    }
    复制代码

     

    4:给定一个单链表的头指针和一个指定节点的指针,在O(1)时间删除该节点;

    删除节点的核心还是将这个节点的下一个节点,代替当前节点。

    复制代码
    //给定一个单链表的头指针和一个指定节点的指针,在O(1)时间删除该节点
    void DeleteNode(NodeL* head,NodeL* delNode)
    {
        if (!head || !delNode)
        {
            return;
        }
    
        if (delNode->next!=NULL)//删除中间节点
        {
            NodeL* next=delNode->next;
            delNode->next=next->next;
            delNode->value=next->value;
            delete next;
            next=NULL;
        }else if (head==delNode)//删除头结点
        {
            delete delNode;
            delNode=NULL;
            *head=NULL;
        }else//删除尾节点,考虑到delNode不在head所在的链表上的情况
        {
            NodeL* tmpNode=head;
            while (tmpNode && tmpNode->next!=delNode)
            {
                tmpNode=tmpNode->next;
            }
            if (tmpNode!=NULL)
            {
                delete delNode;
                delNode=NULL;
                tmpNode->next=NULL;
            }
        }
    }
    
    void DeleteNodeTest()
    {
        int nodeCount=10;
        for (int K=0;K<nodeCount;K++)
        {
            NodeL* head=NULL;
            NodeL* cur=NULL;
            NodeL* delNode=NULL;
            for (int i=0;i<nodeCount;i++)
            {
                NodeL* tmpNode=new NodeL(i);
                if (i==0)
                {
                    cur=head=tmpNode;
                }else{
                    cur->next=tmpNode;
                    cur=tmpNode; 
                }
                if (i==K)
                {
                    delNode=tmpNode;
                } 
            }
            DeleteNode(head,delNode) ;
        } 
    }
    复制代码

     

    5:找到链表倒数第K个节点;

    通过两个指针,两个指针都指向链表的开始,一个指针先向前走K个节点,然后再以前向前走,当先走的那个节点到达末尾时,另一个节点就刚好与末尾节点相差K个节点。

    复制代码
    //找到链表倒数第K个节点
    NodeL* FindKthToTail(NodeL* head,unsigned int k)
    {
        if(head==NULL || k==0)
            return NULL;
        NodeL* tmpNode=head;
        for (int i=0;i<k;i++)
        {
            if (tmpNode!=NULL)
            {
                tmpNode=tmpNode->next;
            }else{
                return NULL;
            } 
        }
        NodeL* kNode=head;
        while (tmpNode!=NULL)
        {
            kNode=kNode->next;
            tmpNode=tmpNode->next;
        }
        return kNode;
    }
    
    void FindKthToTailTest()
    {
        int nodeCount=10;
        for (int K=0;K<nodeCount;K++)
        {
            NodeL* head=NULL;
            NodeL* cur=NULL; 
            for (int i=0;i<nodeCount;i++)
            {
                NodeL* tmpNode=new NodeL(i);
                if (i==0)
                {
                    cur=head=tmpNode;
                }else{
                    cur->next=tmpNode;
                    cur=tmpNode;  
                }
            }
            NodeL* kNode=FindKthToTail(head,K+3) ;
            if (kNode)
            {
                cout<<"倒数第 "<<K+3<<" 个节点是:"<<kNode->value<<endl;
            }else{
                cout<<"倒数第 "<<K+3<<" 个节点不在链表中" <<endl;
            }
        } 
    }
    复制代码

     

    6:反转单链表;

    按顺序一个个的翻转就是了。

    复制代码
    //反转单链表
    NodeL* ReverseList(NodeL* head)
    {
        if (head==NULL)
        {
            return NULL;
        }
        NodeL* reverseHead=NULL;
        NodeL* curNode=head;
        NodeL* preNode=NULL;
        while (curNode!=NULL)
        {
            NodeL* nextNode=curNode->next;
            if (nextNode==NULL)
                reverseHead=curNode;  
    
            curNode->next=preNode;
            preNode=curNode;
            curNode=nextNode;
        }
        return reverseHead;
    }
    
    void ReverseListTest()
    {
        for (int K=0;K<=10;K++)
        {
            NodeL* head=NULL;
            NodeL* cur=NULL; 
            for (int i=0;i<K;i++)
            {
                NodeL* tmpNode=new NodeL(i);
                if (i==0)
                {
                    cur=head=tmpNode;
                }else{
                    cur->next=tmpNode;
                    cur=tmpNode;  
                }
            }
    
            cur=ReverseList( head);
            while (cur)
            {
                cout<<cur->value<<" ";
                cur=cur->next;
            }
            cout<<endl;
        }
        cout<<endl;
    }
    复制代码

     

    7:通过两个栈实现一个队列;

    直接上代码

    复制代码
    //通过两个栈实现一个队列
    template<typename T>
    class CQueue
    {
    public:
        void push(const T& val)
        {
            while (s2.size()>0)
            {
                s1.push(s2.top());
                s2.pop();
            }
            s1.push(val);
        }
        void pop()
        { 
            while (s1.size()>0)
            {
                s2.push(s1.top());
                s1.pop();
            }
            s2.pop();
        }
    
        T& front()
        { 
            while (s1.size()>0)
            {
                s2.push(s1.top());
                s1.pop();
            }
            return s2.top();
        }
        int size()
        {
            return s1.size()+s2.size();
        }
    private:
        stack<T> s1;
        stack<T> s2;
    };
    
    void CQueueTest()
    {
        CQueue<int> q;
        for (int i=0;i<10;i++)
        {
            q.push(i);
        }
        while (q.size()>0)
        {
            cout<<q.front()<<" ";
            q.pop();
        }
    }
    复制代码

     

    8:二分查找;

    二分查找记住几个要点就行了,代码也就那几行,反正我现在是可以背出来了,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;
    }
    复制代码

     

    9:快速排序;

    来自百度百科,说不清楚

    复制代码
    //快速排序
    //之前有个面试叫我写快排,想都没想写了个冒泡,思路早忘了,这段代码来自百度百科
    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);
    }
    
    void QsortTest()
    {
        int a[]={1,3,5,7,9,2,4,6,8,0};
        int len=sizeof(a)/sizeof(a[0])-1;
        Qsort(a,0,len); 
        for(int i=0;i<=len;i++)
        {
            cout<<a[i]<<" ";
        } 
        cout<<endl;
    } 
    复制代码

     

    10:获得一个int型的数中二进制中的个数;

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

    复制代码
    //获得一个int型的数中二进制中1的个数
    int Find1Count(int num)
    {
        if (num==0)
        {
            return 0;
        }
        int count=1;
        while (num= num & (num-1))
        {
            count++;
        }
        return count;
    }
    复制代码

     

    11:输入一个数组,实现一个函数,让所有奇数都在偶数前面;

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

    复制代码
    //输入一个数组,实现一个函数,让所有奇数都在偶数前面
    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]; 
            }
        }
    }
    
    void RecordOddEvenTest()
    {
        int A[]={1,2,3,4,5,6,7,8,9,0,11};
        int len=sizeof(A)/sizeof(A[0]);
        RecordOddEven( A , len);
        for (int i=0;i<len;i++)
        {
            cout<<A[i]<<" ";
        }
        cout<<endl;
        for (int i=0;i<len;i++)
        {
            A[i]=2;
        }
        RecordOddEven( A , len);
        for (int i=0;i<len;i++)
        {
            cout<<A[i]<<" ";
        }
        cout<<endl;
        for (int i=0;i<len;i++)
        {
            A[i]=1;
        }
        RecordOddEven( A , len);
        for (int i=0;i<len;i++)
        {
            cout<<A[i]<<" ";
        }
    }
    复制代码

     

    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;
        }
    }
    复制代码

    展开全文
  • acm简单算法设计题目100道 入门必做的题2 1.一种计算机病毒叫黑色星期五,如果当天是13号,又恰好是星期五,就会发作起来毁球计算机的存储系统,试编程找出九十年代中这种病毒可能发作的日期,假设1990年1月1日...
  • LeetCode 刷题攻略:配思维导图,100+经典算法题目刷题顺序、经典算法模板、共40w字的详细图解,以及难点视频题解。按照刷题攻略上的顺序来刷题,让你在算法学习上不再迷茫! 目录: 算法面试思维导图 B站算法视频...
  • 这个word文档中是C++经典算法的程序代码!
  • #难度:简单 #时间:2021/01/17: 老子回来了 题目 1: #难度:简单 #时间:11 月第一周 题目 1: 题目 2: 题目 3: 题目 4: 题目 5: #难度:简单 #时间:10/26–10/30 题目 1: 题目 2: 题目 3: 题目 4: 题目 ...
  • 经典dijkstra算法题目及代码

    千次阅读 2017-05-22 17:10:33
    经典dijkstra算法题目及代码 Dijkstra算法是解决单源最短路的经典算法,现对这样一道简单的题目给出完整代码(有注释)。 输入n和m,代表n个节点,m条边,然后是m行输入,每行有x,y,z,代表x到y的路距离为z。问题:...

    Dijkstra算法是解决单源最短路的经典算法,现对这样一道简单的题目给出完整代码。

    输入n和m,代表n个节点,m条边,然后是m行输入,每行有x,y,z,代表x到y的路距离为z。问题:从1出发到各点的最短路径。

    测试样例:

    /*
    10 12
    1 4 1
    1 5 1
    1 6 1
    4 8 1
    4 3 1
    3 5 1
    5 7 1
    3 7 1
    6 2 1
    7 2 1
    7 10 1
    2 9 1
    */


    直接给出AC代码。

    #include<cstdio>
    #include<cstring>
    const int maxn=100;
    int map[maxn][maxn];
    int dis[maxn];
    int path[maxn];
    bool vis[maxn];
    int n;
    void dijk(int s)
    {
        memset(path,-1,sizeof(path));
        memset(dis,0x3f,sizeof(dis));      //快速初始化为无穷大
        memset(vis,0,sizeof(vis));
        dis[s]=0;
        while(1)
        {
            int k=0;
            for(int j=1;j<=n;j++)
            {
                if(!vis[j]&&dis[j]<dis[k]) //这一步找未收录顶点中dis值最小的
                    k=j;
            }
            if(!k) return ;               //没有未收录的顶点,则返回(注意顶点从1开始,k为0一定是没找到)
            vis[k]=1;                     //收录顶点k
            for(int j=1;j<=n;j++)
            {
                if(dis[j]>dis[k]+map[k][j])
                {
                    dis[j]=dis[k]+map[k][j];
                    path[j]=k;
                }
            }
        }
    }
    void print(int x)
    {
        if(x==-1) return ;
        print(path[x]);
        printf("%d->",x);
    }
    int main()
    {
        int m,x,y,z,order;
        scanf("%d%d",&n,&m);
        memset(map,0x3f,sizeof(map));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            map[x][y]=map[y][x]=z;
        }
        dijk(1);
        scanf("%d",&order);
        printf("%d\n",dis[order]);
        print(path[order]);
        printf("%d",order);
        return 0;
    }
    


    展开全文
  • 大公司面试有哪些经典算法题目

    千次阅读 2020-01-04 12:15:00
    BAT 等国内的一线名企,在招聘工程师的过程中,对算法和数据结构都会重点考察。但算法易学难精,我的很多粉丝技术能力不错,但面试时总败在算法这一关,拿不到好 Offer。但说实话,数据结构...

    BAT 等国内的一线名企,在招聘工程师的过程中,对算法和数据结构都会重点考察。但算法易学难精,我的很多粉丝技术能力不错,但面试时总败在算法这一关,拿不到好 Offer。但说实话,数据结构和算法花点时间,用对方法,很容易解决。

    面试官为什么爱问数据结构与算法,答案很简单

    • 算法能力能够准确辨别一个程序员的技术功底是否扎实;

    • 算法能力是发掘程序员的学习能力与成长潜力的关键手段;

    • 算法能力能够协助判断程序员在面对新问题时,分析并解决问题的能力;

    • 算法能力是设计一个高性能系统、性能优化的必备基础。 

    很多人力扣( LeetCode)上狂刷题,还炫耀自己刷了多少,但这样反而学不到东西。我建议你在刷题的过程中,把问题拆解、解题分析、得出结论、举一反三,每一个环节都要想的清清楚楚,这样才是高效的刷题方式。

    我认识一个 Google 的资深软件工程师,叫苏勇。这哥们最开始去硅谷面试,因为算法问题,求职的过程非常坎坷。但他铆足了劲,就想进大厂,用了5个月的时间,把力扣( LeetCode)的题,基本刷了个遍,把一些常见题目、巧妙的解法都整理成了一套刷题笔记。靠着这套笔记,这哥们一路逆袭,拿到 Google 的高薪 Offer,让我实属佩服。

    现在,他不仅是Google 资深软件工程师、还是 Google 技术面试官,经常参与面试考题、评分标准设计等各个重要环节,拥有大量技术人才选拔经验。

    他的这套笔记,有难度较低的数组、链表、栈、队列。也有递归、深度、广度优先搜索比较难以掌握的内容。为了写出这套刷题笔记,他对很多题目进行了二刷、三刷,对重点核心题目研究出了好多最优解法。

    我最近正在学习的《300分钟搞定数据结构与算法》,就是他根据自己的刷题笔记整理而成的。感觉学完之后醍醐灌顶,所以赶紧和大家推荐一下。

    可以进入 Google 的刷题笔记 + 力扣(LeetCode)官方多年的算法大数据 + 拉勾网对数百家企业面试官的调研。可以说这是目前市面最值得你学习的数据结构与算法课程。

    ∆扫码免费试看专栏 

    这个专栏最大的优势就是专注于算法面试场景,(面试是我们谁都无法逃避的问题,不论是求职还是晋升。)

    数据结构和算法五花八门,有些你根本不需要花费大量的时间和精力去准备,有些甚至看都不用看。我看中这门课一个比较核心的目的,就是可以有的放矢地准备面试,知道哪些数据结构和算法是常考的,哪些是必须花时间好好准备的。

    苏勇在力扣(LeetCode)上千道题目中,筛选了 30 道有代表性的考题,15 道面试官高频考题。涵盖了面试中绝大部分的基础知识和算法,而且都是面试实战中必须要牢牢掌握好的。有难度较低的数组、链表、栈、队列,也有递归、深度、广度优先搜索等比较难以掌握的内容。

    课里的代码,都通过了力扣(LeetCode)平台的测试,都是比较精简的实现,剔除冗余和复杂的逻辑,帮你用最简单的方式,体现解题的思路。让你在最短的时间里准确地把握住面试准备的方向,有的放矢地学习应该要掌握好的数据结构和算法。

    从最暴力的方式开始,一步步地将你引导到最佳的解法,课程中有丰富的动画,让你在学习枯燥的数据结构和算法中,准确地体会到解题的精髓所在。

    适合谁学?

    如果你是刚刚毕业的学生,无论是计算机专业科班出身还是其他专业,这门课程能帮助你掌握好数据结构和算法的基础,同时,通过力扣平台,能让你尽快地融入到找工作的状态。

    如果你有了一定的工作经验并想找到更具挑战的大厂,那么这门课程能帮助你在分析问题的时候,从最基本的暴力法开始,一步步地学习到如何想出最佳的办法,达到大厂的面试水准。

    无论你是前端工程师,后端工程师还是全栈工程师,在面试的时候,都必须要准确地分析出算法的时间复杂度和空间复杂度,在这门课里,有专门介绍分析复杂度的环节,尤其是对递归算法的复杂度分析,相信一定能帮助到你。

    专栏已经全部更新完毕,不论你是准备面试突击使用,还是先储备知识,留作之后面试都十分合适。 

    限时福利

    看在我的真心推荐上,拉勾给了我们一些限时福利:

    1. 原价 ¥198,限时优惠 ¥68,接近 3折 的优惠(仅限24小时);

    2. 订阅后,点击「阅读原文」,凭购买截图可免费进入“算法交流群”。

    如何订阅?

    扫描下图二维码订阅或试看专栏

    ∆扫码免费试看专栏

    下面是课程的目录,大家可以先行查看,按需选择。

    点击「阅读原文」,进算法交流群共同学习交流。

    展开全文
  • 练习使用Rust语言刷或者算法题目, 一些不支持Rust判题的会使用Python进行解决,并对解题思路进行简单分析,分类,及总结. Environment rustc 1.44.0 cargo 1.44.0 How to test cargo test // 测试所有的测试 cargo test...
  • C#简单课程题目

    2015-11-13 13:43:03
    C#课程使用的基本代码,简单算法,新手可以看看。
  • 我的数据结构与算法题目集代码仓:https://github.com/617076674/Data-structure-and-algorithm-topic-set 原题链接:https://pintia.cn/problem-sets/15/problems/825 题目描述: 知识点:队列 思路:用队列...

    我的数据结构与算法题目集代码仓:https://github.com/617076674/Data-structure-and-algorithm-topic-set

    原题链接:https://pintia.cn/problem-sets/15/problems/825

    题目描述:

    知识点:队列

    思路:用队列模拟

    时间复杂度和空间复杂度均是O(N)。

    C++代码:

    #include<iostream>
    #include<queue>
    
    using namespace std;
    
    int N;
    queue<int> qa, qb, result;
    
    int main() {
    	scanf("%d", &N);
    	int num;
    	for(int i = 0; i < N; i++) {
    		scanf("%d", &num);
    		if(num % 2 == 0) {
    			qb.push(num);
    		} else {
    			qa.push(num);
    		}
    	}
    	while(!qa.empty() || !qb.empty()) {
    		if(!qa.empty()) {
    			result.push(qa.front());
    			qa.pop();
    			if(!qa.empty()) {
    				result.push(qa.front());
    				qa.pop();
    			}
    		}
    		if(!qb.empty()) {
    			result.push(qb.front());
    			qb.pop();
    		}
    	}
    	while(!result.empty()){
    		printf("%d", result.front());
    		result.pop();
    		if(!result.empty()){
    			printf(" ");
    		}else{
    			printf("\n");
    		}
    	}
    	return 0;
    }

    C++解题报告:

     

    展开全文
  • codeup《算法笔记》题目索引(题目+解析+代码)

    万次阅读 多人点赞 2019-04-27 21:28:53
    黑色的题目没有题解(题目本身错误,或者后端判题机有问题,或者博主本身能力不足做不出来= =),还请多担待~~ 如果想考PAT,不是很建议刷codeup里面的题目,如果有时间可以看一下我总结的经验,希望能帮助到你~~...
  • 手动整理了1500多个深度学习及机器学习相关算法在实际应用中的项目,完全可以作为本科生当前较新的毕业设计题目选择方向。讲道理有些题目,比如“用户评分的隐式成分信息的研究”这种题目取的就比较广,有点科学研究...
  • 计算机面试常见题目-算法

    千次阅读 2020-05-11 22:48:47
    算法 数据结构、 冒泡排序优化 求质数(素数) 十进制整数转二进制(除2取余,逆序排序) 逆序输出整数 数据结构、 冒泡排序优化 普通 //优化版本一:设置flag及时停止比较 void Bubble(int arr[],int length) { int...
  • 感知器算法-作业

    2018-11-25 21:50:59
    感知器算法的练习题,用非常简单的例子,可以帮助更好的理解感知器的原理。
  • 题目:计算函数f(x)=∑i=1nxi2\sum_{i=1}^{n}x_i^2∑i=1n​xi2​(-20≤xix_ixi​≤20)的最小值,其中个体x的维数n=10。 解答:优化结束后,根据所得的图可知,优化后的结果为:x=[-0.0282 0.0046 -0.0158 0.0265 0....
  • 遗传算法

    万次阅读 多人点赞 2019-04-06 21:41:47
    使用遗传算法求解多峰函数的最大值,是我的一项课程作业,做完之后,顺便把文档整理出来做个记录。全部内容如下: 1、问题描述 编程实现遗传算法,并求解多峰函数的最大值。多峰函数的表达式如下所示: 用MATLAB...
  • (我的答案中有2种算法)。 第二题: 输入3个数字,然后比较输出一个最大的数字。 第三题: 输入一个数字"i"然后再输入一个数字"j",然后用数字"i"一直相加到数字"j"为止 第四题: 输入2个数字,然后按照从大到小输出 ...
  • 1 一选择题 A广度优先 B最小耗费优先 C最大 1二分搜索算法是利用 A 实现的算 效益优先 D深度优先 法 10下列算法中通常以深度优先方式系统搜索问题 A分治策略 B 动态规划法 C 贪心 解的是 D 法 D 回溯法 A备忘录法 B...
  • 基本算法总结,力扣题目整理

    千次阅读 2020-03-17 15:00:14
    随着打卡题目数量的增多,我发现算法常见考察的知识点大概有十几种,包括:二分,滑动窗口,双指针,单调栈(单调队列),链表,二叉树,字符串处理,dfs + 回溯,并查集,动态规划,贪心,位运算,数论(质数、约数...
  • 我今年面了数十家公司,90%的题目是原题(没办法,就那几个知识点,能有什么新题)。 题库在哪里呢? 按照循序渐进的原则,一一介绍: 1. cc150,全名cracking the coding interview - 150 Programming Questions ...
  • 算法笔记》2.1小节——C/C++快速入门->基本数据类型 本小节无练习题orz ...简单数学 1939 Problem A 守形数 1940 Problem B 反序数 1957 Problem C 百鸡问题 1958 Problem D abc 1968 Proble...
  • 贪心算法题目 电池的寿命

    千次阅读 2020-03-03 12:00:10
    贪心算法 电池的寿命 题目: 小S新买了一个掌上游戏机,这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏,他买了很多5号电池,这些电池的生产商不同,质量也有差异,因而使用寿命也有所不同,有的能使用5个...
  • 经典Prim算法题目及代码

    千次阅读 2017-05-22 17:23:17
    经典Prim算法题目及代码 Prim算法是解决最小生成树的经典算法(尤以稠密图效率很高),现对这样一道简单最小生成 题目给出完整代码(有注释)。 输入n和m,代表n个节点,m条边,然后是m行输入,每行有x,y,z,代表x到...
  • 梯度下降算法

    千次阅读 2019-11-29 14:14:14
    4.梯度下降 4.1什么是梯度下降? 梯度下降法的基本思想可以类比为一个下山的过程 ...这个时候,他就可以利用梯度下降算法来帮助自己下山。 具体来说就是,以他当前的所处的位置为基准,寻找这个位置最陡峭...
  • 微软面试简单算法题目

    千次阅读 2009-05-25 08:56:00
  • KMP算法例题Oulipo题解

    2018-08-17 11:39:37
    KMP算法的一个经典题题解,
  • 这篇文章为本专栏所有力扣题目提供目录链接,更加方便读者根据题型或面试频率进行阅读,此外也会介绍我在刷题过程中总结的刷算法题目的顺序/注意点/技巧,最后说下文中出现的思维导图源文件的问题. 我主页中的思维导图...
  • 2020年腾讯实习生算法笔试题目(感触良多)

    万次阅读 多人点赞 2020-04-27 10:50:57
    2020年腾讯实习生算法笔试题目题目描述代码示例题目描述代码示例题目描述代码示例题目描述代码示例题目描述   参加了腾讯20年的实习生笔试,本来都不打算写这种笔试的题目。但是感觉着产生的想法很多。首先声明我...
  • 本人在牛客做的算法题的一些总结,这是相对简单的一些题目
  • 原创 IT168企业级 2017-09-20 17:21 算法是比较复杂又基础的...1)请简单解释算法是什么? 算法是一个定义良好的计算过程,它将一些值作为输入并产生相应的输出值。简单来说,它是将输入转换为输出的一系列计

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 189,231
精华内容 75,692
关键字:

简单算法题目