发布笔记随写26 分钟读完 (大约3921个字)  次访问

LeetCode刷题技巧

春招季过了，在此整理下刷LeetCode题时常用的技巧，以及一些常见题型。

C++/Java/Python 刷题常用技巧

C++

万能头文件

1
#include <bits/stdc++.h>

迭代器最大值

1
*max_element(nums.begin(), nums.end())

数组大小

1
2
3
4
5
6
7
8
 // vector
 nums.size();

// array
int length = sizeof (arr) / sizeof (arr[0]);

// 字符串长度
str.length()

拷贝数组

1
copy(tmp.begin(),tmp.end(),dst.begin());

vector合并

1
2
3
4
5
6
vector<int> vec1 = {...};
vector<int> vec2 = {...};// vec1和vec2都存有内容

vector<int> vec3;//vec3是空的
vec3.insert(vec3.end(),vec1.begin(),vec1.end())//将vec1压入
vec3.insert(vec3.end(),vec2.begin(),vec2.end())//继续将vec2压入

vector赋值

1
2
3
4
5
6
7
vector<int> f;
f.assign(n, -1);

vector<int> ff(n,-1);

emplace_back(k,v);
push_back(make_pair(k,v))

vector/list 删除

1
2
it=vec.begin();
vec.erase(it);

列表翻转/求和

1
2
std::reverse(v.begin(), v.end());
int sum = std::accumulate(v.begin(), v.end(), 0);	// init_value=0

string相关

1
2
3
4
5
6
7
8
9
10
11
// 查找
string s("1a2b3c4d5e6f7jkg8h9i1a2b3c4d5e6f7g8ha9i");
position = s.find("jk");
if (position != s.npos)  //如果没找到，返回一个特别的标志c++中用npos表示，我这里npos取值是4294967295，
{
    printf("position is : %d\n" ,position);
}

// 可用作栈
str.pop_back();
str.push_back(ch);

字符串分割

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 方法一：检索
vector<string>  split(const string& str,const string& delim) { //将分割后的子字符串存储在vector中
	vector<string> res;
	if("" == str) return  res;
	
	string strs = str + delim; //*****扩展字符串以方便检索最后一个分隔出的字符串
	size_t pos;
	size_t size = strs.size();
 
	for (int i = 0; i < size; ++i) {
		pos = strs.find(delim, i); //pos为分隔符第一次出现的位置，从i到pos之前的字符串是分隔出来的字符串
		if( pos < size) { //如果查找到，如果没有查找到分隔符，pos为string::npos
			string s = strs.substr(i, pos - i);//*****从i开始长度为pos-i的子字符串
			res.push_back(s);//两个连续空格之间切割出的字符串为空字符串，这里没有判断s是否为空，所以最后的结果中有空字符的输出，
			i = pos + delim.size() - 1;
		}
		
	}
	return res;	
}

// 方法二：stringstream（只适用于空格等分隔符）
vector<string> split_str(string s){
    stringstream ss(s);
    vector<string> words;
    string word;
    while(ss>>word){
      	words.push_back(word);
    }

    return words;
}

sort函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
/*
sort	对给定区间所有元素进行排序
stable_sort	对给定区间所有元素进行稳定排序
partial_sort	对给定区间所有元素部分排序
partial_sort_copy	对给定区间复制并排序
nth_element	找出给定区间的某个位置对应的元素
is_sorted	判断一个区间是否已经排好序
partition	使得符合某个条件的元素放在前面
stable_partition	相对稳定的使得符合某个条件的元素放在前面
*/
int arr[] = { 2, 4, 5, 3, 1 };
sort(arr, arr + 5, greater<int>());

#include<qsort>
void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
/*
1 待排序数组首地址
2 数组中待排序元素数量
3 各元素的占用空间大小
4 指向函数的 指针，用于确定排序的顺序
*/

// 排序索引
template <typename T>
std::vector<int> sort_indexes(const std::vector<T> &v) {
  // 初始化索引向量
  std::vector<int> idx(v.size());
  //使用iota对向量赋0~？的连续值
  std::iota(idx.begin(), idx.end(), 0);
  // 通过比较v的值对索引idx进行排序
  //NOTE: lambda函数 auto fun = [捕获参数](函数参数){函数体};
  std::sort(idx.begin(), idx.end(), [&v](int i1, int i2) { return v[i1] < v[i2]; });
  return idx;
}

全排列

