前言

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

题目

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 := 0for _, 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   intval   intcount int
}func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {arr := make([]Node, len(workerTimes))for i, work := range workerTimes {arr[i].val = workarr[i].cur = workarr[i].count = 2}sort.Slice(arr, func(i, j int) bool {return arr[i].cur < arr[j].cur})ans := 0for mountainHeight > 0 {ans = max(ans, arr[0].cur)arr[0].cur += arr[0].val * arr[0].countarr[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 := 1r := int(1e16) // 需要比所有的测试用例输出大。有个测试点的数据为 5e15ans := math.MaxIntfor l < r {mid := (l + r) / 2sumHeight := 0for _, 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 := 0left := 0for _, 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)
}