头像

Ncik




离线:8小时前



Ncik
11小时前
class NumMatrix {
public:
    vector<vector<int>> s;

    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() or matrix[0].empty()) return;
        s = vector<vector<int>> (matrix.size() + 1, vector<int>(matrix[0].size() + 1));
        for (int i = 1; i <= matrix.size(); ++i) {
            for (int j = 1; j <= matrix[0].size(); ++j) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int x1, int y1, int x2, int y2) {
        ++x1, ++y1, ++x2, ++y2;
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    }
};



Ncik
2天前
class NumArray {
    private int[] preSum;

    // 预处理阶段
    public NumArray(int[] nums) {
        int n = nums.length;
        // 计算前缀和数组
        preSum = new int[n + 1];
        preSum[0] = 0;
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return preSum[j + 1] - preSum[i];
    }
}



Ncik
2天前

引论

对网络流算法的认识

网络流算法是一种高效实用的算法,相对于其它图论算法来说,模型更加复杂,编程复杂度也更高,但是它综合了图论中的其它一些算法(如最短路径),因而适用范围也更广,经常能够很好地解决一些搜索与动态规划无法解决的,看似 $\rm NP$ 的问题。

具体问题的应用

网络流在具体问题中的应用,最具挑战性的部分是模型的构造。这没有现成的模式可以套用,需要对各种网络流的性质了如指掌(比如点有容量、容量有上下限、多重边等等),并且归纳总结一些经验,发挥我们的创造性。

网络流有许多分支的问题,这里只为大家介绍最大流问题。涉及到 $\rm FF,EK,Dinic$ 三个算法。
注意:网络流部分的课程当中也有“增广路径”的概念,但这与匈牙利算法当中的增广路径含义不同。

  • 二分图:通过拓展增广路径来获得更多的匹配
  • 最大流:通过寻找增广路径来获取更大的流量

什么是网络流?

我们从一个简单的例子开始说起。
你所在的村庄新开通了地下流水管道,自来水厂源源不断的提供水,村民们用水直接或间接用水,而村庄用完的废水统一回收于另一点(设排来的水全部回收)。当然每个管道有一定的容量。求废水站最多可以汇聚多少水?
当然这是一个有向图。所有的水都从一个点流出(水厂),最后全部汇聚到一个点(废水站)。

我们有以下称呼:
容量:每条边都有一个容量(水管的最大水流流量)。
源点:出发点(水厂)。
汇点:结束点(废水站)。
$\color{red}{流}$:一个 $\color{red}{合法解}$ 称作一个流。也就是一条从源点到汇点的有效路径。
流量:每条边被经过的次数(如果把每单位的水看作一个整体,流量即是被经过的次数)。

可以想到,图中有两个限制:
$\color{blue}{1. 流量限制:每条边的实际流量不能超过其容量。}$
$\color{blue}{2. 流量平衡:除了源点和汇点之外的所有点,流出量与流入量相等。}$
那么,怎么求出图中的最大流呢(即 废水站最多可以流入多少水)?

FF 算法

$\color{red}{\rm FF(Ford-Fulkerson)}$算法,即增广路方法。其思路是每次找出一条 $\color{orange}{从源到汇的能够增加流的路径}$,调整流值和残留网络,不断调整直到没有
增广路为止。$\rm FF$ 方法的基础是增广路定理 $\color{red}{\rm (Augmenting \ Path \
Theorem)}$:网络达到最大流当且仅当残留网络中没有增广路。




Ncik
3天前
class Solution {
public:
    int K;
    unordered_map<char, int> cnt;

    void add(char c, int& x, int& y) {
        if (!cnt[c]) x++;
        cnt[c]++;
        if (cnt[c] == K) y++;
    }

    void del(char c, int& x, int& y) {
        if (cnt[c] == K) y--;
        cnt[c]--;
        if (!cnt[c]) x--;
    }

    int longestSubstring(string s, int _K) {
        K = _K;
        int res = 0;
        // 枚举区间里包含的不同字符的数量
        for (int k = 1; k <= 26; ++k) {
            cnt.clear();
            // x 表示不同字符的数量,y 表示满足要求的字符数量
            for (int i = 0, j = 0, x = 0, y = 0; i < s.size(); ++i) {
                add(s[i], x, y);
                while (x > k) del(s[j++], x, y);
                if (x == y) res = max(res, i - j + 1);
            }
        }
        return res;
    }
};



