logo头像

不忘初心,奋力前行

Leetcode题目解析(191112):200&206

Leetcode 200:岛屿数量

题目描述

给定一个由 ‘1’(陆地)和 ‘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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

class UnionFind {
public:
    UnionFind(vector < vector<char>> & grid) {
        count = 0;
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == '1') {
                    parent.push_back(i * n + j);
                    ++count;
                }
                else {
                    parent.push_back(-1);
                }
                rank.push_back(0);
            }
        }
    }
    int find(int i) {
        if (parent[i] != i)
            parent[i] = find(parent[i]);
        return parent[i];
    }
    void Union(int x, int y)
    {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty)
        {
            if (rank[rootx] > rank[rooty])
                parent[rooty] = rootx;
            else if (rank[rootx] < rank[rooty])
                parent[rootx] = rooty;
            else {
                parent[rooty] = rootx;
                rank[rootx] += 1;
            }
            --count;
        }
    }
    int getCount() const {
        return count;
    }
private:
    vector<int> parent;
    vector<int> rank;
    int count;
};
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();
        UnionFind uf(grid);
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    grid[r][c] = '0';
                    if (r - 1 >= 0 && grid[r - 1][c] == '1') uf.Union(r * nc + c, (r - 1) * nc + c);
                    if (r + 1 < nr && grid[r + 1][c] == '1') uf.Union(r * nc + c, (r + 1) * nc + c);
                    if (c - 1 >= 0 && grid[r][c - 1] == '1') uf.Union(r * nc + c, r * nc + c - 1);
                    if (c + 1 < nc && grid[r][c + 1] == '1') uf.Union(r * nc + c, r * nc + c + 1);
                }
            }
        }
        return uf.getCount();
    }
};

Leetcode 206:反转链表

题目描述

反转一个单链表。

示例

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路

首先我们应该考虑两个问题(鲁棒性):

  1. 链表为空呢?返回空。
  2. 链表就只有一个结点呢?返回这个结点。

其它一般情况就是多个结点了。为了正确翻转一个链表,需要调整链表中指针的方向。我们假设有下面三个结点:a->b->c,假设我们要翻转b的next指向a,那么指向a之后,b和c之间的联系就断了,因此我们需要把结点c的地址保存下来。也就是说,我们在调整结点b的next指针的时候,除了需要知道结点b本身,还需要知道结点b的前一个结点a,因为我们要把结点b的next指针指向a。同时,我们还需要实现保存b的一个结点c,以防止链表断开。

我们新建一个next指针,让它来保存b指针的next所指向的地址,然后把a的next指向NULL,然后令node=a,然后把lnode=b;这个时候,进入下一个循环,next指向了c,然后把b的next指向了a,然后令node=b,然后将lnode往下指向c;下一个循环,next=空了,然后把c的next指向了b,然后node=c,然后lnode=空。这个时候判断了lnode为空,结束循环,形成了a<-b<-c

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13

 ListNode* reverseList(ListNode* head) {
    ListNode* node = head;
    ListNode* pre = nullptr;
    while (node != nullptr)
    {
        ListNode* temp = node->next;
        node->next = pre;
        pre = node;
        node = temp;
    }
    return pre;
}

复杂度分析

时间复杂度:O(n),空间复杂度:O(1)

运行时间

支付宝打赏 微信打赏 QQ钱包打赏

感觉不错?欢迎给我 打个赏~我将不胜感激!