1
2
3
4
5
6
7
8
9
#include <algorithm>
bool next_permutation(iterator start,iterator end);
//当序列不存在下一个排列时，函数返回false，否则返回true
// 需要先按升序排序！！！！

do  
{  
    cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;  
}while(next_permutation(num,num+3));

unordered_set

1
2
3
4
5
insert()	//向容器中添加新元素。
erase()	//删除指定元素。
clear()	//清空容器，即删除容器中存储的所有元素。
myset.find(x) != myset.end()	//存在
myset.count(x)

multiset(可以保存重复元素)

红黑树实现，默认升序

1
2
3
4
5
6
#include <set>

st.erase(x) // 删除所有值为x的项
st.erase(myset.find(x)) // 删除一个
st.upper_bound(20); // 返回 iterator，未找到 multiset::end
*it 取值

map查询元素是否存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 使用 find() 函数检查元素是否存在
auto it = mymap.find("a");
if (it != mymap.end()) {
  // 元素存在
} else {
  // 元素不存在
}

// 使用 count() 函数检查元素是否存在
int count = mymap.count("a");
if (count > 0) {
  // 元素存在
} else {
  // 元素不存在
}

map遍历

1
2
3
4
5
6
7
8
9
10
for (auto& [first, second] : mp){

}
// or
map<int, int>::iterator iter;
iter = _map.begin();
while(iter != _map.end()) {
    cout << iter->first << " : " << iter->second << endl;
    iter++;
}

tie批量赋值

1
tie(dp0,dp1)=make_tuple(min(dp0,dp1)+cost[i],min(dp0,dp1+cost[i-1]));

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆
*/

#include <queue>
//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;

q.empty()          //如果队列为空，则返回true，否则返回false

q.size()           //返回队列中元素的个数

q.pop()            //删除队首元素，但不返回其值

q.top()            //返回具有最高优先级的元素值，但不删除该元素

q.push(item);       //在基于优先级的适当位置插入新元素

    
// 自定义排序规则
auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) {
            return a.second == b.second ? a.first < b.first : a.second > b.second;
        };
priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> que(cmp);

双端队列

1
2
3
4
5
6
7
8
#include <deque>
deque<int> dq1(8);
deque<int> dq1(8,0);

push_back();
push_front();
back();
front();

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int search(vector<int>& nums, int target) {
    int l=0;
    int r=nums.size()-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(nums[mid]>target){
            r=mid-1;
        }else if(nums[mid]<target){
            l=mid+1;
        }else{
            return mid;
        }
    }
    return -1;
}
1
2
3
4
// STL 二分查找排好序的数组
lower_bound( begin,end,num) // 第一个大于或等于num的数字
upper_bound( begin,end,num) // 第一个大于num的数字
lower_bound( vec.begin(),vec.end(),num,greater<type>() ) // 第一个小于或等于num的数字

子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 二进制掩码
vector<vector<int>> subsets(vector<int>& nums) {
    vector<int> t;
    vector<vector<int>> ans;
    int n = nums.size();
    for (int mask = 0; mask < (1 << n); ++mask) {
        t.clear();
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                t.push_back(nums[i]);
            }
        }
        ans.push_back(t);
    }
    return ans;
}

// 迭代
vector<vector<int>> subsets(vector<int>& nums) {
    int n=nums.size();
    vector<vector<int>> res(1,vector<int>());

    for(auto i:nums){
        vector<vector<int>> tmp;
        for(auto &pre:res){
            vector<int> t=pre;
            t.push_back(i);
            tmp.push_back(t);
        }
        res.insert(res.end(),tmp.begin(),tmp.end());
    }
    return res;
}

二分图最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct Edge
{
    int from;
    int to;
    int weight;

    Edge(int f, int t, int w):from(f), to(t), weight(w) {}
};

vector<int> G[__maxNodes]; // G[i] 存储顶点 i 出发的边的编号 
int matching[__maxNodes]; /* 存储求解结果 */
int check[__maxNodes];	// 标志位

bool dfs(int u)
{
    for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 对 u 的每个邻接点
        int v = edges[*i].to;
        if (!check[v]) {     // 要求不在交替路中
            check[v] = true; // 放入交替路
            if (matching[v] == -1 || dfs(matching[v])) {
                // 如果是未盖点，说明交替路为增广路，则交换路径，并返回成功
                matching[v] = u;
                matching[u] = v;
                return true;
            }
        }
    }
    return false; // 不存在增广路，返回失败
}

