leetcode contest 建信金科

题目质量还是非常高的，只做出两道的节奏，最后两道题目没有做出来，但是又从中学到了新的知识点和技能．第四题可能是我最喜欢的题目类型了，带有思考性质和数学问题，非常喜欢这种思维加数学的题型，通过算法和计算可以学习到数学的问题．

建信01. 间隔删除链表结点

给你一个链表的头结点 head，每隔一个结点删除另一个结点（要求保留头结点）。
请返回最终链表的头结点。

示例 1：

输入：head = [1,2,3,4]

输出: [1,3]

解释：
蓝色结点为删除的结点

示例 2：

输入：head = [5,1,8,6,1]

输出: [5,8,1]

提示：

• 链表中结点的数目在[1, 5000]范围内。
• 1 <= Node.val <= 10000

地址

https://leetcode-cn.com/contest/ccbft-2021fall/problems/woGGnF/

题意

遍历

思路

1. 这个题目出的比较无聊，我们每隔一个节点删除一个节点即可，将节点的指针指向下一个节点的下一个节点即可。
2. 复杂度分析:

• 时间复杂度: $O(N)$,其中 $N$ 为链表的长度,我们此时需要遍历一遍即可。
• 空间复杂度: $O(1)$,我们指针保存中间变量即可。

代码

class Solution {
public:
    ListNode* deleteListNode(ListNode* head) {
        ListNode * curr = head;
        
        while(curr){
            ListNode * prev = curr;
            curr = curr->next;
            if(curr){
                prev->next = curr->next;
                curr = curr->next;
            }else{
                break;
            }
        }
        
        return head;
    }
};

建信02. 柱状图分析

题目

某柱状图上共有 N 个柱形，数组 heights 中按照排列顺序记录了每个柱形的高度。假定任选 cnt 个柱形可组成一个柱形组，请在所有可能的柱形组中，找出最大高度与最小高度的差值为最小的柱形组，按高度升序返回该柱形组。若存在多个柱形组满足条件，则返回第一个元素最小的柱形组。

示例 1：

输入：heights = [3,2,7,6,1,8], cnt = 3

输出：[1,2,3]

解释：[1,2,3] 与 [6,7,8] 都符合在所有的柱形组中，最大高度与最小高度的差值为最小的条件，选择第一个元素最小的 [1,2,3] 返回。

示例 2：

输入：heights = [4,6,1,8,4,10], cnt = 4

输出：[4,4,6,8]

解释：柱形组 [4,4,6,8] 满足最大高度与最小高度的差值为最小条件。

提示：

• 2 <= cnt < heights.length <= 10^5
• 0 <= heights[i] <= 10^6

地址

https://leetcode-cn.com/contest/ccbft-2021fall/problems/9Rs2aO/

题意

排序

思路

1. 所谓任选 $cnt$ 个柱形使得最大高度与最小高度最小，则此时我们按照排序从小到大，最大值与最小值之差的最小值肯定是在选择连续 $cnt$ 个元素中．

• 时间复杂度分析: 时间复杂度为 $O(n\log(n))$，其中 $n$ 表示数组的长度．
• 空间复杂度分析: 空间复杂度为 $O(1)$，我们只需要常数个变量保存中间变量．

代码

class Solution {
public:
    vector<int> analysisHistogram(vector<int>& heights, int cnt) {
        sort(heights.begin(),heights.end());
        vector<int> ans;
        int mindiff = INT_MAX;
        int n = heights.size();
        int idx = -1;
        
        
        for(int i = 0; i <= n-cnt; ++i){
            if(heights[i+cnt-1] - heights[i] < mindiff){
                idx = i;
                mindiff = heights[i+cnt-1] - heights[i];
            }
        }
        for(int i = idx; i < idx+cnt; ++i){
            ans.push_back(heights[i]);
        }
    
        return ans;
    }
};

建信03. 地铁路线规划

题目

某城市有若干条地铁线路，lines 记录了每条地铁线路依次停靠的站点（每条线路均是双向的）
李林想从站点 start 出发前往 end，请规划一条可行路线使得他可以以最小的换乘次数到达目的站点。若有多条路线满足要求，请返回字典序最小的路线（要求路线上无重复的站点）。

注意：

• 输入数据保证存在 start 到 end 的路线
• 任意路线上的点在该条路线上仅出现一次（即任意一条路线均不是环线）

示例 1：

输入：lines = [[1,2,3,4,5],[2,10,14,15,16],[10,8,12,13],[7,8,4,9,11]], start = 1, end = 7

输出：[1,2,3,4,8,7]

解释：路线如图所示
从站点 1 到站点 7 的最少换乘 1 次，路线为 [1,2,3,4,8,7]

示例 2：

