小沙同学个人博客

第 89 场双周赛复盘 最后一题尚未解决 二的幂数组中查询范围内的乘积关键在于：求出power数组，power数组存放一个数的二进制分解结果 12345int ind=0;for (int i = 0; i <= MAXP; i++){ if (n >> i & 1) power[ind++]=1<<i;} 最小化数组中的最大值最小化最大值 —> 二分答案 二分答案的模板 1234567while(l<=r){ mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1;} 1234567891011121314151617181920212223242526272829303132333435class Solution { public int minimizeArrayValue(int[] nums) { in ...

位运算小技巧 英文字符与空格或操作将其转换为小写 12(char) ('D' | ' ') // d(char) ('d' | ' ') // d 英文字符与下划线与操作将其转化为大写 12(char) ('d' & '_') // D(char) ('D' & '_') // D 英文字符与空格异或操作进行大小写互换 12(char) ('D' ^ ' ') // d(char) ('d' ^ ' ') // D 判断两个数是否异号（通过商或者乘积的方式，容易会导致结果溢出） 12int x=-2; int y=1;System.out.println((x^y)<0); // true n &（n-1）作用就是将最后一位1变成0 位 1 的个数 2 的幂 a ^ a =0 a ^ 0= a异或运 ...

归并排序归并排序实质是二叉树的后序遍历。 思想：先将左半边数组排好序，再将右半边数组排好序，将两个排好序的数组合并。 代码实现： 提前将数组new出来，避免在递归中频繁的分配和释放内存，影响性能 123456789101112131415161718192021222324252627282930313233343536373839404142public class Merge { // 辅助数组 private static int[] temp; public static void sort(int[] a){ temp = new int[a.length]; sort(a,0,a.length-1); } // 对数组a[start...end]排序 private static void sort(int a[],int start,int end){ int mid = start + (end - start) / 2; if(e ...

314场周赛复盘第四道6203. 矩阵中和能被 K 整除的路径 dfs 必定超时 动态规划 确定状态（原问题和子问题变化的部分）：i，j, 从（0，0）到（i，j）路径和与k的余数也是一直变化的 确定dp数组的含义：dp[i][j][x]:从（0，0）到（i，j）路径和mod k ==x的数量 确定选择：向右，向下 我们要求：dp[m-1][n-1][0] 1234567891011121314151617181920212223242526272829class Solution { private static final int V=7+1000*1000*1000; public int numberOfPaths(int[][] grid, int k) { int m=grid.length; int n=grid[0].length; int dp[][][]=new int[m][n][k]; dp[0][0][grid[0][0] % k]=1; // 处理第0行 ...

Redisson 分布式锁原理Redisson如何解决重入问题可重入锁：同一线程可以获取同一把锁 实现：在获取锁的时候，如果存在，判断锁标识是不是同一个线程，如果是，也可以获取锁，并使用计数器记录重入的次数 lua 脚本获取锁trylock123456789101112131415161718192021222324-- KEYS[1] 代表锁的key-- ARGV[1] 锁失效时间-- ARGV[2] id+":"+threadID 线程唯一标识-- 判断锁是否存在if (redis.call('exists', KEYS[1]) == 0) then -- 锁不存在 -- 在redis中添加锁 源码中使用的是hincrby redis.call('hset', KEYS[1], ARGV[2], 1); -- 设置锁的过期时间 redis.call('pexpire', KEYS[1], ARGV[1]); return nil;end; -- 说明锁已 ...

二叉堆 父结点索引 i/2 左孩子结点索引 2*i 右孩子结点索引2*i 最大堆：每个结点都大于等于它的两个左右子结点 优先级队列功能：插入和删除元素，元素会自动排序。底层二叉树操作 最大优先级队列代码实现： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687public class MaxPQ <Key extends Comparable<Key>> { // Key是任何一种可比较大小的数据类型 // 存储元素的数组 private Key[] pq; // 当前 Priority Queue 中的元素个数 private int size = 0; public MaxPQ(int cap) { // 索引 0 ...

二分搜索没有重复元素的有序数组 普通二分查找 重复元素的有序数组 左侧边界的二分搜索，右侧边界的二分搜索 左侧边界的二分搜索 当target存在数组nums中时，返回的是第一个重复元素的索引 当target不存在数组nums中时 例：nums[]=[2,3,5,7] target=4 返回的left=2 left指向nums中大于target的最小元素索引 返回的是target应该插入的位置索引 返回nums数组中小于target的个数 右侧边界的二分搜索 返回的是最后一个重复元素的索引 二分搜索的应用什么问题可以应用二分搜索？ 从题目中抽象出一个自变量 x，一个关于 x的函数 f(x)，以及一个目标值 target。 同时，x, f(x), target 还要满足以下条件： f(x) 必须是在 x 上的单调函数（单调增单调减都可以）。 题目是让你计算满足约束条件 f(x) == target 时的 x 的值。 例：875. 爱吃香蕉的珂珂 分析：自变量x是珂珂吃香蕉的速度，f(x)是吃完所有堆上所用时间。 x越大，吃的越快，所花时间f(x)就越小。吃香蕉的时 ...

事务的隔离性数据库原本c的值为1 不同隔离级别的结果 隔离级别为读未提交（read uncommitted）:一个事务还没提交时，它的事务就能被别的事务所看见。 事务B未提交，但结果已经被事务A所看见。 V1=2 V2=2 V3=2 隔离级别为读提交（read committed）:一个事务提交之后，它的结果才能被其他事务所看见。 V1=1 V2=2 V3=2 隔离级别为可重复读（repeatable read）: 一个事务执行过程中看到的数据，总是和这个事务在启动时看到的一样。并且，未提交的变更对其他事务也是不可见的。 V1=1 V2=1 V3=2 隔离级别为串行化（serializable）:对于同一行记录，“写”会加“写锁”，“读”会加“读锁”。当出现读写锁冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行。 在事务B将1改成2时锁住，直到事务A执行完成,事务B才能继续执行。 V1=1 V2=1 V3=2

一条SQL查询语句的执行流程 1select * from T where ID=10; 连接器连接器负责跟客户端建立连接、获取权限、维持和管理连接 1mysql -h$ip -P$port -u$user -p 如果用户名或密码不对，你就会收到一个”Access denied for user”的错误，然后客户端程序结束执行。 如果用户名密码认证通过，连接器会到权限表里面查出你拥有的权限。 长连接 & 短连接 长连接是指连接成功后，如果客户端持续有请求，则一直使用同一个连接。 短连接则是指每次执行完很少的几次查询就断开连接，下次查询再重新建立一个。 查询缓存之前执行过的语句及其结果可能会以key-value对的形式，被直接缓存在内存中。key是查询的语句，value是查询的结果。但查询缓存的失效非常频繁，只要有对一个表的更新，这个表上所有的查询缓存都会被清空。MySQL 8.0版本无查询缓存功能。 分析器分析器先会做“词法分析”。MySQL需要识别出SQL语句的字符串分别是什么，代表什么。 MySQL从你输入的”select”这个关键字识别出来，这是一个查询语句。它也 ...

树结构二叉排序树，缺陷：在极端情况下，一个有序序列会退化成链表 所以，要使用平衡树来进行调节 为什么要保证树的平衡？ 因为树的查询效率取决于树的高度，让树尽可能的平衡，就是为了减少树的高度。 那B树的作用是什么？ B树又叫多路查找树，每个结点可以拥有多于两个孩子结点。m路B树最多就可以拥有m个孩子结点 这是棵三路B树。为什么要设计成多路？就是为了进一步降低树的高度。路数越多，树就越低。那路数无限大，不就更好？ 为什么文件系统的索引使用B树，而不使用红黑树或者是有序数组？ 文件系统或者数据库的索引是存储在硬盘上的，如果数据量越大，就不能一次性的加载到内存。这时候，能够体现B树的多路存储作用，每次加载B树的一个结点，然后一步一步往下找。 假设内存一次性只能加载两个树，这时候有序数组【25，25，30，40，43，45，50，59，65，77，85】是不能够一次性加载到内存的，所以，可以构建三路B树，每个结点至多有两个数。 那B+树有什么作用？ 这是一棵4路B+树，数据都在叶子结点，并且通过链表相连。 使用场景：比如select查询多条数据，B树可能需要做中序遍历，跨层访问，而B+树所 ...