每日一题(4)

2024-06-03

题目: 1103. 分糖果 II

题解和思路

直接模拟，根据题意给每个小朋友分配对应的糖果即可。

定义 $i=0$，表示每个小朋友要分配的糖果，第 $i\mod n$ 个小朋友将分配 $i+1$ 颗糖果，当糖果不够分的时候，直接将剩余的糖果全部给当前的小朋友即可

func distributeCandies(candies int, n int) []int {  
    ans := make([]int, n)  
    for i := 0; candies > 0; i++ {  
        ans[i%n] += min(candies, i+1)  
        candies -= i + 1  
    }  
    return ans  
}

2024-06-04

题目: 3067. 在带权树网络中统计可连接服务器对数目

题解和思路

首先通过 $dfs$ 枚举以节点 $a$ 为跟的树有多少个符合要求的节点，假设存在三棵树，三棵树是有序地，从左到右依次为($a_1, a_2,a_3$)，树中满足要求的节点分别为 $(3,4,5)$。

• $a_2$ 左边的节点只有 $a_1$，两两相连得到 $3 \times 4$
• $a3$ 左边的节点有 $a_1, a_2$，两两相连得到 $(3+4) \times 5$
• 只从左往右开，这样可以避开重复的对，题目中要求 $a < b$，即不允许出现重复

遍历每个节点，统计最终符合要求的最终节点，其中如果节点 $a$ 只有一个子树可以跳过。

type edge struct {  
    to, weight int  
}  
  
func countPairsOfConnectableServers(edges [][]int, signalSpeed int) []int {  
    n := len(edges) + 1  
    g := make([][]edge, n)  
    for _, e := range edges {  
        u, v, w := e[0], e[1], e[2]  
        g[u] = append(g[u], edge{v, w})  
        g[v] = append(g[v], edge{u, w})  
    }  
      
    var dfs func(int, int, int) int  
    dfs = func(to, from, sum int) int {  
        cnt := 0  
        if sum%signalSpeed == 0 {  
            cnt = 1  
        }  
        for _, e := range g[to] {  
            if e.to != from {  
                cnt += dfs(e.to, to, sum+e.weight)  
            }  
        }  
        return cnt  
    }  
      
    res := make([]int, n)  
    for i, gi := range g {  
        if len(gi) == 1 {  
            continue  
        }  
        s := 0  
        for _, e := range gi {  
            cnt := dfs(e.to, i, e.weight)  
            res[i] += cnt * s  
            s += cnt  
        }  
    }  
    return res  
}

2024-06-05

题目: 3072. 将元素分配到两个数组中 II

题解和思路

主要是实现 $greaterCount$，这部分我没搞懂，见树状数组

type fenwick []int

// 把下标为 i 的元素增加 1
func (f fenwick) add(i int) {
	for ; i < len(f); i += i & -i {
		f[i]++
	}
}

// 返回下标在 [1,i] 的元素之和
func (f fenwick) pre(i int) (res int) {
	for ; i > 0; i &= i - 1 {
		res += f[i]
	}
	return
}

func resultArray(nums []int) (ans []int) {
	sorted := slices.Clone(nums)
	slices.Sort(sorted)
	sorted = slices.Compact(sorted)
	m := len(sorted)

	a := nums[:1]
	b := []int{nums[1]}
	t1 := make(fenwick, m+1)
	t2 := make(fenwick, m+1)
	t1.add(sort.SearchInts(sorted, nums[0]) + 1)
	t2.add(sort.SearchInts(sorted, nums[1]) + 1)
	for _, x := range nums[2:] {
		v := sort.SearchInts(sorted, x) + 1
		gc1 := len(a) - t1.pre(v) // greaterCount(a, v)
		gc2 := len(b) - t2.pre(v) // greaterCount(b, v)
		if gc1 > gc2 || gc1 == gc2 && len(a) <= len(b) {
			a = append(a, x)
			t1.add(v)
		} else {
			b = append(b, x)
			t2.add(v)
		}
	}
	return append(a, b...)
}

2024-06-06

题目: 2938. 区分黑球与白球

题解和思路

没有什么技巧，只能一个个移动，从左到右记录黑球数量 $cnt$，当遇到白球时需要把白球左移 $cnt$ 个才能移到左侧。遍历 $s$ 的同时累加 $cnt$ 即是答案。

func minimumSteps(s string) int64 {  
    ans := 0  
    cnt := 0  
    for _, c := range s {  
        if c == '1' {  
            cnt++  
        } else {  
            ans += cnt  
        }  
    }  
    return int64(ans)  
}

2024-06-07

题目: 3038. 相同分数的最大操作数目 I

题解和思路

按照题意从左网友循环即可

func maxOperations(nums []int) int {  
    s := nums[0] + nums[1]  
    ans := 1  
    for i := 3; i < len(nums) && nums[i-1]+nums[i] == s; i += 2 {  
        ans++  
    }  
    return ans  
}

2024-06-08

题目: 3040. 相同分数的最大操作数目 II

题解和思路

根据题意的操作，就是求子问题，且是两侧缩小的，确定了第一次删除的元素和，之后再通过三个中的操作继续递归即可。

定义 $dfs(i,j)$ 表示再区间 $[i,j]$ 内连续子数组，最多可以执行多少次操作。递归终点 $i>=j$，已经没有剩下的数，无法递归。

