环己三烯的冬眠舱

天天网抑云，偶尔读点书。

0%

发表于 更新于

概述

哈希化是一种常见的数据存储方式，可以把一堆数据存到一起，并在O(1)复杂度下检索其中的任意一项。而对于字符串来说，普通的unordered_set<string>在哈希的时候会对整个字符串进行遍历，今天做到的这道题会因此TLE。

在需要对某个字符串的子字符串进行哈希时，可以对整个字符串进行一个预处理，使后续的哈希从伪O(1)实O(n)降低为真正的O(1)。

原理

字符串哈希将整个字符串看作一个base进制的数，这个base一般会取一个足够大的质数，例如1331、13331等。为方便理解，我们先取base为10，并取字符串s = "123456"。

如果我想得到s[1:2]的哈希值（即23)，我们可以先取得s[0:2]的哈希值(记为h[2])，即123，再减去多余的100即可。那这个100怎么来的呢？只需要将s[0]的值乘以若干次方（此处为2次）的base就可以了。根据这个原理，我们就可以得到一个通用的公式：h[l:r] = h[r] - h[l-1] * p[r - l + 1]，其中h[l:r]表示字符串s下标从1开始数第l为和第r位之间的子串的哈希值，h[idx]表示字符串s前idx位的哈希值，p数组是次方数组，其内容为{1,base,base²,base³,...}。

由此，我们可以做到一次预处理，无数次O(1)哈希其子字符串，节省大量时间。

例题

LeetCode 1044. 最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

示例 1：

1
2
输入：s = "banana"
输出："ana"

示例 2：

1
2
输入：s = "abcd"
输出：""

题解

刚看到这道题的时候就傻眼了，除了暴力想不到什么可行的办法。一看评论区，"温馨提示, 今天这个打卡题出自136场周赛第四题, 当时国服只有6个人做出来，所以不会做很正常哦"，原来大家都不会做，那我就放心了呀！

不过其实知道怎么做之后，这题还是没那么难的。虽然本题暴力验证每一个长度的子字符串存不存在重复非常的蠢，但是有了字符串哈希的技巧，验证其中某一个长度的子字符串存不存在重复却可以在O(n)的时间复杂度下完成。而且出现重复的可能性是单调递减的， 即待验证的子字符串长度越长，子字符串出现重复的可能性越小。所以我们可以对答案空间进行二分搜索，免去了大量的无用功。虽然不是第一次见这种技巧了，但有时就差这么tingle一下，想不到可以这么解。

还有一个技巧就是使用unsigned long long来储存哈希值，这样超过了2^64的时候就会自动取模，省的再做大数处理。（回忆起了周赛做了一个小时大数处理没做出来的恐惧[ac01]）

代码：

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
class Solution {
private:
    vector<unsigned long long> h;
    vector<unsigned long long> p;
    unsigned long long getHash(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
public:
    string longestDupSubstring(string s) {
        int n = s.length();
        int l = 0; int r = n - 1;
        const int base = 1331;
        h.resize(n + 1);
        p.resize(n + 1);
        p[0] = 1;
        h[0] = 0;
        for (int i = 1; i < n + 1; i++) {
            h[i] = h[i - 1] * base + s[i - 1] - 'a' + 1;
            p[i] = p[i - 1] * base;
        }
        string res;
        while (l <= r) {
            int len = (l + r) >> 1;
            unordered_set<unsigned long long> set;
            bool find = false;
            for (int i = 0; i < n - len + 1; i++) {
                unsigned long long hash = getHash(i + 1, i + len);
                if (set.count(hash)) {
                    find = true;
                    if (len > res.length()) res = s.substr(i, len);
                    break;
                }
                set.insert(hash);
            }
            if (find) l = len + 1;
            else {
                if (l == r) break;
                else r = len;
            }
        }
        return res;
    }
};

有的没的

没事听点歌（不才 - 夜航星)

发表于

Tags

日期 2022年9月18日
是否独立完成 是
涉及算法 广度优先搜索、哈希表

题面

LeetCode 827. 最大人工岛

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例 1：