输入：lines = [[1,2,3,4,5,6,7,8,9,10,11],[12,13,2,14,8,15],[16,1,17,10,18]], start = 9, end = 1

输出：[9,8,7,6,5,4,3,2,1]

解释：路线如图所示
从站点 9 到站点 1 的最少换乘 0 次，路线为 [9,8,7,6,5,4,3,2,1]

提示：

• 1 <= lines.length, lines[i].length <= 100
• 1 <= lines[i][j], start, end <= 10000

地址

https://leetcode-cn.com/contest/ccbft-2021fall/problems/zQTFs4/

题意

dijistra 或者　DFS

思路

1. 感觉这个题目当时拿到时确实没有特别好的思路, 感觉可以通过暴力搜索即可解决该题目，最后看到几个解答，发现有直接 $DFS$ 加减枝就可以搞定的. 其实想想这个题目最难的地方有两点需要注意:

• 字典序最小的路径如何求出,最后看了下别人的解法竟然都是直接记录下当前的路径,然后比较两个整数数组的字典序大小即可，当初拿到题目的时候一直在想如何记录最小的字典序，结果都是使用暴力来记录．
• 如何记录两个站点之间的线路切换，我们在遍历的时候需要记录上一站的站点 $x$ 和路线 $y$，在下一站点切换时，我们会遍历站点 $x$ 周围所有的站点和路线, 这个需要稍微用点技巧, 我们在记录站点的邻接站点时,同时记录下它的站点号和路线号.

2. $DFS$ 暴力搜索的解法就感觉比较简单, 利用回溯记录下所有从 $start$ 可能的路径,并同时记录该路径经历的换乘次数, 同时记录下路径用来比较字典序,感觉这个解法确实没有什么难度,但是感觉复杂度还挺高的,感觉需要用到欧拉拓扑之类的，这个解法的时间复杂度应该挺高的，感觉应该在 $O(n^{3})$.当时感觉应该用 $BFS$ 来解决的,但是确实没有想到 $BFS$ 解决的好办法.
3. $BFS$: 我们可以使用 $dijistra$ 算法快速收敛,每次记录下当前路线的换站次数，路线号，已经经过的站点路劲，每次选择下一跳时，我们优先选择切换站点次数最少，且路径字典序最小的路径．实际 $BFS$ 写起来非常简洁.
4. 复杂度分析:

• 时间复杂度为 $O(MN\times log(MN))$,其中 $N$ 为站点的个数, $M$ 为线路的个数.
• 空间复杂度为 $O(N^2)$,其中 $N$ 为站点的个数.

代码