int main()
{
    int ans = 0;
    memset(matching, -1, sizeof(matching));
    for (int u=0; u < num_left; ++u) {
        if (matching[u] == -1) {
            memset(check, 0, sizeof(check)); // 清除标志位
            if (dfs(u))
                ++ans;
        }
    }
    return ans;
}

位运算技巧

1
2
3
n&1;	// 取最低位
n&(n-1);	// 去除最低位的 1	（若n为2的幂，结果为0）
n&(-n);	//只取最低位的 1 （若n为2的幂，结果为n）

Java

String相关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void string_test() {
        String s1 = new String("abc123 321 q w 测试 p");
        System.out.println(s1);
        String s2 = s1.substring(3, 6);
        System.out.println(s2);

        String[] ss = s1.split(" ");    // 字符串分割
        System.out.printf("the second part is: %s\n", ss[1]);
        System.out.println(Arrays.toString(ss));    // 输出列表

        // str -> int
        int i1 = Integer.parseInt(s2);
        Integer i2 = Integer.valueOf(s2);
    }

数组相关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    public static void array_test() {
        Integer[] a = {1,3,2,4,10,5};
        Arrays.sort(a);

        System.out.println(a.length);
        
        Arrays.sort(a, Collections.reverseOrder()); // 必须用包装类

        // Comparator<Integer> myCom = new CMP();
        // Arrays.sort(a, myCom);
        System.out.println(Arrays.toString(a));
    }
// 自定义比较函数
class CMP implements Comparator<Integer>{
    @Override //可以去掉。作用是检查下面的方法名是不是父类中所有的
    public int compare(Integer a,Integer b){
//        两种都可以，升序排序的话反过来就行
//        return a-b<0?1:-1;
        return b-a;
    }
}

数组求和

1
Arrays.stream(array).sum();

Python

输入

  1. 输入一行

    1
    listt=map(lambda x:int(x),raw_input().split())

  2. 输入N行

    1
    2
    3
    4
    5
    6
    7
    n = input()
    def f(x):
        if ord(x[0]) < 58:  # 判断是数字还是字母
            return int(x)
        return x
    a = [map(f, raw_input().split()) for i in range(n)]
    a=[map(lambda x:int(x) if ord(x[0])<58 else x,raw_input().split())for i in range(n)]

  3. 多样例输入（EOF）

    1
    2
    3
    4
    import sys    
    for line in sys.stdin:
        print int(line)**2
    # pow(3,2,4) == 3**2%4

输出

  1. 字符串拼接输出

    1
    2
    3
    4
    strr = ''  # 创建一个空字符串
    for i in listt:
        strr += i  # 依次添加 i，若是数字，记得换为str(i)
    print strr

  2. 一行输出列表

    1
    print str(a).replace(', ',' ').replace('\'','')[1:-1]+' '

一些算法

基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void radixSort(vector<int>& nums){
        int maxVal = *max_element(nums.begin(),nums.end());
        int len = nums.size();
        vector<int> tmp(len);
        
        int exp=1;
        while(maxVal>=exp){
            // 相当于10个指针，记录下标位置
            vector<int> cnt(10);
            // 统计每个桶中元素个数
            for(int i=0;i<len;i++){
                int mod=nums[i]/exp%10;
                cnt[mod]++;
            }
            // 计算每个桶的下标结束位置
            for(int i=1;i<10;i++){
                cnt[i]+=cnt[i-1];
            }
            // 填充新元素
            for(int i=len-1;i>=0;i--){
                int mod=nums[i]/exp%10;
                tmp[cnt[mod]-1]=nums[i];
                cnt[mod]--;
            }
            exp*=10;
            copy(tmp.begin(),tmp.end(),nums.begin());
        }
    }

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;		// 父节点
        rank[i] = 1;	// 深度
    }
}
int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //递归找父亲的父亲设为根节点
        return fa[x];         //返回父节点
    }
    // return x == fa[x] ? x : (fa[x] = find(fa[x]));	// 精简形式
}
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);
    if (rank[x] <= rank[y])	// 深度大的做根节点
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)	// 深度相同时，新根节点深度+1
        rank[y]++;
}

快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void quickSort(int[] s, int l, int r){
    if(l>=r)return;
    int i = l, j = r, x = s[l];
    while(i<j){
        while(i<j&&s[j]>=x){
            j--;
        }
        if(i<j){	// 第一位取出来了，所以可以放进去
            s[i++]=s[j];
        }
        while(i<j&&s[i]<x){
            i++;
        }
        if(i<j){
            s[j--]=s[i];
        }
    }
    // i==j时出来
    s[i]=x;		// 再把标准值放回中间
    quickSort(s,l,i-1);
    quickSort(s,i+1,r);
}

