【TalkGo算法之美】第 2次在线比赛

算法之美
1

算法之美线上比赛开启报名

目的

希望志同道合的刷题人可以有一个一起比赛、探讨的平台，也希望大神们可以来这里秀出你的最优解。

报名形式

直接回贴：报名参加 即可。

报名截止时间

2021.03.05 23:59:59

活动方式

参加 LeetCode 在 2021.03.07 早上10:30的周赛。leetcode 第 231 场周赛

比赛结束后，请将个人比赛的题解以及你所取得的成绩排名截图一并回复到你报名的帖子里。

我们将会按照报名成功的候选人中选出一名优胜者（以比赛最终排名为准）。

活动奖励

任意一本图书（如果你可以你给出选择理由以及看过之后的推荐语，那就更好了）

备注：想更更多真正积极活跃的人一起讨论，可以微信私信 night_reading_go，最好将你的“算法”相关情况进行备注说明。

2

只做出前两道
image

5697. 检查二进制字符串字段

func checkOnesSegment(s string) bool {
    flag := false
    for i:=0; i<len(s); i++ {
        if s[i] == '1' {
            if flag == false {
                flag = true
            } else if s[i-1] == '0' {
                return false
            }  
        }
    }
    return true
}

1785. 构成特定和需要添加的最少元素

func minElements(nums []int, limit int, goal int) int {
    sum := 0
    for _, v := range nums {
        sum += v
    }
    
    delta := abs(goal-sum)
    ret := delta / limit
    if (delta % limit) > 0 {
        ret++
    }
    return ret
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
3

报名参加

4

报名参加

5

报名参加

6

报名参加

7

报名参加

8

报名参加

9

1. 检查二进制字符串字段

解题思路：直接遍历判断即可

func checkOnesSegment(s string) bool {
    cnt, one, n := 0, 0, len(s)
    for i := 0; i < n; i++ {
        if s[i] == '0' {
            if one > 0 {
                cnt++
            }
            one =0
        } else {
            one++
        }
    }
    if one > 0 {
        cnt++
    }
    return cnt < 2
}

2. 构成特定和需要添加的最少元素

解题思路：首先计算数组和与目标值差多少 diff，如果 diff < 0，则挑 -limit 去填充，如果 diff > 0，则挑 limit 去填充。

func absInt(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func minElements(nums []int, limit int, goal int) int {
    n, s := len(nums), 0
    for i := 0; i < n; i++ {
        s += nums[i]
    }
    diff := absInt(goal - s)
    ret := diff / limit
    if diff % limit > 0 {
        ret++
    }
    return ret
}

3. 从第一个节点出发到最后一个节点的受限路径数

解题思路

  • 带最短路径限制的图（u → v 存在边，且 d[u] < d[v]），我们很容易知道其是一个 DAG，有着良好的拓扑序。
  • 求解 DAG 中某个顶点 u → v 的路径数，我们直接采用 DP 求解即可。
type Edge struct {
    v, w int
}

func countRestrictedPaths(n int, edges [][]int) int { 
    m := len(edges)
    mod := int(1e9+7)
    adj := make([][]Edge, n+1)
    for i := 0; i < m; i++ {
        u, v, w := edges[i][0], edges[i][1], edges[i][2]
        adj[u] = append(adj[u], Edge{v, w})
        adj[v] = append(adj[v], Edge{u, w})
    }
    
    // 最短路径求解采用 SPFA 算法，比赛时候写错了一个地方，导致 debug 了较长时间
    // 模板算法一定要熟且尽可能手敲出来
    dis := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dis[i] = 0x3f3f3f3f3f3f3f3f
    }
    que := make([]int, 0, 100000)
	inq := make([]bool, n+1)
	que = append(que, n)
    dis[n] = 0
	inq[n] = true
	for len(que) > 0 {
		u := que[0]
		que = que[1:]
		inq[u] = false 
        for _, e := range adj[u] {
            v, w := e.v, e.w
            if dis[v] > dis[u] + w {
                dis[v] = dis[u] + w
                if !inq[v] {  
                    inq[v] = true
                    que = append(que, v)
                }
            }
        }
	}
    
    dp := make([]int, n+1)
    mark := make([]bool, n+1)
    ee := make([]Edge, 0, n)
    for i := 1; i <= n; i++ {
        ee = append(ee, Edge{i, dis[i]})
    }
    sort.Slice(ee, func(i, j int) bool {
        return ee[i].w < ee[j].w
    })
    dp[n] = 1
    mark[n] = true
    for i := 1; i < n; i++ {
        u := ee[i].v
        for _, e := range adj[u] {
            v := e.v 
            if mark[v] && dis[v] < dis[u] {
                dp[u] = (dp[u] + dp[v]) % mod
            }
        }
        mark[u] = true
        if u == 1 {
            return dp[u]
        }
    }
    return 0
}

4. 使所有区间的异或结果为零

解题思路

  1. 虽然在解第三题的过程中也再想第四题，感觉是用 dp 做，但是在设计 dp 状态时，发现无论怎么设计都无法满足 dp 无后效性这一原则。其实本质上是没有挖掘出数组的性质来，导致无法设计正确的 dp。
  2. 首先由题目可知最终结果中需要满足 a1^a2^…a^k = a2^a3^…^ak^a(k+1)=a3^…，根据成立的等式，我们发现整个结果数组是存在长度为 k 的循环节的，即最终结果中 a1 = a(k+1) = a(2k+1) …, ak = a(2k) = a(3*k) …
  3. 由于存在长度为 k 的循环节，因此我们只需要确定 a1, a2, …, ak 最终是啥整个数组遍确定了；我们 dp 便可以按照这 k 来划分阶段。假设 dp(i, j) 表示前 i 组数确定后最终异或和为 j 情况下需要变更的最少元素数。我们在选择第 i 组数是啥的时候存在两种情况：
    1. 第 i 组数不属于原先 i 组中的任何一个数字，此时花费 size(i) 即第 i 组数的个数，在选择从 i - 1 阶段哪个状态转换而来时，我们只需要选择 dp(i-1,x) 最小值即可。
    2. 从 i 组数中选择一个数作为结果，求解花费数。其中一种情况 2 会对 1 的结果进行纠正(1 算大了)。
  4. 状态转移方程
    1. dp(i, j) = min{dp(i-1,k)}{0<=k<lim} + size(i)
    2. dp(i, j) = min{dp(i-1,j^x) + size(i)-cnt(x)}，其中 x 为第i组中的某个数
  5. 上述 lim 即为 2^x > max{nums[i]}，因为二进制异或中比最大值最高位的 1 还大的数字是没有意义的，只会引入更多的花费。想想这是为什么？
  6. 本题其实的通用问法是：最终所有长度为 k 子数组的异或和为 x。感觉这道题目应该在哪儿出现过。。。
func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func minChanges(nums []int, k int) int {
    n :=  len(nums)
    group := make(map[int]map[int]int, k)
    groupSize := make([]int, k+1)
    for i := 1; i <= k; i++ {
        group[i] = make(map[int]int)
    }
    maxV :=  0
    for i := 0; i < n; i++ {
        idx := i % k
        group[idx+1][nums[i]]++
        groupSize[idx+1]++
        maxV = maxInt(maxV, nums[i])
    }

    lim := 1 
    for lim <= maxV {
        lim <<= 1
    }

    dp := make([][]int, k+1)
    for i := 0; i <= k; i++ {
        dp[i] = make([]int, lim)
        for j := 0; j < lim; j++ {
            dp[i][j] = 0x3f3f3f3f
        }
    }
    dp[0][0] = 0
    for i := 1; i <= k; i++ {
        minV := dp[i-1][0]
        for j := 1; j < lim; j++ {
            minV = minInt(minV, dp[i-1][j])
        }
        for j := 0; j < lim; j++ {
            dp[i][j] = minV + groupSize[i]
            for x, c := range group[i] {
                dp[i][j] = minInt(dp[i][j],  dp[i-1][j^x] + groupSize[i]-c)
            }
        }
    }
    return dp[k][0]
}

image
image2345×132 15 KB

2 个赞
10

新年 flag：leetcode 稳定出四题。

11

1784.检查二进制字符串字段

// CreateTime: 2021-03-07 10:30:22
class Solution {
public:
    bool checkOnesSegment(string s) {
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == '1' && s[i-1] == '0') {
                return false;
            }
        }
        return true;
    }
};

