每日一刷--牛客网算法题！

1. 第一题

题目描述：
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
你能给出空间复杂度O（1）的解法么？

1.最开始理解错题目了，认为环链就是尾部指头部，但是运行时死循环，然后我悟了，这玩意可以从尾部回头指向任何位置。
2.大佬的第一个思路是用unordered_map,其跟map比在于内部不是平衡二叉树形式，而是内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。3.unordered_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的，上方已经解释了，但是就外部使用来说却是一致的。
4.map适用于需要排序问题，unordered_map适合于查找问题，速度极快。

（1）法一：用unordered_map（空间：O(n)）

/*
 * Definition for singly-linked list.
struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_map<ListNode*, bool> m;
        while(head)
        {
            if(m.find(head)!=m.end()) return true;
            m[head]=true;
            head=head->next;           
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（2）法二：快慢指针法

快指针fast每次比慢指针low多走一个，因为快指针比慢指针块，如果有环，则快指针一定会追上慢指针，但至于会不会恰好超过去，因为每次快指针恰好比慢指针多走一步，而最终快慢指针相遇时，快指针应比慢指针多走一圈长度L，1一定是L的因子，所以一定行！

切记切记while循环的条件有一个fast->next!=NULL,否则可能会出现异常，指针要多留心。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        //快慢指针法：
        ListNode* fast=head;
        ListNode* low=head;
        while(fast!=NULL&&fast->next!=NULL)
        {
            fast=fast->next->next;
            low=low->next;
            if(fast!=NULL&&low!=NULL&&fast==low)
            {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

（3）法三：破坏链表法（最快，而且不许查找）

这个思路真的超级好，如果有环则一定会到之前某个地方，只要能够快速判断出这个结点我之前访问过就行，但是该链表结构已经定下来了，没法加flag，但是这并不妨碍你可以断开链表，让所有已经走过的点都指向head,只要最后存在回去的路，那回去之后的下一个一定是head。注意，特殊情况请特殊考虑。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* p=head;
        ListNode* q=head;
        while(p!=NULL)
        {
            q=p->next;
            if(q==head)
            {
                return true;
            }
            p->next=head;
            p=q;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.第二题

题目：
给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> out;
        if(input.size()>=k)
        {
            vector<int>::iterator iter=input.begin();
            sort(input.begin(),input.end());
            out.insert(out.begin(),iter,iter+k);
        }
        return out;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

3.第三题：

题目：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路很清晰，效率也还可以。

stack stack1; //stack1作为栈存储后来的数据
stack stack2; //stack2作为队列存储stack1中数据的逆序形式
//说明：每次取数据都是从stack2中取，所以stack2为空时，
//此时将stack1中的所有数据pop到stack2中去。

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        int temp; 
        while(stack1.size()>1)
        {
            temp=stack1.top();
            stack1.pop();
            stack2.push(temp); 
        }
        if(stack1.size()==1)
        {
            temp=stack1.top();
            stack1.pop();
        }
        while(!stack2.empty())
        {
            int a=stack2.top();
            stack2.pop();
            stack1.push(a); 
        }
        return temp;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

进阶版本：

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        int temp;
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                int a=stack1.top();
                stack2.push(a);
                stack1.pop();
            }
        }
        temp=stack2.top();
        stack2.pop();
        return temp;
    }

private:
    stack<int> stack1;  //stack1作为栈存储后来的数据
    stack<int> stack2;  //stack2作为队列存储stack1中数据的逆序形式
    //说明：每次取数据都是从stack2中取，所以stack2为空时，
    //此时将stack1中的所有数据pop到stack2中去。
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29