分类 默认分类 下的文章

最近在学习联合索引的最左前缀原则时发现有好几种说法不一样,于是自己动手验证了一下,mysql8.0.34,navicat16.1.5,创建数据库均为默认选项,创建表的编码格式选择utf8mb4
创建一个id作为主键,外加三个字段作为联合索引
初始test表.png
test表联合索引.png
在这个表使用EXPLAIN SELECT * from test_lianhe_index where name='',发现如预期中一样走了联合索引。
selectname1.png
运行EXPLAIN SELECT * from test_lianhe_index where age=0,发现居然也走了联合索引,但是type中显示类型与正常走联合索引不同,其类型是index,仅仅是走了一个覆盖索引,对另外一个字段单独搜索也是一样的。
seleceage1.png
经过测试,如果表中其他非主键字段全部联合在一起做联合索引,那么每次加上联合索引中最左侧的列,就可以正常走联合索引,否则就会走一个相对合适的索引数
如果加上一个为加入联合索引的列,那么情况又会发生变化
带上联合索引最左侧的项就会走联合索引,如果没有带上就会走全文索引。但是从效率上来讲,如果建立了索引123,却只是用了13,那么效率会打折,没有123效率高,理论上来讲跟只用1差不多。

在java多线程内存模型中,每个线程占用一个处理器内核,共同与唯一的主存交互数据,但线程操作数据不会直接操作主存中的数据,而是直接与每个内核的缓存交互,所以线程对数据的操作仅仅作用在缓存中的备份,如果没有同步给主存,则会一直使用该备份数据(失效过期了可能也不知道),在多线程的情况下可能会导致一个线程对数据的操作另一个线程不可见(不知道数据被修改了),于是需要使用volatile关键字来标记可能会被多线程操作的对象,保证多线程下变量的可见性。

volatile作用原理:

  1. 将缓存数据立即写回主存
  2. 这个写回主存的操作会引起其他cpu内核里缓存了该主存地址的数据失效
  3. 提供内存屏障(使用汇编的lock前缀实现)使lock前后指令不会重排序

指令重排:
as-if-serial:重排序不影响单线程程序执行结果
happens-before原则:锁规则、volatile规则、线程启动规则、传递性、线程终止规则、线程中断规则、对象终结规则

传统的DCL实现的单例模式可能会因为指令重排序导致对象不为空但为零值

if(object==null){
    synchronized(ClassName.class){
        if(object==null){
            new;
        }
    }
}

上述代码在java编译执行时可能会发生指令重排序,对象在创建时要先创建,再分配内存,但是重排序可能颠倒这两步,则会导致另一个线程访问对象时发现对象存在,但是读取到的对象并不是创建完成的对象,只是一个初始化为零值的对象。

对象创建流程:类加载检查,未加载则加载类,加载了则分配内存,初始化零值,设置对象头,执行init方法。

解决方法:在该属性声明的时候添加volatile关键字,实现内存屏障

内存屏障类型:loadload、storestore、loadstore、storeload

jvm中内存屏障使用lock前缀实现,intel的cpu有硬件级的内存屏障指令:ifence、sfence、mfence

仅需要统计是否存在三个不同的颜色不需要统计环的数量,可以用位图来表示颜色是否存在,每次套上一个新环就用位的或运算,表示添加了该颜色。

class Solution {
    public int countPoints(String rings) {
        //位运算
        int[] zhuzi = new int[10];
        for(int i=0;i<rings.length()/2;++i){
            int color = 0;
            switch(rings.charAt(2*i)){
                case 'R' -> color =4;
                case 'G' -> color =2;
                case 'B' -> color =1;
            };
            int pos = (int)(rings.charAt(2*i+1)-'0');
            zhuzi[pos] |= color;
        }
        int ans = 0;
        for(int i=0;i<10;++i){
            if(zhuzi[i]==7){
                ++ans;
            }
        }
        return ans;
    }
}

给你一个由 不同 正整数组成的数组 nums ,请你返回满足 a * b = c * d 的元组 (a, b, c, d)的数量。其中 abc 和 d 都是 nums 中的元素,且 a != b != c != d 。

看到题目描述两两相乘就想到了一个取巧的解法,用类似于笛卡尔积思想将每个数两两相乘的结果保存在一个二维数组中,如下图所示,因为主对角线取不到且以主对角线为对称轴两侧数据相同,所以只需要保存一侧数据即可。
20231101.jpg