背包问题

01背包问题

容量为10的背包，有5种物品，每种物品只有一个，其重量分别为5，4，3，2，1，其价值分别为1，2，3，4，5。
设计算法，实现背包内物品价值最大。（输出14）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() 
{
    int total_weight = 10;
    int w[6] = { 0,5,4,3,2,1};
    int v[6] = { 0,1,2,3,4,5};
    int dp[11] = { 0 };

    for (int i = 1; i <= 5; i++)
        for (int j = 10; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << "总的价值为: " << dp[10] << endl;
    return 0;
}

完全背包问题

容量为10的背包，有5种物品，每种物品数量无限，其重量分别为5，4，3，2，1，其价值分别为1，2，3，4，5。
设计算法，实现背包内物品价值最大。（输出50）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() 
{
    int total_weight = 10;
    int w[6] = { 0,5,4,3,2,1};
    int v[6] = { 0,1,2,3,4,5};
    int dp[11] = { 0 };

    for (int i = 1; i <= 5; i++)
        for (int j = w[i]; j <= 10;j++)
                dp[j] = max(dp[j],dp[j - w[i]] + v[i]);

    cout << "总的价值为: " << dp[10] << endl;
    return 0;
}

多重背包问题

容量为10的背包，有5种物品，每种物品数量分别为1，2，1，2，1，其重量分别为5，4，3，2，1，其价值分别为1，2，3，4，5。
设计算法，实现背包内物品价值最大。（输出16）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
    int total_weight = 10;
    int w[6] = { 0,5,4,3,2,1 };
    int v[6] = { 0,1,2,3,4,5 };
    int cot[6] = { 0,1,2,1,2,1 };
    int dp[11] = { 0 };

    for (int i = 1; i <= 5; i++)
        for (int k = 1; k <= cot[i];k++)
            for (int j = 10; j >= w[i]; j--)
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << "总的价值为: " << dp[10] << endl;
    return 0;
}

子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
vector<vector<int>> subsets(vector<int>& nums) {
    int n=nums.size();
    vector<vector<int>> res(1,vector<int>());

    for(auto i:nums){
        vector<vector<int>> tmp;
        for(auto &pre:res){ // 每个结果都加上当前数
            vector<int> t=pre;
            t.push_back(i);
            tmp.push_back(t);
        }
        res.insert(res.end(),tmp.begin(),tmp.end());
    }
    return res;
}

// 回溯法
class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    void dfs(int cur, vector<int>& nums) {
        if (cur == nums.size()) {// 记录答案
            ans.push_back(t);
            return;
        }
        t.push_back(nums[cur]);
        dfs(cur + 1, nums);// 考虑选择当前位置
        t.pop_back();
        dfs(cur + 1, nums);// 考虑不选择当前位置
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(0, nums);
        return ans;
    }
};

ST表

ST表（Sparse Table，稀疏表）是一种简单的数据结构，主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。它主要应用倍增的思想，可以实现 O(nlogn)预处理、 O(1)查询。

ST表使用一个二维数组dp[i][j]，表示(i, i + 2^j - 1)范围内的最大值。

递推式 dp[i][j] = max(dp[i][j-1],dp[i+ 2^j][j-1])

对于每个询问(l, r) ，我们把它分成两部分：[l, l+ 2^s -1]与[r-2^s +1,r] 。

其中 s=floor(log(r-l+1))。

img

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
const int logn = 21;
const int maxn = 2000001;
int f[maxn][logn + 1], Logn[maxn + 1];
inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
void pre() {
  Logn[1] = 0;
  Logn[2] = 1;
  for (int i = 3; i < maxn; i++) {
    Logn[i] = Logn[i / 2] + 1;
  }
}
int main() {
  int n = read(), m = read();
  for (int i = 1; i <= n; i++) f[i][0] = read();
  pre();
  for (int j = 1; j <= logn; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    int s = Logn[y - x + 1];
    printf("%d\n", max(f[x][s], f[y - (1 << s) + 1][s]));
  }
  return 0;
}

一些例题

问题简化——移项

