zkkKillua's Blog
0%

发表于 分类于

项目地址

可以给已有的markdown文章批量添加hexo头部信息，且遵从hexo scaffolds的模板格式。

使用方法

  1. 在hexo博客的根目录下创建一个空的文件夹（推荐使用英文名称）。
  2. 将”hexoer.py”移动到新创建的文件夹中。
  3. 复制所有待修改的markdown文件到新创建的文件夹中。
  4. python hexoer.py 并等待完成。

发表于 分类于 ，

一. 隔离级别简介

数据库的隔离级别主要有四种：

  1. 读未提交（Read Uncommitted）：最低的隔离级别，允许读取尚未提交的数据变更，可能导致脏读、幻读或不可重复读。
  2. 读已提交（Read Committed）：大多数数据库系统的默认隔离级别（如Oracle, PostgreSQL）。保证了一个事务在读取数据时，那些已经被其他完成的事务修改的数据，可以被当前事务读取。防止了脏读，但幻读和不可重复读仍可能出现。
  3. 可重复读（Repeatable Read）：在同一事务内的查询都能够看到一致的快照数据。在MySQL InnoDB引擎中，可重复读是默认的隔离级别。它解决了脏读和不可重复读，但幻读仍可能出现。
  4. 串行化（Serializable）：最高的隔离级别，它通过强制事务串行执行，避免了前三个隔离级别中可能出现的问题。但这种级别会导致性能下降，因为事务完全是一个接一个地执行，没有并行性。

以上四种隔离级别，隔离级别越高，数据一致性越好，但并发性能越差。因此在实际应用中，需要根据业务需求和系统负载情况，选择合适的隔离级别。

二. InnoDB各隔离级别的解决方案

阅读全文 »

发表于 分类于

1. dp

设dp[i][j]代表s的前i个字符和t的前j个字符满足题目的匹配要求的个数，则
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]，当s[i-1] == t[j-1]时；
dp[i][j] = dp[i-1][j]，当s[i-1] != t[j-1]时。
原因是要满足题目要求，t的字符必须全部匹配，故t[0~j-1]必选。
对于s[i-1]，如果可匹配则可选可不选；如果不匹配，则不选。
初始化dp[i][0] = 1, dp[0][j>0] = 0.
时间O(mn)，空间O(mn)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numDistinct(string s, string t) {
        int ns = s.length(), nt = t.length();
        if (ns < nt)
            return 0;
        
        vector<vector<long long>> dp(ns + 1, vector<long long>(nt + 1, 0));
        for (int i = 0; i <= ns; i++)
            dp[i][0] = 1;
        
        for (int i = 1; i <= ns; i++) {
            for (int j = 1; j <= i && j <= nt; j++) {     // j可以超过i就停止，因为s短则比不可能匹配t
                if (s[i - 1] == t[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                dp[i][j] += dp[i - 1][j];
            }
        }

        return dp[ns][nt];
    }
};

2. 优化空间

方法1中更新dp[i][j]只用到了dp[i-1][j-1]和dp[i-1][j]，因此可以在空间上进行优化。
空间上只保留一行，同时j逆序更新。
时间O(mn)，空间O(n)。

阅读全文 »

发表于 分类于

1. 辅助栈

使用一个辅助栈记录当前期待访问的是栈中元素的左子节点还是右子节点。
如果栈顶记录的是左子节点，则修改为期待访问右子节点。
如果栈顶记录的是右子节点，代表当前访问的节点是其右子节点，弹出栈顶。
如果访问的是数字，将其入栈，之后访问的是它的子树。
如果访问的是#，不入栈，因为其对应的栈顶节点的左子树或者右子树为空。
时间O(n)，空间O(n)。 

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 {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.length();
        if (n == 0 || (n > 1 && preorder[0] == '#'))
            return false;
        else if (n == 1 && preorder[0] == '#')
            return true;

        stack<bool> isLeft;
        int idx = 0;
        while (idx < n && preorder[idx] >= '0' && preorder[idx] <= '9')
            idx++;
        isLeft.push(true);
        
        while (!isLeft.empty() && idx < n) {
            if (preorder[idx] == ',') {
                idx++;
                continue;
            } else if (preorder[idx] == '#') {
                if (isLeft.top() == true)
                    isLeft.top() = false;   // stack.top() returns a "reference"
                else 
                    isLeft.pop();
                idx++;
            } else {
                while (idx < n && preorder[idx] >= '0' && preorder[idx] <= '9')
                    idx++;
                if (isLeft.top() == true) 
                    isLeft.top() = false;
                else 
                    isLeft.pop();
                isLeft.push(true);
            }
        }
        
        return isLeft.empty() && idx == n;
    }
};

