Leetcode 200：岛屿数量

题目描述

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

代码实现


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

解题思路

首先我们应该考虑两个问题（鲁棒性）：

链表为空呢？返回空。
链表就只有一个结点呢？返回这个结点。

其它一般情况就是多个结点了。为了正确翻转一个链表，需要调整链表中指针的方向。我们假设有下面三个结点：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。

代码实现


 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;
}