讨论/求职面试/「春招学习计划」 周常总结 Week 2/
「春招学习计划」 周常总结 Week 2

简介

大家好,我负责「春招学习计划」第二周 (2021.01.25 - 2021.01.31) 的 Leetor,由于学习板块问题较少,本总结会对本周「每日阅读计划」知识点进行汇总,但更侧重于对每日一题问题的整理。如果有问题可以指出来,我会及时修改。

每日阅读计划:数组和字符串

字符串是由 0 个或多个字符或符号的顺序排列所组成的复合数据结构,简称「串」(string)。字符串长度是指一个字符串所包含的字符个数,空串特指长度为零的串。字符串也是具有线性特征的一种数据结构。在实际应用中,字符串是最基本的语言信息储存方式,并且其相关操作比较直观。

「七章刷完数据结构——字符串」

在不同编程语言中,字符串可变性不同。例如 C++ 中可以直接修改字符串某个元素的值,字符串行为类似数组, 而 Python 字符串是不可变对象。下面梳理一下字符串相关的算法和应用。

高精度运算

当参与运算的数据大小超过编程语言内建整型时,可利用字符串表示大整数,进而实现高精度计算。其思路一般是通过字符串或数组模拟竖式运算。例如计算 12345+33612345 + 336 用过下列字符串数组模拟运算:

idx  4  3  2  1  0
    [1, 2, 3, 4, 5]
+   [0, 0, 3, 3, 6]
------------------
    [1, 2, 6, 8, 1]

关于高精度运算更详细的解释,可参考 oi-wiki:高精度计算,尤其注意高精度乘法和除法。

高精度题目汇总:

字符串匹配:KMP

字符串匹配即给定一个主串和模式串,判断模式串是否在主串中出现,以及出现的位置。

假设主串长度为 mm,模式串长度为 nn

KMP 算法将时间复杂度优化到 O(m+n)O(m + n)。举个例子:考虑主串 abcabcabd 和模式串 abcabd 。从第一个字符开始匹配,模式串可以匹配到主串的 abcab ,此时主串的 c 和模式串最后一位 d 失配。暴力的做法是退回到主串的第二个字符,模式串指针回退到其第一个字符,重新开始匹配模式串(时间复杂度 O(mn)O(mn) )。但已知 abcab 存在最长公共前后缀 ab ,那么可以在主串指针不回退情况下,只回退模式串指针,且尽可能回退得少,那么就是回退到公共前缀的下一位。如下图,字符串下标从 00 开始,在主串下标 55 处发生失配,模式串从下标 55 回退到下标 22 ,继续在主串下标5处判断是否匹配。

      0 1 2 3 4 5 6 7 8
main: a b c a b c a b d
      0 1 2 3 4 5
pat : a b c a b d 
            0 1 2 3 4 5
pat :       a b c a b d      

next数组用来记录发生失配时模式串回退的位置。更具体的介绍可以参考如下链接:

字典树/前缀树/Trie

前缀树的结构比较好想象,就是用树存储一个字符串合集的前缀。从根节点到叶子节点走过的路径表示一个字符串合集中的单词前缀。对于每个单词,查询的时间复杂度是 O(m)O(m),其中 mm 是单词的长度。下图是一棵字典树,注意每个子节点还需要维护当前节点是否为单词的结尾。

IMG_D0CE00E3D5FC-1.jpeg

字典树比较好上手,下面是一些相关题目:

每日一题问题汇总

本周每日一题仍然并查集为主,问题主要分成三类:编程语言相关问题、算法相关问题和对并查集模板不熟悉导致的问题。结尾我会放置并查集模板,并针对模版问的比较多的地方做详细注释。另外十分推荐先看一下上周课代表的总结「春招学习计划」周常总结 Week 1 结尾并查集部分。

编程语言相关问题

LeetCode 959. 由斜杠划分区域 所以 '\\' 当一个字符来处理就可以了吗?

当成一个字符处理即可,详见 C++ 转义序列

LeetCode 1579. 保证图可完全遍历
为什么这里用 auto edge 就会报错溢出,加上 & 就没问题呢。

for(auto& edge: edges){
            --edge[1];
            --edge[2];
 }

& 在 C++ 是引用操作,修改的是 edgesedges 本身的每一项,去掉后并没有改变 edgesedges 的任何内容。最小用例如下

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    vector<int> nums{0, 1, 2, 3};
    for(int n: nums) --n;
    for(int n: nums) cout << n << ' '; cout << endl;
    for(int &n: nums) --n;
    for(int n: nums) cout << n << ' '; cout << endl;
    return 0;
}

代码输出为

0 1 2 3 
-1 0 1 2 

