记录：2022-9-13 正则表达式匹配 Java中的String能有多大 文件系统目录 原子性操作 锁 同步 信号量

学习时间：2022-9-13

学习内容

1、LeetCode 困难题：10. 正则表达式匹配

难度有点大，最大的原因还是在于边界和要考虑的条件太多，当判断时，要考虑不少的东西，另外我做的时候没有想到DP，因为最优子结构太难找，题解dp最优子结构如下：
考虑边界条件如下：（题解摘自：笨猪爆破组 leetcode）
选择从右往左扫描
星号的前面肯定有一个字符，星号也只影响这一个字符，它就像一个拷贝器。

s、p 串是否匹配，取决于：最右端是否匹配、剩余的子串是否匹配。
只是最右端可能是特殊符号，需要分情况讨论而已。
通用地表示出子问题
大子串是否匹配，和剩余子串是否匹配，是规模不一样的同一问题。

情况1：s[i-1]s[i−1] 和 p[j-1]p[j−1] 是匹配的
最右端的字符是匹配的，那么，大问题的答案 = 剩余子串是否匹配。

情况2：s[i-1]s[i−1] 和 p[j-1]p[j−1] 是不匹配的
右端不匹配，还不能判死刑——可能是 p[j-1]p[j−1] 为星号造成的不匹配，星号不是真实字符，它不匹配不算数。
如果 p[j-1]p[j−1] 不是星号，那就真的不匹配了。

p[j−1]==“∗”，且 s[i-1]s[i−1] 和 p[j-2]p[j−2] 匹配
p[j-1]p[j−1] 是星号，并且 s[i-1]s[i−1] 和 p[j-2]p[j−2] 匹配，要考虑三种情况：
p[j−1] 星号可以让 p[j-2]p[j−2] 在 p 串中消失、出现 1 次、出现 >=2 次。
只要其中一种使得剩余子串能匹配，那就能匹配，见下图 a1、a2、a3。

a3 情况：假设 s 的右端是一个 a，p 的右端是 a * ， 让 a 重复 >= 2 次
星号不是真实字符，s、p是否匹配，要看 s 去掉末尾的 a，p 去掉末尾一个 a，剩下的是否匹配。
星号拷贝了 >=2 个 a，拿掉一个，剩下 >=1 个a，p 末端依旧是 a* 没变。
s 末尾的 a 被抵消了，继续考察 s(0,i-2) 和 p(0,i-1) 是否匹配。
p[j−1]==“∗”，但 s[i-1]s[i−1] 和 p[j-2]p[j−2] 不匹配
s[i−1] 和 p[j−2]p[j−2] 不匹配，还有救，p[j−1]p[j−1] 星号可以干掉 p[j−2]p[j−2]，继续考察 s(0,i-1)s(0,i−1) 和 p(0,j-3)p(0,j−3)。

base case
p为空串，s不为空串，肯定不匹配。
s为空串，但p不为空串，要想匹配，只可能是右端是星号，它干掉一个字符后，把 p 变为空串。
s、p都为空串，肯定匹配。

dp[i][j]:表示s的前i个字符，p的前j个字符是否能够匹配

class Solution {
    public boolean isMatch(String s, String p) {
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();

        // dp[i][j]:表示s的前i个字符，p的前j个字符是否能够匹配
        boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];

        // 初期值
        // s为空，p为空，能匹配上
        dp[0][0] = true;
        // p为空，s不为空，必为false(boolean数组默认值为false，无需处理)

        // s为空，p不为空，由于*可以匹配0个字符，所以有可能为true
        for (int j = 1; j <= cp.length; j++) {
            if (cp[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        // 填格子
        for (int i = 1; i <= cs.length; i++) {
            for (int j = 1; j <= cp.length; j++) {
                // 文本串和模式串末位字符能匹配上
                if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (cp[j - 1] == '*') { // 模式串末位是*
                    // 模式串*的前一个字符能够跟文本串的末位匹配上
                    if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
                        dp[i][j] = dp[i][j - 2]      // *匹配0次的情况
                                || dp[i - 1][j];     // *匹配1次或多次的情况
                    } else { // 模式串*的前一个字符不能够跟文本串的末位匹配
                        dp[i][j] = dp[i][j - 2];     // *只能匹配0次
                    }
                }
            }
        }
        return dp[cs.length][cp.length];
    }
}
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

2、Java中的String能有多大

（运行时期）在对象堆中的String能有4GB，原因是String长度可以达到2³²-1,假设一个字符两个字节（2B），则(2³¹-1)*2/1024/1024/1024 = 4GB
（编译时期）在常量池中的String类型为u2，这个类型最大只能2¹⁶-1，即65535=64KB左右，如果编译时字符串大于这个大小，则JVM直接报错

3、操作系统 文件系统 文件系统目录 原子性操作 锁

文件是一种外存上的相关信息的命名组合，数据只能通过文件才能写到外存，是操作系统到外存的桥梁

文件系统目录

文件有多种属性，如名称，标识符，类型，位置等等，所有的文件都保存在目录结构中，该目录结构保存在外存中。（是否类似于索引？让管理更加高效）

原子性操作（文件操作）

• 创建文件：在文件系统中找到空间并在目录中创建新条目。
• 写文件：根据名称，从目录中找到文件位置，并给一个写指针，当写操作触发时，写指针必须被更新。
• 搜索目录并找到相关的条目后，给与一个读指针，写与读指针可以是一个指针
• 文件重定位：搜索目录并找到相关条目（不需要IO）
• 删除文件：找到条目后，释放空间，然后删除条目
• 截断文件：仅删除文件的内容，保留他的属性

文件所用的锁

文件锁类似于读者-作者锁
文件锁有两种：

• 共享锁：类似读者锁，可以有多个进程同时的访问并发获取它
• 独占锁：一次只能有一个进程获得这个锁

try{
	RandomAccessFile raf = new RandomAccessFile("file.txt","rw");
	
	FileChannel ch = raf.getChannel();
	//前50%为独占锁
	exclusiveLock = ch.lock(0,raf.length()/2,false);
	exclusiveLock.release();
	//后50%为共享锁
	sharedLock = ch.lock(raf.length()/2,raf.length(),true);
	sharedLock.release();
}
1
2
3
4
5
6
7
8
9
10
11

4、同步 信号量

为了让进程之间的协作可以更好的协调进行，就必须引入同步的概念，一个同步的重要办法，就是信号量，在信号量之前，首先引入的是信号，两个进程共享一个资源，这个资源少了或者满了，就会给另外的进程发送信号，使其等待或者唤醒，但这单单满足了信号的传递，当有多个进程需要同步时，这种方式就会出问题，所以需要信号量。信号量是一个公共变量，可以被多个进程访问，假设信号量<=0时，就说明目前有进程正在等待中，若信号量>0，则说明目前有资源，可以进行访问