redis缓存穿透和雪崩
缓存击穿 指的是一个非常热的key 一直有非常大流量的并发访问，当缓存中key失效过期的瞬间，所有的访问量瞬间击破缓存，所有请求瞬间全部访问到数据库，
例： 微博某个热搜，刘畊宏直播，
大量的访问量直接访问到后端数据库 同时数据库还要会写到缓存，导致数据库压力很大甚至崩溃。
决方案：
1.热key缓存永不过期 ，防止缓存过期打到数据库
2.分布式锁：一个线程获取，其他线程等待，防止后端数据库崩溃
缓存穿透 当用户访问一个数据 缓存中没有，缓存没命中，所以向持久层数据库查询
也没有 本次查询失败，但是当大量没用命中访问量都去访问数据库持久层的时候，数据库压力很大 缓存也就失效了 相当于缓存穿透。
例：秒杀活动，双十一 618购物街，短时内大量点击率抢购数量有限的商品，会出现大量查询失败，
解决办法：
1.布隆过滤器 、
2.存储空对象：数据库没找到后，redis中临时存一个空对象（空对象多了也会占用内存）
缓存雪崩 缓存中的key都是有失效时间的 ，缓存雪崩指的是 某个时间点，缓存集体失效，redis缓存失去了作用。
第二种情况是 缓存服务器down机 自然形成了雪崩的情况。
例： 双十一商品 都是提前加载到缓存，到凌晨开始抢购的时候，缓存都过期了了当雪崩的时候没有一片雪花是无辜的，每个key失效都不是问题，但是所有key集体失效，会造成所有的访问直接打到了持久层数据库，数据库访问调用暴增。
解决方案：
1.redis高可用：多设置几台redis
2.限流降级：缓存失效后，通过加锁或者队列来控制读数据库写缓存的数量
3.数据预热：大量数据加载到缓存中，根据不同访问量来设置不同过期时间，防止大面积集体过期
安装 apt install tcl wget https://download.redis.io/redis-stable.tar.gz tar -xzvf redis-stable.tar.gz cd redis-stable make all make install 配置redis自动启动 在redis-stable目录下复制启动脚本 sudo cp utils/redis_init_script /etc/init.d/redis_6379
在编辑启动脚本vim /etc/init.d/redis_6379在
### BEGIN INIT INFO # Provides: redis_6379 下边增加以下两行：
# Required-Start: $remote_fs $syslog # Required-Stop: $remote_fs $syslog 在redis-stable目录下配置文件 sudo cp redis.conf /etc/redis/6379.conf 编辑配置文件vim /etc/redis/6379.conf daemonize从no改为yes pidfile设置为/var/run/redis_6379.pid dir设置为/var/lib/redis/6379
最后更新启动脚本到默认运行级别sudo update-rc.d redis_6379 defaults
运行redissudo /etc/init.d/redis_6379 start
检查：
yum list | grep mysql
(PS:据说Centos7.0的源中暂时还没有mysql，但是相同版本的Centos在阿里云是可以直接使用yum install mysql-server 来直接安装mysql的)
下载mysql的repo源：
wget http://repo.mysql.com/mysql-community-release-el7-5.noarch.rpm
安装mysql-community-release-el7-5.noarch.rpm包：
rpm -ivh mysql-community-release-el7-5.noarch.rpm
安装mysql：
yum install mysql-server
重置密码：（重置密码前，首先要登录）
mysql -u root
mysql > use mysql;
mysql > update user set password=password('密码') where user='root';
mysql > exit;
修改权限可以使其他机器登录：
mysql>GRANT ALL PRIVILEGES ON *.* TO 'root'@'%' WITH GRANT OPTION //赋予任何主机访问数据的权限
mysql>FLUSH PRIVILEGES //修改生效
mysql>EXIT //退出MySQL服务器
（腾讯云yum安装mysql_腾讯云CentOS7.0使用yum安装mysql_MySQL_雨诺寒雪的博客-CSDN博客）
原题传送门
1. 题目描述 2. Solution 1 **1、思路分析 ** 递归使用回溯法。 2、代码实现
package Q0099.Q0078Subsets; import org.junit.Test; import java.util.ArrayList; import java.util.Arrays; import java.util.List; // Recursive (Backtracking) public class Solution1 { /* Time: O(n * 2^n) Space: O(n/2 * 2^n) ~= O(n * 2^n) */ public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, 0); return list; } private void backtrack(List<List<Integer>> list, ArrayList<Integer> curRes, int[] nums, int start) { list.
原题传送门
1. 问题描述 2. Solution 1、思路分析 题意: 给定一个整数n，把n的各个数位上的数字求和，把和用英语单词输出。如，给定n=12345，各个数位上的和为1+2+3+4+5=15，则输出one five。 分析: 输入的整数到了100次方量级，用int有溢出的风险。只能按字符串读入，按位求和。然后，遍历和，逐位输 出英语单词(使用字符串单词map)。
2、代码实现
// PAT Advance Level 1005 // Ye Qiu #include <iostream> #include <cstdio> #include <string> #include <algorithm> using namespace std; int main() { #ifdef ONLINE_JUDGE #else freopen(input/1005.txt, r, stdin); #endif string numEngMap[10] = {zero, one, two, three, four, five, six, seven, eight, nine}; string s; cin >> s; int res = 0; for (char c: s) res += c - '0'; string strRes = to_string(res); for (int i = 0; i < strRes.
原题传送门
1. 问题描述 2. Solution 1、思路分析 遍历，求最大值、最小值，字符串比较即可。
2、代码实现
// PAT Advance Level 1006 // Ye Qiu #include <iostream> #include <cstdio> #include <string> #include <algorithm> using namespace std; int main() { #ifdef ONLINE_JUDGE #else freopen(input/1006.txt, r, stdin); #endif int m; string idNumbers, singIn, singOut, earlyId, lateId, earlyTime = 23:59:59, lateTime = 00:00:00; scanf(%d, &m); for (int i = 0; i < m; i++) { cin >> idNumbers >> singIn >> singOut; if (singIn < earlyTime) { earlyTime = singIn; earlyId = idNumbers; } if (singOut > lateTime) { lateTime = singOut; lateId = idNumbers; } } cout << earlyId << << lateId; return 0; } 3、复杂度分析 时间复杂度: O(n) 空间复杂度: O(1)
原题传送门
1. 问题描述 2. Solution 1、思路分析 题目大意：电梯从0层开始向上，给出该电梯依次按顺序停的楼层数，并且已知上升需要6秒/层，下降需要4秒/层，停下来的话需要停5秒，问走完所有需要停的楼层后总共花了多少时间～
分析：累加计算输出～now表示现在的层数，a表示将要去的层数，当a > now，电梯上升，需要6 * (a – now)秒，当a < now，电梯下降，需要4 * (now – a)秒，每一次需要停5秒，最后输出累加的结果sum～ 2、代码实现
// PAT Advance Level 1008 // Ye Qiu #include <iostream> #include <cstdio> using namespace std; int main() { #ifdef ONLINE_JUDGE #else freopen(input/1008.txt, r, stdin); #endif int up = 6, down = 4, stop = 5, res = 0, cur = 0, goal; cin >> goal; while (cin >> goal) { if (goal > cur) { // up res += (goal - cur) * up; } else { res += (cur - goal) * down; } res += stop; cur = goal; } printf(%d, res); return 0; } 3、复杂度分析 时间复杂度: O(n) 空间复杂度: O(1)
原题传送门
1. 问题描述 2. Solution 1、思路分析 DP求最大连续子序列和，设输入数组为nums。(参考算法笔记11.2 最大连续子序列和) 1> 状态定义: dp[i] = 以nums[i]结尾的最大连续子序列和。 2> 状态转移方程: case 1: 以nums[i]结尾的最大和的连续序列只有一个元素，即nums[i]。 case 2: 最大和为dp[i-1]+nums[i]。 整合上面两种情况，得到转态转移方程: dp[i] = max{nums[i], dp[i-1]+nums[i]} 用sumOfHere替代dp[i-1]，res替代dp[i]以降低空间复杂度。 3> 边界: dp[0] = nums[0]。
2、代码实现
// PAT Advance Level 1007 // Ye Qiu #include <iostream> #include <cstdio> #include <vector> using namespace std; int main() { #ifdef ONLINE_JUDGE #else freopen(input/1007.txt, r, stdin); #endif int k, sumOfHere = 0, res = -1, begin = 0, start = 0; scanf(%d, &k); int end = k - 1; vector<int> nums(k); for (int i = 0; i < k; i++) { cin >> nums[i]; sumOfHere += nums[i]; if (sumOfHere < 0) { sumOfHere = 0; begin = i + 1; } else if (sumOfHere > res) { res = sumOfHere; start = begin; end = i; } } if (res < 0) res = 0; printf(%d %d %d, res, nums[start], nums[end]); return 0; } 3、复杂度分析 时间复杂度: O(n) 空间复杂度: O(n)
原题传送门
1. 题目描述 2. Solution 1 1、思路分析 使用递归遍历所有的位置， 2、代码实现
package Q0099.Q0079WordSearch; public class Solution { /* Here accepted solution based on recursion. To save memory I decided to apply bit mask for every visited cell. Please check board[y][x] ^= 256; */ public boolean exist(char[][] board, String word) { for (int i = 0; i < board.length; i++) { // y represent row number for (int j = 0; j < board[i].
原题传送门
1. 题目描述 2. Solution 1 1、思路分析 Question wants us to return the length of new array after removing duplicates and that we don't care about what we leave beyond new length , hence we can use i to keep track of the position and update the array. 2、代码实现
package Q0099.Q0080RemoveDuplicatesFromSortedArrayII; public class Solution { /* Q026 的续集，Remove Duplicates from Sorted Array II (allow duplicates up to 2): */ public int removeDuplicates(int[] nums) { int i = 0; for (int n : nums) { if (i < 2 || n > nums[i - 2]) nums[i++] = n; } return i; } } 3、复杂度分析 时间复杂度: O(n) 空间复杂度: O(1)