LeetCode 1579. 保证图可完全遍历 想请问下分析公共边和独占边的时候,为啥用我注释里的代码在数据量大的时候就会超时呢?在我的认知中,在公共边中 eraseerase 以后,留到独占边里遍历的内容就变少了应该更快才对。然而实际上却慢了许多。这是为什么呢?

在使用内置函数的时候,一定要注意函数的时间复杂度。主要问题在这里,对于 erase() 操作,该操作时间复杂度是 O(n)O(n)参考网站说明如下

Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).

对于此问题,edge 数量在 10510^5erase 加上外层循环,总复杂度为 O(n2)O(n^2) ,会超时。

for(int i=0;i<edges.size();){ // 循环 n 次
        auto edge=edges[i];
        if(edge[0]==3)
        {
            if(ufsA.Union(edge[1],edge[2]))//not connected
                ufsB.Union(edge[1],edge[2]);
            else
                ans++;
            edges.erase(edges.begin()+i); // 复杂度 O(n),总复杂度 O(n2)
        }
        else
            i++;
}

LeetCode 1631. 最小体力消耗路径

并查集解法 edges 里用数组超时?求大佬解答这是为什么啊啊啊?还是说其他地方错了。

C++ 语言的问题,自定义比较函数对于 vector 一定要传引用,否则会多一步生成实例的操作。

sort(edges.begin(), edges.end(), [&](vector<int> a, vector<int> b){
        return a[2] < b[2];
    });

修改为:

sort(edges.begin(), edges.end(), [](const vector<int> &a, const vector<int> &b){
    return a[2] < b[2];
});

LeetCode 最小体力消耗路径

有没有大佬解释一下这段?

sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2) {
            auto&& [x1, y1, v1] = e1;
            auto&& [x2, y2, v2] = e2;
            return v1 < v2;
        });

这两个 auto&& 的用法不是很明白?

参考 C++17 结构化绑定,如下

int a = 1;
const auto& [x] = std::make_tuple(a); // OK, not dangling
auto&       [y] = std::make_tuple(a); // error, cannot bind auto& to rvalue std::tuple
auto&&      [z] = std::make_tuple(a); // also OK

算法相关问题

LeetCode 0959. 由斜杠划分区域 一个格子最多被分成两个区域,所以 n×n×2n\times n\times 2 就可以了。

来自@Johnny 的评论,真的让我学到了。原题解将一个格子分成 44 个三角区域并编号,该同学在基础上做了空间和时间上的常数优化,其具体操作是根据网格中的字符,将网格动态划分为左右两部分,再合并时根据网格中的字符判断合并哪一部分,这样的好处是并查集申请数组更小,同时合并操作更少,但复杂度和官解保持一致。如下图:

IMG_2EA4B4FD3AD0-1.jpeg

代码如下,从官方代码修改而来:

class Solution {
public:
    int find(vector<int>& f, int x) {
        if (f[x] == x) {
            return x;
        }
        int fa = find(f, f[x]);
        f[x] = fa;
        return fa;
    }

    void merge(vector<int>& f, int x, int y) {
        int fx = find(f, x);
        int fy = find(f, y);
        f[fx] = fy;
    }

    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        vector<int> f(n * n * 2);
        for (int i = 0; i < n * n * 2; i++) {
            f[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int idx = 2 * (i * n + j);
                if (j < n - 1) {
                    merge(f, idx + 1, idx + 2);
                }
                if (grid[i][j] == ' '){
                    merge(f, idx, idx + 1);
                }
                if (i < n - 1){
                    int now = grid[i][j] == '/'? idx + 1: idx;
                    int nxt = grid[i + 1][j] == '/'? idx + 2 * n: idx + 2 * n + 1;
                    merge(f, now, nxt);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n * n * 2; i++) {
            if (i == find(f, i)) ++ans;
        }
        return ans;
    }
};

LeetCode 1128. 等价多米诺骨牌对的数量

ret += num[val];
num[val]++;

这 2 行代码没明白

num[val] 表示当前多米诺牌 val 的数量。ret 表示的是当前可以组成骨牌对的个数。

假设多米诺牌 val 数量为 nn 。那么组成的骨牌对可以通过组合数表达为:

Cn2=n(n1)2=0+1+2++(n1)C_{n}^{2} = \frac{n(n - 1)}{2} = 0 + 1 + 2 + \cdots+(n - 1)

在循环中计算就是后面的等差数列展开式,即 ret 先加上当前的骨牌计数,然后在更新计数数组,即 ret +=num[val]; num[val]++

也可以理解为新加入的骨牌可以与之前的骨牌组成多少个骨牌对,显然是 num[val] 个。

LeetCode 1579. 保证图可完全遍历

