76. 最小覆盖子串 Minimum Window Substring
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 10^5
s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
代码1： 滑动窗口
package main import ( "fmt" ) func minWindow(s string, t string) string { if len(s) < len(t) { return "" } need := make(map[byte]int) // 存储t中每个字符的出现次数 for i := 0; i < len(t); i++ { need[t[i]]++ } left, right := 0, 0 // 滑动窗口的左右指针 count := len(t) // 记录滑动窗口中还需要的字符数 minLen := len(s) + 1 // 记录最小覆盖子串的长度 start := 0 // 记录最小覆盖子串的起始位置 for right < len(s) { // 当右指针指向的字符是需要的字符，count减一 if _, ok := need[s[right]]; ok { if need[s[right]] > 0 { count-- } need[s[right]]-- } right++ // 当count为0时，说明滑动窗口中已经包含t中的所有字符 for count == 0 { // 如果当前的覆盖子串更小，则更新最小覆盖子串的长度和起始位置 if right-left < minLen { minLen = right - left start = left } // 当左指针指向的字符是需要的字符，count加一 if _, ok := need[s[left]]; ok { need[s[left]]++ if need[s[left]] > 0 { count++ } } left++ } } if minLen == len(s)+1 { return "" } return s[start : start+minLen] } func main() { fmt.Println(minWindow("ADOBECODEBANC", "ABC")) fmt.Println(minWindow("a", "a")) fmt.Println(minWindow("a", "aa")) }
代码2：双指针
package main import ( "fmt" ) func minWindow(s string, t string) string { if len(s) < len(t) { return "" } need := make(map[byte]int) // 存储t中每个字符的出现次数 for i := 0; i < len(t); i++ { need[t[i]]++ } left, right := 0, 0 // 滑动窗口的左右指针 count := len(t) // 记录滑动窗口中还需要的字符数 minLen := len(s) + 1 // 记录最小覆盖子串的长度 start := 0 // 记录最小覆盖子串的起始位置 for right < len(s) { // 当右指针指向的字符是需要的字符，count减一 if _, ok := need[s[right]]; ok { if need[s[right]] > 0 { count-- } need[s[right]]-- } right++ // 当count为0时，说明滑动窗口中已经包含t中的所有字符 for count == 0 { // 如果当前的覆盖子串更小，则更新最小覆盖子串的长度和起始位置 if right-left < minLen { minLen = right - left start = left } // 当左指针指向的字符是需要的字符，count加一 if _, ok := need[s[left]]; ok { need[s[left]]++ if need[s[left]] > 0 { count++ } } left++ } } if minLen == len(s)+1 { return "" } return s[start : start+minLen] } func main() { fmt.Println(minWindow("ADOBECODEBANC", "ABC")) fmt.Println(minWindow("a", "a")) fmt.Println(minWindow("a", "aa")) }
输出：
BANC
a
//空行
77. 组合 Combinations
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 20
1 <= k <= n
代码1： 回溯法
package main import ( "fmt" ) func combine(n int, k int) [][]int { var res [][]int // 存储所有组合 var path []int // 存储当前组合 var backtrack func(start int) // 定义回溯函数 backtrack = func(start int) { if len(path) == k { // 当前组合长度为k，加入结果中 temp := make([]int, k) copy(temp, path) res = append(res, temp) return } for i := start; i <= n; i++ { // 枚举可选的数字 path = append(path, i) // 加入当前数字 backtrack(i + 1) // 从i+1开始枚举下一个数字 path = path[:len(path)-1] // 撤销当前数字 } } backtrack(1) // 从1开始枚举第一个数字 return res } func main() { fmt.Println(combine(4, 2)) fmt.Println(combine(1, 1)) }
输出：
[[1 2] [1 3] [1 4] [2 3] [2 4] [3 4]]
[[1]]
代码2： 枚举法
package main import ( "fmt" ) func combine(n int, k int) [][]int { var res [][]int // 存储所有组合 for i := 0; i < 1<<uint(n); i++ { // 枚举所有二进制数 var path []int // 存储当前组合 for j := 1; j <= n; j++ { // 枚举n个数字 if i&(1<<uint(j-1)) != 0 { // 当前数字被选中 path = append(path, j) } } if len(path) == k { // 当前组合长度为k，加入结果中 res = append(res, path) } } return res } func main() { fmt.Println(combine(4, 2)) fmt.Println(combine(1, 1)) }
78. 子集 Subsets
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
代码1：回溯法
go
输出：
[[] [1] [1 2] [1 2 3] [1 3] [2] [2 3] [3]]
[[] [0]]
代码2：
package main import ( "fmt" ) func subsets(nums []int) [][]int { var res [][]int // 存储所有子集 res = append(res, []int{}) // 初始为空集 for i := 0; i < len(nums); i++ { // 枚举每个数字 for _, sub := range res { // 枚举已有的子集 temp := append([]int{}, sub...) temp = append(temp, nums[i]) // 加入当前数字 res = append(res, temp) // 加入新的子集 } } return res } func main() { nums := []int{1, 2, 3} fmt.Println(subsets(nums)) nums = []int{0} fmt.Println(subsets(nums)) }
输出：
[[] [1] [2] [1 2] [3] [1 3] [2 3] [1 2 3]]
[[] [0]]
代码3： 位运算
package main import ( "fmt" ) func subsets(nums []int) [][]int { var res [][]int // 存储所有子集 n := len(nums) for i := 0; i < (1 << n); i++ { // 枚举所有二进制数 var path []int // 存储当前子集 for j := 0; j < n; j++ { // 枚举n个数字 if i&(1<<j) != 0 { // 当前数字被选中 path = append(path, nums[j]) } } res = append(res, path) // 加入当前子集 } return res } func main() { nums := []int{1, 2, 3} fmt.Println(subsets(nums)) nums = []int{0} fmt.Println(subsets(nums)) }
输出：
[[] [1] [2] [1 2] [3] [1 3] [2 3] [1 2 3]]
[[] [0]]
