袋熊的树洞

日拱一卒，功不唐捐

0%

Posted on

想在Github上搭建一个简易的个人Blog，Hexo是一个不错的选择。Hexo是一个快速、简洁的博客框架，使用Markdown解析文章，在几秒内就可以生成静态网页，然后就可以部署在Github上生成个人网站。

Read more »

Posted on Edited on

问题描述

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:

Can you solve it without using extra space?

Related Topics: Linked List, Two Pointers

原问题: 142. Linked List Cycle II

中文翻译版: 142. 环形链表 II

解决方案

解决方案1

用一个 Set 保存已访问的节点，此时可以遍历整个链表并返回第一个出现重复的节点。时间复杂度为 O(n)，空间复杂度为 O(n)

参考解题代码 
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> node_set;
        ListNode *node;

        node = head;
        while (node != NULL) {
            if (node_set.find(node) == node_set.end())
                node_set.insert(node);
            else
                return node;
            node = node->next;
        }

        return node;
    }
};

解决方案2

方案2是 LeetCode 141 解题思路的进一步改进，算法分为两个阶段：

  • 阶段1 : 首先使用快指针 fast 和慢指针 slow 遍历链表，如果链表有环，两指针最终会相遇到某个节点
  • 阶段2 : 初始化额外的两个指针，ptr1 指向链表的头节点，ptr2 指向相遇节点。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点

关于阶段2的实现原理，这里提供一个不错的解答说明：LeetCode: 环形链表 II 官方解答

参考解题代码 
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
34
35
36
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (NULL == head || NULL == head->next)
            return NULL;

        ListNode *slow, *fast;

        slow = fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                break;
        }
        // no cycle
        if (slow != fast)
            return NULL;

        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return fast;
    }
};

Posted on Edited on

问题描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

  • Methods pop, top and getMin operations will always be called on non-empty stacks.

Related Topics: Stack, Design

原问题: 155. Min Stack

中文翻译版: 155. 最小栈

解决方案

可以使用两个栈解决该题，一个栈stack存储push进来的数据，另一个栈min_stack存储现有数据的最小值，两个栈存储同等数量的元素。关键的操作 push 实现如下：

  • push : push的数据为x，如果x小于min_stack栈顶的值，说明x比现用元素值都要小，则将x压入min_stack，否则将min_stack栈顶的值压入min_stack
参考解题代码 
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
34
35
36
37
38
39
40
class MinStack {
private:
    stack<int> m_stack;
    stack<int> m_min_stack;

public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        if (m_stack.empty()) {
            m_stack.push(x);
            m_min_stack.push(x);
        } else {
            int top = m_min_stack.top();

            if (top > x)
                m_min_stack.push(x);
            else
                m_min_stack.push(top);

            m_stack.push(x);
        }
    }

    void pop() {
        m_stack.pop();
        m_min_stack.pop();
    }

    int top() {
        return m_stack.top();
    }

    int getMin() {
        return m_min_stack.top();
    }
};

Posted on Edited on

1. 问题描述

Reverse a singly linked list.

Example:

1
2
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Related Topics: Linked List

原问题: 206. Reverse Linked List

中文翻译版: 206. 反转链表

2. 解决方案

2.1 非递归

非递归的解决方案是按原始顺序迭代节点，并将它们逐个移动到链表的头部。以下举个例子进行说明

黑色节点23是原始头节点。

  1. 首先，我们将黑色节点的下一个节点（即节点6）移动到链表的头部：

  2. 然后，我们将黑色节点的下一个节点（即节点15）移动到链表的头部：

  3. 黑色结点的下一个结点现在是空。因此，我们停止这一过程并返回新的头结点15

从以上流程可以知道该算法的时间复杂度为 O(N)，空间复杂度为 O(1)

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur, *next;

        cur = head;
        while (cur != NULL && cur->next != NULL) {
            next = cur->next;
            cur->next = next->next;
            next->next = head;
            head = next;
        }

        return head;
    }
};

2.2 递归

用递归解此题时，此时递归的函数返回的是反转链表后的新的头节点 new_head，进行整合时，只需要将头节点 head 添加到反转链表的尾部即可。拿前面例子来说，头节点23后部分都已经反转完毕，此时链表构造为

1
23 -> 6 <- 15

此时 new_head 指向节点15，head 指向节点23，要将节点23添加到反转链表尾部，执行以下操作即可：

1
2
head->next->next = head
head->next = NULL

经过以上操作以后，链表构造变为

1
NULL <- 23 <- 6 <- 15

最后返回新的头节点 new_head 即可

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;

        ListNode *new_head;

        new_head = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;

        return new_head;
    }
};

Posted on Edited on

问题描述

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

1
2
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

