ACWing 全部内容
Acwing个人笔记汇总 (主要是基础班、寒假每日一题、语法课)
算法基础课总结
算法基础课总结
基础课Directory(基础课题目和视频导航)
(一)、DP相关问题
1.背包问题中 体积至多是 j ,恰好是 j ,至少是 j 的初始化问题的研究
背包问题总结
最长公共子序列【求具体方案】
最长上升子序列(LIS)模型
最长上升子序列模型
(二)基础知识
递归
(三)图论
Dijkstra求最短路算法 【 详细整理 】
图论中最短路5个算法总结
(四)数论
数论的整体学习思路(包含李永乐视频)
数论小结
数论相关分享(包含视频) (这是一个博主的分享列表,数论比较好的)
数论总结
高阶数论笔记以及一些练习题
(五)、数据结构相关
【数据结构】树专题——练习递归
算法基础课第二讲 总结---- 数据结构
【数据结构】并查集
二叉树的4种遍历
单调队列和单调栈
数据结构篇-栈与队列 (包括单调栈和队列)
单调栈题目
一维和二维数组翻转的问题
LeetCode究极班总结
一、题型分类
(一)LeetCode究极班题型分类
说明:对LeetCode题型进行归类,连接lc和ACWing的桥梁
具体分为DP、滑动窗口、二分、DFS、模板题、数组(链表)翻转、观察找规律和小技巧、经典问题(股票系列lc121、lc122\lc123和回文lc125)、数据结构(优先队列、哈希、二维数组)
【题型整理】LeetCode题型总结(持续更新)
LeetCode 题目分类——配套基础课进阶课
双指针算法学习笔记LeetCode
双指针算法
例题:leecode
1. 两数之和
15. 三数之和
16. 最接近的三数之和
26. 删除排序数组中的重复项
1004. 最大连续1的个数 III
88. 合并两个有序数组
392. 判断子序列
leetcode区间dp合集
leetcode数位dp合集
leetcode状压dp合集
状压DP复习笔记 (来自洛谷上的题)
二、Leetcode 好题总结
C++语法课总结
AcWing语法课总结
第五讲 字符串
C++ STL
C++ STL 简介
STL笔记
vector用法 (来自晨曦时雨)
vector的主要函数及例题
C++STL的vector中front(),back(),begin(),end()的用法
C++中提供 哈希表 容器 详细应用–>
vector总结
vector的主要函数及例题
优先队列中的大于号和小于号重载方法总结
c++ 指针 学习总结
C++ pair用法及使用sort函数对pair数据进行排序
C++ multiset的用法
1.vector
有pop_back();
//删除最后一个元素
vector
根据位置删除元素
删除第i
个v.erase(v.begin()+i);
删除一个区间(包括左边,不包括右边)v.erase(v.begin()+a,v.begin()+b);
2.从字符串中截取字串
string s;
int start,len;
s.substr(start,len);
3.堆默认是大根堆,下面是小根堆的写法
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
priority_queue<int, vector<int, int>, greater<int, int>> heap;
4.memcpy数组复制
int arr1[10];//假设里面已经有值
int arr2[10];
memcpy(arr2,arr1,sizeof arr2);
由src指向地址为起始地址的连续n个字节的数据复制到以destin指向地址为起始地址的空间内。
void *memcpy(void*dest, const void *src, size_t n);
与strcpy相比,memcpy并不是遇到’\0’就结束,而是一定会拷贝完n个字节。
memcpy用来做内存拷贝,你可以拿它拷贝任何数据类型的对象,可以指定拷贝的数据长度;
例:
char a[100], b[50];
memcpy(b, a,sizeof(b)); //注意如用sizeof(a),会造成b的内存地址溢出。
strcpy就只能拷贝字符串了,它遇到'\0'就结束拷贝;例:
char a[100], b[50];
strcpy(a,b);
5.字符串的find函数,返回最早出现字串的索引,不存在字串返回-1,时间复杂度为O(n*n),暴力bf算法。
string s1="abcd";
string s2="bc";
cout<<s1.find(s2);//结果为1
6.结构体中重载大于小于号
struct node{
int v,c;
bool operator < (const node& t) const
{
if(c!=t.c) return c>t.c; // c按从大到小排
return v<t.v; // cnt相等时,按值从小到大排
}
}a[N];
7.
8.
9.
10.
自己的整理:
2021 寒假每日一题活动
相关考点总结归纳
acer分享分容列表
Chicago (包括算法竞赛进阶指南和刷题顺序)
其他
个人ACM模板总结 –> 直接到 更好的阅读体验
C/C++语言的错误大全及中文解释
挂分小技巧
知识点大全和超链接
Markdown基本语法学习
容易被忽视的模运算法则
y老师语录
YLS总结的面试必考题(等待自己写专题)
C/C++语言的错误大全及中文解释
滚动数组思想
Jetbrains快捷键
一些有趣的网站 (数学工具、函数工具、图论工具)
学习资源汇总
pat题目技巧 + 思路 + 易错点总结
博客园美化
数据的机器级表示与处理
尺取法
自学计算机
建图工具csacademy
面试相关
面试经验
wangzitiansky(已入职知乎acwinger) (这位前辈的分享面试经验和知识很重要)
shopee · 新加坡 后端一面面经(Java)2021 秋招
快手 · 电商后端一二三面面经(java)2021
字节 · 安卓一面 凉凉~
多个公司面经(美团2面,快手3面,百度2面,微众银行,七牛云,拼多多,58同城)
21届秋招 · 各大厂面经(字节,百度,网易互娱,腾讯,阿里,华为)
同花顺 · 后台开发C++面经
深信服 · C++面经2020
字节 · 社招 后端 一二三面已过丶以及 学习感言
字节 · 算法岗面经
面试学习资料
golang
学习资料
学习方法
项目背景
项目内容
项目架构
- 抢购代金券部分
整个开发过程是 先使用传统的关系型数据库完成开发,然后测试时出现问题 超卖问题和一人多单问题,再使用redis解决
添加秒杀活动
这个功能就是 新增一个秒杀活动,根据代金券ID查询该代金券是否已经参与了抢购活动,就是验证数据库中是否已经存在该券的秒杀活动,如果存在就不能插入秒杀活动表中,否则添加该抢购活动到数据库表中(这部分主要涉及到的是 订单表、秒杀活动表、优惠券表)。
另外,添加秒杀活动是商家添加的和普通用户无关,所以需要在网关中放行
客户端秒杀抢购代金券
现在要开始抢购,也就是用户要开始下单了,下单成功则库存减一,减完之后订单表中生成订单数据
所以在mapper中写了减库存的方法,是一个update操作,返回的是相应的行数来表示update操作是否成功
在抢购代金券的service层中会做一些 健壮性的处理:
包括 基本参数校验(得知道抢购的是哪个代金券、哪个用户在抢购,所以要传入登录用户的信息,传的是accessToken 是登录token)
除了基本参数校验外还有 判断此代金券是否加入了抢购,以及是否有效,判断是否开始或已经结束了,然后还要判断代金券是否已经卖完了,如果这些都符合的情况下就可进一步 远程调用获取登录用户信息(因为我们的系统是微服务的),然后判断当前用户是否已经抢到此代金券了,如果已经抢到了就直接返回(这里我是在生成订单的mapper中 实现了 根据用户ID和秒杀的代金券ID查询代金券订单,也就是要看下当前用户有没有抢过这个代金券,如果抢过了,就能查到,那就不能再抢了因为我们是秒杀代金券一个用户只能买一次。)
那如果当前用户没有抢购过此代金券,就进入下面的扣库存和下单步骤了(这里我上面说了 我是先用传统的关系型数据库做的,然后做了压力测试后发现有问题了,使用redis解决问题的)
下面是 扣库存和下单的步骤:
扣库存
在秒杀代金券的mapper中实现了 扣库存操作,是一个update操作返回的是响应行数,只要不是0,就说明扣成功了,如果返回的是0说明没有修改成功,也就意味着这个券已经卖完了
这是用传统关系型数据库实现的扣库存,然后如果库存只要能扣除成功那就可以下单了,下单是在订单mapper中实现了 下单操作,就是insert操作,返回的也是响应行数,响应行数如果不是0就表示抢购成功了,如果是0表示抢购失败。
// 在生成订单的mapper中还实现了 新增代金券订单 就是如果当前用户没有抢过,就让当前用户下订单,让用户抢一张代金券,当然前提是 库存中得有。
抢购代金券的完整逻辑大致就是这样。只不过这里使用的是传统关系型数据库实现的,我用压力测试工具Jmeter进行测试会有问题。
【秒杀代金券的Controller层 传入的参数是代金券ID和用户登录token 来判断用户能否下单,具体判断逻辑就是上面service中描述的】
压力测试
下面讲下我是如何做压力测试并出现了什么问题。
我们现在要对某个抢购活动下的100张代金券进行压力测试,如果不用第三方的测试工具来测试紧靠刷新浏览器的方式肯定是不行的,所以这里我用Jmeter压力测试工具进行测试。
这里我设计了两种测试计划:
1. 多人测试抢购代金券,会发起5000个并发,2000个账号同时对100张代金券进行抢购
2. 一个用户发起多个抢购请求,这里是 让一个账户发起10000次请求。 有点类似于12306黄牛刷票的软件一样,一直在疯狂抢票,看下是否会出现一个人会抢多张优惠券,如果一人买了多单说明程序是有问题的
这里在测试 第一种 多人测试抢购代金券时,会出现库存数变成负数的问题,订单数也会超多100, 也就是超卖问题
分析service层代码,第一步是做基本参数校验、第二步是判断此代金券是否加入了抢购活动表中,这一步其实就可以获取到代金券的数量了。后面做扣库存下单等操作。
我们现在是有5000个并发,2000个账户在抢购,假设一个极端情况,1000个并发同时进来了都拿到了当前代金券的数量 假设是100,也就是这1000个请求他们的库存量都是100,往下执行 然后这1000个请求都去扣库存 对库存减一,就可能出现库存量是-900的情况,因为库存量只有100,但是1000个请求都在做减一操作,就是-900了,为什么出现这种情况,就是因为在高并发的情况下请求过多,然后瞬间1000个请求进来就直接执行到扣库存这里了,然后等到第1001个请求过来时,此时库存量是-900,就不会执行下面的扣库存下单操作了,就给客户端返回 该券已经卖完了,但是前面的1000个请求因为太密集了,高并发已经执行了,所以会出现数据库中超卖的情况,包括库存变成负数情况
这是第一种测试计划 出现超卖问题和库存变为负数的 原因。
第二种测试计划 一个用户发起多个抢购请求,会出现 一个用户抢购了4张甚至更多张票,也就是一人多单问题
redis防止超卖
解决超卖问题和一人多单问题,我用的是redis来解决的,我先说下 redis防止超卖的解决方案:
redis限制一人一单
- Feed流
3.
%%%