每日一题(3)

2024-05-27

题目: 2028. 找出缺失的观测数据

题解与思路:

$m+n$ 次投掷的总和 $s = mean \times (m+n)$ ，减去 $rolls$ 的值就是缺失的 $n$ 份数据的总和。

如果确实的总和不在区间 $[n, 6n]$ 中，则答案不存在，小于 $n$ 不够分，大于 $6n$ 分不完。

计算出平均数 $avg = \lfloor \frac {s-sum(rolls)}{n} \rfloor$ ，然后把再数组中插入 $n$ 个 $avg$，然后计算 $poor = (s-sum(rolls)) \% n$，将数组前 $poor$ 个数的值加 $1$ 即可。

func missingRolls(rolls []int, mean int, n int) []int {  
    m := len(rolls)  
    s := mean * (m + n)  
    for _, roll := range rolls {  
        s -= roll  
    }  
      
    if s < n || s > n*6 {  
        return nil  
    }  
      
    avg := s / n  
    poor := s % n  
    ans := make([]int, n)  
    for i := 0; i < n; i++ {  
        ans[i] = avg  
        if i < poor {  
            ans[i] += 1  
        }  
    }  
      
    return ans  
}

2024-05-28

题目: 2951. 找出峰值

题解与思路:

从第二个数到倒数第二个数，比较相邻的数即可

func findPeaks(mountain []int) []int {  
    ans := []int{}  
    for i := 1; i < len(mountain)-1; i++ {  
        if mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1] {  
            ans = append(ans, i)  
        }  
    }  
    return ans  
}

2024-05-29

题目：[2981. 找出出现至少三次的最长特殊子字符串 I

题解与思路:

假设字符 $a$ 的最大三个长度分别为 $l_0,l_1,l_2$，此时只会出现以下几种情况：

• 从最长的 $l_0$ 中取 $3$ 个长度为 $l_0-2$ 的子串;
• 从最长的 $l_0$ 中与第二长的 $l_1$ 中取 $3$ 个子串：
  • 如果 $l_0=l_1$，此时可以取 $3$ 个长度为 $l_0-1$ 的子串；
  • 如果 $l_0>l_1$，此时可以从 $l_0$ 中取两个长度为 $l_1$ 的自创，从 $l_0$ 中去一个长度为 $l_1$ 的子串;
  • 以上两种情况合并为至少可以取三个长度为 $min(l_0-1,l_1)$;
• 从 $l_0,l_1,l_2$ 中分别取出长度为 $l_2$ 的子串;

上述三种情况的最大值，就是字符 $a$ 构成最长子字符串的长度 $l$，$l=max(l_0-2, min(l_0-1,l_1), l_2)$。

特别的，当字符 $a$ 只出现一次，即没有 $l_1,l_2$ 时，手动补 $0$ 即可，当最终结果为 $0$ 时表示没找到，返回 $-1$。

func maximumLength(s string) int {  
    groups := make(map[byte][]int)  
    cnt := 0  
    for i, v := range s {  
        cnt++  
        if i+1 == len(s) || s[i+1] != byte(v) {  
            groups[byte(v)] = append(groups[byte(v)], cnt)  
            cnt = 0  
        }  
    }  
      
    ans := 0  
    for _, l := range groups {  
        if len(l) == 0 {  
            continue  
        }  
        sort.Slice(l, func(i, j int) bool {  
            return l[i] > l[j]  
        })  
          
        l = append(l, 0, 0) // 添加两个空串,防止长度不够  
        ans = max(ans, l[0]-2, min(l[0]-1, l[1]), l[2])  
    }  
    if ans == 0 {  
        return -1  
    }  
    return ans  
}

2024-05-30

题目: 2982. 找出出现至少三次的最长特殊子字符串 II

题解与思路：同上

2024-05-31

题目: 2965. 找出缺失和重复的数字

题解与思路:

遍历计算出现次数，在找出出现两次和零次的

func findMissingAndRepeatedValues(grid [][]int) []int {  
    n := len(grid)  
    cnt := make([]int, n*n+1)  
    for _, g := range grid {  
        for _, x := range g {  
            cnt[x]++  
        }  
    }  
      
    ans := make([]int, 2)  
    for i := 1; i <= n*n; i++ {  
        if cnt[i] == 0 {  
            ans[1] = i  
        } else if cnt[i] == 2 {  
            ans[0] = i  
        }  
    }  
      
    return ans  
}

位运算也可以实现，这里懒得想了。

2024-06-01

题目: 2928. 给小朋友们分糖果 I

题解与思路:

假设给第一个小朋友分了 $x$ 个糖果，第二个小朋友分了 $y$ 个糖果，那么第三个小朋友将分到 $n-x-y$ 个糖果，只要他们分到的糖果小于 $limit$ 即为一个合法的方案。

func distributeCandies(n int, limit int) int {  
    ans := 0  
    for x := 0; x <= limit; x++ {  
        for y := 0; y <= limit; y++ {  
            if x+y > n {  
                break  
            }  
            if n-x-y <= limit {  
                ans++  
            }  
        }  
    }  
    return ans  
}

容斥原理

func cal(n int) int {  
    if n < 2 {  
        return 0  
    }  
    return n * (n - 1) / 2  
}  
  
func distributeCandies2(n, limit int) int {  
    return cal(n+2) - 3*cal(n-limit-1) + 3*cal(n-2*limit) - cal(n-3*limit-1)  
}

2024-06-02

题目: 575. 分糖果

题解与思路:

最多只能吃 $n/2$ 颗糖果，但是当糖果类型个数 $k$ 小于 $n/2$ 时，就只能吃 $k$ 颗糖果，即 $min(n/2, k)$

func distributeCandies(candyType []int) int {
m := map[int]struct{}{}
for _, c := range candyType {
m[c] = struct{}{}
}
return min(len(m), len(candyType)/2)
}