1
2
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Note:

  • The relative order inside both the even and odd groups should remain as it was in the input.
  • The first node is considered odd, the second node even and so on …

Related Topics: Linked List

原问题: 328. Odd Even Linked List

中文翻译版: 328. 奇偶链表

解决方案

解此题主要需要两个指针 odd 以及 even，odd 指向奇节点，even 指向偶节点。odd 从第一个节点开始遍历，even 从第二节点开始遍历，两个指针每次移动都是移动两个节点，每次移动前，先将 next 字段指向下下个节点，即

1
2
odd = odd->next->next;
even = even->next->next;

这样当两个指针遍历完链表时，链表刚好被分为两部分，odd 指向奇节点链表最后一个节点，此时将这两个链表拼在一起即可。偶节点链表头部是头节点的下一个节点，由于在指针遍历时，会破坏链表结构，因此在遍历前先保存该节点 node，链表拼接时只需

1
odd->next = node
参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;

        ListNode *even, *odd, *node;

        odd = head;
        even = head->next;
        node = head->next;
        while (odd != NULL && odd->next != NULL
               && even != NULL && even->next != NULL) {
            odd->next = odd->next->next;
            odd = odd->next;
            even->next = even->next->next;
            even = even->next;
        }
        odd->next = node;

        return head;
    }
};

Posted on Edited on

问题描述

Remove all elements from a linked list of integers that have value val.

Example:

1
2
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Related Topics: Linked List

原问题: 203. Remove Linked List Elements

中文翻译版: 203. 移除链表元素

解决方案

链表删除基本操作的实现，使用三个指针 prev、curr 以及 next，prev 指向 curr 前一个节点，curr 指向要删除的节点，next 指向 curr 下一个节点。curr 从头节点开始遍历，按照链表删除元素操作依次删除值为 val 的节点即可

1
2
3
4
next = curr->next;
prev->next = next;
delete curr;
curr = next;

这里要注意的是头节点，如果头节点的值刚好 val，这个删除操作和上面的代码片段有少许区别

参考解题代码 
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
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *prev, *curr, *next;

        prev = NULL;
        curr = head;
        while (curr != NULL) {
            if (curr->val == val) {
                next = curr->next;
                if (prev == NULL)
                    head = next;
                else
                    prev->next = next;
                delete curr;
                curr = next;
            } else {
                prev = curr;
                curr = curr->next;
            }
        }

        return head;
    }
};

Posted on Edited on

问题描述

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

1
2
Input: 16
Output: true

Example 2:

1
2
Input: 14
Output: false

Related Topics: Math, Binary Search

原问题: 367. Valid Perfect Square

中文翻译版: 367. 有效的完全平方数

解决方案

本题换种说法就是：求正整数 num 的平方根 x，且 x 的平方等于 num，如何求正整数的平方根，可以用二分查找进行求解，这个可以参考LeetCode原题 69. Sqrt(x)（解题报告：LeetCode 69 - Sqrt(x)），二分查找后得到的平方根 x，只需判断 x 的平方是否等于 num 即可判断 num 是否为完全平方数

参考解题代码 
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
34
35
36
37
38
39
40
#include <iostream>
using namespace std;


class Solution {
public:
    bool isPerfectSquare(int num) {
        long long low, mid, high;

        low = 0;
        high = (long)num + 1;
        while (low < high) {
            mid = low + (high - low) / 2;
            if (mid * mid < num)
                low = mid + 1;
            else
                high = mid;
        }

        // if it doesn't find square of number
        if (low * low != num)
            return false;

        return true;
    }
};


int main()
{
    int num;
    Solution solu;

    // max of int
    // num = 2147483647;
    num = 14;
    cout << num << " is perfect square: "
         << solu.isPerfectSquare(num) << endl;
    return 0;
}

Posted on Edited on

问题描述

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Related Topics: Linked List, Two Pointers

原问题: 19. Remove Nth Node From End of List

中文翻译版: 19. 删除链表的倒数第N个节点

解决方案

这道题可以使用双指针方法解决，设定两个指针 p1 和 p2，先让指针 p1 遍历 n 个节点，然后指针 p2 开始和指针 p1 同步遍历链表，当指针 p1 遍历完链表后，指针 p2 刚好指向倒数第 n 个节点，此时删除该节点即可。

参考解题代码 
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
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == NULL)
            return NULL;

        ListNode *pos1, *pos2, *prev;
        int step;

        prev = NULL;
        pos1 = pos2 = head;
        step = 0;
        while (pos2 != NULL) {
            pos2 = pos2->next;
            step += 1;
            if (step > n) {
                prev = pos1;
                pos1 = pos1->next;
            }
        }
        if (prev == NULL)
            head = head->next;
        else
            prev->next = pos1->next;

        return head;
    }
};