20210221 1438. 绝对差不超过限制的最长连续子数组

题目

https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

题解

1.暴力求解

获取beginIndex和endIndex的所有可能,移动指针的时候记录下最大值和最小值然后求解(超时)

public int longestSubarray(int[] nums, int limit) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int max = nums[i];
            int min = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                max = Math.max(max, nums[j]);
                min = Math.min(min, nums[j]);
                if (max - min <= limit) {
                    result = Math.max(result, j - i);
                }
            }
        }
        return result + 1;
    }

2 滑动窗口+优先队列

这个题可以比较简单的想到用滑动窗口,但是一旦移动如何记录l和r指针区间的max和min值是一个问题,加入还好说类似上边比较即可,但是一旦l移动,如果不存储原有值就比较难求出新的max和min值,这里可以用排序的list或者set也可以用优先队列

public int longestSubarray(int[] nums, int limit) {
    if(nums.length<2){
        return nums[0]<limit?1:0;
    }
    int result = 0;
    int r = 1;
    int l = 0;
    PriorityQueue<Integer> minQueue = new PriorityQueue<>(Comparator.naturalOrder());
    PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());
    minQueue.add(nums[l]);
    maxQueue.add(nums[l]);
    while (l < r && r < nums.length) {
        minQueue.add(nums[r]);
        maxQueue.add(nums[r]);
        if (maxQueue.peek() - minQueue.peek() <= limit) {
            result = Math.max(result, r - l + 1);
            r++;
            continue;
        }
        minQueue.remove(nums[l]);
        maxQueue.remove(nums[l]);
        l++;
        r++;
    }
    return result;
}

上边考虑边界值其实复杂了可以简化成下边的写法

public int longestSubarray2(int[] nums, int limit) {
int result = 0;
int r = 0;
int l = 0;
PriorityQueue<Integer> minQueue = new PriorityQueue<>(Comparator.naturalOrder());
PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());
while (l < nums.length && r < nums.length) {
minQueue.add(nums[r]);
maxQueue.add(nums[r]);
if (maxQueue.peek() - minQueue.peek() <= limit) {
result = Math.max(result, r - l + 1);
r++;
continue;
}
minQueue.remove(nums[l]);
maxQueue.remove(nums[l]);
l++;
r++;
}
return result;
}

20210219 1104 最大连续1的个数 III

题目

https://leetcode-cn.com/problems/max-consecutive-ones-iii/

思路

1.最多可以将K个值从0变成1,可以看成是最多有K个0的最长子串,这样就可以转化成滑窗问题,首先l,r都在数组的最前端,r不断向后滑动,直到0的个数比K大,这时向右移动l,直到0的个数又小于等于K的大小,在移动r,在这个区间需要把滑窗的最大值记录下来,这个值就是子串长度的最大值

public static int longestOnes(int[] A, int K) {
        int l = 0, r = 0;
        int maxLength = 0;
        int kSize = 0;
        for (; r < A.length; r++) {
            if (A[r] == 0) {
                kSize++;
            }
            while (kSize > K) {
                if (A[l] == 0) {
                    kSize--;
                }
                l++;
            }
            maxLength = Math.max(maxLength, r - l + 1);
        }
        return maxLength;
    }

20210218 995 K 连续位的最小翻转次数

题目

https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/

思路

1.暴力求解每次遇到0就翻K个数字,不断重试知道最后都遍历完,或者最后不够K个翻转.小trick翻转的时候遇0变1,遇1变0其实可以用A[i]和1异或^,如果是1异或值为0,如果是0和1异或的值为1,java暴力只有这样才能过

public static int minKBitFlips(int[] A, int K) {
        int n = A.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (A[i] == 0) {
                if (i + K > n) {
                    return -1;
                }
                for (int j = i; j < i + K; j++) {
                    A[j] = ~A[j];
                }
                ans++;
            }
        }
        return ans;
    }

2.差分方程:没看懂,留个坑

mysql第一天

字符集和比较规则

1.服务器,库,表,列都可以单独设置字符集和比较规则

2.没有定义的话向上兼容,比如列没有定义字符集继承表的,表没有继承库的,库没有继承服务器的

3.字符集和比价规则是绑定的,如果只改一个会联动的改掉相关的 eg:utf8和gbk的比较规则就是不同的,不可能用gbk的比较规则去比较utf8字符集,反过来同理,这个会影响我们order by的查询或者列的比较

4.从client发送请求到服务端返回给client一共有三个字符集会影响

InnoDB行记录存储结构

1.InnoDB采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB中页的大小一般为 16 KB。也就是在一般情况下,一次最少从磁盘中读取16KB的内容到内存中,一次最少把内存中的16KB内容刷新到磁盘中。

2.创建或者修改表的时候可以修改相关的”行模式”