Ncik
4天前

算法

(DP) $(\mid word1 \mid + \mid word2 \mid)^2$

实际上就是一个有条件限制的最长回文子序列问题。考虑串 $S=word1+word2$,这里的限制条件就是前 $|word1|$ 个字符中至少取一个,且后 $|word2|$ 个字符中至少取一个。

我们首先考虑没有限制条件的最长回文子序列。这是一个经典的动态规划问题,我们有两种做法:

  1. 中心扩展,$dp[L][R]$ 表示 $S[L\dots R]$ 范围的最长回文子序列。
  2. 令 $T=S’$($S$ 的倒序),然后求 $S$ 和 $T$ 的最长公共子序列。

考虑引入限制条件。我们使用三个数组,分别记录使用了 $word1$ 的最长回文子序列,使用了 $word2$ 的最长回文子序列和既使用了 $word1$ 又使用了 $word2$ 的最长回文子序列的长度。

在每一次转移时,我们根据当前字符的归属情况(属于 $word1$ 还是 $word2$)来决定是否能进行转移。

需要注意的是,这里我们应该使用上面的方法一(方法二可能也可以,但是会比较复杂),因为方法一中,我们是同时使用了两个字符,可以确保归属情况的正确处理。

C++ 代码

class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        string s = word1 + word2;
        vector<vector<int>> lps1(n + m + 1, vector<int>(n + m + 1));
        vector<vector<int>> lps2(n + m + 1, vector<int>(n + m + 1));
        vector<vector<int>> lps12(n + m + 1, vector<int>(n + m + 1));
        for (int len = 1; len <= n + m; ++len)
            for (int l = 1; l + len - 1 <= n + m; ++l) {
                int r = l + len - 1;
                bool use1 = l <= n;
                bool use2 = r > n;
                if (len == 1) {
                    if (use1)
                        lps1[l][l] = 1;
                    if (use2)
                        lps2[l][l] = 1;
                    continue;
                }
                if (s[l - 1] == s[r - 1]) {
                    if (use1 && use2) {
                        lps12[l][r] = lps12[l + 1][r - 1] + 2;
                    }
                    if (use1) {
                        if (lps2[l + 1][r - 1] > 0)
                            lps12[l][r] = max(lps12[l][r], lps2[l + 1][r - 1] + 2);
                        lps1[l][r] = lps1[l + 1][r - 1] + 2;
                    }
                    if (use2) {
                        if (lps1[l + 1][r - 1] > 0)
                            lps12[l][r] = max(lps12[l][r], lps1[l + 1][r - 1] + 2);
                        lps2[l][r] = lps2[l + 1][r - 1] + 2;
                    }
                }
                lps12[l][r] = max(lps12[l][r], max(lps12[l + 1][r], lps12[l][r - 1]));
                lps1[l][r] = max(lps1[l][r], max(lps1[l + 1][r], lps1[l][r - 1]));
                lps2[l][r] = max(lps2[l][r], max(lps2[l + 1][r], lps2[l][r - 1]));
        }
        return lps12[1][n + m];
    }
};



Ncik
4天前
class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        string s = word1 + word2;
        vector<vector<int>> lps1(n + m + 1, vector<int>(n + m + 1));
        vector<vector<int>> lps2(n + m + 1, vector<int>(n + m + 1));
        vector<vector<int>> lps12(n + m + 1, vector<int>(n + m + 1));
        for (int len = 1; len <= n + m; ++len)
            for (int l = 1; l + len - 1 <= n + m; ++l) {
                int r = l + len - 1;
                bool use1 = l <= n;
                bool use2 = r > n;
                if (len == 1) {
                    if (use1)
                        lps1[l][l] = 1;
                    if (use2)
                        lps2[l][l] = 1;
                    continue;
                }
                if (s[l - 1] == s[r - 1]) {
                    if (use1 && use2) {
                        lps12[l][r] = lps12[l + 1][r - 1] + 2;
                    }
                    if (use1) {
                        if (lps2[l + 1][r - 1] > 0)
                            lps12[l][r] = max(lps12[l][r], lps2[l + 1][r - 1] + 2);
                        lps1[l][r] = lps1[l + 1][r - 1] + 2;
                    }
                    if (use2) {
                        if (lps1[l + 1][r - 1] > 0)
                            lps12[l][r] = max(lps12[l][r], lps1[l + 1][r - 1] + 2);
                        lps2[l][r] = lps2[l + 1][r - 1] + 2;
                    }
                }
                lps12[l][r] = max(lps12[l][r], max(lps12[l + 1][r], lps12[l][r - 1]));
                lps1[l][r] = max(lps1[l][r], max(lps1[l + 1][r], lps1[l][r - 1]));
                lps2[l][r] = max(lps2[l][r], max(lps2[l + 1][r], lps2[l][r - 1]));
        }
        return lps12[1][n + m];
    }
};



