学习时间：2022-9-17
学习内容
1、leetcode
442. 数组中重复的数据
采用原地Hash的方式做，代码如下：
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<Integer>();
for(int i = 0;i<nums.length;i++){
int value = nums[i];
int index = value-1;
if(index == i){
continue;
}
if(nums[i] == nums[index]){
continue;
}
swap(nums,i,index);
i--;
}
for(int i = 0;i<nums.length;i++){
//找下标
if(i != nums[i]-1){
ans.add(nums[i]);
}
}
return ans;
}
public void swap(int[] nums,int a,int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
264. 丑数 II
使用动态规划+三指针法（多路归并），最优子结构为：
dp[i] = Math.min(Math.min(num2,num3),num5);
class Solution {
public int nthUglyNumber(int n) {
int ptr2 = 1;
int ptr3 = 1;
int ptr5 = 1;
int[] dp = new int[n+1];
dp[1] = 1;
for(int i = 2;i<=n;i++){
int num2 = dp[ptr2]*2;
int num3 = dp[ptr3]*3;
int num5 = dp[ptr5]*5;
dp[i] = Math.min(Math.min(num2,num3),num5);
if(dp[i] == num2){
ptr2++;
}
if(dp[i] == num3){
ptr3++;
}
if(dp[i] == num5){
ptr5++;
}
}
return dp[n];
}
}
2、文件分配
文件分配给磁盘有三种分配方式：连续分配|链接分配|索引分配
连续分配
对标数组中查找、新增元素
寻道时间最短 访问容易 有大量外部碎片产生（内存的特性）
解决方案为合并磁盘空间，但是这样就算解决了外部碎片，开销也过于大
链接分配
对标链表中查找、新增元素
寻道时间比较长（磁头寻道时间较长）
创建指针会有单独的内存开销
没有外部碎片
解决开销问题：将多个块组成簇，这种方法会增加内部碎片
索引分配
对标hash表中查找、新增元素
通过加大空间消耗来使链接分配的方式折中寻道时间（增加索引块）
但是索引块对空间的占用比较大
另外对索引块大小也有考究，不能过小或过大
目前的链接目的有：把索引块做成链接块，本身就可以读的话，就可以减少专门作索引块的压力
使用多级索引
3、位图概念及redis中位图的使用
位图，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。
举个例子，如下图，如果我们想要存放 0,2,4,5,10,11,12,14,15这几个数字，如果采用普通存储方式，若4位表示一个数字，这9个数字需要4*9=36位，至少36位才能存储这些数据。
如果采用位图的方式，只需要上图的16位就能存储这9个数字。
查找的时候，只需要查找这个位的数是1还是0即可，就可以确定该数存在不存在。
当数量足够大时候，不光大大压缩了存储空间，查找速率也极快，可以说是O(1)。
bitmap是redis的一种扩展数据类型，主要用于二值状态统计，比如公司记录员工打卡记录，电商网站记录用户登录行为，积分商城记录用户签到情况。
例子转自知乎：redis灵魂拷问：聊一聊bitmap使用
下面我们看一下bitmap的使用。
员工打卡
假如一个公司有100个员工，公司要对员工11月份的打卡行为进行统计，我们可以为11月份每一天分配一个bitmap，这个bitmap保存100个bit位，来记录员工的打卡行为。
注意:bitmap偏移量从0开始，所以100个bit位是从0~99，依次记录1-100号员工。
我们定义bitmap的key格式为:signed:20201101，记录2020年11月1日的打卡情况。下面代码是员工打卡和查询员工打卡情况：
/**
* SETBIT命令
* 员工打卡
* 时间复杂度：O(1)
*/
public void sign(String key, int employeeNumber){
redisTemplate.opsForValue().setBit(key, employeeNumber - 1, true);
}
/**
* GETBIT命令
* 查看员工打卡情况
* 时间复杂度：O(1)
*/
public boolean isSigned(String key,int employeeNumber){
return redisTemplate.opsForValue().getBit(key, employeeNumber - 1);
}
我们可以查看某一天的打卡总人数，代码如下，入参：“signed:20201101”：
/**
* BITCOUNT命令
* 查看某一天的打卡人数
* 时间复杂度：O(N)
*/
public Long signedCount(String key){
return (Long) redisTemplate.execute((RedisCallback<Long>) conn -> conn.bitCount(key.getBytes()));
}
那如果想看当月没有迟到过的员工呢？这个时候就要用到交集了，对当月每天的bitmap做交集，值为1的员工就是没有迟到过的。
这时就要用到bitmap的聚合运算了，命令BITOP， 支持AND(与)、OR(或), XOR(异或) and NOT(非)运算，除了NOT后面跟一个bitmap外，其他3种聚合运算后面都可以跟多个bitmap，命令如下：
BITOP AND destkey srckey1 srckey2 srckey3 … srckeyN
BITOP OR destkey srckey1 srckey2 srckey3 … srckeyN
BITOP XOR destkey srckey1 srckey2 srckey3 … srckeyN
BITOP NOT destkey srckey
bitmap广泛地运用在二值计算的场景，对于一个二值状态只用一个bit位就可以，非常节约内存。比如我们对一个10亿的用户进行日活计算，占用的空间为10亿/8/1024/1024=120M
文章出处登录后可见！
