Neo's Blog

//队列 —— 模板题 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;
    }
};

堆 —— 模板题 AcWing 838. 堆排序, AcWing 839. 模拟堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;  //[l, mid], [mid + 1, r]
            int s = 0;
            //注意这里是遍历了所有的元素
            for (int i = 0; i < nums.size(); ++i) s += (nums[i] >= l && nums[i] <= mid);
            if (s > (mid - l + 1)) r = mid;
            else l = mid + 1; //数量不够，说明这个区间内的某个数肯定被替换掉了，所以肯定在另外一边。
        }
        
        return r;
    }
};

#include <iostream>
#include <algorithm>

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) 
            if (nums[i] < 0 || nums[i] > n - 1) return -1;
        
        for (int i = 0; i < n; ++i) {
            while (i != nums[i]) {
                int x = nums[i];
                if (nums[x] == x) return x; //如果坑位已经被占了，说明重复了。
                else swap(nums[x], nums[i]);
            }
        }
        x
        return -1;
    }
};

int rand10()
{
int x;
do
{
    x = (rand7()-1)*7+rand7();
}while(x > 40)  //【1, 40】的范围
return (x-1） / 4+1; //分为10段，0～9 + 1 =》 1 ～ 10
}

int randB()
{
int x1, x2;
do
{
    x1 = randA();
    x2 = randA();
}while(x1+x2 != 1)
return x1;
}

// 得到一个在闭区间 [min, max] 内的随机整数
int randInt(int min, int max);

void shuffle(int[] arr) {
    int n = arr.length();
    for (int i = 0 ; i < n; i++) {
        // 从 i 到最后随机选一个元素
        int rand = randInt(i, n - 1);
        swap(arr[i], arr[rand]);
    }
}

void generate(int m,int n)
{
int t = m;
for(int i = 0; i < n; i++)
    if(Rand(0,n-1-i) < t) //即以t/(n-i)的概率执行下面的语句
    {
        printf("%d\n",i); //这里打印的是i，一直在增长；所以不会重复！！！
        t--;
    }
}
//随着算法继续，i越大，rand（0，n-1-i)得到的数值越小，就容易被选中，
//如果i已经等于n-1-t了，则后面的必然全不都被选中。

int i = 0;
vector<int> res;
while (cin >> Elem) {
    i++;
    if (i < N) {
        res.push(Elem);
        continue;
    }

    X = rand(0, i); 
    if (X < N) {
        swap(res[X], res[i]);
    }
}