记录：2022-9-28 岛屿的最大面积 字母异位词分组 雪花算法实现 偏向锁 |锁升级 阻塞线程的方式

学习时间：2022-9-28

学习内容

1、leetcode

695. 岛屿的最大面积

思路

BFS，算max

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int ans = 0;
        LinkedList<int[]> queue = new LinkedList<int[]>();
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                //若访问的点已经访问过或者这个点是海 则直接返回 找下一个
                if(visited[i][j] || grid[i][j] == 0){
                    continue;
                }
                //没有访问过的1
                queue.add(new int[]{i,j});
                int max = 0;
                while(!queue.isEmpty()){
                    int[] res = queue.poll();
                    int row = res[0];
                    int col = res[1];
                    if(visited[row][col]) continue;//重复
                    //将他的四方加入，如果访问过 或者是0 或者到边界 则不加入队列
                    //左：
                    if(col-1>=0&&!visited[row][col-1]&&grid[row][col-1]!=0){
                        queue.add(new int[]{row,col-1});
                    }
                    //右：
                    if(col+1<=n-1&&!visited[row][col+1]&&grid[row][col+1]!=0){
                        queue.add(new int[]{row,col+1});
                    }
                    //上：
                    if(row-1>=0&&!visited[row-1][col]&&grid[row-1][col]!=0){
                        queue.add(new int[]{row-1,col});
                    }
                    //下：
                    if(row+1<=m-1&&!visited[row+1][col]&&grid[row+1][col]!=0){
                        queue.add(new int[]{row+1,col});
                    }
                    visited[row][col] = true;
                    max++;
                }
                ans = Math.max(ans,max);
            }
        }
        return ans;
    }
}

更优解

DFS：

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        for (int i = 0; i != grid.length; ++i) {
            for (int j = 0; j != grid[0].length; ++j) {
                ans = Math.max(ans, dfs(grid, i, j));
            }
        }
        return ans;
    }

    public int dfs(int[][] grid, int cur_i, int cur_j) {
        if (cur_i < 0 || cur_j < 0 || cur_i == grid.length || cur_j == grid[0].length || grid[cur_i][cur_j] != 1) {
            return 0;
        }
        grid[cur_i][cur_j] = 0;
        int[] di = {0, 0, 1, -1};
        int[] dj = {1, -1, 0, 0};
        int ans = 1;
        for (int index = 0; index != 4; ++index) {
            int next_i = cur_i + di[index], next_j = cur_j + dj[index];
            ans += dfs(grid, next_i, next_j);
        }
        return ans;
    }
}

49. 字母异位词分组

思路

将string排序之后作为哈希表的key，还需要存放value，value是所在ans中的位置，每次若找到相同的异构，需要加到index处

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();//String和index
        ArrayList<List<String>> ans = new ArrayList<List<String>>();
        int index = 0;
        for(int i = 0;i<strs.length;i++){
            String ori = strs[i];
            String sortStr = sortStr(ori);
            if(map.containsKey(sortStr)){
                int arrIdx = map.get(sortStr);
                ans.get(arrIdx).add(ori);
            }else{
                ArrayList sub = new ArrayList<String>();
                sub.add(ori);
                ans.add(sub);
                map.put(sortStr,index++);
            }
        }
        return ans;
    }
    public String sortStr(String str){
        //将str按字符ASCII码排序
        char[] chs = str.toCharArray();
        Arrays.sort(chs);
        String result = new String(chs);
        return result;
    }
}

更优解（另解）

由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

2、雪花算法实现

主体代码

雪花算法主体代码实现如下：

    public synchronized long getNextId(){
        long currentStamp = getCurrentStamp();
        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (currentStamp < lastStamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastStamp - currentStamp));
        }
        if(currentStamp == lastStamp){
            //说明是同一毫秒时间戳生成
            sequence = (sequence+1) & sequenceMask;//防止越位
            if(sequence == 0){
                //此时说明4096已满
                currentStamp = getNextStamp(lastStamp);
            }
        }else{
            sequence = 0L;//重置
        }
        lastStamp = currentStamp;
        return ((currentStamp-12345678L)<<TimeShift) |
                (machineId<<MachineShift) |
                (computerId<<ComputerShift) |
                (sequence);
    }

其他地方大差不差，但是必须注意，不能写Long，必须要写long，否则判断时一直是null，还有一点是需要synchronized，生成id这个方法需要一个一个来

    private long getNextStamp(long currentStamp){
        long nowStamp = getCurrentStamp();
        while(nowStamp <= currentStamp){//自旋锁
            nowStamp = getCurrentStamp();
        }
        return nowStamp;
    }

实现线程等待

Thread.join()

适用于一个线程的情况

CountDownLatch

适用于有多个线程，用一个count来记录线程数，当一个线程执行完 需要调用count.countDown(); 在最外处count.await() 来等待其他线程执行完毕

LongAdder

在加和sum方面，比AtomicInteger快，因为其他线程不需要一直自旋，这是用时间换空间

3、Java锁机制（2） 偏向锁 |锁升级

Java对象内部结构|synchronized锁的什么？

一个对象分为以下几个部分，对象头中存储的就是各类状态信息，synchronized也是锁的这里
这个以外还有实例数据，如一些属性成员变量等，最后会有对齐填充，为了把整个对象填满8位，这样索引方便

偏向锁与锁升级

这个概念是一种锁的优化，还是synchronized关键字，这个对象会在多线程竞争的过程中逐渐升级，其过程如下：

首先是无状态时期，当前线程若4s阻塞则自动开启偏向锁，偏向锁是锁的线程Id号，当进来的线程也是这个id号，说明不是并发情况，就不需要每次都去锁整个线程了，这样可以减少上下文的切换；当升级成偏向锁后，如果遇到了不是这个id的进程，则升级成轻量级锁，这个锁采用CAS方法，一个线程执行其他线程自旋，当自旋次数超过一定值后，将会升级成重量级锁，把所有自旋线程放入等待队列中。（此时重量级锁性能优于轻量级锁）
下图为对象头的表示信息：

真实情况下偏向锁时对象头状态如下：

4、阻塞线程的方式

1. while 自旋锁
2. wait 需要和synchronized一起使用
3. park 暂时没用到
4. sleep 需要一个唤醒时间 Thread.sleep()方法是睡眠当前线程