C笔试题之编程题三

佚名 6年前 (2019-05-12) 随笔 1795人围观抢沙发百度已收录

9、写一个函数找出一个整数数组中第二大的数。—— Microsoft

 1 const int MINNUMBER = -32768;//假设int占2个字节
 2 
 3 int find_sec_max(int data[], int count)
 4 {
 5     int maxnumber = data[0];
 6     int sec_max = MINNUMBER;
 7 
 8     for (int i = 1; i < count; i++)
 9     {
10         if (data[i] > maxnumber)
11         {
12             sec_max = maxnumber;
13             maxnumber = data[i];
14         }
15         else
16         {
17             if (data[i] > sec_max)
18                 sec_max = data[i];
19         }
20     }
21 
22     return sec_max;
23 }

10、如何判断一个单链表是有环的？不能用标志位，最多只能用两个额外指针。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　思路：如果一个单链表中有环，用一个指针去遍历，永远不会结束，所以可以用两个指针，一个指针一次走一步，另一个指针一次走两步，如果存在环，则这两个指针会在环内相遇，时间复杂度为O(n)。

 1 struct Node
 2 {
 3     int data;
 4     Node * next;
 5 };
 6 typedef struct Node Node;
 7 
 8 bool check(Node * pHead)
 9 {
10     if (pHead == NULL)
11         return false;
12     Node * pSlow = pHead;
13     Node * pFast = pHead;
14 
15     while ((pFast != NULL) && (pFast->next != NULL))
16     {
17         pSlow = pSlow->next;
18         pFast = pFast->next->next;
19         if (pSlow == pFast)
20             return true;
21     }
22     return false;
23 }