记录：2022-9-9 水果成篮 最大正方形 分页 银行家算法习题2道

学习时间：2022-9-9

学习内容

1、leetcode两道中等题

这个题解我做的时间空间优于题解，这个题主要需要考虑这个窗口什么时候走，什么时候停，下一次从哪个位置继续
1、用两个变量表示篮子，当数在篮子中时，窗口像右移动（此时需要记录右指针位置）
2、当停下来时，左指针移动到右指针原先的位置，继续重复1操作
3、需要保证两个篮子里的东西不能相等
代码如下：

class Solution {
    public int totalFruit(int[] fruits) {
        if(fruits.length == 1){
            return 1;
        }
        int ans = 1;
        int mx = 1;
        int l1 = 1;
        int l2 = 0;
        int l1Fruit = fruits[1];
        int l2Fruit = fruits[0];
        //初始化 找到两个不一样的水果
        while(l1Fruit == l2Fruit){
            if(l1 + 1 >= fruits.length){
                return l1-l2+1;
            }
            l1Fruit = fruits[++l1];
        }
        while(l1<fruits.length){
            int originL1 = l1;
            while(fruits[l1] == l1Fruit || fruits[l1] == l2Fruit){
                l1++;
                if(l1 >= fruits.length){
                    mx = l1 - l2;
                    ans = Math.max(mx,ans);
                    return ans;
                }
            }
            mx = l1 - l2;
            ans = Math.max(mx,ans);
            l2 = originL1;
            //找到最近的那个L1不同的
            for(int i = l2+1;i<fruits.length;i++){
                if(fruits[i] != fruits[l2]){
                    l1 = i;
                    break;
                }
            }
            if(l1 >= fruits.length){
                return Math.max(l1-l2+1,ans);
            }
            l2Fruit = fruits[l2];
            l1Fruit = fruits[l1];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

又是自己没有找到DP条件的一天，这个题dp为：以i j为右下角的正方形可以达到的最大边长

nums[i][j] != 0
dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) +1
nums[i][j] == 0
dp[i][j] = 0

2、操作系统概念 分页

分页基本方法

将物理内存分为帧或页帧，将逻辑内存分为页或页面，帧和页的大小相同，当执行一个进程时，他的页加载到内存的可用帧中。
逻辑内存和物理内存之间存在一个页表，类似于书的目录，这样就可把帧和页对应起来
以下为分页的硬件结构与概念上的分页模型

可以看到在硬件下，页表的p是页码，即在页表中处在第p个单元，f是指向的物理地址，并且这个偏移量d 逻辑地址与物理地址相同，也印证了帧与页一样长。
除了页表，也有帧表，该表每个条目对应的是一个帧，表示该帧是已经占用还是空闲

硬件支持

标准解决方案：使用转换表缓冲区（TLB），TLB与页表一起使用的关系就类似于Reids与MySQL的关系，但是TLB是硬件层面的

找到了页码，则可直接调用帧码，否则查找后加入，若满了则使用替换算法

共享页

分页的优点之一是可以共享代码
如果代码是可重用或纯代码，则可以共享
可重用代码：在相似业务场景下，用的是同一份代码

页表结构

分层页表

为了拆分单页，不让他那么大
这种方案也叫向前映射页表（不太明白他是否减小了虚构内存）

哈希页表

用哈希表来充当页表，优势类似于其他哈希结构（查找快），还是存在哈希碰撞

倒置页表

修改了页表的结构，存储的值不再是单纯的页码，这样的作用是让页表每次存储的都是一个有效的进程，而无效进程不往里面存。

3、银行家算法 习题2道

这两个题解决了我对于银行家问题的困惑，即如何才能得到序列，实际上就是Avalibale和Need的对比，如果满足使用，则说明安全，若这个i在遍历一次进程队列都没有找到，说明资源被占用，非安全。
进程的请求，只需要改变Avaliable，Work，Need的状态，再重复安全状态检查即可