Ncik
4天前
// 考虑当前已经从numsnums左边取了LL个数,从右边取了RR个数,
// 则对于第L+R+1L+R+1个数,multipliers[L+R+1]multipliers[L+R+1](这里下标从11开始)的取值是确定的,
// 而在numsnums中,我们可以选择nums[L+1]nums[L+1]或nums[N-R-1]nums[N−R−1]。
// 由于这里无论我们选择左边还是右边,都与前面的L+RL+R次选择无关,满足无后效性的要求,
// 所以我们可以考虑进行动态规划,用dp[L][R]dp[L][R]表示左边取LL个,右边取RR个数时的最大分数。
// 实际上,如果已经取了KK个数,而左边取了LL个,右边自然是取了N-LN−L个,因此我们可以进一步将空间降低到一维。

#define INF 0x3f3f3f3f

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int n = nums.size(), m = multipliers.size();
        vector<int> dp(m + 1, -INF);
        dp[0] = 0;
        for (int i = 0; i < m; ++i) {
            vector<int> ndp(m + 1, -INF);
            for (int j = 0; j <= i; ++j) {
                ndp[j + 1] = max(ndp[j + 1], dp[j] + nums[j] * multipliers[i]);
                ndp[j] = max(ndp[j], dp[j] + nums[n - 1 - (i - j)] * multipliers[i]);
            }
            dp = move(ndp);
        }
        return *max_element(dp.begin(), dp.end());
    }
};



Ncik
4天前
// 分别考虑把所有左边的球移到当前盒子的操作数,以及把所有右边的球移到当前盒子的操作数。
// 对于左边的情况,我们只需要维护当前一共的球数,就能够计算出再向右移动一位需要的额外花费。
// 右边的情况可以类似地进行处理。
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> l(n), r(n);
        int ln = 0, tot = 0;
        for (int i = 0; i < n; ++i) {
            l[i] = tot;
            if (boxes[i] == '1')
                ln++;
            tot += ln;
        }
        int rn = 0;
        tot = 0;
        for (int i = n - 1; i >= 0; --i) {
            r[i] = tot;
            if (boxes[i] == '1')
                rn++;
            tot += rn;
        }
        vector<int> ans(n);
        for (int i = 0; i < n; ++i)
            ans[i] = l[i] + r[i];
        return ans;
    }
};



Ncik
4天前
class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int l1 = word1.size(), l2 = word2.size();
        string ans;
        int p1 = 0, p2 = 0;
        while (p1 < l1 || p2 < l2) {
            if (p1 < l1)
                ans.push_back(word1[p1++]);
            if (p2 < l2)
                ans.push_back(word2[p2++]);
        }
        return ans;
    }
};


活动打卡代码 LeetCode 684. 冗余连接

Ncik
4天前
// 可以通过Tarjan算法,从最后一条边开始依次判断是否为桥边。
// 如果不是桥边,则是一个冗余连接,可以将其删除。
class Solution {
    int n, idx = 0;
    vector<int> dfn, low;
    vector<vector<int>> adj;
    void tarjan(int u, int p) {
        dfn[u] = low[u] = ++idx;
        for (int v : adj[u]) {
            if (v == p)
                continue;
            if (!dfn[v]) {
                tarjan(v, u);
                low[u] = min(low[u], low[v]);
            } else
                low[u] = min(low[u], dfn[v]);
        }
    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        n = edges.size();
        adj = vector<vector<int>>(n + 1);
        for (auto v : edges) {
            adj[v[0]].emplace_back(v[1]);
            adj[v[1]].emplace_back(v[0]);
        }
        dfn = vector<int>(n + 1);
        low = vector<int>(n + 1);
        tarjan(1, 0);
        for (int i = n - 1; i >= 0; --i) {
            int &u = edges[i][0], &v = edges[i][1];
            if (dfn[u] >= low[v] && dfn[v] >= low[u])
                return edges[i];
        }
        return {};
    }
};