2. 优化空间到O(1)

方法1中使用的栈记录了当前期待的是每个节点的左子树还是右子树，使得我们可以直接构建出这棵树。
但实际上并不需要这么详细的信息，因为每个节点都是首先期待左子树，之后期待右子树，然后出栈。
所以我们可以只用一个变量记录栈中节点期待的子树的总数目，当遇到下一个节点时，期待–。减小的期待可能是栈顶节点的左子树也可能是其右子树，但我们并不关心。
所以将方法1中的栈改为一个整型变量expect，模拟一个虚拟栈即可。
时间O(n)，空间O(1)。

阅读全文 »

发表于 分类于

1. 辅助栈

一个栈存操作数，一个栈存操作符。
为了避免-1+2和1+(-2+3)等情况，还要判断操作符的上一位，看是否需要在操作数栈中添加0.
时间O(n)，空间O(n)。 

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
class Solution {
public:
    int calculate(string s) {
        int n = s.length();
        char last = ' ';
        stack<int> nums;
        stack<char> ops;

        for (int i = 0; i < n; i++) {
            if (s[i] == ' ')
                continue;
            else if (s[i] >= '0' && s[i] <= '9') {
                int num = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + (s[i++] - '0');
                }
                i--;
                nums.push(num);
                last = 'n';
            } else {
                if (s[i] != '(' && last != 'n' && last != ')')
                    nums.push(0);
                while (s[i] != '(' && !ops.empty() && ops.top() != '(') {
                    char op = ops.top();
                    ops.pop();
                    int b = nums.top();
                    nums.pop();
                    int a = nums.top();
                    nums.pop();
                    if (op == '+')
                        nums.push(a + b);
                    else if (op == '-')
                        nums.push(a - b);
                }
                if (s[i] != ')')
                    ops.push(s[i]);
                else
                    ops.pop();
                last = s[i];
            }
        }

        while (!ops.empty()) {
            char op = ops.top();
            ops.pop();
            int b = nums.top();
            nums.pop();
            int a = nums.top();
            nums.pop();
            if (op == '+')
                nums.push(a + b);
            else if (op == '-')
                nums.push(a - b);
        }

        return nums.top();
    }
};

2. 去括号

算式中只有加减法，因此可以全部看作是加法，将减法看作是负数。
还是使用辅助栈，不过栈只存正负号，代表当前括号外部是正号还是负号。
时间O(n)，空间O(n)。

阅读全文 »

发表于 分类于

1. dp

设dp[i]是以s[i]为结尾的子串的最少分割次数，则
dp[i] = min(dp[j-1]+1)，j是i左侧的位置，s[j~i]是s[0~i]最后一个回文串。
从后遍历所有的回文串，找到分割最短的。
使用预处理之后，以O(1)的时间判断s[i][j]的回文性。
时间O(n^2)，空间O(n^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
27
28
29
30
class Solution {
public:
    int minCut(string s) {
        int n = s.length();
        vector<vector<bool>> palindromic(n, vector<bool>(n));
        vector<int> dp(n, INT_MAX);

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (j - i < 2)
                    palindromic[i][j] = s[i] == s[j];
                else
                    palindromic[i][j] = palindromic[i + 1][j - 1] && s[i] == s[j];
            }
        }

        for (int i = 0; i < n; i++) {
            if (palindromic[0][i]) {
                dp[i] = 0;
                continue;
            }
            for (int j = i; j > 0; j--) {
                if (palindromic[j][i])
                    dp[i] = min(dp[i], dp[j - 1] + 1);
            }
        }

        return dp[n - 1];
    }
};

发表于 分类于

1. 回溯