n=5x+2y+z，x,y,z为非负整数，给出一个n，求x,y,z的取值情况数。

  • 朴素解法 n^3

    x 0~n/5

    y 0~n/2

    z 0~n

  • 移项，等号变不等号，复杂度降为 n^2

    n-z = 5x+2y >=0

    只需遍历 x,y

  • 寻找数学规律，降为O(n)

    这次把5x移过来

    n-5x=2y+z=k

    先观察上式等于k时，y,z的取值有 floor(k/2)+1(即y可区从0到k/2)

    那么对于每个x的取值，只需O(1)即可求解出答案，x从0遍历至n/5，复杂度为O(n).

  • 终极优化O(1)！！！

    经过上一步，已经不难发现其实答案时个等差数列求和，所以只需代入前3项即可求出二次多项式。

最大公约数

辗转相除法

a=a%b

swap(a,b)

直到b==0

swap终极优化版

b=b xor a

a=a xor b

b=b xor a

（异或2次等于本身）

1
2
3
4
5
// 终极简化版
int gcd(int a,int b){
	while(b^=a^=b^=a%=b);
	return a;
}

LRU（最近最少使用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
struct Node {
    int key, value;
    Node* last;
    Node* next;
    Node(int k=0, int v=0): key(k), value(v), last(nullptr), next(nullptr) {}
};
class LRUCache {
private:
    unordered_map<int, Node*> cache;
    Node* head;
    Node* tail;
    int size;
    int capacity; //容量
public:
//  tail <-next-- head 
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->last = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        Node* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            Node* node = new Node(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                removeNode(tail->last);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            Node* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(Node* node) {
        node->last = head;
        node->next = head->next;
        head->next->last = node;
        head->next = node;
    }
    
    void removeNode(Node* node) {
        node->last->next = node->next;
        node->next->last = node->last;
        cache.erase(node->key);// 删除哈希表中对应的项
        delete node;
    }

    void moveToHead(Node* node) {
        node->last->next = node->next;
        node->next->last = node->last;
        addToHead(node);
    }

};

LFU （最不经常使用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
struct Node {
    int key, value, freq;
    Node* last;
    Node* next;
    Node(int k=-1, int v=-1): key(k), value(v), last(nullptr), next(nullptr), freq(1) {}
};

class FreqList{
public:
    Node* head;
    Node* tail;
    int size;
    FreqList():size(0){
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->last = head;
    }
    void addToHead(Node* node) {
        node->last = head;
        node->next = head->next;
        head->next->last = node;
        head->next = node;
        size++;
    }
    void removeNode(Node* node){
        node->last->next = node->next;
        node->next->last = node->last;
        size--;
    }

    // 删除最后，返回key
    int removeTail(){
        int k=-1;
        // if(size>0){
            Node* node=tail->last;
            k=node->key;
            removeNode(node);
            delete node;
        // }
        return k;
        
    }
};

class LFUCache {
private:
    unordered_map<int, Node*> cache;
    unordered_map<int, FreqList*> freqMap; // 频率

    int minFreq;
    int size;
    int capacity; //容量
public:
    LFUCache(int _capacity): capacity(_capacity),size(0),minFreq(1){

    }
    
    int get(int key) {
        if(cache.count(key)){
            Node* node = cache[key];
            freqMap[node->freq]->removeNode(node); //remove

            node->freq++;

            if(!freqMap.count(node->freq))freqMap[node->freq]=new FreqList();

            freqMap[node->freq]->addToHead(node); // add to [freq+1]
            return node->value;
        }else{
            return -1;
        }
    }
    
    void put(int key, int value) {
        if(capacity==0)return;
        if(cache.count(key)){
            Node* node = cache[key];
            freqMap[node->freq]->removeNode(node); //remove

            node->value=value;
            node->freq++;

            if(!freqMap.count(node->freq))freqMap[node->freq]=new FreqList();

            freqMap[node->freq]->addToHead(node); // add to [freq+1]
            cache[key]=node;
        }else{
            Node* node = new Node(key,value);
            
            if(size==capacity){
                while(freqMap[minFreq]->size==0)minFreq++;
                cache.erase(freqMap[minFreq]->removeTail());
                //     delete freqMap[minFreq];
                size--;
            }
            cache[key]=node;
            if(!freqMap.count(node->freq))freqMap[node->freq]=new FreqList();
            freqMap[node->freq]->addToHead(node); // add to [1]
            minFreq=1;
            size++;
        }
    }
};

LeetCode刷题技巧

https://blog.luzy.top/posts/1993660772/

作者

江风引雨

发布于

2021-07-02

更新于

2024-03-15

许可协议

CC BY 4.0

#

喜欢这篇文章？打赏一下作者吧

评论

×