3.一行记录不光有真实信息,还有每一列的存储大小(毕竟varchar这种是变长的,需要真实记录一下占用了多少字符),null值列,头信息(是否删除的标记位等),真实数据,逆序排列比如建表的时候是列A,列B,列C,在变长字段中就是列C长度,列B长度,列A长度

4.我们所有存储最少都是按照一个字节存储,所以一旦M(varchar(M)或者char(M))*L(该列字符集一个字符占用的字节数)>255(1个字节可以表示的大小),那就必须要用两个字节表示,一共占用了多大字节,在大的话mysql是不允许的(比如insert varchar(7000000),mysql会直接报错,建议你使用text或者blog),只能用blog或者text.

5.null列,0代表是非null,1代表null,同样也是整字节不够用0补,同样是逆序. eg: 不是所有的列都会在里面,如果该列是not null的不会再里面

6.溢出页:行的数据比较多16kB已经放不下了,就会溢出,有两种模式一个是在记录部分真实数据的基础上后边在加一个其他页地址,索引到其他页,每一页之间用链表链接,另外一种是真实数据也不记录一部分了,直接只有一个其他页索引,真实的数据都放到索引页中.

计数排序

算法思路

对一组数据排序,如果我们能事先知道数组的范围比如我们的”待排序数组A[]”所有的数字都在0到10之间,那我们可以初始化一个数组B[]大小就是10,默认值都是0(这里为了方便叙述,所有数组下标从1开始),A数组从头到尾遍历,比如第一个数字是5,那B[5]=1,第二个数是3那B[3]=1,第三个数字是5那B[5] = B[5]+1=2,以此类推获得数组B,此时B数组里面index即原数组A里面的数字,value为A数组里面值为index的数字出现了几次,遍历所以遍历B数组打印每打印一次A[index]-1直到A[index]=0,这样我们就将所有的数字排序打出

举例

问题

① 数组大小可以为max-min+1减小空间复杂度比如[99,100]其实size为2就够了

② 如何让排序稳定,比如{6,5,5}我们给5编一个号码方便简述5a,5b,如果是上边的方式5a和5b其实是不稳定的,但是如果我们可以对原数组进行累加,原有多少个index数组,就变成有多少个数字比index小了,例如上边的数组,辅助数组为{2,1}->{2,3}然后将{6,5a,5b}从后到前遍历,5b放到index为2的地方{2,3}->{1,3},然后遍历到5a,5a放到index为1的地方,最后6放到index为3的地方得到{6,5a,5b}稳定排序

HashMap

put

  • 判断是否有tab[],没有证明还没有初始化,先初始化(容量,threadHold)
  • 对key hash后和length-1与寻找bucket,如果bucket为空放入,如果不为空但是key相同换掉,如果是treeNode证明已经树化,调用putTreeVal,否则是链化的,向下寻找找到key相同的或者链的tail插入(尾插),并判断是链的容量是否到了树化的临界点,到了把tab树化最后判断是否需要扩容,最后把oldVal返回
  • 问题: 如何树化,树化之后的putTreeVal如何操作,如何扩容

get

  • 1.获得key的hash,和length-1求与得到bucket的firstNode,如果key相同返回value不同判断是不是treeNode,是的话调用getTreeNode,不是的话顺着链向下找直到key相同返回相应的value或者是null
  • 问题: treeNode如何get

如何树化

  • 当链表超过8个,就会树化,如果链表的size比较小,还会扩容(为什么扩容) 第一次树化只是由node变成treenode,维护了pre和next指针,但是并没有真正树化真的树化,应该是第一次putTreeVal的时候树化之后入会putTreeVal找到树的root,通过hash值寻找root大的dir+,小的dir-如果key相同返回p,如果key不同,但是hash相同,看下key有没有实现compator类如果没有实现或者实现了,但是compator之后也相同,就search当前的节点直到找到应该插入的地方,如果找不到(key不同compator相同)只能调用system的hash方法然后调整树至平衡

treeNode如何get

  • 找到root,根据hash值find

扩容

  • map有最大size,如果超过了直接返回老的map,不会再扩了否则就是init下初始的容量threadHold值,或者不是第一次init的话就扩容为原来的二倍,从头到尾遍历,
  • 不是树化的bucket: 如果目标bucket上只有一个节点,直接放到原来2的index上 多个节点 节点的hash和oldCap求于,为0的穿成一串 不为0的穿成一串,同时保留第一个的头结点 最后把0的头结点放到原地,不为0的头结点放到2的index上
  • 树化的bucket: 同样也是hash和oldCap求于,然后分成两串,串的size大于8的树化,小于6的链化

remove

  • 根据key获得bucket的index,然后寻找需要被remove的node同理寻找的过程也分为链化和树化的节点
  • 链化的:不断next判断key是否相同,找到之后直接通过指针把找到的noderemove了
  • 树化的:和get中寻找treeNode相同,先找到目标节点

注: remove有的会去匹配value的值,如果key的value和传入的value不同
不可以删除当前节点