力扣周赛 —— 416

前言

只做出了第一道，第二第三道都超时。
痛，太痛了。

题目

Q1.举报垃圾信息

给你一个字符串数组 message 和一个字符串数组 bannedWords。
如果数组中 至少 存在两个单词与 bannedWords 中的任一单词 完全相同，则该数组被视为 垃圾信息。
如果数组 message 是垃圾信息，则返回 true；否则返回 false。
示例1：
输入： message = [“hello”,“world”,“leetcode”], bannedWords = [“world”,“hello”]
输出： true
解释：
数组 message 中的 “hello” 和 “world” 都出现在数组 bannedWords 中。

解题思路

哈希

利用哈希表存储 banneWords 中的 key，扫描 message ，统计 key 出现的次数，大于等于2返回 true，小于2返回 fase。

时间复杂度：O(m+n)

func reportSpam(message []string, bannedWords []string) bool {
hash := map[string]bool{}
for _, word := range bannedWords {
hash[word] = true
}
count := 0
for _, s := range message {
if _, ok := hash[s]; ok {
count++
}
if count >= 2 {
return true
}
}
return false
}

Q2. 移山所需的最少秒数

给你一个整数 mountainHeight 表示山的高度。
同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :

• 山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] * 2 + … + workerTimes[i] * x 秒。例如：
  • 山的高度降低 1，需要workerTimes[i] 秒。
  • 山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2秒，依此类推。

返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。
示例 1：
输入： mountainHeight = 4, workerTimes = [2,1,1]
输出： 3
解释：
将山的高度降低到 0 的一种方式是：
工人 0 将高度降低 1，花费 workerTimes[0] = 2 秒。
工人 1 将高度降低 2，花费 workerTimes[1] + workerTimes[1] * 2 = 3 秒。
工人 2 将高度降低 1，花费 workerTimes[2] = 1 秒。
因为工人同时工作，所需的最少时间为 max(2, 3, 1) = 3 秒

解题思路

贪心

每次花最少的时间让山高度降低1。

我们可以维持一个降低山的高度的最小成本的切片。每次从切片头部取出最小的时间，对齐进行处理，并重排序。

时间复杂度：O(nlogn + $n^m$） 。n 为 workerTimes 长度，m 为 mountainHeight 。

type Node struct {
cur   int
val   int
count int
}

func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
arr := make([]Node, len(workerTimes))
for i, work := range workerTimes {
arr[i].val = work
arr[i].cur = work
arr[i].count = 2
}
sort.Slice(arr, func(i, j int) bool {
return arr[i].cur < arr[j].cur
})
ans := 0
for mountainHeight > 0 {
ans = max(ans, arr[0].cur)
arr[0].cur += arr[0].val * arr[0].count
arr[0].count++
mountainHeight--
for i := 0; i < len(arr)-1; i++ {
if arr[i].cur > arr[i+1].cur {
arr[i], arr[i+1] = arr[i+1], arr[i]
}
}
}
return int64(ans)
}

提交，运行，超时。通过测试用例：556 / 571

二分法

因为所有人都在同时工作，那么我们只需要找出所有人同时工作使山的高度降低到 0 所需要的最小秒数。

如何查找？通过二分查找，否则会超时。

令 t = workerTimes[i]，求 m s内能降低山的最大高度。设 x 为最大高度。

则 t + 2 * t + … + x * t = $\frac{t\ast (1+x)\ast x}{2}$ <= m

由求根公示得正根为：x = $\frac{\sqrt{1+8\ast \frac{m}{t}}-1}{2}$

func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
l := 1
r := int(1e16) // 需要比所有的测试用例输出大。有个测试点的数据为 5e15
ans := math.MaxInt
for l < r {
mid := (l + r) / 2
sumHeight := 0
for _, time := range workerTimes {
sumHeight += int(math.Sqrt(1.0/4.0+float64(float64(2*mid)/float64(time))) - 0.5)
}
if sumHeight >= mountainHeight {
ans = min(ans, mid)
r = mid
} else {
l = mid + 1
}
}
return int64(ans)
}

Q3. 统计重新排列后包含另一个字符串的字符串数目 I

Q3、Q4题目是一样的，不过Q4的数据量更大。

给你两个字符串 word1 和 word2 。
如果一个字符串 x 重新排列后，word2 是重排字符串的前缀 ，那么我们称字符串 x 是合法的 。
请你返回 word1中合法子字符串的数目。

示例

输入：word1 = “bcca”, word2 = “abc”
输出：1
解释：
唯一合法的子字符串是 “bcca” ，可以重新排列得到 “abcc” ，“abc” 是它的前缀。

解释

• 1 <= word1.length <= $10^5$
• 1 <= word2.length <= $10^4$
• word1 和 word2 都只包含小写英文字母。

解题思路

看的灵神的题解。

滑动窗口

由于子串可以重排，只要子串可以涵盖 word2，那么子串就可以通过重排，使得 word2 是字串的前缀。
固定右边界，移动左边界，找出涵盖 wrod2 的最大左边界。
满足条件的个数为：left 个。

对比 word1 是否涵盖 word2 可以通过一个数组实现，数组记录 word2 与 word1 的字幕出现次数之差。在 word2 中出现的字母 +1， 在 word1 中出现的字母 -1。另外通过一个 less 参数记录窗口内有多少个字母的出现次数比 word2 的小。这样当 less = 0时，即 word1 涵盖 word2。

func validSubstringCount(word1 string, word2 string) int64 {
cnt := [26]int{} // word2 与 word1 的字母出现次数之差
for _, c := range word2 {
cnt[c-'a']++
}
less := 0// 统计窗口内有多少个字母的出现次数比 t 的小
for _, v := range cnt {
if v > 0 {
less++
}
}

ans := 0
left := 0
for _, b := range word1 {
cnt[b-'a']--
if cnt[b-'a'] == 0 {
less--
}
for less == 0 {
cnt[word1[left]]++
if cnt[word1[left]] > 0 {
less++
}
left++
}
ans += left
}
return int64(ans)
}

原文地址：https://blog.csdn.net/Wksycxy/article/details/142459040

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！