1785.构成特定和需要添加的最少元素

// CreateTime: 2021-03-07 10:34:01
class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        long long s = 0;
        for (auto &x: nums) {
            s += x;
        }
        long long k = (long long)(goal)-s;

        return abs(k) / limit + (abs(k) % limit != 0);
    }
};

1786.从第一个节点出发到最后一个节点的受限路径数

// CreateTime: 2021-03-07 10:39:55
class Solution {
public:
    typedef pair<int, int> PII;
    typedef long long LL;

    LL ans = 1;

    vector<int> d;
    vector<int> m;
    vector<vector<PII>> g;
    const int MOD = 1e9+7;

    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        d.resize(n+1, INT_MAX);
        m.resize(n+1);
        g.resize(n+1);

        for (auto &edge: edges) {
            auto x = edge[0];
            auto y = edge[1];
            auto w = edge[2];
            g[x].push_back({y, w});
            g[y].push_back({x, w});
        }


        queue<int> que;
        que.push(n);
        d[n] = 0;

        while (que.size()) {
            auto x = que.front();
            que.pop();

            for (auto &e: g[x]) {
                auto y = e.first;
                auto w = e.second;

                if (d[x]+w < d[y]) {
                    d[y] = d[x]+w;
                    que.push(y);
                }
            }
        }

        return dfs(n);
    }

    int dfs(int n, int x = 1, LL sub = 0) {
        if (m[x]) {
            return m[x];
        }

        for (auto &e: g[x]) {
            auto y = e.first;
            auto w = e.second;

            if (y == n) {
                sub++;
                continue;
            }

            if (d[y] >= d[x]) {
                continue;
            }

            sub += dfs(n, y);
        }

        sub = sub % MOD;
        return m[x] = sub;
    }
};

比赛成绩

image
image1948×688 126 KB