Neo's Blog

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

字符串哈希 —— 模板题 AcWing 841. 字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

class Solution {
public:
    void reverse(string& s, int i, int j) {
        while (i < j) {
            swap(s[i++], s[j--]);
        }
    }

    string trans(string s, int n) {
        int begin = 0;
        for (int i = 0; i < s.length();) {
            if (s[i] == ' ') {
                reverse(s, begin, i - 1);
                i++;
                begin = i;
            }
            else {
                i++;
            }
        }
        reverse(s, begin, s.length() - 1);

        reverse(s, 0, s.length() - 1);

         for (int i = 0; i < s.length(); ++i) {
             if (s[i] >= 'a' && s[i] <= 'z') {
                 s[i] = 'A' + (s[i] - 'a');
             } else if (s[i] >= 'A' && s[i] <= 'Z') {
                 s[i] = 'a' + (s[i] - 'A');
             }  
         }
        return s;
    }
};

//单调栈 —— 模板题 AcWing 830. 单调栈
//常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

vector<int> dailyTemperatures(vector<int>& t) {
    int n = t.size();
    stack<int> s;
    int top = 0;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && t[i] > t[top = s.top()]){
            t[top] = i - top;
            s.pop();
        }

        s.push(i); //压入了一个更小的，递减栈
    }


    while (!s.empty()) {
        t[s.top()] = 0;
        s.pop();
    }
    return t;
}

//队列 —— 模板题 AcWing 829. 模拟队列
1. 普通队列：
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)  //如果hh <= tt, 则队列不空。
{

}

//2. 循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt) //只要两者不相等，队列就不空。
{

}

class MyQueue {
public:
    stack<int> is;
    stack<int> os;
    
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        is.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if (os.empty()) {
            while (!is.empty()) {
                os.push(is.top());
                is.pop();
            }
        }
        int r = os.top();
        os.pop();
        return r;
    }
    
    /** Get the front element. */
    int peek() {
        if (os.empty()) {
            while (!is.empty()) {
                os.push(is.top());
                is.pop();
            }
        }
        return os.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return is.empty() && os.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */

//单调队列 —— 模板题 AcWing 154. 滑动窗口
//常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    //新的元素入队
    q[ ++ tt] = i;
}

struct ListNode {
    int val;
    ListNode* next;
    ListNode* pre;
}


class LRUCache {
private:
    unordered_map<int, ListNode*> hash;
    ListNode* head;
    ListNode* tail;
    int n;

    LRUCache(int nn) {
        n = nn;
        head = new ListNode();
        tail = new ListNode();
        head->next = tail;
        tail->pre = head;
    } 

    void put(int k, int v) {
        ListNode* r = get2(k);
        if (r != NULL) return;

        ListNode* node = NULL;
        if (hash.size() > n) {
            //链表上移除
            auto node = tail->pre;
            node->next->pre = node->pre;
            node->pre->next = node->next;  
            //hash移除 
            hash.erase(node->k);
        }
        else {
            node = new ListNode();
        }

        node.val = v;
        //将node放在头部
        node->next = head->next;
        node->pre = head;
   
        head->next->pre = node;
        head->next = node;

        hash[k] = node;

    }

    ListNode* get2(int k) {
        auto it = hash.find(k);
        if it == hash.end() {
            return NULL;
        }

        auto node = *it;
        
        //移除
        node->next->pre = node->pre;
        node->pre->next = node->next;

        node->next = head->next;
        node->pre = head;
   
        head->next->pre = node;
        head->next = node;
    }

    int get(int k) {
        ListNode* r = get2(k);
        if (r == NULL) return -1;
        else r->val;
    }
};