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++;
}
}
};
作者

江风引雨

发布于

2021-07-02

更新于

2024-07-10

许可协议

CC BY 4.0

评论