类似“全排列”，对于每个子答案：

  1. 从规定的起点向后遍历所有的回文串
  2. 对于遍历到的每个回文串，添加到子答案数组中，然后起点向后移动，继续调用dfs
  3. 当返回时，弹出当前添加到子答案数组中的回文串，回到2，即添加下一个可能的答案

时间复杂度O(n * 2^n)；这里n为输入字符串的长度，每一个位置可拆分，也可不拆分，尝试所有拆分的时间复杂度为O(2^n，判断每一个子串是否是回文子串，时间复杂度为O(n)
当然也可以用O(n^2)的时间预处理计算出每一段子串s[i][j]是否回文，则之后可以以O(1)的时间获取，不过空间要增加到O(n^2)
空间复杂度：O(n)，递归调用栈的深度 

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
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> subAns;
        vector<vector<string>> ans;
        dfs(s, subAns, ans, 0);

        return ans;
    }
private:
    bool isPalindromic(string s, int start, int end) {
        bool res = true;
        while (end > start) {
            if (s[start] != s[end]) {
                res = false;
                break;
            }
            start++;
            end--;
        }

        return res;
    }

    void dfs(string s, vector<string>& subAns, vector<vector<string>>& ans, int start) {
        int n = s.length();
        if (start == 0)
            subAns.clear();
        else if (start == n) {
            ans.push_back(subAns);
            return;
        }

        for (int i = start; i < n; i++) {
            if (isPalindromic(s, start, i)) {
                subAns.push_back(s.substr(start, i - start + 1));
                dfs(s, subAns, ans, i + 1);
                subAns.pop_back();
            }
        }
    }
};

发表于 分类于

1. 位运算

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;
        for (int i = 0; i < 32; i++) {
            sum += n & 1;
            n >>= 1;
        }

        return sum;
    }
};

2. 不修改n

方法1会修改n，且由于右移如果是负数，最高位补的是1，故不能写while(n)
方法2使用一个辅助变量，不是右移n，而是左移辅助变量 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;
        uint32_t f = 1;
        while (f) {
            if (n & f)
                sum++;
            f <<= 1;
        }

        return sum;
    }
};
阅读全文 »

发表于 分类于

1. 单调栈

  • 使用单调递减栈
  • 数组中的最大值的“下一个更大元素”不存在，是-1
  • 获得所有元素的“下一个最大元素”最多需要2次遍历
  • 数组最大值一共有x个，当数组的最后一个元素是最大值时结束；否则当单调栈中只有x+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
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return {};
        stack<int> st;
        vector<int> res(n, -1);

        int maxValue = nums[0], maxValueFreq = 0;
        for (int i = 1; i < n; i++)
            if (nums[i] > maxValue)
                maxValue = nums[i];
        for (int i = 0; i < n; i++)
            if (nums[i] == maxValue)
                maxValueFreq++;

        for (int i = 0; i < n; i++) {
            while (!st.empty() && nums[i] > nums[st.top()]) {
                if (res[st.top()] == -1)
                    res[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
            if (i == n - 1) {
                if (nums[i] == maxValue)
                    break;
                else
                    i = -1;
            }
            if (st.size() == maxValueFreq + 1 && nums[st.top()] == maxValue)
                break;
        }

        return res;
    }
};

发表于 分类于

1. 单调栈+hash表

使用一个单调递减栈遍历nums2，当元素比栈顶小时入栈；当比栈顶大时代表该元素是栈顶及随后一部分比该元素小的元素的“下一个更大元素”，故弹出较小的元素，将该元素作为他们的“下一个更大元素”，将该元素入栈。
这样求得的是所有元素的“下一个更大元素”，需要hash表记录一下，最后只取nums1中对应的。
时间O(m + n)，空间O(m + n)。 

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 {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        stack<int> st;
        unordered_map<int, int> nextGreater;
        vector<int> res;

        for (int i = 0; i < n2; i++) {
            while (!st.empty() && nums2[i] > st.top()) {
                nextGreater[st.top()] = nums2[i];
                st.pop();
            }
            st.push(nums2[i]);
        }
        while (!st.empty()) {
            nextGreater[st.top()] = -1;
            st.pop();
        }

        for (int i = 0; i < n1; i++)
            res.push_back(nextGreater[nums1[i]]);
        
        return res;
    }
};