记录：2022-9-25 IO概念 字符串的排列 路径总和 III BIO 线程池 IO概念（1）

学习时间：2022-9-25

学习内容

1、leetcode

567. 字符串的排列

思路

我用的双指针写法，将s1放入HashMap中，用两个指针来找，如果R指针移动中发现不够，则L移动，以此往复

代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s2.length();
        
        HashMap<Character,Integer> orign = new HashMap<Character,Integer>();
        for(int i = 0;i<s1.length();i++){
            orign.put(s1.charAt(i),orign.getOrDefault(s1.charAt(i),0)+1);
        }
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        map.putAll(orign);
        
        int count = 0;
        int L = 0;
        int R = 0;
        // boolean ans = false;
        while(L<n){
            if(!map.containsKey(s2.charAt(L))){
                L++;
                R = L;
                // continue;
            }else{
                while(R < n
                    &&map.containsKey(s2.charAt(R)) 
                    && map.get(s2.charAt(R))>0){
                    map.put(s2.charAt(R),map.get(s2.charAt(R))-1);
                    R++;
                    count++;
                    if(count == s1.length()){
                        return true;
                    }
                }
                L ++;
                R = L;
                count = 0;
                map.putAll(orign);//map复原
            }
        }
        return false;
    }
}

可以看到几乎超时

更优解

更优解是使用滑动窗口，我的感觉是如果能使用双指针的情况下，可以先思考能否使用滑动窗口，滑动窗口还是比较好使的

下面这个是双指针的更优解，这个写法没有用hashmap，用数组代替

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
        }
        int left = 0;
        for (int right = 0; right < m; ++right) {
            int x = s2.charAt(right) - 'a';
            ++cnt[x];
            while (cnt[x] > 0) {
                --cnt[s2.charAt(left) - 'a'];
                ++left;
            }
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-7k7u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个是滑动窗口写法 并有优化

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
            ++cnt[s2.charAt(i) - 'a'];
        }
        int diff = 0;
        for (int c : cnt) {
            if (c != 0) {
                ++diff;
            }
        }
        if (diff == 0) {
            return true;
        }
        for (int i = n; i < m; ++i) {
            int x = s2.charAt(i) - 'a', y = s2.charAt(i - n) - 'a';
            if (x == y) {
                continue;
            }
            if (cnt[x] == 0) {
                ++diff;
            }
            ++cnt[x];
            if (cnt[x] == 0) {
                --diff;
            }
            if (cnt[y] == 0) {
                ++diff;
            }
            --cnt[y];
            if (cnt[y] == 0) {
                --diff;
            }
            if (diff == 0) {
                return true;
            }
        }
        return false;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-7k7u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

437. 路径总和 III

思路

对每一个节点，都算他下面可以得到target的数量，使用两个递归

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans = 0;
    public int pathSum(TreeNode root, int targetSum) {
        order(root,targetSum);

        return ans;
    }
    public void order(TreeNode root,int targetSum){
        if(root == null){
            return;
        }
        getVal(root,0,targetSum);
        order(root.left,targetSum);
        order(root.right,targetSum);

    }
    //得到该节点下面有多少个
    public void getVal(TreeNode root,long sum,int targetSum){
        if(root == null){
            return;
        }
        
        if(sum + root.val == targetSum){
            ans+= 1;
        }
        sum = sum+root.val;
        getVal(root.left,sum,targetSum);
        getVal(root.right,sum,targetSum);

    }
}

这个空间复杂度就离谱。。

更优解

前缀和

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val;

        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }
}

2、BIO 线程池伪异步写法

使用了线程池改良原先的Thread，好处是不会无限制的开启线程，节约资源

服务端代码：

