Leetcode_01

239滑动窗口最大值

使用deque(double ended queue)维护一个单调队列，此队列就是窗口移动过程中每个位置的内部最大值

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            // 如果输入空数列
            if (nums.size() == 0 || k == 0)
                return {};

            deque<int> deque;
            // 输出的数列为nums.size - (k-1)
            vector<int> ans(nums.size() - k + 1);

            for (int j = 0, i = 1 - k; j < nums.size(); i++, j++) {
                if (i > 0 && deque.front() == nums[i - 1])
                    deque.pop_front();

                while (!deque.empty() && deque.back() < nums[j])
                    deque.pop_back();
                deque.push_back(nums[j]);

                if (i >= 0)
                    ans[i] = deque.front();
            }
            return ans;
        }
};

200岛屿数量

208Trie

是一种特殊的树，以英文字母为例，其子结点的next指针是一个大小为26的数组，下标表示值(26个英文字母)。
通过next沿Trie树向下移动，最后根据isEnd判断单词是否结束

#include <iostream>
#include <string>
using namespace std;

class Trie {
    private:
        bool isEnd;
        Trie*  next[26];
    public:
        void insert(string word);
        bool search(string word);
        bool startsWith(string prefix);
};


void Trie::insert(string word) {
    Trie* node = this;
    for (char c : word) {
        if (node->next[c - 'a'] == NULL) {
            node->next[c - 'a'] = new Trie();
        }
        node = node->next[c - 'a'];
    }

    node->isEnd = true;
}

bool Trie::search(string word) {
    Trie* node = this;
    for (char c : word) {
        node = node->next[c - 'a'];
        if (node == NULL) {
            return false;
        }
    }
    return node->isEnd;
}

bool Trie::startsWith(string prefix) {
    Trie *node = this;
    for (char c : prefix) {
        node = node->next[c - 'a'];
        if (node == NULL) {
            return false;
        }
    }
    return true;
}