1
2
3
输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2：

1
2
3
输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例 3：

1
2
3
输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

题解

广度优先搜索+哈希表

可以用广度优先搜索把每个岛都标记成对应的下标（为了方便后续统计总面积，将下标定为由-1开始增长的负整数），每搜索完一个岛就把其对应的面积存在哈希表里。然后第开始第二次遍历，遇到0就计算其周围四格的岛的面积，并实时更新最大值。

代码：

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
48
class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        unordered_map<int, int> area;
        int idx = -1;
        vector<int> dir{ -1,0,1,0,-1 };
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 1) continue;
                queue<pair<int, int>> q;
                q.push({ i,j });
                int cnt = 0;
                while (!q.empty()) {
                    pair<int, int> cur = q.front();
                    q.pop();
                    int r = cur.first, c = cur.second;
                    if (grid[r][c] < 0) continue;
                    grid[r][c] = idx;
                    for (int d = 0; d < 4; d++) {
                        int nr = r + dir[d], nc = c + dir[d + 1];
                        if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] <= 0) continue;
                        q.push({ nr,nc });
                    }
                    cnt++;
                }
                area[idx] = cnt;
                idx--;
            }
        }
        int res = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) continue;
                unordered_set<int> visited;
                for (int d = 0; d < 4; d++) {
                    int ni = i + dir[d], nj = j + dir[d + 1];
                    if (ni < 0 || ni >= n || nj < 0 || nj >= n || grid[ni][nj] >= 0 || visited.count(grid[ni][nj])) continue;
                    visited.insert(grid[ni][nj]);
                    grid[i][j] += area[grid[ni][nj]];
                }
                res = max(res, grid[i][j]);
            }
        }
        if (res == -1) return area[-1];
        else return res + 1;
    }
};

发表于

Tags

日期 2022年9月17日
是否独立完成 否
涉及算法 动态规划 Again & Again

题面

LeetCode 940. 不同的子序列 II

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

  • 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

示例 1：

1
2
3
输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

1
2
3
输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

1
2
3
输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

题解

动态规划

如果s中的字符是无重复的就很简单了，针对每个字符“取”或者“不取”都有两种可能，定义dp[i]为s前i个字母的不同非空子序列的个数，就可以引出转移公式dp[i+1]=dp[i]*2。

但是s中的字符是有重复的，所以要考虑去重的事。例如s="abb"，其中的a和两个b均能分别组成一次’ab’，所以要去掉一次，即dp[i+1]=dp[i]*2-dp[last]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int distinctSubseqII(string s) {
        int mod = 1e9+7;
        int n = s.length();
        vector<int> dp(n+1);
        unordered_map<char,int> map;
        dp[0]=1;
        for(int i=0;i<n;i++){
            dp[i+1]=dp[i]*2 % mod;
            if(map.count(s[i])) dp[i+1]-=dp[map[s[i]]];
            dp[i+1]%=mod;
            map[s[i]]=i;
        }
        return (dp[n]-1+mod) % mod;
    }
};

发表于 更新于

Tags

日期 2022年9月15日
是否独立完成 否（差一点点！）
涉及算法 动态规划Again

题面

LeetCode 1771. 由子序列构造的最长回文串的长度

给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：

  • 从 word1 中选出某个 非空 子序列 subsequence1 。
  • 从 word2 中选出某个 非空 子序列 subsequence2 。
  • 连接两个子序列 subsequence1 + subsequence2 ，得到字符串。

返回可按上述方法构造的最长 回文串 的 长度 。如果无法构造回文串，返回 0 。

字符串 s 的一个 子序列 是通过从 s 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。

回文串 是正着读和反着读结果一致的字符串。

示例 1：

1
2
3
输入：word1 = "cacb", word2 = "cbba"
输出：5
解释：从 word1 中选出 "ab" ，从 word2 中选出 "cba" ，得到回文串 "abcba" 。

示例 2：

1
2
3
输入：word1 = "ab", word2 = "ab"
输出：3
解释：从 word1 中选出 "ab" ，从 word2 中选出 "a" ，得到回文串 "aba" 。