public class BIOServer {
    public static void main(String[] args) {
        try {
            ServerSocket server = new ServerSocket(8099);
            System.out.println("server is running at 8099");
            BIOThreadPool pool = new BIOThreadPool(2,3);
            while(true){
                Socket client = server.accept();//阻塞线程 直到有socket进来
                pool.execute(new BIOServerThread(client));
//                new BIOServerThread(client).run();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

线程池代码：

public class BIOThreadPool {
    ExecutorService pool;
    public BIOThreadPool(int coreNum,int waitSize){
        this.pool = new ThreadPoolExecutor(coreNum,
        6,
        120,
        TimeUnit.MINUTES,
        new ArrayBlockingQueue<Runnable>(waitSize));
    }
    public void execute(Runnable runnable){
        pool.execute(runnable);
    }
}

服务端线程代码（改成runnable 其余不变）：

public class BIOServerThread implements Runnable {
    Socket socket;
    public BIOServerThread(Socket socket) {
        this.socket = socket;
    }
    @Override
    public void run() {
        //拿到这个socket并不断监听
        try {
            InputStream inputStream = socket.getInputStream();
            BufferedReader br = new BufferedReader(new InputStreamReader(inputStream));
            String msg = "";
            //被阻塞在这里，不会一直执行这个while
            while((msg = br.readLine()) != null){
                System.out.println(msg);
            }

        } catch (IOException e) {
            e.printStackTrace();
        }

    }
}

客户端代码：

public class BIOClient {
    public static void main(String[] args) {
        try {
            Socket socket = new Socket("127.0.0.1",8099);
            OutputStream outputStream = socket.getOutputStream();
            PrintStream ps = new PrintStream(outputStream);
            Scanner sc = new Scanner(System.in);
            while(true){
                String msg = sc.nextLine();
                ps.println(msg);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

3、操作系统概念 IO概念（1）

IO设备

IO设备可以分成：块设备、字节设备和网络设备

块设备

如磁盘设备就是块设备，可以提前知道要取多少

字节设备

键盘等设备就是字节设备，事先不知道需要输入多少，需要用户来输入
如昨天那个屏幕的例子，就可以看到rw_char，即转入到字节设备输入

网络设备

网卡等，一般为网络套接字socket接口，有select()操作，这个操作可以得知哪些套接字有接收数据需要处理等

非阻塞与异步IO

可以分成BIO NIO AIO ，分别为同步阻塞IO，同步非阻塞IO，异步非阻塞IO
NIO并不只是在JAVA中被用于网络套接字，他实际上在很多地方也有用到，如在用户接口接收键盘和鼠标事件，他会接收到事件输入，并且处理数据展示到显示器。
AIO调用将立即返回，无需等待IO完成，当IO完成后，通过设置应用程序地址空间内的某个变量，或通过触发信号或软件中断或在线性控制流以外执行的回调函数来通知应用程序

内核IO系统

内核可以给IO提供多个服务，如调度、缓冲、缓存、假脱机，这里只讲这四种，其余的不太能看懂

调度

调度是非常重要的一个改善系统性能的方式，因为应用程序执行系统调用的顺序很难说是最佳的。调度的核心就是分配这个最佳队列。
每个设备可以维护一个请求等待队列，当应用程序发出阻塞IO系统调用时，该请求被添加到队列中，然后IO调度程序将会重新安排队列。
当内核支持异步时，可以跟踪多个IO请求，所以系统可能还会把等待队列加入到设备状态表中，每个条目将会对应一个IO设备

缓冲

缓冲区是一块内存区域，使用缓冲有三个理由（重要，可以想想String和StringBuffer）

1. 处理数据流的生产者和消费者之间的速度不匹配问题（不仅仅是CPU和磁盘）
2. 协调传输大小不一数据的设备，如计算机网络中的分组网络传输
3. 支持应用程序IO的复制语义（Ctrl+c 将内容放入缓冲区 Ctrl+v 将缓冲区内容输出）

缓存

保存数据副本的告诉内存区域。访问缓冲副本比访问原版更有效
缓冲与缓存的区别：缓冲可以保存数据项的唯一现有副本，缓存只是提供一个位于其他位置的数据项的更快存储副本
一个内存区域可以用于缓存和缓冲两个目的，并不一定是割裂的

假脱机

假脱机是保存设备输出的缓冲区，为了不让交叉的数据流混入一起

请求转换到硬件流程

具体就是昨天那个案例的抽象：
首先需要建立inode的链接，此处inode存放的是设备的空间位置信息，open函数可以通过一个安装表找到，也就是file_table,假设调用write操作，会先看这个设备是字节设备还是块设备，例如屏幕，就是一个字节设备，然后就可以找到rw_char函数，来写入或读入字节，这里还会读入一个表，这个表是设备表，有主设备和次设备之分，，这个major存放的是设备的驱动程序，得到这个函数就可以往这个设备里面写了
所以，总体操作就是：建立文件链接，得到inode，然后通过具体的IO，区分当前设备，通过参数从major设备表中找到对应的io操作（再往下就是汇编代码）