头像

滑稽_ωノ

河北科技师范学院




离线:4小时前



原文链接: LRU和LFU实现 - Dillonh

LRU

原题链接: LeetCode146. LRU 缓存机制

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if(mp.find(key) == mp.end()) return -1;
        put(key, mp[key]->second);//借助put函数来进行更新
        return mp[key]->second;
    }

    void put(int key, int value) {
        if(mp.find(key) != mp.end()) {
            recent.erase(mp[key]);
        } else if(mp.size() == capacity) {
                mp.erase(recent.back().first);
                recent.pop_back();
        }
        recent.push_front(make_pair(key, value));
        mp[key] = recent.begin();
    }
private:
    int capacity;//LRU的容量
    list<pair<int,int>> recent;//用双向链表来实现LRU的功能,头为最近使用,尾为最远使用
    unordered_map<int, list<pair<int,int>>::iterator> mp;//key值对应队列中的结点
};

LFU

原题链接: LeetCode460. LFU 缓存

class LFUCache {
public:
    LFUCache(int capacity) : capacity(capacity), lst(0) {}

    int get(int key) {
        if(all.count(key) == 0) return -1;
        put(key, all[key].first);//借助put函数来更新
        return all[key].first;
    }

    void put(int key, int value) {
        if(capacity == 0) return;
        if(all.count(key) == 0) {
            if((int)all.size() >= capacity) {
                all.erase(fre[lst].back());
                pos.erase(fre[lst].back());
                fre[lst].pop_back();
            }
            lst = 1;//新增加一个key那么最低频率肯定是1
            all[key] = {value, 1};
            fre[1].push_front(key);
            pos[key] = fre[1].begin();
        } else {
            int cnt = all[key].second;
            ++all[key].second;
            fre[cnt].erase(pos[key]);
            fre[cnt+1].push_front(key);
            pos[key] = fre[cnt+1].begin();
            all[key].first = value;
            if(fre[lst].size() == 0) ++lst;
        }
    }
private:
    int capacity, lst;//LFU的容量、最低频率
    unordered_map<int, list<int>> fre;//每个频率存一个链表
    unordered_map<int, pair<int,int>> all;//key对应的value和频率
    unordered_map<int, list<int>::iterator> pos;//key对应的链表中的位置
};


活动打卡代码 AcWing 3240. 压缩编码

区间DP

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int w[N], sum[N];
int f[N][N];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)  scanf("%d", &w[i]),  sum[i] = sum[i - 1] + w[i];

    for(int len = 2; len <= n; len ++)
        for(int i = 1; i + len - 1 <= n; i ++)
        {
            int j = i + len - 1;

            f[i][j] = 2e9;
            for(int k = i; k < j; k ++)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
        }
    printf("%d\n", f[1][n]);
    return 0;
}


活动打卡代码 AcWing 3257. 跳一跳

#include<cstdio>

int main()
{
    int res = 0, len = 0, x;
    while(~scanf("%d", &x))
    {
        if(x == 2)  res += 2 * ( ++ len);
        else
        {
            len = 0;
            res += x;
        }
    }
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 3250. 通信网络

#include<cstdio>
#include<cstring>

const int N = 1010, M = 20010;

int h[N], hs[N], e[M], ne[M], idx;
void add(int h[], int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool st[N], vis[N];
void dfs(int u, int h[])
{
    st[u] = vis[u] = true;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j])  dfs(j, h);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);

    int n, m;
    scanf("%d%d", &n, &m);
    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(h, a, b);
        add(hs, b, a);
    }

    int res = 0;
    for(int i = 1; i <= n; i ++)
    {
        memset(vis, 0, sizeof vis);

        memset(st, 0, sizeof st);
        dfs(i, h);
        memset(st, 0, sizeof st);
        dfs(i, hs);

        int cnt = 0;
        for(int j = 1; j <= n; j ++)
            if(vis[j])  cnt ++;
        if(cnt == n)  res ++;
    }
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 3227. 折点计数

#include<cstdio>

const int N = 1010;

int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)  scanf("%d", &a[i]);

    int res = 0;
    for(int i = 2; i < n; i ++)
        if(a[i] > a[i - 1] and a[i] > a[i + 1] or a[i] < a[i - 1] and a[i] < a[i + 1])  res ++;
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 3215. 网络延时

树的直径

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 20010, M = N << 1;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int d[N], res;
void dfs(int u, int fa)
{
    res = max(res, d[u]);
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa)  continue;
        d[j] = d[u] + 1;
        dfs(j, u);
    }
}

int main()
{
    memset(h, -1, sizeof h);

    int n, m;
    scanf("%d%d", &n, &m);
    n += m;
    for(int i = 2; i <= n; i ++)
    {
        int x;
        scanf("%d", &x);
        add(x, i),  add(i, x);
    }

    dfs(1, -1);
    int rt = 1;
    while(d[rt] != res)  rt ++;
    d[rt] = 0;
    dfs(rt, -1);
    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 3232. 最大波动

#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1010;

int a[N];

int main()
{
    int n;
    scanf("%d", &n);

    int res = 0;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        if(i > 1)  res = max(res, abs(a[i] - a[i - 1]));
    }
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 3205. 最优配餐

BFS

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n;
int cnt[N][N], d[N][N];
PII q[M];
int hh = 0, tt = -1;

LL bfs()
{
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};

    LL res = 0;
    while(hh <= tt)
    {
        PII u = q[hh ++];
        int x = u.x, y = u.y;
        res += (LL)d[x][y] * cnt[x][y];

        for(int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a >= 1 and a <= n and b >= 1 and b <= n and cnt[a][b] != -1 and d[a][b] == -1)
            {
                d[a][b] = d[x][y] + 1;
                q[ ++ tt] = {a, b};
            }
        }
    }
    return res;
}

int main()
{
    memset(d, -1, sizeof d);

    int m, k, p;
    scanf("%d%d%d%d", &n, &m, &k, &p);
    vector<PII> v;
    while(m --)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        d[x][y] = 0;
        q[ ++ tt] = {x, y};
    }
    while(k --)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        cnt[x][y] += c;
    }
    while(p --)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        cnt[x][y] = -1;
    }
    printf("%lld\n", bfs());
    return 0;
}


活动打卡代码 AcWing 3203. 画图

#include<cstdio>

const int N = 110;

int a[N][N];

int main()
{
    int n;
    scanf("%d", &n);
    while(n --)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        for(int i = x1; i < x2; i ++)
            for(int j = y1; j < y2; j ++)
                a[i][j] = 1;
    }

    int res = 0;
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
            res += a[i][j];
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 3195. 有趣的数

隔板法

#include<cstdio>

typedef long long LL;

const int N = 2010, mod = 1e9 + 7;

int qmi(int a, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1)  res = (LL)res * a % mod;
        k >>= 1;
        a = (LL)a * a % mod;
    }
    return res;
}

int fact[N], infact[N];
void init()
{
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i ++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = qmi(fact[i], mod - 2);
    }
}

int C(int a, int b)
{
    if(a < b)  return 0;
    return (LL)fact[a] * infact[a - b] % mod * infact[b] % mod;
}

int main()
{
    init();

    int n;
    scanf("%d", &n);

    int res = 0;
    for(int i = 2; i <= n - 2; i ++)
        res = (res + (LL)C(n - 1, i - 1) * (i - 1) % mod * (n - i - 1)) % mod;
    printf("%d\n", res);
    return 0;
}