示例 3：

1
2
3
输入：word1 = "aa", word2 = "bb"
输出：0
解释：无法按题面所述方法构造回文串，所以返回 0 。

题解

动态规划

怎么Hard题这么多动态规划啊。而且与回文串有关的题题号也恰好是回文的，有点巧妙。

一开始的思路是把word2给reverse一下，然后通过动态规划算word1和word2的最长公共子序列，就可以得到答案了。但是遇到了下面这个测试用例WA了。

1
2
string word1 = "afaaadacb";
string word2 = "ca";

WA后初步认为是两个串不一样长导致的，所以添加了平衡字符串长度的代码，然后发现并不是长度的原因。还是得把两个串合在一起dp，并只在两个子串都不为空时更新答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        int n1 = word1.length(), n2 = word2.length();
        int n = n1 + n2;
        string word = word1 + word2;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        int res = (word[n1 - 1] == word[n1]) ? 2 : 0;
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        for (int i = 0; i < n - 1; i++) dp[i][i + 1] = (word[i] == word[i + 1]) ? 2 : 1;
        for (int l = 2; l < n; l++) {
            for (int i = 0; i + l < n; i++) {
                int j = i + l;
                if (word[i] == word[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                    if (i < n1 && j >= n1) res = max(res, dp[i][j]);
                }
                else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
            }
        }
        return res;
    }
};

有的没的

没事听点歌（Knock 2 - dashstar*）

发表于

Tags

日期 2022年9月14日
是否独立完成 否
涉及算法 暴力枚举、几何

题面

LeetCode 149. 直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

1
2
输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

1
2
输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

题解

暴力枚举

对于点a,b,c，如果其中任意两点构成的直线斜率相同，则三点共线。我们可以枚举所有的点对，用哈希表记录斜率，则可以判断有多少个点出现在同一条直线上。

本题难点在于计算斜率需要用到除法，而浮点数的除法是存在误差的。为了避免这个误差，一共有两种思路：

  1. 利用乘法来避免除法（把两个斜率相等的表达式用对角相乘法则化为两个乘法表达式相等）。
  2. 用字符串来哈希。

本题我选择用第二个思路解。在计算斜率时通过最大公约数把分式约分为最间，保证相同斜率的直线能全部哈希在一起。

代码：

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
class Solution {
private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
public:
    int maxPoints(vector<vector<int>>& points) {
        int res = 0;
        for (int i = 0; i < points.size(); i++) {
            unordered_map<string, int> map;
            int mx = 0;
            for (int j = i + 1; j < points.size(); j++) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                int a = x1 - x2;
                int b = y1 - y2;
                int g = gcd(a, b);
                string key = to_string(a / g) + "_" + to_string(b / g);
                map[key]++;
                mx = max(mx, map[key]);
            }
            res = max(res, mx + 1);
        }
        return res;
    }
};

发表于 更新于

Tags

日期 2022年9月13日
是否独立完成 否
涉及算法 滑动窗口（或前缀和）、动态规划

题面

LeetCode 689. 三个无重叠子数组的最大和

给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组，并返回这三个子数组。

以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。

示例 1：

1
2
3
4
输入：nums = [1,2,1,2,6,7,5,1], k = 2
输出：[0,3,5]
解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。

示例 2：

1
2
输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
输出：[0,2,4]

题解

滑动窗口 + 动态规划

看到多个子数组求和第一反应就是前缀和，后来看题解发现滑动窗口也可以，而且更省内存一点。

求完所有长度为k的子数组和后，可以维护一个left和一个right数组，其中left 存从左开始到当前位置最大的和，right存从右开始到当前位置最大的和。我们枚举处于中间位置的数组，再通过left和right快速检索与这个位置不冲突的左侧最大子数组和以及右侧最大子数组和，在枚举过程中不断更新结果就可以了。

