Flag敢立，才敢拔！

0%

发表于 更新于 分类于 ，
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目：

  • 描述如何只用一个数组来实现三个栈。

    你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标，value表示压入的值。

    构造函数会传入一个stackSize参数，代表每个栈的大小

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 样例1
     输入：
    ["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
    [[1], [0, 1], [0, 2], [0], [0], [0], [0]]
     输出：
    [null, null, null, 1, -1, -1, true]
    说明：当栈为空时`pop, peek`返回-1，当栈满时`push`不压入元素。
        
    # 样例2
    输入：
    ["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]
    [[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]
     输出：
    [null, null, null, null, 2, 1, -1, -1]

    # 提示：
    0 <= stackNum <= 2
阅读全文 »

发表于 更新于 分类于 ，
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目：

  • 给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。

    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况

  • ~~~python # 样例1 输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点

    样例2

    输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点 

    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
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59

    <!--more-->

    ### 解题方法：

    {% note warning%}

    哈希表法思路比较简洁明了，需要注意的是存储的是node地址，而非值；快慢指针是很重要的技巧，需要熟练掌握，优点是时间复杂度和哈希表法相同，但是只用$O(1)$的额外空间

    {% endnote %} 

    1. **哈希表法：**遍历链表，每经过一个node就把他的地址放到表里，第一个重复的地址即为圈的首节点

       {% note primary %}

       时间复杂度为$O(n)$，额外的空间复杂度为$O(n)$

       {% endnote %} 

    3. **快慢指针：**

       {% note primary %}

       时间复杂度为$O(n)$，额外的空间复杂度为$O(1)$

       {% endnote %} 


    ### 解法一：哈希表法

    {% note warning %}

    - map、set、unordered_map、unordered_set总结：https://blog.csdn.net/qq_30815237/article/details/91047041


    {% endnote %}

    ~~~c++
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            unordered_set<ListNode *> visited;
            while(head != NULL)
            {
                if(visited.count(head) == 1) 
                // if(visited.find(head) != visited.end())
                // count实测比find函数快，执行时间分别是4ms和8ms
                {
                    return head;
                }
                else
                {
                    visited.insert(head);
                    head = head->next;
                }
            }
            return NULL;
        }
    };

解法二：快慢指针

解题思路：

  • 使用两个指针，fast与slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇
    • 此时fast走的距离为 \(a+n(b+c)+b\)，此时slow走了 \(a+m(b+c)+b\) 的距离
    • 根据定义，fast走了slow的两倍距离，因此 \(a+n(b+c)+b=2(a+m(b+c)+b)\)
    • 解得 \(a=(n-2m-1)*(b+c)+c\)
  • 相遇后：新建指针p = head从头走，slow和p一起走，当p走了\(a\)步时，slow也走了\((n-2m-1)*(b+c)+c\) 步，即\(n-1\)圈再加上额外的\(c\)步，即相遇时为环的起点

证明1：快慢指针一定会相遇吗？（数学归纳法）

  • 如果两指针间距为一，则两者再走一次就相遇了
  • 如果间距为n，则两者再走一次后，间距就变为 \(n+1-2=n-1\) 了，重复这个过程，直至两者相遇

证明2：快指针的速度是慢指针的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
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL) return NULL;
        ListNode *slow = head, *fast = head, *p = head;
        while(fast->next!=NULL)
        {
            if(fast->next->next == NULL) break;
            fast = fast->next->next;
            slow = slow->next;            

            if(fast == slow)
            {
                // cout << fast->val;
                while(slow != p) 
                // p和slow刚好在环的起始节点相遇，两者走的距离都是a=(n-1)*(b+c)+c
                {
                    slow = slow->next;
                    p = p->next;
                }
                return p;
            }
            
        }
        return NULL;
    }
};

发表于 分类于 ，
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目：

  • 给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 样例1
    输入：s1 = "waterbottle", s2 = "erbottlewat"
    输出：True
        
    # 样例2
    输入：s1 = "aa", s2 = "aba"
    输出：False

    # 提示：
    字符串长度在[0, 100000]范围内。

    # 说明:
    你能只调用一次检查子串的方法吗？
阅读全文 »

发表于 分类于 ，
本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目：

  • 编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

    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
    # 样例1
    输入：
    [
      [1,1,1],
      [1,0,1],
      [1,1,1]
    ]
    输出：
    [
      [1,0,1],
      [0,0,0],
      [1,0,1]
    ]
        
    # 样例2
    输入：
    [
      [0,1,2,0],
      [3,4,5,2],
      [1,3,1,5]
    ]
    输出：
    [
      [0,0,0,0],
      [0,4,5,0],
      [0,3,1,0]
    ]
阅读全文 »

发表于 分类于 ，
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目：

  • 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

    不占用额外内存空间能否做到？

    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
    # 样例1
    给定 matrix = 
    [
      [1,2,3],
      [4,5,6],
      [7,8,9]
    ],

    原地旋转输入矩阵，使其变为:
    [
      [7,4,1],
      [8,5,2],
      [9,6,3]
    ]
        
    # 样例2
    给定 matrix =
    [
      [ 5, 1, 9,11],
      [ 2, 4, 8,10],
      [13, 3, 6, 7],
      [15,14,12,16]
    ], 

    原地旋转输入矩阵，使其变为:
    [
      [15,13, 2, 5],
      [14, 3, 4, 1],
      [12, 6, 8, 9],
      [16, 7,10,11]
    ]
阅读全文 »