[数据结构与算法]LeetCode 热题 HOT 100 第十二天

Leetcode200. 岛屿数量

思路：Flood fill算法使用DFS实现

class Solution {
public:
    int ans = 0;
    int n, m;
    vector<vector<char>> g;
    int numIslands(vector<vector<char>>& grid) {
        n = grid.size(), m = grid[0].size();
        g = grid;
        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < m; j ++ ) {
                if (g[i][j] == '1') {
                dfs(i, j);
                ans ++ ;
                }
            }
        }
        return ans;
    }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    void dfs(int x, int y) {
        g[x][y] = '0';
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '1') {
                dfs(a, b);
            }
        }
    }
};

Leetcode206. 反转链表

思路： 迭代法

双指针，两个指针分别指向前后两个结点，让第二个指针指向第一个指针的位置，两个指针后移，最后头结点指向空节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return head;
        auto a = head, b = head->next;
        while (b) {
            auto c = b->next;
            b->next = a;
            a = b;
            b = c;
        }
        head->next = nullptr;
        return a;
    }
};

思路二：递归算法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};

Leetcode207. 课程表

思路：拓扑排序

如果说拓扑排序以后元素的个数是n说明，每一门课程都是可以学完的

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        vector<int> d(n);
        for (auto& edge : edges) {
            int a = edge[0], b = edge[1];
            g[b].push_back(a);
            d[a] ++ ;
        }

        queue<int> q;
        for (int i = 0; i < n; i ++ )
            if (!d[i])
                q.push(i);
        
        int cnt = 0;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            cnt ++ ;
            for (auto& c : g[t]) {
                if ( -- d[c] == 0)
                    q.push(c);
            }
        }
        return cnt == n;
    }
};

LeetCode208. 实现 Trie (前缀树)

思路：

$Trie$树一般使用结构体实现，首先创建一颗树，如果单词结尾打上标记。查找的时候，没有分支$returnfalse;$否则一直找，如果单词结束但是不是结尾$returnfalse$

class Trie {
public:
    struct Node {
        bool is_end;
        Node *son[26];
        Node() {
            is_end = false;
            for (int i = 0; i < 26; i ++ )
                son[i] = NULL;
        }
    }*root;
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        auto p = root;
        for (auto& c : word) {
            int u = c - 'a';
            if (!p->son[u]) p->son[u] = new Node();
            p = p->son[u];
        }
        p->is_end = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        auto p = root;
        for (auto& c : word) {
            int u = c - 'a';
            if (!p->son[u]) return false;
            p = p->son[u];
        }
        return p->is_end;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string word) {
                auto p = root;
        for (auto& c : word) {
            int u = c - 'a';
            if (!p->son[u]) return false;
            p = p->son[u];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

LeetCode215. 数组中的第K个最大元素

思路：快速排序

快排递归排序过程中，只排序存在k的区间，剩下的元素就是第k大的数

class Solution {
public:
    int quick_sort(vector<int>& nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i ++ ; while (nums[i] > x);
            do j -- ; while (nums[j] < x);
            if (i < j) swap(nums[i], nums[j]);
        }
        if (k <= j) return quick_sort(nums, l, j, k);
        else return quick_sort(nums, j + 1, r, k);
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quick_sort(nums, 0, nums.size() - 1, k - 1);
    }
};