代码：

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
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        vector<int> sum;
        int cur = 0;
        for (int i = 0; i < k; i++) cur += nums[i];
        sum.push_back(cur);
        int n = nums.size();
        for (int i = k; i < n; i++) {
            cur = cur + nums[i] - nums[i - k];
            sum.push_back(cur);
        }
        n = sum.size();
        vector<int> left(n, 0);
        vector<int> right(n, n - 1);
        for (int i = 1; i < n; i++) {
            if (sum[i] > sum[left[i - 1]]) left[i] = i;
            else left[i] = left[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            if (sum[i] >= sum[right[i + 1]]) right[i] = i;
            else right[i] = right[i + 1];
        }
        int mx = 0;
        vector<int> res(3, 0);
        for (int i = k; i < n - k; i++) {
            if (mx < sum[i] + sum[left[i - k]] + sum[right[i + k]]) {
                mx = sum[i] + sum[left[i - k]] + sum[right[i + k]];
                res = { left[i - k],i,right[i + k] };
            }
        }
        return res;
    }
};

有的没的

没事听点歌（One Republic - Counting Stars）

发表于

Tags

日期 2022年9月12日
是否独立完成 是
涉及算法 动态规划

题面

LeetCode 174. 地下城游戏

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K) -3 3
-5 -10 1
10 30 -5 (P)

说明：

  • 骑士的健康点数没有上限。
  • 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

题解

动态规划

随机刷居然能刷到做过的题，我还想这题还能是Hard…

动态规划经典题，从右下角向左上角dp，每个单元格表示在能救到公主的前提下进入该单元格前所需的最低生命值。最后dp[0][0] - dungeon[0][0]就是最终答案（当然，小于等于0当1处理）。

代码：

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
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[m - 1][n - 1] = 1;
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = dp[i + 1][n - 1] - dungeon[i + 1][n - 1];
            if (dp[i][n - 1] <= 0) dp[i][n - 1] = 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            dp[m - 1][i] = dp[m - 1][i + 1] - dungeon[m - 1][i + 1];
            if (dp[m - 1][i] <= 0) dp[m - 1][i] = 1;
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int a = dp[i][j + 1] - dungeon[i][j + 1];
                int b = dp[i + 1][j] - dungeon[i + 1][j];
                dp[i][j] = min(a, b);
                if (dp[i][j] <= 0) dp[i][j] = 1;
            }
        }
        int res = dp[0][0] - dungeon[0][0];
        return  res <= 0 ? 1 : res;
    }
};

有的没的

关于每日Hard

题已经刷了不少了，接下来打算加大刷题的难度。其实暑假期间就计划要每日一题Hard来着，后来没坚持几天就摸了。于是决定每次做完题来Blog打个卡，算是督促自己坚持刷题吧。也不是真的要每天做一题Hard，只能说在时间允许的前提下努力坚持吧。

发表于 更新于

概述

听名字就能大概猜出“有限状态自动机”是干嘛的了。

  • 有一个当前状态 pre

  • 每轮循环输入一个 cur

  • 有限状态自动机可以根据事先的定义来进行状态的转移

有限状态自动机并不能降低算法的复杂度，但是可以让代码看起来非常简洁清爽，也不会写着写着就晕掉了。

例题

剑指 Offer 20. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

  1. 若干空格

  2. 一个 小数 或者 整数

  3. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

  4. 若干空格

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）

  2. 下述格式之一：

    1. 至少一位数字，后面跟着一个点 '.'

    2. 至少一位数字，后面跟着一个点 '.'，后面再跟着至少一位数字

    3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（’+’ 或 ‘-‘）

  2. 至少一位数字

部分数值列举如下：

  • ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：

  • ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

示例 1：

1
2
输入：s = "0"
输出：true

示例 2：

1
2
输入：s = "e"
输出：false

示例 3：

1
2
输入：s = "."
输出：false

示例 4：

1
2
输入：s = "    .1  "
输出：true

题解