  • 求解为什么不能使用一次遍历呢,一次遍历里类型 33 双方合并,1212 各自合并,其他的与题解不变,唯一不一样的就是遇到类型 33 时候,只要双方谁合并过,弃用边就 +1+1,都合并过就 +2+ 2,表示弃用之前的,但是这个思路测试并不能通过
  • 为什么我按 edges[i][0] 降序排序再分别合并,答案就不对呢,不也是优先合并公共边吗?求解答

一次遍历需要对边按照类型排序,以保证公共边优先遍历。但是这种情况下时间复杂度比官方题解高,时间主要耗费在排序算法上,为 O(mlogm)O(m\log m) 。这里「一次遍历」是负优化,代码可以见评论链接提供一个 cpp 排序 + 合并的思路

LeetCode 1631. 最小体力消耗路径

  • 我这个解法算 DP 么?
  • 这题能用DP做么?

评论链接作者写出了 SPFA 算法,该算法时间复杂度没有保证。

动态规划我认为不太可以,例如定义 dp[i][j] 为从 (0, 0) 到达 (i, j) 的最小路径,这道题没有限制移动的方向,可能列出的状态转移方程为

dp(i,j)=min(x,y)S(i,j)(max(h(x,y)h(i,j),dp(x,y))dp(i,j)=\min_{(x,y)\in S(i,j)}\left(\max(|h(x,y)−h(i,j)|,dp(x,y)\right)

其中S(i,j)S(i,j)表示坐标i,ji,j 的四邻域。该方程说明当前位置最小值与其周围 4 个位置的最小值相关,不满足动态规划的无后效性。(有同学通过这个方程写出了SPFA/bellman ford)

另外一个思路是定义 dp[i][j][k] 表示在绝对值限制为 k 时能否到达 i, j,此时是暴力枚举,显然不是最优。

此外最短路算法指路 oi-wiki: 最短路其实我也只是熟悉 Dijkstra

并查集模板相关的问题

经常有一些提问如下:

  • 问一下我的代码总是在第 6060 个测试用例遇到测试和提交结果不一样的问题,怎么解决?

  • self.size [x] += self.size [y] 没看懂

  • return parent[x] == x ? x : (parent[x] = findset(parent[x]));
    return parent[x] == x ? x : findset(parent[x]);
    

    有大佬知道这两句代码的区别吗 我试了一下第一句代码运行时间更短

  • 官方的 java 代码中的 connected 方法有用到吗,是不是多余了

  • 有个问题 并查集里的 size 数组和 setCount 是干嘛用的

  • ...

当使用并查集的时候,要理解各个变量的具体含义。

比如要明确应该初始化有多少个元素的 parent 数组,并保证操作过过程中节点应该能通过坐标映射到唯一的并查集parent数组下标。例如节点编号范围为 [1,n][1, n] ,映射函数为 f(idx)=idxf(idx) = idx 那并查集应初始化数组大小为 n+1n + 1,初始化联通块数量为 nn。又如本周常见的 2D2D 数组问题,假设其长宽为 row,colrow, col,那么一个成立的下标映射函数为

f(i,j)=icol+jf(i, j) = i * col + j

有的题解评论下给的代码坐标映射函数有问题,将网格中的两个不同节点映射到并查集 parent 数组相同下标,导致代码不能通过。

另外并查集 setCount 这个变量表示联通分量的数量。初始化为所有节点的数量,每执行一次合并减少1就可以。还可以通过统计并查集中根节点的数量确定联通分量数量,根节点满足 parent[x] == x

下面官解模板,加上了解释。

// 并查集模板
class UnionFind {
public:
    vector<int> parent;
    vector<int> size; // 用于按秩合并合并
    int n;
    int setCount;  // 当前连通分量数目
    
public:
    UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int findset(int x) {
        return parent[x] == x ? x : parent[x] = findset(parent[x]); // 路径压缩
    }
    
    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) { // 根节点 size 表示其联通区域内元素个数,用于按秩合并
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount; // setCount 表示联通分量数目,发生每次合并操作数目减1
        return true;
    }
    
    bool connected(int x, int y) { // 用于判断两个节点是否联通
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

关于按秩合并、路径压缩等更详细的解释,可以参考「春招学习计划」周常总结 Week 1

后记

看评论区明显感觉大家提高飞快,经过周内最小体力消耗路径那题的洗礼,周末的两道 Hard 级别的并查集很多同学都能够自信地说: 就这?

我编程语言十分单一,在评论区出现过 Swift 等代码无法通过的问题,建议确定自己复杂度没问题的情况下 提交工单 或者在讨论区问一下大佬来解决。

33
共 9 个回复

学长好厉害!

3

学长好厉害

2

学长好厉害!

2

学长好厉害!

2

学长好厉害

1

给浩哥打call

1

学长好厉害!

1

学长好厉害!

1

学长好厉害!

1