几道练习

---

Java IO和NIO的区别

线程的五种状态

new, runnable, running, block, terminal。

不借助临时遍历进行变量交换

异或，相同为0。

a = a^b;
b = a^b;  // b = a^b^b = a
a = a^b;  // a = a^b^a = b

手撕单例模式和验证

DCL

class Singleton {
    private volatile static Singleton instance;
    
    private Singleton() {}
    
    public static Singleton getInstance() {
        if(instance==null) {
            synchronized(Singleton.class) {
                if(instance==null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

静态内部类

如果用static来修饰一个内部类，那么就是静态内部类。这个内部类属于外部类本身，但是不属于外部类的任何对象。因此使用static修饰的内部类称为静态内部类。静态内部类有如下规则：

• 静态内部类不能访问外部类的实例成员，只能访问外部类的类成员。
• 外部类可以使用静态内部类的类名作为调用者来访问静态内部类的类成员，也可以使用静态内部类对象访问其实例成员。

class Singleton {
    private static class InstanceFac {
        static Singleton ins = new Singleton();
    }
    
    private Singleton() {}
    
    public static Singleton getInstance() {
        return InstanceFac.ins;
    }
}

检验

import java.util.Random;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;

public class Singleton {
    private volatile static Singleton instance;
    
    private Singleton() {}
    
    public static Singleton getInstance() {
        if(instance==null) {
            synchronized(Singleton.class) {
                if (instance == null) {
                    //Thread.sleep(new Random().nextInt(300));
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
    public static void main(String[] strings) throws InterruptedException {
        int SIZE = 1000;
        CountDownLatch latch = new CountDownLatch(SIZE);
        ConcurrentHashMap<Singleton,Integer> map = new ConcurrentHashMap<>();
        for(int i=0;i<SIZE;i++) {
                new Thread(()->{
                    Singleton s = Singleton.getInstance();
                    synchronized(s) {
                        map.put(s,map.getOrDefault(s,0)+1);
                    }
                    
                    latch.countDown();
                } 
            ).start();
        }
        latch.await();
        for(Singleton s:map.keySet()) {
            System.out.println(s+" "+map.get(s));
        }
    }
}

最长上升子序列

知道原问题转化为这个问题了，但是奈何这个不会写了。。转化也转化错了。

import java.util.*;

public class Main {
    public static void main(String[] strings) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for(int k=0;k<T;k++) {
            int n = scanner.nextInt();
            int[][] xy = new int[n][2];
            for(int i=0;i<n;i++) xy[i][0]=scanner.nextInt();
            for(int i=0;i<n;i++) xy[i][1]=scanner.nextInt();
            System.out.println(getSuitable(xy));
        }
    }
    
    public static int getSuitable(int[][]xy) {
        int lastx = -1;
        int lasty = -1;
        int result = 0;
        Arrays.sort(xy,(a,b)->{
            if(a[0]!=b[0]) return a[0]-b[0];
            return a[1]-b[1];
        });
        
        // 错了，这样会掩盖一部分可能性
        //List<Integer> dq = new ArrayList<>();
        //for(int i=0;i<xy.length;i++) {
        //    if(xy[i][0]==lastx) continue;
        //    dq.add(xy[i][1]);
        //    lastx = xy[i][0];
        //}
        
        int n = xy.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i=0;i<n;i++) {
            for(int j=0;j<i;j++) {
                if(xy[i][0]>xy[j][0]&&xy[i][1]>xy[j][1]) {
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            result = Math.max(result,dp[i]);
        }
        return result;
    }
}

二分

x1相同的，x2需倒序，这样就不会统计重复x1的了。

牛客那种黑箱式真是磨人，自己构造测试用例通过，一跑，通过0。。。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tail = new int[nums.length];
        tail[0] = nums[0];
        int idx = 1;
        for(int i=1;i<nums.length;i++) {
            if(nums[i]>tail[idx-1]) {
                tail[idx++] = nums[i];
                continue;
            }
            int left = 0;
            int right = idx-1;
            while(left<right) {
                // 3
                // 2 5
                int mid = (left+right)/2;
                if(nums[i]>tail[mid]) {
                    left=mid+1;
                } else {
                    right = mid;
                }
                //System.out.println(Arrays.toString(tail));
               // System.out.printf("%d %d %d\n",i,left,right);
            }
            tail[left] = nums[i];
        }
        return idx;
    }
}