先贴一段我第一次写时的代码，用的是暴力模拟，写半天自己都写晕了，到后面变量名字都开始乱七八糟了，因为不能一次性考虑到所有细节， 所以根据WA给的测试用例缝缝补补勉强通过。

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
class Solution {
private:
    stringstream ss;
public:
    bool isNumber(string s) {
        ss << s;
        ss >> ws;
        if(ss.peek()=='+' || ss.peek()=='-') ss.get();
        bool hasnum=false;
        while(isdigit(ss.peek())){
            ss.get();
            hasnum=true;
        }
        if(ss.peek()=='.') {
            ss.get();
            bool hasnum2=false;
            while(isdigit(ss.peek())){
                ss.get();
                hasnum2=true;
            }
            if(!hasnum2 && !hasnum) return false;
        }
        else if(!hasnum) return false;

        if(ss.peek()=='e' || ss.peek()=='E'){
            ss.get();
            bool hasnum1=false;
            if(ss.peek()=='+' || ss.peek()=='-') ss.get();
            while(isdigit(ss.peek())){
                ss.get();
                hasnum1=true;
            }
            if(!hasnum1) return false;
        }
        ss >> ws;
        return ss.peek()==-1;
        
    }
};

而使用有限状态自动机就可以让代码非常清晰。我们可以定义如下的状态：

图源：LeetCode @Krahets 前辈的题解

在代码中，我们使用数组+字典来储存上图。只有退出后的状态为 2/3/7/8 中的一个时，我们才认为输入的字符串为合法的数值。

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
class Solution {
public:
    bool isNumber(string s) {
        stringstream ss;
        ss << s;
        vector<unordered_map<char, int>> states = {
            { {' ', 0},{ 's', 1},{ 'd', 2}, {'.', 4} },
            { {'d', 2},{ '.', 4} } ,
            { {'d', 2},{ '.', 3}, {'e', 5}, {' ', 8} },
            { {'d', 3}, {'e', 5}, {' ', 8} },
            { {'d', 3} },
            { {'s', 6}, {'d', 7} },
            { {'d', 7} },
            { {'d', 7}, {' ', 8} },
            { {' ', 8} }
        };
        int pre = 0;
        while (ss.peek() != -1) {
            char c = ss.get();
            char cur;
            if ('0' <= c && c <= '9') cur = 'd';
            else if (c == '+' || c == '-') cur = 's';
            else if (c == 'e' || c == 'E') cur = 'e';
            else if (c == '.' || c == ' ') cur = c;
            else cur = '?';
            if (states[pre].count(cur) <= 0) return false;
            pre = states[pre][cur];
        }
        return pre == 2 || pre == 3 || pre == 7 || pre == 8;
    }
};

有的没的

天才操作

13号回的学校。回校前精心挑选了一班快十几分钟的车次，然后当天到了宁波站了才发现终点站是杭州南，不是杭州东，少坐一站可不是快一点嘛。后来找乘务姐姐补了一站路。

新生要来报到了

明天新生就陆续要来报到了，我也该读大三了。没有人永远年轻，但永远有人年轻。

没事听点歌（Neck Deep - Serpent）

发表于 更新于

概述

今天LeetCode的每日一题是设计一个跳表。跳表是一种类似链表的数据结构，可以实现时间复杂度为 O(log n) 的查找和插入，效率堪比红黑树。

常规的链表可以实现常数级时间复杂度的插入，但是查找某一个特定元素的元素却是线性的。而诸如数组和vector之类的简单线性的数据结构，虽然可以通过二分查找来实现 O(log n) 时间复杂度的查找，但是在某个特定位置插入一个元素需要把其后面所有元素都挪动一遍，牵一发而动全身。而AVL树、红黑树可以平衡插入和查找的效率，被广泛应用。今天刚学到的跳表也有相似的性质。

插一个小故事。就前两天我在看《STL源码剖析》试图理解红黑树的时候还看到一段话，说普通的链表查找某一个特定元素是线性的，我就想这个作者也太菜了，你不能二分查找吗？后来仔细一想，才想起来原来链表是没法随机访问的，自然不能二分查找，是我太菜了。

后来还是看不懂红黑树是什么原理。但是跳表就好理解多了。在LeetCode评论区里看到一条，“想了半天要如何确定一个值应该占用几层的链表，然后你给我来个coin filp，我遭不住了，底层逻辑基于随机数，怪不得STL里没你”，笑死我了。