枚举三种操作模式，如果当前操作方式可行，继续向下枚举，即 $dfs(i+2,j),dfs(i+1,j-1),dfs(i,j+2)$ ，返回的结果 $+1$，再这三种结果中取最大值，即为 $dfs(i,j)$，如果三种都操作都不行，返回 $0$。

根据三种操作，递归入口分别为，$dfs(2, n-1), dfs(0, n-3), dfs(1, n-2)$。因为三种初始化对应 $target$ 不同，额外定义 $helper$ 为入口，在里面分别执行 $dfs$。

func maxOperations(nums []int) int {  
    n := len(nums)  
    res1 := helper(nums[2:], nums[0]+nums[1])  
    res2 := helper(nums[:n-2], nums[n-1]+nums[n-2])  
    res3 := helper(nums[1:n-1], nums[0]+nums[n-1])  
    return max(res1, res2, res3) + 1  
}  
  
func helper(a []int, target int) int {  
    n := len(a)  
    memo := make([][]int, n)  
    for i := range memo {  
        memo[i] = make([]int, n)  
        for j := range memo[i] {  
            memo[i][j] = -1  
        }  
    }  
      
    var dfs func(int, int) int  
    dfs = func(i, j int) int {  
        if i >= j {  
            return 0  
        }  
          
        res := 0  
        if memo[i][j] != -1 {  
            return memo[i][j]  
        }  
          
        if a[i]+a[i+1] == target {  
            res = max(res, dfs(i+2, j)+1)  
        }  
        if a[j]+a[j-1] == target {  
            res = max(res, dfs(i, j-2)+1)  
        }  
        if a[i]+a[j] == target {  
            res = max(res, dfs(i+1, j-1)+1)  
        }  
        memo[i][j] = res + 1  
        return res  
    }  
      
    return dfs(0, n-1)  
}

优化：

最大的移动次数为 $\lfloor \frac{n}{2} \rfloor$，当 $res1$ 的结果为 $\lfloor \frac{n}{2} \rfloor$，即递归到 $i<=j$ 时，可以直接返回，因为后续操作不可能再大于 $\lfloor \frac{n}{2} \rfloor$

func maxOperations3040(nums []int) int {  
    n := len(nums)  
    res1, done := helper(nums[2:], nums[0]+nums[1])  
    if done {  
        return n / 2  
    }  
    res2, done := helper(nums[:n-2], nums[n-1]+nums[n-2])  
    if done {  
        return n / 2  
    }  
    res3, done := helper(nums[1:n-1], nums[0]+nums[n-1])  
    if done {  
        return n / 2  
    }  
    return max(res1, res2, res3) + 1  
}  
  
func helper(a []int, target int) (int, bool) {  
    n := len(a)  
    memo := make([][]int, n)  
    for i := range memo {  
        memo[i] = make([]int, n)  
        for j := range memo[i] {  
            memo[i][j] = -1  
        }  
    }  
      
    var done bool  
    var dfs func(int, int) int  
    dfs = func(i, j int) int {  
        if done {  
            return 0  
        }  
        if i >= j {  
            done = true  
            return 0  
        }  
          
        res := 0  
        if memo[i][j] != -1 {  
            return memo[i][j]  
        }  
          
        if a[i]+a[i+1] == target {  
            res = max(res, dfs(i+2, j)+1)  
        }  
        if a[j]+a[j-1] == target {  
            res = max(res, dfs(i, j-2)+1)  
        }  
        if a[i]+a[j] == target {  
            res = max(res, dfs(i+1, j-1)+1)  
        }  
        memo[i][j] = res  
        return res  
    }  
      
    return dfs(0, n-1), done  
}

2024-06-09

题目: 312. 戳气球

题解和思路

首尾气球戳破时旁边没有气球按照 $1$ 处理，可以理解为 $nums[-1]$ 和 $nums[n+1]$ 的值都为 $1$。重新定义数组 $points$ 存储 $nums$ 和首尾的虚拟气球

使用动态规划思路，定义 $dp$ 数组即可，其中 $dp[i][j]=x$，表示戳破气球 $i$ 到气球 $j$ 之间(不包括 $i$ 和 $j$)的所有气球，最高得分为 $x$。因为这两段的气球是虚拟的，所以不需要戳破，最终我们的答案为就是 $dp[0][n+1]$ 的值

假设最后戳破的一个气球为 $k(i<k<j)$，要戳破 $k$ ，就需要把 $(i,k)$ 和 $(k,j)$ 两个区间的气球都戳破，最后剩下气球 $k$，相邻的气球就是 $i$ 和 $j$，此时戳破 $k$ 的得分就是 $points[i]\times points[k]\times points[j]$ 。当 $k$ 被戳破，$(i,j)$ 之间所有的气球都被戳破，而此时 $dp[i][j] = dp[i][k]+dp[k][j]+points[i] \times points[j]\times points[k]$，这就是状态转移方程

func maxCoins(nums []int) int {  
    n := len(nums)  
    points := make([]int, n+2) // 收尾各插入一个1,方便操作  
    points[0], points[n+1] = 1, 1  
    copy(points[1:n+1], nums)  
      
    dp := make([][]int, n+2)  
    for i := range dp {  
        dp[i] = make([]int, n+2)  
    }  
      
    for i := n; i >= 0; i-- {  
        for j := i + 1; j < n+2; j++ {  
            for k := i + 1; k < j; k++ {  
                dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+points[i]*points[j]*points[k])  
            }  
        }  
    }  
      
    return dp[0][n+1]  
}