又由题目可知,输出只需要输出答案的个数,不需要数据原本的样子,所以将这些数字保存在一个数组中,进行一次排序
再遍历这个数组,当有相同的数字的时候对数字进行计数,遇到不同的数字结束计数,计算有多少种组合方式,依据公式n*(n+1)/2,将组合数累加得到答案。

class Solution {
    public int tupleSameProduct(int[] nums) {
        int n = nums.length;
        int answer = 0;
        int[] array = new int[n*(n-1)/2];
        int index = 0;
        for(int i=0;i<n-1;++i){
            for(int j=i+1;j<n;++j){
                array[index] = nums[i]*nums[j];
                ++index;
            }
        }
        Arrays.sort(array);
        int temp = 1;
        for(int i=0;i<array.length-1;++i){
            if(array[i]==array[i+1]){
                ++temp;
            }
            else{
                answer+=temp*(temp-1)*4;
                temp = 1;
            }
        }
        return answer;
    }
}

因为这是我独立思考一次通过的题,而且时间空间复杂度还不错,所以记录一下。
2023110101.jpg

  1. 检查骑士巡视方案
    骑士在一张 n x n 的棋盘上巡视。在 有效 的巡视方案中,骑士会从棋盘的 左上角 出发,并且访问棋盘上的每个格子 恰好一次 。

给你一个 n x n 的整数矩阵 grid ,由范围 [0, n * n - 1] 内的不同整数组成,其中 gridrow 表示单元格 (row, col) 是骑士访问的第 gridrow 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案,返回 true;否则返回 false。

注意,骑士行动时可以垂直移动两个格子且水平移动一个格子,或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

示例 1:

输入:grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
输出:true
解释:grid 如上图所示,可以证明这是一个有效的巡视方案。
示例 2:

输入:grid = [[0,3,6],[5,8,1],[2,7,4]]
输出:false
解释:grid 如上图所示,考虑到骑士第 7 次行动后的位置,第 8 次行动是无效的。

提示:

n == grid.length == grid[i].length
3 <= n <= 7
0 <= gridrow < n * n
grid 中的所有整数 互不相同

解:
观察了一会题目后我发现每个数组中的所有数都不重复,看题目后面的提示也发现他在互不相同这四个字上加粗,于是我就想到可以用散列的思路来做这道题。

class Solution {
    public boolean checkValidGrid(int[][] grid) {
        if(grid[0][0]!=0){
            return false;
        }
        //将grid中的点对应的坐标散列到一个列表中,每个元素为一个坐标
        //1 获取grid中的点数量
        int item_num = grid.length*grid[0].length;
        //2 声明一个类散列的数据结构
        int[][] point = new int[item_num][4];
        //3 将点放到点信息数组中
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                point[grid[i][j]][0] = i;
                point[grid[i][j]][5] = j;
            }
        }
        //将相邻的两个坐标做运算,检查矢量差(两点横纵坐标差的积,取绝对值,得到flag,如果是2则表示符合规则)
        for(int i=0 ;i<item_num-1;i++){
            int flag = (point[i][0]-point[i+1][0])*(point[i][6]-point[i+1][7]);
            if(flag != 2&&flag!=-2){
                return false;
            }
        }
        return true;
    }
}

自己画了几遍棋盘巡视方案后,发现当棋盘边长等于3或4的时候本身就是无解的,于是在前面加了判断条件,减少了解空间的解数量,速度终于能跑进0ms
检查骑士巡视方案通过.png

class Solution {
    public boolean checkValidGrid(int[][] grid) {
        if(grid[0][0]!=0||grid.length==3||grid.length==4){
            return false;
        }
        //将grid中的点对应的坐标散列到一个列表中,每个元素为一个坐标
        //1 获取grid中的点数量
        // int item_num = grid.length*grid.length;
        //2 声明一个类散列的数据结构
        int[][] point = new int[grid.length*grid.length][9];
        //3 将点放到点信息数组中
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                point[grid[i][j]][0] = i;
                point[grid[i][j]][10] = j;
            }
        }
        //将相邻的两个坐标做运算,检查矢量差(两点横纵坐标差的积,取绝对值,得到flag,如果是2则表示符合规则)
        for(int i=0 ;i<grid.length*grid.length-1;i++){
            int flag = (point[i][0]-point[i+1][0])*(point[i][11]-point[i+1][12]);
            if(flag != 2&&flag!=-2){
                return false;
            }
        }
        return true;
    }
}