扯了这么多，那么跳表到底是什么原理呢？用LeetCode上的一张图就可以看懂了。

查找

查找时从上往下依次找到每层小于目标值的最大的节点，然后依次往下查找，中间可以跳过很多个节点。因为可以有可以跳过节点这个性质，跳表查找的平均时间复杂度是O(log n) ，这个有大佬证明了，而我不是大佬所以我不会证明。

插入

插入时也依次从上往下找插入的节点，第0层包含跳表内的所有元素，然后每个元素在插入时有p的概率可以加入到上面那层，p 一般被设置为 1/2 。没错，跳表的结构是随机出来的，就是这么草率。

例题

LeetCode 1206. 设计跳表

就是设计一个上述跳表，要求实现查找、插入和删除三个功能。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[null, null, null, null, false, null, true, false, true, false]

解释
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除

题解

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Skiplist {
private:
    class Node {
    //链表的节点类，把插入和删除的操作都集成进来了
    public:
        int val;
        vector<Node* > next = vector<Node* >(10, nullptr);//为了偷懒这里直接把十层链表的头尾节点都预留好了，内存击败百分五[ac01]
        Node(int v) :val(v) {};//构造函数
        void insert(Node* nxt, int level) {
            //在当前节点后面插入节点nxt，level代表目前操作的层数
            vector<Node* >& cur = this->next;
            nxt->next[level] = cur[level];
            cur[level] = nxt;
            return;
        }
        void erasenext(Node* nxt) {
            //在整个跳表中移除节点nxt
            vector<Node* >& cur = this->next;
            for (int i = 0; i < 10; i++) {
                if (cur[i] == nxt) {
                    cur[i] = cur[i]->next[i];
                }
            }
        }
    };
    //head和tail为头尾节点
    Node* head;
    Node* tail;
public:
    Skiplist() {
        //Skiplist类的构造函数，将head和tail进行初始化
        head = new Node(-1);
        tail = new Node(1e9 + 7);
        for (int i = 0; i < 10; i++) {
            //初始状态head的十个指针均应指向tail
            head->next[i] = tail;
        }
    }

    bool search(int target) {
        Node* cur = head;
        //从上往下依次找到每层比target小的最大节点
        for (int i = 9; i >= 0; i--) {
            while (cur->next[i]->val < target) cur = cur->next[i];
        }
        //如果最后一层的下一个节点的值不是target的话，那target一定不在跳表里。
        return cur->next[0]->val == target;
    }

    void add(int num) {
        /*前半部分和search过程一样
        只是需要多用一个stack把路上遇到的节点都存起来 */
        stack<Node* > stk;
        Node* cur = head;
        for (int i = 9; i >= 0; i--) {
            while (cur->next[i]->val < num) cur = cur->next[i];
            stk.push(cur);
        }
        int level = 0;
        Node* newnode = new Node(num);//创建新节点
        cur->insert(newnode, level);//第0层含有跳表全部元素，所以必须加入
        while (level < 9 && rand() % 2 == 0) {
            //进行一次判定，有1/2的几率可以进入上一层
            level++;
            stk.pop();
            stk.top()->insert(newnode, level);
        }
    }

    bool erase(int num) {
        //前半部分和add一样需要把路过的节点存起来
        stack<Node* > stk;
        Node* cur = head;
        for (int i = 9; i >= 0; i--) {
            while (cur->next[i]->val < num) cur = cur->next[i];
            stk.push(cur);
        }
        if (cur->next[0]->val != num) return false;//如果跳表里没有num就直接返回false
        else {
            /*否则调用erase函数删除后面一个节点
            此处传入的是节点的指针，保证不会误伤别的具有相同值的节点 */
            cur->erasenext(cur->next[0]);
            return true;
        }
    }
};

有的没的

暑假生活

暑假在家真的宅烂了，今天跟两个初中同学去南虹吃了一整天。吃了臭豆腐、老长沙手工肠、颜记排骨、虾滑、两杯茶百道、KFC、炸串串，饱死了。

没事听点歌（胡歌 - 忘记时间）