• DFS:

  class Solution { public: int ans = INT_MAX; vector<int> ret; void dfs(int cur, int target, vector<vector< pair<int, int> >>& g, vector<bool>& vis, int last, int cost, vector<int>& path) { if(cost > ans) return; if(cur == target) { if(cost < ans || (cost == ans && path < ret)) { ans = cost; ret = path; } return; } for(auto& [next, route] : g[cur]) { if(!vis[next]) { vis[next] = true; path.push_back(next); if(route != last) { dfs(next, target, g, vis, route, cost + 1, path); } else { dfs(next, target, g, vis, route, cost, path); } path.pop_back(); vis[next] = false; } } } vector<int> metroRouteDesignI(vector<vector<int>>& a, int start, int end) { int n = a.size(); // 路线个数 vector<vector< pair<int, int> >> g(10005); // 邻接表 for(int i = 0; i < n; ++i) { int m = a[i].size(); for(int j = 0; j < m; ++j) { if(j < m - 1) { g[a[i][j]].push_back({a[i][j + 1], i}); g[a[i][j + 1]].push_back({a[i][j], i}); } } } vector<bool> vis(10005, 0); vector<int> path; path.push_back(start); vis[start] = true; // 深搜 for(auto [next, route] : g[start]) { vis[next] = true; path.push_back(next); dfs(next, end, g, vis, route, 0, path); path.pop_back(); vis[next] = false; } return ret; } };

• BFS:

typedef pair<int,int> pii;

struct Node{
    int line;
    int change;
    vector<int> path;
};

struct cmp{
    bool operator()(const Node & a, const Node & b) {
        if(a.change == b.change){
            return a.path > b.path;
        }
        return a.change > b.change;
    }
};


class Solution {
public:    
    vector<int> metroRouteDesignI(vector<vector<int>>& lines, int start, int end) {
        int n = lines.size();
        vector<int> ans;
        
        unordered_map<int,vector<int>> nodes;
        unordered_map<int,vector<pii>> graph;
        for(int i = 0; i < n; ++i){
            for(auto v : lines[i]){
                nodes[v].emplace_back(i);
            }
            for(int j = 1; j < lines[i].size(); ++j){
                graph[lines[i][j-1]].push_back(make_pair(i,lines[i][j]));
                graph[lines[i][j]].push_back(make_pair(i,lines[i][j-1]));
            }
        }
        
        priority_queue<Node,vector<Node>,cmp> pq;
        for(auto v : nodes[start]){
            Node t;
            t.line = v;
            t.change = 0;
            t.path.emplace_back(start);
            pq.push(t);
        }
        while(!pq.empty()){
            Node curr = pq.top();
            pq.pop();
            if(curr.path.back() == end){
                return curr.path;
            }
            unordered_set<int> visited;
            for(auto v : curr.path){
                visited.insert(v);
            }
            for(auto neg : graph[curr.path.back()]){
                if(visited.count(neg.second)) continue;
                Node next;
                next.line = neg.first;
                next.path = curr.path;
                next.path.emplace_back(neg.second);
                //change line*/
                if(neg.first != curr.line){
                    next.change = curr.change + 1;
                }else{ // the same line
                    next.change = curr.change;
                }
                pq.push(next);
            }
        }
        
        return ans;
    }
};

建信04. 电学实验课

题目

某电学实验使用了 row * col 个插孔的面包板，可视作二维矩阵，左上角记作 (0,0)。老师设置了若干「目标插孔」，它们位置对应的矩阵下标记于二维数组 position。实验目标要求同学们用导线连接所有「目标插孔」，即从任意一个「目标插孔」沿导线可以到达其他任意「目标插孔」。受实验导线长度所限，导线的连接规则如下：

• 一条导线可连接相邻两列的且行间距不超过 1 的两个插孔
• 每一列插孔中最多使用其中一个插孔（包括「目标插孔」）
  若实验目标可达成，请返回使用导线数量最少的连接所有目标插孔的方案数；否则请返回 0。

注意：

• 输入数据保证每列最多仅有一个「目标插孔」；
• 答案需要以 1e9 + 7 (1000000007) 为底取模， 如：计算初始结果为：1000000008，请返回 1
  示例 1：

  输入：row = 5, col = 6, position = [[1,3],[3,2],[4,1]] 输出：0 解释：根据连接规则无法达成实验目标。

  示例 2：

  输入：row = 3，col = 4, position = [[0,3],[2,0]] 输出：3 解释：根据连接规则共有三种方案达成目标。

示例 3：

输入：row = 5, col = 6, position = [[1,3],[3,5],[2,0]]

输出：6

解释：根据连接规则共有六种方案达成目标。

提示：

• 1 <= row <= 20
• 3 <= col <= 10^9
• 1 < position.length <= 1000
• 0 <= position[i][0] < row
• 0 <= position[i][1] < col

地址

https://leetcode-cn.com/contest/ccbft-2021fall/problems/lSjqMF/

题意

动态规划 + 数学问题　

解题思路

1. 这个题目,我非常喜欢的类型, 用数学方法解决类似于动态规划的题目，与509. 斐波那契数的数学解法非常相似．我们知道斐波那契数数列的递推关系为$f[i] = f[i-1] + f[i-2]$, 然后我们可以利用利用矩阵乘法,求解公式如下:
   $$
   [f(n+1),f(n)] = [f(n) + f(n-1), f(n)] \
   = [f(n),f(n-1)] \times
   \left[
   \begin{array}{l}
   1 & 1 \
   1 & 0 \
   \end{array}
   \right]
   $$
2. 首先在本题中我们需要分析一下, 每个目标插孔连接时一定是按照列的大小依次进行相连的, 因为题目的约束规则是一条导线可连接相邻两列的且行间距不超过 1 的两个插孔且每一列插孔中最多使用其中一个插孔,这就意味着我们不可能先连接列数较大的目标孔后,再来连接列数较小的目标控. 因此首先我们需要按照列数的大小对目标孔进行排序, 然后依次按照列数大小开始连接.
3. 我们知道对于递推关系如下,设$f[i][j]$ 表示第 $i$ 行 $j$ 列的导线的穿线数目，则我们可以知道:
   $$
   f[i][j] = f[i-1][j-1] + f[i][j-1] + f[i+1][j-1]
   $$
   我们可以归纳递推关系为:
   $$
   \left{
   \begin{array}{lr}
   f[0][j] = f[0][j-1] + f[1][j-1]\
   f[1][j] = f[0][j-1] + f[1][j-1] + f[2][j-1]\
   \cdots \
   f[n-2][j] = f[n-3][j-1] + f[n-2][j-1] + f[n-1][j-1]\
   f[n-1][j] = f[n-2][j-1] + f[n-1][j-1]\
   \end{array}
   \right.
   $$
   转换为矩阵乘法即为:
   $$
   [f[0][j], f[1][j], \cdots,f[n-2][j],f[n-1][j]] = \
   [f[0][j-1], f[1][j-1], \cdots,f[n-2][j-1],f[n-1][j-1]] \times
   \left[
   \begin{array}{lr}
   1 & 1 & 0 & \cdots 0 & 0 \
   1 & 1 & 1 & \cdots 0 & 0 \
   0 & 1 & 1 & \cdots 0 & 0 \
   0 & 0 & 1 & \cdots 0 & 0 \
   0 & 0 & 0 & \cdots 0 & 0 \
   \vdots & \vdots & \vdots & \ddots & \vdots \
   0 & 0 & 0 & \cdots 1 & 0 \
   0 & 0 & 0 & \cdots 1 & 1 \
   0 & 0 & 0 & \cdots 1 & 1 \
   \end{array}
   \right]
   $$
   我们设矩阵 $A$ 满足:
   $$
   A =
   \left[
   \begin{array}{lr}
   1 & 1 & 0 & \cdots 0 & 0 \
   1 & 1 & 1 & \cdots 0 & 0 \
   0 & 1 & 1 & \cdots 0 & 0 \
   0 & 0 & 1 & \cdots 0 & 0 \
   0 & 0 & 0 & \cdots 0 & 0 \
   \vdots & \vdots & \vdots & \ddots & \vdots \
   0 & 0 & 0 & \cdots 1 & 0 \
   0 & 0 & 0 & \cdots 1 & 1 \
   0 & 0 & 0 & \cdots 1 & 1 \
   \end{array}
   \right]
   $$
   则此时我们可以知道对于第 $i$ 列的元素设为矩阵 $f[j]$, 对于第 $j$ 列的方法数的元素为矩阵 $f[i]$, 我们假设 $ i \le j$, 则我们可以知道递推关系为:
   $$
   f[j] = f[i]\times A^{j-i}
   $$
   此时我们则将方法数的计算转换为矩阵的乘法运算, 我们只需要每次求出第到达 $i$ 列的目标控的方法数，然后根据矩阵的乘法可以计算出处在第 $j$ 列的目标孔的方法数.
4. 实际计算过程中,我们还需要利用快速幂法,快速的计算出矩阵的 $n$ 次幂.　我们可以进行预处离．
5. 复杂度分析:

• 时间复杂度分析: $O(C\times n \times row^{3}$, 其中 $n$ 为点的个数, $C = 32$, $row$ 为矩阵的行数.
• 空间复杂度分析: $O(C\times row \times col)$,其中 $C=32$.

代码

• 数学问题

  typedef long long ll; class Solution { public: vector<vector<ll>> mult(vector<vector<ll>> mat1, vector<vector<ll>> mat2, long long mod){ int m = mat1.size(); int col = mat1[0].size(); int n = mat2[0].size(); vector<vector<ll>> res(m,vector<ll>(n)); for(int i = 0; i < m; ++i){ for(int j = 0; j < n; ++j){ for(int k = 0; k < col; ++k){ res[i][j] = (res[i][j] + mat1[i][k]*mat2[k][j])%mod; } } } return res; } vector<vector<ll>> fastpow(vector<vector<ll>> & mat, int p, long long mod){ int m = mat.size(); vector<vector<ll>> res(m,vector<ll>(m)); vector<vector<ll>> curr = mat; for(int i = 0; i < m; ++i){ res[i][i] = 1; } for(; p != 0; p = (p>>1)){ if(p%2){ res = mult(res,curr,mod); } curr = mult(curr,curr,mod); } return res; } int electricityExperiment(int row, int col, vector<vector<int>>& position) { int n = position.size(); long long ans = 0; long long mod = 1e9 + 7; sort(position.begin(),position.end(),[&](const vector<int> & a,const vector<int> & b){ return a[1] < b[1]; }); vector<vector<ll>> mat(row,vector<ll>(row)); vector<vector<vector<ll>>> arr(32); for(int i = 0; i < row; ++i){ mat[i][i] = 1; if(i >= 1) mat[i][i-1] = 1; if(i+1 < row) mat[i][i+1] = 1; } arr[0] = mat; for(int i = 1; i < 31; ++i){ arr[i] = mult(arr[i-1],arr[i-1],mod); } vector<vector<ll>> curr(1,vector<ll>(row)); curr[0][position[0][0]] = 1; for(int i = 1; i < n; ++i){ long long p = position[i][1] - position[i-1][1]; for(int j = 0; j < 31; ++j){ if(p&(1<<j)){ curr = mult(curr,arr[j],mod); } } for(int j = 0; j < row; ++j){ if(j != position[i][0]){ curr[0][j] = 0; } } } return curr[0][position[n-1][0]]; } };

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mike-box.github.io/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