0801-0900-Easy¶
804.唯一摩尔斯密码词(1)¶
题目
国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串，
比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。
为了方便，所有26个英文字母对应摩尔斯密码表如下：
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..",
"--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。
例如，"cab" 可以写成 "-.-..--..."，(即 "-.-." + "-..." + ".-"字符串的结合)。
我们将这样一个连接过程称作单词翻译。
返回我们可以获得所有词不同单词翻译的数量。
例如:
输入: words = ["gin", "zen", "gig", "msg"]
输出: 2
解释:
各单词翻译如下:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
共有 2 种不同翻译, "--...-." 和 "--...--.".
注意:
单词列表words 的长度不会超过 100。
每个单词 words[i]的长度范围为 [1, 12]。
每个单词 words[i]只包含小写字母。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n) | O(n) |
var table = []string{
".-", "-...", "-.-.", "-..", ".",
"..-.", "--.", "....", "..", ".---",
"-.-", ".-..", "--", "-.", "---",
".--.", "--.-", ".-.", "...", "-",
"..-", "...-", ".--", "-..-", "-.--",
"--..",
}
func uniqueMorseRepresentations(words []string) int {
res := make(map[string]bool)
for _, w := range words {
b := ""
for i := 0; i < len(w); i++ {
b = b + table[w[i]-'a']
}
res[b] = true
}
return len(res)
}
806.写字符串需要的行数(1)¶
题目
我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，
如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。
我们给定了一个数组 widths ，这个数组 widths[0] 代表 'a' 需要的单位，
widths[1] 代表 'b' 需要的单位，...， widths[25] 代表 'z' 需要的单位。
现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？
将你的答案作为长度为2的整数列表返回。
示例 1:输入:
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
输出: [3, 60]
解释:
所有的字符拥有相同的占用单位10。所以书写所有的26个字母，
我们需要2个整行和占用60个单位的一行。
示例 2:输入:
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
输出: [2, 4]
解释:
除去字母'a'所有的字符都是相同的单位10，并且字符串 "bbbcccdddaa" 将会覆盖 9 * 10 + 2 * 4 = 98 个单位.
最后一个字母 'a' 将会被写到第二行，因为第一行只剩下2个单位了。
所以，这个答案是2行，第二行有4个单位宽度。
注:
字符串 S 的长度在 [1, 1000] 的范围。
S 只包含小写字母。
widths 是长度为 26的数组。
widths[i] 值的范围在 [2, 10]。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历-模拟 | O(n) | O(1) |
func numberOfLines(widths []int, S string) []int {
res := []int{0, 0}
if len(S) == 0 {
return res
}
res[0] = 1
for i := 0; i < len(S); i++ {
if res[1]+widths[S[i]-'a'] > 100 {
res[0]++
res[1] = widths[S[i]-'a']
} else {
res[1] = res[1] + widths[S[i]-'a']
}
}
return res
}
811.子域名访问计数(2)¶
题目
一个网站域名，如"discuss.leetcode.com"，包含了多个子域名。
作为顶级域名，常用的有"com"，下一级则有"leetcode.com"，最低的一级为"discuss.leetcode.com"。
当我们访问域名"discuss.leetcode.com"时，也同时访问了其父域名"leetcode.com"以及顶级域名 "com"。
给定一个带访问次数和域名的组合，要求分别计算每个域名被访问的次数。
其格式为访问次数+空格+地址，例如："9001 discuss.leetcode.com"。
接下来会给出一组访问次数和域名组合的列表cpdomains 。
要求解析出所有域名的访问次数，输出格式和输入格式相同，不限定先后顺序。
示例 1:输入: ["9001 discuss.leetcode.com"]
输出: ["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
说明:
例子中仅包含一个网站域名："discuss.leetcode.com"。
按照前文假设，子域名"leetcode.com"和"com"都会被访问，所以它们都被访问了9001次。
示例 2输入:
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
输出:
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org",
"1 intel.mail.com","951 com"]
说明:
按照假设，会访问"google.mail.com" 900次，"yahoo.com" 50次，
"intel.mail.com" 1次，"wiki.org" 5次。
而对于父域名，会访问"mail.com" 900+1 = 901次，"com" 900 + 50 + 1 = 951次，和 "org" 5 次。
注意事项：
cpdomains 的长度小于 100。
每个域名的长度小于100。
每个域名地址包含一个或两个"."符号。
输入中任意一个域名的访问次数都小于10000。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历-哈希辅助 | O(n) | O(n) |
| 02 | 遍历-哈希辅助 | O(n) | O(n) |
func subdomainVisits(cpdomains []string) []string {
m := make(map[string]int)
for _, domains := range cpdomains {
domain, count := parse(domains)
isNew := true
for isNew {
m[domain] = m[domain] + count
domain, isNew = cut(domain)
}
}
return getResult(m)
}
func parse(s string) (string, int) {
ss := strings.Split(s, " ")
count, _ := strconv.Atoi(ss[0])
return ss[1], count
}
func cut(s string) (string, bool) {
index := strings.Index(s, ".")
if index == -1 {
return "", false
}
return s[index+1:], true
}
func getResult(m map[string]int) []string {
res := make([]string, 0, len(m))
for k, v := range m {
res = append(res, fmt.Sprintf("%d %s", v, k))
}
return res
}
#
func subdomainVisits(cpdomains []string) []string {
m := make(map[string]int)
for _, domains := range cpdomains {
arr := strings.Split(domains, " ")
count, _ := strconv.Atoi(arr[0])
tempArr := getSubdomains(arr[1])
for i := 0; i < len(tempArr); i++ {
m[tempArr[i]] += count
}
}
res := make([]string, 0)
for k, v := range m {
res = append(res, strconv.Itoa(v)+" "+k)
}
return res
}
func getSubdomains(s string) []string {
res := make([]string, 0)
for i := len(s) - 1; i >= 0; i-- {
if s[i] == '.' {
res = append(res, s[i+1:])
}
}
res = append(res, s)
return res
}
812.最大三角形面积(2)¶
题目
给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
示例:输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]] 输出: 2
解释: 这五个点如下图所示。组成的橙色三角形是最大的，面积为2。
注意:
3 <= points.length <= 50.
不存在重复的点。
-50 <= points[i][j] <= 50.
结果误差值在 10^-6 以内都认为是正确答案。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法-鞋带公式 | O(n^3) | O(1) |
| 02 | 暴力法-海伦公式 | O(n^3) | O(1) |
func largestTriangleArea(points [][]int) float64 {
maxArea := 0.0
n := len(points)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
if area(points[i], points[j], points[k]) > maxArea {
maxArea = area(points[i], points[j], points[k])
}
}
}
}
return maxArea
}
// 三角形面积=|(x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1)|/2
func area(p1, p2, p3 []int) float64 {
return abs(
p1[0]*p2[1]+p2[0]*p3[1]+p3[0]*p1[1]-
p1[0]*p3[1]-p2[0]*p1[1]-p3[0]*p2[1]) / 2
}
func abs(num int) float64 {
if num < 0 {
num = -num
}
return float64(num)
}
#
func largestTriangleArea(points [][]int) float64 {
maxArea := 0.0
n := len(points)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
// p = (a+b+c)/2
// s = p*(p-a)*(p-b)*(p-c)
a := length(points[i], points[j])
b := length(points[i], points[k])
c := length(points[j], points[k])
p := (a + b + c) / 2
area := math.Sqrt(p * (p - a) * (p - b) * (p - c))
if area > maxArea {
maxArea = area
}
}
}
}
return maxArea
}
// 求两点距离
func length(p1, p2 []int) float64 {
l := (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
return math.Sqrt(float64(l))
}
819.最常见的单词(2)¶
题目
给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。
题目保证至少有一个词不在禁用列表中，而且答案唯一。
禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。
示例：输入:
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
输出: "ball"
解释:
"hit" 出现了3次，但它是一个禁用的单词。
"ball" 出现了2次 (同时没有其他单词出现2次)，所以它是段落里出现次数最多的，且不在禁用列表中的单词。
注意，所有这些单词在段落里不区分大小写，标点符号需要忽略（即使是紧挨着单词也忽略， 比如 "ball,"），
"hit"不是最终的答案，虽然它出现次数更多，但它在禁用单词列表中。
提示：
1 <= 段落长度 <= 1000
0 <= 禁用单词个数 <= 100
1 <= 禁用单词长度 <= 10
答案是唯一的, 且都是小写字母 (即使在 paragraph 里是大写的，即使是一些特定的名词，答案都是小写的。)
paragraph 只包含字母、空格和下列标点符号!?',;.
不存在没有连字符或者带有连字符的单词。
单词里只包含字母，不会出现省略号或者其他标点符号。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助遍历+内置函数 | O(n) | O(n) |
| 02 | 哈希辅助遍历 | O(n) | O(n) |
func mostCommonWord(paragraph string, banned []string) string {
isBanned := make(map[string]bool)
for _, b := range banned {
isBanned[b] = true
}
chars := []string{"!", "?", ",", "'", ";", "."}
for _, c := range chars {
paragraph = strings.Replace(paragraph, c, " ", -1)
}
p := strings.ToLower(paragraph)
ss := strings.Fields(p)
count := make(map[string]int)
for _, v := range ss {
if isBanned[v] {
continue
}
count[v]++
}
res := ""
max := 0
for s, c := range count {
if max < c {
max = c
res = s
}
}
return res
}
#
func mostCommonWord(paragraph string, banned []string) string {
isBanned := make(map[string]bool)
for _, b := range banned {
isBanned[b] = true
}
count := make(map[string]int)
length := len(paragraph)
for i := 0; i < length; i++ {
for i < length && !isChar(paragraph[i]) {
i++
}
j := i
temp := ""
for ; j < length; j++ {
if !isChar(paragraph[j]) {
break
}
if paragraph[j] >= 'A' && paragraph[j] <= 'Z' {
temp = temp + string(paragraph[j]-'A'+'a')
} else {
temp = temp + string(paragraph[j])
}
}
i = j
if isBanned[temp] {
continue
}
count[temp]++
}
res := ""
max := 0
for s, c := range count {
if max < c {
max = c
res = s
}
}
return res
}
func isChar(b byte) bool {
if (b >= 'a' && b <= 'z') || (b >= 'A' && b <= 'Z') {
return true
}
return false
}
821.字符的最短距离(3)¶
题目
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
示例 1:输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
说明:
字符串 S 的长度范围为 [1, 10000]。
C 是一个单字符，且保证是字符串 S 里的字符。
S 和 C 中的所有字母均为小写字母。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 双指针遍历 | O(n) | O(1) |
| 02 | 遍历-往两边找 | O(n^2) | O(1) |
| 03 | 遍历-数组辅助 | O(n^2) | O(n) |
func shortestToChar(S string, C byte) []int {
n := len(S)
res := make([]int, n)
for i := range res {
res[i] = 100001
}
left, right := -n, 2*n
for i := 0; i < n; i++ {
j := n - i - 1
if S[i] == C {
left = i
}
if S[j] == C {
right = j
}
// i从0->n-1 跟左边的C比较得到最近的距离
// j从n-1->0 跟右边的C比较得到最近的距离
res[i] = min(res[i], dist(i, left))
res[j] = min(res[j], dist(j, right))
}
return res
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func dist(i, j int) int {
if i > j {
return i - j
}
return j - i
}
#
func shortestToChar(S string, C byte) []int {
n := len(S)
res := make([]int, n)
for i := 0; i < n; i++ {
if S[i] == C {
res[i] = 0
continue
}
min := n
for j := i + 1; j < n; j++ {
if S[j] == C {
if min > j-i {
min = j - i
}
break
}
}
for j := i - 1; j >= 0; j-- {
if S[j] == C {
if min > i-j {
min = i - j
}
break
}
}
res[i] = min
}
return res
}
#
func shortestToChar(S string, C byte) []int {
n := len(S)
res := make([]int, n)
arr := make([]int, 0)
for i := 0; i < len(S); i++ {
if S[i] == C {
arr = append(arr, i)
}
}
for i := 0; i < n; i++ {
min := n
for _, value := range arr {
if value == i {
min = 0
break
}
if min > dist(i, value) {
min = dist(i, value)
}
}
res[i] = min
}
return res
}
func dist(i, j int) int {
if i > j {
return i - j
}
return j - i
}
824.山羊拉丁文(2)¶
题目
给定一个由空格分割单词的句子 S。每个单词只包含大写或小写字母。
我们要将句子转换为 “Goat Latin”（一种类似于 猪拉丁文 - Pig Latin 的虚构语言）。
山羊拉丁文的规则如下：
如果单词以元音开头（a, e, i, o, u），在单词后添加"ma"。
例如，单词"apple"变为"applema"。
如果单词以辅音字母开头（即非元音字母），移除第一个字符并将它放到末尾，之后再添加"ma"。
例如，单词"goat"变为"oatgma"。
根据单词在句子中的索引，在单词最后添加与索引相同数量的字母'a'，索引从1开始。
例如，在第一个单词后添加"a"，在第二个单词后添加"aa"，以此类推。
返回将 S 转换为山羊拉丁文后的句子。
示例 1:输入: "I speak Goat Latin"
输出: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"
示例 2:输入: "The quick brown fox jumped over the lazy dog"
输出: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa
azylmaaaaaaaaa ogdmaaaaaaaaaa"
说明:
S 中仅包含大小写字母和空格。单词间有且仅有一个空格。
1 <= S.length <= 150。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 内置函数 | O(n) | O(n) |
| 02 | 遍历 | O(n) | O(n) |
func toGoatLatin(S string) string {
ss := strings.Split(S, " ")
for i := range ss {
ss[i] = handle(ss[i], i)
}
return strings.Join(ss, " ")
}
func handle(s string, i int) string {
postfix := "ma" + strings.Repeat("a", i+1)
if isBeginWithVowel(s) {
return s + postfix
}
return s[1:] + s[0:1] + postfix
}
func isBeginWithVowel(s string) bool {
switch s[0] {
case 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U':
return true
default:
return false
}
}
#
func toGoatLatin(S string) string {
res := ""
begin := 1
count := 1
temp := ""
for i := 0; i < len(S); i++ {
if S[i] == ' ' {
res = res + temp + strings.Repeat("a", count) + " "
count++
begin = 1
} else {
if begin == 1 {
begin = 0
if isBeginWithVowel(S[i]) {
res = res + string(S[i])
temp = "ma"
} else {
temp = string(S[i]) + "ma"
}
} else {
res = res + string(S[i])
}
}
}
return res + temp + strings.Repeat("a", count)
}
func isBeginWithVowel(b byte) bool {
switch b {
case 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U':
return true
default:
return false
}
}
830.较大分组的位置(2)¶
题目
在一个由小写字母构成的字符串 S 中，包含由一些连续的相同字符所构成的分组。
例如，在字符串 S = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。
我们称所有包含大于或等于三个连续字符的分组为较大分组。找到每一个较大分组的起始和终止位置。
最终结果按照字典顺序输出。
示例 1:输入: "abbxxxxzzy"输出: [[3,6]]
解释: "xxxx" 是一个起始于 3 且终止于 6 的较大分组。
示例 2:输入: "abc"输出: []
解释: "a","b" 和 "c" 均不是符合要求的较大分组。
示例 3:输入: "abcdddeeeeaabbbcd"输出: [[3,5],[6,9],[12,14]]
说明: 1 <= S.length <= 1000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 双指针 | O(n) | O(1) |
| 02 | 双指针 | O(n) | O(1) |
func largeGroupPositions(S string) [][]int {
res := make([][]int, 0, len(S)/3)
left := 0
for right := 0; right < len(S); right++ {
if right == len(S)-1 || S[right] != S[right+1] {
if right-left+1 >= 3 {
res = append(res, []int{left, right})
}
left = right + 1
}
}
return res
}
#
func largeGroupPositions(S string) [][]int {
res := make([][]int, 0, len(S)/3)
left, right := 0, 1
for ; right < len(S); right++ {
if S[left] != S[right] {
left = right
continue
}
if right-left+1 == 3 {
res = append(res, []int{left, right})
} else if right-left+1 > 3 {
res[len(res)-1][1] = right
}
}
return res
}
832.翻转图像(2)¶
题目
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
示例 1:
输入: [[1,1,0],[1,0,1],[0,0,0]]
输出: [[1,0,0],[0,1,0],[1,1,1]]
解释: 首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]
示例 2:
输入: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解释: 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
说明:
1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历+双指针 | O(n^2) | O(1) |
| 02 | 遍历 | O(n^2) | O(1) |
func flipAndInvertImage(A [][]int) [][]int {
for k := 0; k < len(A); k++ {
i, j := 0, len(A[k])-1
for i < j {
A[k][i], A[k][j] = invert(A[k][j]), invert(A[k][i])
i++
j--
}
if i == j {
A[k][i] = invert(A[k][i])
}
}
return A
}
func invert(i int) int {
if i == 0 {
return 1
}
return 0
}
#
func flipAndInvertImage(A [][]int) [][]int {
for k := 0; k < len(A); k++ {
i, j := 0, len(A[k])-1
for i < j {
A[k][i], A[k][j] = A[k][j], A[k][i]
i++
j--
}
for i := 0; i < len(A[k]); i++ {
A[k][i] = A[k][i] ^ 1
}
}
return A
}
836.矩形重叠(3)¶
题目
矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形，判断它们是否重叠并返回结果。
示例 1：输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3] 输出：true
示例 2：输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1] 输出：false
提示：
两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。
矩形中的所有坐标都处于 -10^9 和 10^9 之间。
x 轴默认指向右，y 轴默认指向上。
你可以仅考虑矩形是正放的情况。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 正面条件判断 | O(1) | O(1) |
| 02 | 不满足条件判断 | O(1) | O(1) |
| 03 | 投影 | O(1) | O(1) |
func isRectangleOverlap(rec1 []int, rec2 []int) bool {
// 满足条件
if rec1[1] < rec2[3] && rec1[0] < rec2[2] &&
rec2[1] < rec1[3] && rec2[0] < rec1[2] {
return true
}
return false
}
#
func isRectangleOverlap(rec1 []int, rec2 []int) bool {
// 不满足条件, rec2固定，rec1在rec2的方位
// 左侧：rec1[2] <= rec2[0]
// 右侧：rec1[0] >= rec2[2]
// 上方：rec1[1] >= rec2[3]
// 下方：rec1[3] <= rec2[1]
if rec1[2] <= rec2[0] ||
rec1[3] <= rec2[1] ||
rec1[0] >= rec2[2] ||
rec1[1] >= rec2[3] {
return false
}
return true
}
#
func isRectangleOverlap(rec1 []int, rec2 []int) bool {
return min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]) &&
min(rec1[3], rec2[3]) > max(rec1[1], rec2[1])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
840.矩阵中的幻方(2)¶
题目
3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，
其中每行，每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
示例：输入: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
输出: 1
解释:
下面的子矩阵是一个 3 x 3 的幻方：
438
951
276
而这一个不是：
384
519
762
总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
提示:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法 | O(n^2) | O(1) |
| 02 | 暴力法-打表 | O(n^2) | O(1) |
func numMagicSquaresInside(grid [][]int) int {
m, n := len(grid), len(grid[0])
res := 0
for i := 0; i+2 < m; i++ {
for j := 0; j+2 < n; j++ {
if grid[i+1][j+1] != 5{
continue
}
if !available(i, j, grid) {
continue
}
if grid[i][j]+grid[i][j+1]+grid[i][j+2] == 15 &&
grid[i+1][j]+grid[i+1][j+1]+grid[i+1][j+2] == 15 &&
grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2] == 15 &&
grid[i][j]+grid[i+1][j]+grid[i+2][j] == 15 &&
grid[i][j+1]+grid[i+1][j+1]+grid[i+2][j+1] == 15 &&
grid[i][j+2]+grid[i+1][j+2]+grid[i+2][j+2] == 15 &&
grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2] == 15 &&
grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j] == 15 {
res++
}
}
}
return res
}
func available(x, y int, g [][]int) bool {
tmp := [16]int{}
for i := x; i <= x+2; i++ {
for j := y; j <= y+2; j++ {
tmp[g[i][j]]++
}
}
for i := 1; i <= 9; i++ {
if tmp[i] != 1 {
return false
}
}
return true
}
#
func numMagicSquaresInside(grid [][]int) int {
m, n := len(grid), len(grid[0])
res := 0
for i := 0; i+2 < m; i++ {
for j := 0; j+2 < n; j++ {
if grid[i+1][j+1] != 5 {
continue
}
if available(i, j, grid) {
res++
}
}
}
return res
}
var m = map[string]bool{
"816357492": true,
"834159672": true,
"618753294": true,
"672159834": true,
"492357816": true,
"438951276": true,
"294753618": true,
"276951438": true,
}
func available(x, y int, g [][]int) bool {
str := ""
for i := x; i <= x+2; i++ {
for j := y; j <= y+2; j++ {
str = str + strconv.Itoa(g[i][j])
}
}
if m[str] {
return true
}
return false
}
844.比较含退格的字符串(2)¶
题目
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。
# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：输入：S = "ab#c", T = "ad#c"输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：输入：S = "ab##", T = "c#d#"输出：true
解释：S 和 T 都会变成 “”。
示例 3：输入：S = "a##c", T = "#a#c"输出：true
解释：S 和 T 都会变成 “c”。
示例 4：输入：S = "a#c", T = "b" 输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。
提示：
1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 '#'。
进阶：
你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历-数组模拟栈操作 | O(n) | O(n) |
| 02 | 遍历-从后往前 | O(n) | O(n) |
func backspaceCompare(S string, T string) bool {
return check(S) == check(T)
}
func check(str string) string {
res := make([]string, 0)
for _, v := range str {
if string(v) == "#" {
if len(res) != 0 {
res = res[:len(res)-1]
}
} else {
res = append(res, string(v))
}
}
return strings.Join(res, "")
}
#
func backspaceCompare(S string, T string) bool {
return check(S) == check(T)
}
func check(S string) string {
str := ""
count := 0
for i := len(S) - 1; i >= 0; i-- {
if S[i] == '#' {
count++
} else {
if count != 0 {
count--
continue
}
str = string(S[i]) + str
}
}
return str
}
849.到最近的人的最大距离(4)¶
题目
在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。
至少有一个空座位，且至少有一人坐在座位上。
亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。
返回他到离他最近的人的最大距离。
示例 1：输入：[1,0,0,0,1,0,1]输出：2
解释：如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。
如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。
因此，他到离他最近的人的最大距离是 2 。
示例 2：输入：[1,0,0,0]输出：3
解释： 如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。
这是可能的最大距离，所以答案是 3 。
提示：
1 <= seats.length <= 20000
seats 中只含有 0 和 1，至少有一个 0，且至少有一个 1。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历-数组辅助 | O(n) | O(n) |
| 02 | 遍历-双指针 | O(n) | I |
| 03 | 遍历 | O(n) | O(n) |
| 04 | 遍历 | O(n) | O(1) |
func maxDistToClosest(seats []int) int {
n := len(seats)
left := make([]int, n)
right := make([]int, n)
for i := 0; i < n; i++ {
left[i], right[i] = n, n
}
for i := 0; i < n; i++ {
if seats[i] == 1 {
left[i] = 0
} else if seats[i] != 1 && i > 0 {
left[i] = left[i-1] + 1
}
}
for i := n - 1; i >= 0; i-- {
if seats[i] == 1 {
right[i] = 0
} else if seats[i] != 1 && i < n-1 {
right[i] = right[i+1] + 1
}
}
res := 0
for i := 0; i < n; i++ {
if seats[i] == 0 {
if min(left[i], right[i]) > res {
res = min(left[i], right[i])
}
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
#
func maxDistToClosest(seats []int) int {
n := len(seats)
res := 0
left := -1
right := 0
for i := 0; i < n; i++ {
if seats[i] == 1 {
left = i
} else {
// 找到右边有人的位置
for (right < n && seats[right] == 0) || right < i {
right++
}
leftLen := 0
rightLen := 0
if left == -1 {
leftLen = n
} else {
leftLen = i - left
}
if right == n {
rightLen = n
} else {
rightLen = right - i
}
if min(leftLen, rightLen) > res {
res = min(leftLen, rightLen)
}
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
#
func maxDistToClosest(seats []int) int {
n := len(seats)
var arr []int
for i := 0; i < n; i++ {
if seats[i] == 1 {
arr = append(arr, i)
}
}
if len(arr) == 0 {
return 0
}
max := -1
for i := 0; i < n-1; i++ {
if arr[i+1]-arr[i] > max {
max = arr[i+1] - arr[i]
}
}
max = max / 2
// 判断首尾
if arr[0] > max {
max = arr[0]
}
if n-arr[len(arr)-1]-1 > max {
max = n - arr[len(arr)-1] - 1
}
return max
}
#
func maxDistToClosest(seats []int) int {
res := 0
count := 0
for i := 0; i < len(seats); i++ {
if count == i {
res = count
} else {
res = max(res, (count+count%2)/2)
}
if seats[i] == 1 {
count = 0
} else {
count++
}
}
return max(res, count)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
852.山脉数组的峰顶索引(3)¶
题目
我们把符合下列属性的数组 A 称作山脉：
A.length >= 3
存在 0 < i < A.length - 1 使得
A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
给定一个确定为山脉的数组，返回任何满足
A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。
示例 1：输入：[0,1,0]输出：1
示例 2：输入：[0,2,1,0]输出：1
提示：
3 <= A.length <= 10000
0 <= A[i] <= 10^6
A 是如上定义的山脉
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 二分查找 | O(log(n)) | O(1) |
| 03 | 内置函数 | O(log(n)) | O(1) |
func peakIndexInMountainArray(A []int) int {
n := len(A)
for i := 0; i < n-1; i++ {
if A[i] > A[i+1] {
return i
}
}
return 0
}
#
func peakIndexInMountainArray(A []int) int {
left, right := 0, len(A)-1
for {
mid := left + (right-left)/2
if A[mid] > A[mid+1] && A[mid] > A[mid-1] {
return mid
}
if A[mid] > A[mid-1] {
left = mid + 1
} else {
right = mid
}
}
}
# 3
func peakIndexInMountainArray(arr []int) int {
n := len(arr)
return sort.Search(n-1, func(i int) bool {
return arr[i] > arr[i+1]
})
}
859.亲密字符串(2)¶
题目
给定两个由小写字母构成的字符串 A 和 B ，只要我们可以通过交换 A 中的两个字母得到与 B 相等的结果，
就返回 true ；否则返回 false 。
示例 1： 输入： A = "ab", B = "ba" 输出： true
示例 2： 输入： A = "ab", B = "ab"输出： false
示例 3: 输入： A = "aa", B = "aa" 输出： true
示例 4： 输入： A = "aaaaaaabc", B = "aaaaaaacb" 输出： true
示例 5： 输入： A = "", B = "aa" 输出： false
提示：
0 <= A.length <= 20000
0 <= B.length <= 20000
A 和 B 仅由小写字母构成。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 遍历 | O(n) | O(1) |
func buddyStrings(A string, B string) bool {
if len(A) != len(B) {
return false
}
if A == B {
return hasDouble(A)
}
count := 2
strA, strB := "", ""
i := 0
for ; count > 0 && i < len(A); i++ {
if A[i] != B[i] {
strA = string(A[i]) + strA
strB = strB + string(B[i])
count--
}
}
return count == 0 && strA == strB && A[i:] == B[i:]
}
func hasDouble(s string) bool {
seen := [26]bool{}
for i := range s {
b := s[i] - 'a'
if seen[b] {
return true
}
seen[b] = true
}
return false
}
#
func buddyStrings(A string, B string) bool {
if len(A) != len(B) {
return false
}
if A == B {
return hasDouble(A)
}
first := -1
second := -1
for i := 0; i < len(A); i++ {
if A[i] != B[i] {
if first == -1 {
first = i
} else if second == -1 {
second = i
} else {
return false
}
}
}
return A[first] == B[second] && A[second] == B[first]
}
func hasDouble(s string) bool {
seen := [26]int{}
for i := range s {
b := s[i] - 'a'
if seen[b] >= 1 {
return true
}
seen[b] = 1
}
return false
}
860.柠檬水找零(1)¶
题目
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。
你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：输入：[5,5,5,10,20] 输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：输入：[5,5,10] 输出：true
示例 3：输入：[10,10] 输出：false
示例 4：输入：[5,5,10,10,20] 输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
0 <= bills.length <= 10000
bills[i] 不是 5 就是 10 或是 20
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历+模拟 | O(n) | O(1) |
func lemonadeChange(bills []int) bool {
fives, tens := 0, 0
for _, b := range bills {
switch b {
case 5:
fives++
case 10:
fives--
tens++
case 20:
if tens > 0 {
tens--
fives--
} else {
fives = fives - 3
}
}
if fives < 0 || tens < 0 {
return false
}
}
return true
}
867.转置矩阵(1)¶
题目
给定一个矩阵 A， 返回 A 的转置矩阵。
矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。
示例 1：输入：[[1,2,3],[4,5,6],[7,8,9]]输出：[[1,4,7],[2,5,8],[3,6,9]]
示例 2：输入：[[1,2,3],[4,5,6]]输出：[[1,4],[2,5],[3,6]]
提示：
1 <= A.length <= 1000
1 <= A[0].length <= 1000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(n^2) |
func transpose(A [][]int) [][]int {
m, n := len(A), len(A[0])
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, m)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
res[j][i] = A[i][j]
}
}
return res
}
868.二进制间距(3)¶
题目
给定一个正整数 N，找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。
如果没有两个连续的 1，返回 0 。
示例 1：输入：22 输出：2
解释：22 的二进制是 0b10110 。
在 22 的二进制表示中，有三个 1，组成两对连续的 1 。
第一对连续的 1 中，两个 1 之间的距离为 2 。
第二对连续的 1 中，两个 1 之间的距离为 1 。
答案取两个距离之中最大的，也就是 2 。
示例 2：输入：5 输出：2
解释：5 的二进制是 0b101 。
示例 3：输入：6 输出：1
解释： 6 的二进制是 0b110 。
示例 4：输入：8 输出：0
解释： 8 的二进制是 0b1000 。
在 8 的二进制表示中没有连续的 1，所以返回 0 。
提示：1 <= N <= 10^9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历-数组辅助 | O(log(n)) | O(log(n)) |
| 02 | 遍历 | O(log(n)) | O(1) |
| 03 | 遍历-内置函数 | O(log(n)) | O(log(n)) |
func binaryGap(N int) int {
arr := make([]int, 0)
index := 0
for N > 0 {
if N%2 == 1 {
arr = append(arr, index)
}
index++
N = N / 2
}
res := 0
for i := 0; i < len(arr)-1; i++ {
if arr[i+1]-arr[i] > res {
res = arr[i+1] - arr[i]
}
}
return res
}
#
func binaryGap(N int) int {
res := 0
count := 0
for N > 0 {
if N%2 == 1 {
if count > res {
res = count
}
count = 1
} else if count > 0 {
count++
}
N = N / 2
}
return res
}
#
func binaryGap(N int) int {
res := 0
str := strconv.FormatInt(int64(N), 2)
j := -1
for i := 0; i < len(str); i++ {
if str[i] == '1' {
if j == -1 {
j = i
} else {
if i-j > res {
res = i - j
}
j = i
}
}
}
return res
}
872.叶子相似的树(2)¶
题目
请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个叶值序列 。
举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
提示：
给定的两颗树可能会有 1 到 200 个结点。
给定的两颗树上的值介于 0 到 200 之间。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(n) | O(log(n)) |
| 02 | 迭代 | O(n) | O(n) |
var a1, a2 []int
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
a1 = make([]int, 0)
a2 = make([]int, 0)
dfs(root1, &a1)
dfs(root2, &a2)
if len(a1) != len(a2) {
return false
}
for i := 0; i < len(a1); i++ {
if a1[i] != a2[i] {
return false
}
}
return true
}
func dfs(root *TreeNode, arr *[]int) {
if root != nil {
if root.Left == nil && root.Right == nil {
*arr = append(*arr, root.Val)
return
}
dfs(root.Left, arr)
dfs(root.Right, arr)
}
}
#
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
a1 := make([]int, 0)
a2 := make([]int, 0)
bfs(root1, &a1)
bfs(root2, &a2)
if len(a1) != len(a2) {
return false
}
for i := 0; i < len(a1); i++ {
if a1[i] != a2[i] {
return false
}
}
return true
}
func bfs(root *TreeNode, arr *[]int) {
stack := make([]*TreeNode, 0)
stack = append(stack, root)
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if node.Left == nil && node.Right == nil {
*arr = append(*arr, node.Val)
}
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
}
874.模拟行走机器人(2)¶
题目
机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：
-2：向左转 90 度
-1：向右转 90 度
1 <= x <= 9：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物。
第 i 个障碍物位于网格点 (obstacles[i][0], obstacles[i][1])
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。
返回从原点到机器人的最大欧式距离的平方。
示例 1：输入: commands = [4,-1,3], obstacles = [] 输出: 25
解释: 机器人将会到达 (3, 4)
示例 2：输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]] 输出: 65
解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处
提示：
0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
答案保证小于 2 ^ 31
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历-模拟 | O(n) | O(n) |
| 02 | 遍历-模拟 | O(n) | O(n) |
// 上、右、下、左
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func robotSim(commands []int, obstacles [][]int) int {
i := 0 // 方向， 0上， 1右， 2下， 3左
x := 0
y := 0
res := 0
m := map[string]bool{}
for _, v := range obstacles {
str := strconv.Itoa(v[0]) + "," + strconv.Itoa(v[1])
m[str] = true
}
for _, v := range commands {
if v == -2 {
i = (i + 3) % 4 // 左转
} else if v == -1 {
i = (i + 1) % 4 // 右转
} else {
for v > 0 {
ddx := x + dx[i]
ddy := y + dy[i]
tp := strconv.Itoa(ddx) + "," + strconv.Itoa(ddy)
if _, ok := m[tp]; ok {
// 有障碍物，停止
break
} else {
x = ddx
y = ddy
if x*x+y*y > res {
res = x*x + y*y
}
}
v--
}
}
}
return res
}
#
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func robotSim(commands []int, obstacles [][]int) int {
m := make(map[string]bool, 10000)
for _, o := range obstacles {
i, j := o[0], o[1]
m[encode(i, j)] = true
}
x, y, res := 0, 0, 0
index := 0
for _, c := range commands {
index = (index + 4) % 4
switch {
case c == -2:
index--
case c == -1:
index++
default:
dx1, dy1 := dx[index], dy[index]
for c > 0 && !m[encode(x+dx1, y+dy1)] {
c--
x = x + dx1
y = y + dy1
}
if x*x+y*y > res {
res = x*x + y*y
}
}
}
return res
}
func encode(x, y int) string {
return strconv.Itoa(x) + "," + strconv.Itoa(y)
}
876.链表的中间结点(3)¶
题目
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 快慢指针 | O(n) | O(1) |
| 02 | 数组辅助 | O(n) | O(n) |
| 03 | 遍历统计 | O(n) | O(1) |
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
#
func middleNode(head *ListNode) *ListNode {
res := make([]*ListNode, 0)
for head != nil {
res = append(res, head)
head = head.Next
}
return res[len(res)/2]
}
#
func middleNode(head *ListNode) *ListNode {
count := 0
temp := head
for temp != nil {
count++
temp = temp.Next
}
mid := count / 2
for head != nil {
if mid == 0 {
return head
}
head = head.Next
mid--
}
return head
}
883.三维形体投影面积(2)¶
题目
在 N * N 的网格中，我们放置了一些与 x，y，z 三轴对齐的 1 * 1 * 1 立方体。
每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。
现在，我们查看这些立方体在 xy、yz 和 zx 平面上的投影。
投影就像影子，将三维形体映射到一个二维平面上。
在这里，从顶部、前面和侧面看立方体时，我们会看到“影子”。
返回所有三个投影的总面积。
示例 1：输入：[[2]] 输出：5
示例 2：输入：[[1,2],[3,4]] 输出：17
解释： 这里有该形体在三个轴对齐平面上的三个投影(“阴影部分”)。
示例 3：输入：[[1,0],[0,2]] 输出：8
示例 4：输入：[[1,1,1],[1,0,1],[1,1,1]] 输出：14
示例 5：输入：[[2,2,2],[2,1,2],[2,2,2]] 输出：21
提示：
1 <= grid.length = grid[0].length <= 50
0 <= grid[i][j] <= 50
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(1) |
| 02 | 遍历 | O(n^2) | O(1) |
// 1.xy面，grid[i][j]>0的个数累加
// 2.xz面, 行的最大值累加
// 3.yz面, 列的最大值累加
func projectionArea(grid [][]int) int {
yz := [51]int{}
xz := [51]int{}
res := 0
for i, line := range grid {
for j, k := range line {
if k == 0 {
continue
}
res++
yz[i] = max(yz[i], k)
xz[j] = max(xz[j], k)
}
}
for i := range yz {
res = res + yz[i] + xz[i]
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
#
func projectionArea(grid [][]int) int {
res := 0
for i := 0; i < len(grid); i++ {
yz := 0
xz := 0
// 每一行最大值之和，每一列最大值之和
for j := 0; j < len(grid); j++ {
if grid[i][j] > 0 {
res++
}
if yz < grid[i][j] {
yz = grid[i][j]
}
if xz < grid[j][i] {
xz = grid[j][i]
}
}
res = res + yz + xz
}
return res
}
884.两句话中的不常见单词(2)¶
题目
给定两个句子 A 和 B 。 （句子是一串由空格分隔的单词。每个单词仅由小写字母组成。）
如果一个单词在其中一个句子中只出现一次，在另一个句子中却没有出现，那么这个单词就是不常见的。
返回所有不常用单词的列表。
您可以按任何顺序返回列表。
示例 1：输入：A = "this apple is sweet", B = "this apple is sour"输出：["sweet","sour"]
示例 2：输入：A = "apple apple", B = "banana"输出：["banana"]
提示：
0 <= A.length <= 200
0 <= B.length <= 200
A 和 B 都只包含空格和小写字母。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助+内置函数 | O(n) | O(n) |
| 02 | 哈希辅助+遍历 | O(n) | O(n) |
func uncommonFromSentences(A string, B string) []string {
m := map[string]int{}
arrA := strings.Fields(A)
arrB := strings.Fields(B)
for _, v := range arrA {
m[v]++
}
for _, v := range arrB {
m[v]++
}
res := make([]string, 0)
for k, v := range m {
if v == 1 {
res = append(res, k)
}
}
return res
}
#
func uncommonFromSentences(A string, B string) []string {
m := map[string]int{}
A = A + " " + B + " "
j := 0
for i := 0; i < len(A); i++ {
if A[i] == ' ' {
m[A[j:i]]++
j = i + 1
}
}
res := make([]string, 0)
for k, v := range m {
if v == 1 {
res = append(res, k)
}
}
return res
}
888.公平的糖果交换(2)¶
题目
爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 块糖的大小，B[j] 是鲍勃拥有的第 j 块糖的大小。
因为他们是朋友，所以他们想交换一个糖果棒，这样交换后，他们都有相同的糖果总量。
（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）
返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是 Bob 必须交换的糖果棒的大小。
如果有多个答案，你可以返回其中任何一个。保证答案存在。
示例 1：输入：A = [1,1], B = [2,2] 输出：[1,2]
示例 2：输入：A = [1,2], B = [2,3] 输出：[1,2]
示例 3：输入：A = [2], B = [1,3] 输出：[2,3]
示例 4：输入：A = [1,2,5], B = [2,4] 输出：[5,4]
提示：
1 <= A.length <= 10000
1 <= B.length <= 10000
1 <= A[i] <= 100000
1 <= B[i] <= 100000
保证爱丽丝与鲍勃的糖果总量不同。
答案肯定存在。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历+哈希辅助 | O(n) | O(n) |
| 02 | 暴力法 | O(n^2) | O(1) |
func fairCandySwap(A []int, B []int) []int {
m := make(map[int]bool)
sumA := 0
sumB := 0
for _, v := range A {
sumA = sumA + v
m[v] = true
}
for _, v := range B {
sumB = sumB + v
}
half := (sumA - sumB) / 2
a, b := 0, 0
// sumA-A[i]+B[j] == sumB-B[j]+A[i]
// sumA-sumB=2(A[i]-B[j])
// (sumA-sumB)/2 = A[i]-B[j]
for _, b = range B {
a = b + half
if m[a] == true {
return []int{a, b}
}
}
return nil
}
#
func fairCandySwap(A []int, B []int) []int {
sumA := 0
sumB := 0
for _, v := range A {
sumA = sumA + v
}
for _, v := range B {
sumB = sumB + v
}
for i := 0; i < len(A); i++ {
for j := 0; j < len(B); j++ {
if sumA-A[i]+B[j] == sumB-B[j]+A[i] {
return []int{A[i], B[j]}
}
}
}
return nil
}
892.三维形体的表面积(2)¶
题目
在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。
每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
请你返回最终形体的表面积。
示例 1：输入：[[2]] 输出：10
示例 2：输入：[[1,2],[3,4]] 输出：34
示例 3：输入：[[1,0],[0,2]] 输出：16
示例 4：输入：[[1,1,1],[1,0,1],[1,1,1]] 输出：32
示例 5：输入：[[2,2,2],[2,1,2],[2,2,2]]输出：46
提示：
1 <= N <= 50
0 <= grid[i][j] <= 50
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(1) |
| 02 | 遍历 | O(n^2) | O(1) |
// 第1步：总表面积是个数*6
// 第2步：同一位置，从2层以上开始，每升高一层，减少2个面
// 第3步：左右位置，每相邻一个，减少2个面
// 第4步：前后位置，每相邻一个，减少2个面
func surfaceArea(grid [][]int) int {
sum := 0
for i, rows := range grid {
for j := range rows {
sum = sum + grid[i][j]*6
if grid[i][j] > 1 {
sum = sum - (grid[i][j]-1)*2
}
if j > 0 {
sum = sum - min(grid[i][j], grid[i][j-1])*2
}
if i > 0 {
sum = sum - min(grid[i][j], grid[i-1][j])*2
}
}
}
return sum
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
#
// 上、右、下、左
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func surfaceArea(grid [][]int) int {
sum := 0
for i, rows := range grid {
for j := range rows {
sum = sum + grid[i][j]*6
if grid[i][j] > 1 {
sum = sum - (grid[i][j]-1)*2
}
for k := 0; k < 4; k++ {
x, y := i+dx[k], j+dy[k]
if x >= 0 && x < len(grid) && y >= 0 && y < len(grid[0]) {
sum = sum - min(grid[i][j], grid[x][y])
}
}
}
}
return sum
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
893.特殊等价字符串组(2)¶
题目
你将得到一个字符串数组 A。
如果经过任意次数的移动，S == T，那么两个字符串 S 和 T 是特殊等价的。
一次移动包括选择两个索引 i 和 j，且 i ％ 2 == j ％ 2，交换 S[j] 和 S [i]。
现在规定，A 中的特殊等价字符串组是 A 的非空子集 S，
这样不在 S 中的任何字符串与 S 中的任何字符串都不是特殊等价的。
返回 A 中特殊等价字符串组的数量。
示例 1：输入：["a","b","c","a","c","c"] 输出：3
解释：3 组 ["a","a"]，["b"]，["c","c","c"]
示例 2：输入：["aa","bb","ab","ba"] 输出：4
解释：4 组 ["aa"]，["bb"]，["ab"]，["ba"]
示例 3：输入：["abc","acb","bac","bca","cab","cba"] 输出：3
解释：3 组 ["abc","cba"]，["acb","bca"]，["bac","cab"]
示例 4：输入：["abcd","cdab","adcb","cbad"] 输出：1
解释：1 组 ["abcd","cdab","adcb","cbad"]
提示：
1 <= A.length <= 1000
1 <= A[i].length <= 20
所有 A[i] 都具有相同的长度。
所有 A[i] 都只由小写字母组成。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历+哈希辅助 | O(n) | O(n) |
| 02 | 遍历+哈希辅助 | O(n) | O(n) |
func numSpecialEquivGroups(A []string) int {
groups := make(map[[26]int]bool)
for _, a := range A {
count := [26]int{}
i := 0
for i = 0; i < len(A[0]); i++ {
count[a[i]-'a']++
if i%2 == 0 {
count[a[i]-'a'] += 1000
}
}
groups[count] = true
}
return len(groups)
}
#
func numSpecialEquivGroups(A []string) int {
groups := make(map[string]bool)
for _, a := range A {
odd := make([]byte, 0)
even := make([]byte, 0)
for i := 0; i < len(a); i++ {
if i%2 == 0 {
even = append(even, a[i]-'a')
} else {
odd = append(odd, a[i]-'a')
}
}
sort.Slice(odd, func(i, j int) bool {
return odd[i] < odd[j]
})
sort.Slice(even, func(i, j int) bool {
return even[i] < even[j]
})
groups[string(odd)+string(even)] = true
}
return len(groups)
}
896.单调数列(3)¶
题目
如果数组是单调递增或单调递减的，那么它是单调的。
如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。
如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。
当给定的数组 A 是单调数组时返回 true，否则返回 false。
示例 1：输入：[1,2,2,3]输出：true
示例 2：输入：[6,5,4,4]输出：true
示例 3：输入：[1,3,2]输出：false
示例 4：输入：[1,2,4,5]输出：true
示例 5：输入：[1,1,1]输出：true
提示：
1 <= A.length <= 50000
-100000 <= A[i] <= 100000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 遍历 | O(n) | O(1) |
| 03 | 遍历 | O(n) | O(1) |
func isMonotonic(A []int) bool {
toEnd := true
toFirst := true
for i := 0; i < len(A)-1; i++ {
if A[i] > A[i+1] {
toEnd = false
}
if A[i] < A[i+1] {
toFirst = false
}
}
return toEnd || toFirst
}
#
func isMonotonic(A []int) bool {
return inc(A) || desc(A)
}
func inc(A []int) bool {
for i := 0; i < len(A)-1; i++ {
if A[i] > A[i+1] {
return false
}
}
return true
}
func desc(A []int) bool {
for i := 0; i < len(A)-1; i++ {
if A[i] < A[i+1] {
return false
}
}
return true
}
#
func isMonotonic(A []int) bool {
if len(A) == 1 {
return true
}
temp := A[len(A)-1] - A[0]
for i := 0; i < len(A)-1; i++ {
if temp > 0 && A[i] > A[i+1] {
return false
} else if temp < 0 && A[i] < A[i+1] {
return false
} else if temp == 0 && A[i] != A[i+1] {
return false
}
}
return true
}
897.递增顺序查找树(3)¶
题目
给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，
并且每个结点没有左子结点，只有一个右子结点。
示例 ：输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9
提示：
给定树中的结点数介于 1 和 100 之间。
每个结点都有一个从 0 到 1000 范围内的唯一整数值。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归-数组辅助 | O(n) | O(n) |
| 02 | 递归 | O(n) | O(log(n)) |
| 03 | 迭代 | O(n) | O(n) |
func increasingBST(root *TreeNode) *TreeNode {
arr := make([]int, 0)
dfs(root, &arr)
if len(arr) == 0 {
return root
}
newRoot := &TreeNode{Val: arr[0]}
cur := newRoot
for i := 1; i < len(arr); i++ {
cur.Right = &TreeNode{Val: arr[i]}
cur = cur.Right
}
return newRoot
}
func dfs(node *TreeNode, arr *[]int) {
if node == nil {
return
}
dfs(node.Left, arr)
*arr = append(*arr, node.Val)
dfs(node.Right, arr)
}
#
var prev *TreeNode
func increasingBST(root *TreeNode) *TreeNode {
prev = &TreeNode{}
head := prev
dfs(root)
return head.Right
}
func dfs(node *TreeNode) {
if node == nil {
return
}
dfs(node.Left)
node.Left = nil
prev.Right = node
prev = node
dfs(node.Right)
}
#
func increasingBST(root *TreeNode) *TreeNode {
stack := make([]*TreeNode, 0)
newRoot := &TreeNode{}
stack = append(stack, root)
for len(stack) > 0 {
node := stack[len(stack)-1]
if node.Right != nil {
stack = append(stack, node.Right)
node.Right = nil
continue
}
stack = stack[:len(stack)-1]
node.Right = newRoot.Right
newRoot.Right = node
if node.Left != nil {
stack = append(stack, node.Left)
node.Left = nil
}
}
return newRoot.Right
}
0801-0900-Medium¶
801.使序列递增的最小交换次数(1)¶
题目
我们有两个长度相等且不为空的整型数组A和B。
我们可以交换A[i]和B[i]的元素。注意这两个元素在各自的序列中应该处于相同的位置。
在交换过一些元素之后，数组A和B都应该是严格递增的
（数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]）。
给定数组A和B，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。
示例:输入: A = [1,3,5,4], B = [1,2,3,7] 输出: 1
解释: 交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。
注意:A, B两个数组的长度总是相等的，且长度的范围为[1, 1000]。
A[i], B[i]均为[0, 2000]区间内的整数。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n) | O(n) |
func minSwap(A []int, B []int) int {
n := len(A)
dp := make([][2]int, n)
dp[0][0] = 0 // dp[i][0] 第i个位置不换
dp[0][1] = 1 // dp[i][1] 第i个位置换
for i := 1; i < n; i++ {
if A[i-1] < A[i] && B[i-1] < B[i] {
if A[i-1] < B[i] && B[i-1] < A[i] { // 可换可不换
dp[i][0] = min(dp[i-1][0], dp[i-1][1])
dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1
} else {
dp[i][0] = dp[i-1][0] // 不交换则上一轮也不交换
dp[i][1] = dp[i-1][1] + 1 // 交换则上一轮也交换
}
} else {
dp[i][0] = dp[i-1][1] // 不交换则上一轮必须交换
dp[i][1] = dp[i-1][0] + 1 // 交换，则上一轮不能交换
}
}
return min(dp[n-1][0], dp[n-1][1])
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
802.找到最终的安全状态(2)¶
题目
在有向图中，从某个节点和每个转向处开始出发，沿着图的有向边走。如果到达的节点是终点（即它没有连出的有向边），则停止。
如果从起始节点出发，最后必然能走到终点，就认为起始节点是 最终安全 的。
更具体地说，对于最终安全的起始节点而言，存在一个自然数 k ，无论选择沿哪条有向边行走 ，走了不到 k 步后必能停止在一个终点上。
返回一个由图中所有最终安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。
该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是graph的节点数。
图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。
示例 1：输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]] 输出：[2,4,5,6]
解释：示意图如上。
示例 2：输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] 输出：[4]
提示：n == graph.length
1 <= n <= 104
0 <= graph[i].legnth <= n
graph[i] 按严格递增顺序排列。
图中可能包含自环。
图中边的数目在范围 [1, 4 * 104] 内。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 拓扑排序 | O(n) | O(n) |
| 02 | 深度优先搜索 | O(n) | O(n) |
func eventualSafeNodes(graph [][]int) []int {
n := len(graph)
safeArr := make([]bool, n) // 安全节点
arr := make([][]int, n)
m := make(map[int]map[int]bool)
queue := make([]int, 0)
for i := 0; i < n; i++ {
m[i] = make(map[int]bool)
if len(graph[i]) == 0 { // 没有出节点，是安全节点
queue = append(queue, i)
}
for j := 0; j < len(graph[i]); j++ {
a, b := i, graph[i][j] // a=>b
arr[b] = append(arr[b], a) // 反向b=>a
m[a][b] = true // a=>b
}
}
res := make([]int, 0)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
safeArr[node] = true
for i := 0; i < len(arr[node]); i++ { // 反向边遍历
index := arr[node][i]
delete(m[index], node) // 删除
if len(m[index]) == 0 { // 没有出节点
queue = append(queue, index)
}
}
}
for i := 0; i < n; i++ {
if safeArr[i] == true {
res = append(res, i)
}
}
return res
}
# 2
func eventualSafeNodes(graph [][]int) []int {
n := len(graph)
visited := make([]int, n) // 0：未访问、1：在访问（有环）、2：安全
res := make([]int, 0)
for i := 0; i < n; i++ {
if dfs(graph, i, visited) == true {
res = append(res, i)
}
}
return res
}
func dfs(graph [][]int, index int, visited []int) bool {
if visited[index] > 0 {
return visited[index] == 2
}
visited[index] = 1
for i := 0; i < len(graph[index]); i++ {
next := graph[index][i]
if visited[next] == 1 || dfs(graph, next, visited) == false {
return false
}
}
visited[index] = 2
return true
}
807.保持城市天际线(1)¶
题目
在二维数组grid中，grid[i][j]代表位于某处的建筑物的高度。
我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。 高度 0 也被认为是建筑物。
最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。
城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。
建筑物高度可以增加的最大总和是多少？
例子：输入： grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] 输出： 35
解释： The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]
从数组竖直方向（即顶部，底部）看“天际线”是：[9, 4, 8, 7]
从水平水平方向（即左侧，右侧）看“天际线”是：[8, 7, 9, 3]
在不影响天际线的情况下对建筑物进行增高后，新数组如下：
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
说明: 1 < grid.length = grid[0].length <= 50。
grid[i][j] 的高度范围是： [0, 100]。
一座建筑物占据一个grid[i][j]：换言之，它们是 1 x 1 x grid[i][j] 的长方体。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(n) |
func maxIncreaseKeepingSkyline(grid [][]int) int {
res := 0
n, m := len(grid), len(grid[0])
row := make([]int, n)
col := make([]int, m)
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
row[i] = max(row[i], grid[i][j])
col[j] = max(col[j], grid[i][j])
}
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
res = res + min(row[i], col[j]) - grid[i][j]
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
808.分汤(1)¶
题目
有A和B 两种类型的汤。一开始每种类型的汤有N毫升。有四种分配操作：
提供 100ml 的汤A 和 0ml 的汤B。
提供 75ml 的汤A 和 25ml 的汤B。
提供 50ml 的汤A 和 50ml 的汤B。
提供 25ml 的汤A 和 75ml 的汤B。
当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为0.25的操作中进行分配选择。
如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。
注意不存在先分配100 ml汤B的操作。
需要返回的值：汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2。
示例: 输入: N = 50 输出: 0.625
解释:如果我们选择前两个操作，A将首先变为空。对于第三个操作，A和B会同时变为空。
对于第四个操作，B将首先变为空。
所以A变为空的总概率加上A和B同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
注释: 0 <= N <= 10^9。
返回值在10^-6的范围将被认为是正确的。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(1) | O(1) |
func soupServings(N int) float64 {
n := N / 25
if N%25 > 0 {
n = n + 1
}
if n >= 500 {
return 1.0
}
// 当给定i毫升的A和j毫升的B的概率
// dp[i][j]的概率=0.25*(dp[i-4][j]+dp[i-3][j-1]+dp[i-2][j-2]+dp[i-1][j-3])
dp := make([][]float64, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]float64, n+1)
}
dp[0][0] = 0.5
for i := 1; i <= n; i++ {
dp[i][0] = 0
dp[0][i] = 1
}
for i := 1; i <= n; i++ {
a1 := max(i-4, 0)
a2 := max(i-3, 0)
a3 := max(i-2, 0)
a4 := max(i-1, 0)
for j := 1; j <= n; j++ {
b1 := max(j, 0)
b2 := max(j-1, 0)
b3 := max(j-2, 0)
b4 := max(j-3, 0)
dp[i][j] = 0.25 * (dp[a1][b1] + dp[a2][b2] + dp[a3][b3] + dp[a4][b4])
}
}
return dp[n][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
809.情感丰富的文字(1)¶
题目
有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。
我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。
对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，
我们将这个单词定义为可扩张的（stretchy）。
扩张操作定义如下：选择一个字母组（包含字母c），然后往其中添加相同的字母c使其长度达到 3 或以上。
例如，以"hello" 为例，我们可以对字母组"o" 扩张得到 "hellooo"，
但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于3。
此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得"helllllooo"。
如果S = "helllllooo"，那么查询词"hello" 是可扩张的，
因为可以对它执行这两种扩张操作使得query = "hello" -> "hellooo" ->"helllllooo" = S。
输入一组查询单词，输出其中可扩张的单词数量。
示例：输入： S = "heeellooo" words = ["hello", "hi", "helo"] 输出：1
解释：我们能通过扩张 "hello" 的 "e" 和 "o" 来得到 "heeellooo"。
我们不能通过扩张 "helo" 来得到 "heeellooo" 因为 "ll" 的长度小于 3 。
说明：0 <= len(S) <= 100。
0 <= len(words) <= 100。
0 <= len(words[i]) <= 100。
S和所有在words中的单词都只由小写字母组成。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(n) |
func expressiveWords(S string, words []string) int {
res := 0
arr := getCount(S)
for i := 0; i < len(words); i++ {
temp := getCount(words[i])
if len(temp) != len(arr) {
continue
}
flag := true
for j := 0; j < len(arr); j = j + 2 {
if arr[j] != temp[j] {
flag = false
break
}
if arr[j+1] == temp[j+1] {
continue
}
if arr[j+1] < 3 || arr[j+1] < temp[j+1] {
flag = false
break
}
}
if flag == true {
res++
}
}
return res
}
func getCount(str string) []int {
res := make([]int, 0)
count := 1
for i := 0; i < len(str); i++ {
if i == len(str)-1 || str[i] != str[i+1] {
res = append(res, int(str[i]), count)
count = 1
} else {
count++
}
}
return res
}
813.最大平均值和的分组(3)¶
题目
我们将给定的数组A分成K个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。
计算我们所能得到的最大分数是多少。
注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。
示例:输入: A = [9,1,2,3,9] K = 3 输出: 20
解释: A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我们也可以把 A 分成[9, 1], [2], [3, 9].
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
说明:1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
答案误差在10^-6内被视为是正确的。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^3) | O(n) |
| 02 | 动态规划 | O(n^3) | O(n^2) |
| 03 | 动态规划 | O(n^3) | O(n^2) |
func largestSumOfAverages(A []int, K int) float64 {
n := len(A)
arr := make([]int, n+1)
for i := 0; i < n; i++ {
arr[i+1] = arr[i] + A[i]
}
dp := make([]float64, n) // dp[i]=>A[i:]的最大平均值
for i := 0; i < n; i++ {
dp[i] = float64(arr[n]-arr[i]) / float64(n-i) // 划分为1组
}
for k := 1; k < K; k++ { // K组可以划分K-1次
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
target := dp[j] + float64(arr[j]-arr[i])/float64(j-i)
dp[i] = math.Max(dp[i], target)
}
}
}
return dp[0]
}
# 2
func largestSumOfAverages(A []int, K int) float64 {
n := len(A)
arr := make([]int, n+1)
for i := 0; i < n; i++ {
arr[i+1] = arr[i] + A[i]
}
dp := make([][]float64, n) // dp[i]=>A[i:]的最大平均值
for i := 0; i < n; i++ {
dp[i] = make([]float64, K)
dp[i][0] = float64(arr[n]-arr[i]) / float64(n-i) // 划分为1组
}
for k := 1; k < K; k++ { // K组可以划分K-1次
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
target := dp[j][k-1] + float64(arr[j]-arr[i])/float64(j-i)
dp[i][k] = math.Max(dp[i][k], target)
}
}
}
return dp[0][K-1]
}
# 3
func largestSumOfAverages(A []int, K int) float64 {
n := len(A)
arr := make([]int, n+1)
for i := 0; i < n; i++ {
arr[i+1] = arr[i] + A[i]
}
dp := make([][]float64, n+1)
for i := 1; i <= n; i++ {
dp[i] = make([]float64, K+1)
dp[i][1] = float64(arr[i]) / float64(i) // 划分为1组
}
for i := 1; i <= n; i++ {
for k := 2; k <= K && k <= i; k++ {
for j := 1; j < i; j++ {
target := dp[j][k-1] + float64(arr[i]-arr[j])/float64(i-j)
dp[i][k] = math.Max(dp[i][k], target)
}
}
}
return dp[n][K]
}
814.二叉树剪枝(1)¶
题目
给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。
返回移除了所有不包含 1 的子树的原二叉树。
( 节点 X 的子树为 X 本身，以及所有 X 的后代。)
示例1:输入: [1,null,0,0,1] 输出: [1,null,0,null,1]
解释: 只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。
示例2:输入: [1,0,1,0,0,0,1] 输出: [1,null,1,null,1]
示例3:输入: [1,1,0,1,1,0,1,0] 输出: [1,1,0,1,1,null,1]
说明:给定的二叉树最多有 100 个节点。
每个节点的值只会为 0 或 1 。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(n) | O(log(n)) |
func pruneTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left = pruneTree(root.Left)
root.Right = pruneTree(root.Right)
if root.Left == nil && root.Right == nil && root.Val == 0 {
return nil
}
return root
}
816.模糊坐标(1)¶
题目
我们有一些二维坐标，如"(1, 3)"或"(2, 0.5)"，然后我们移除所有逗号，小数点和空格，得到一个字符串S。
返回所有可能的原始字符串到一个列表中。
原始的坐标表示法不会存在多余的零，所以不会出现类似于"00", "0.0", "0.00", "1.0", "001",
"00.01"或一些其他更小的数来表示坐标。
此外，一个小数点前至少存在一个数，所以也不会出现“.1”形式的数字。
最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。
示例 1:输入: "(123)" 输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]
示例 2:输入: "(00011)" 输出: ["(0.001, 1)", "(0, 0.011)"]
解释: 0.0, 00, 0001 或 00.01 是不被允许的。
示例 3: 输入: "(0123)"
输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]
示例 4:输入: "(100)" 输出: [(10, 0)]
解释: 1.0 是不被允许的。
提示:4 <= S.length <= 12.
S[0] = "(", S[S.length - 1] = ")", 且字符串S中的其他元素都是数字。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 枚举 | O(n^3) | O(n^3) |
func ambiguousCoordinates(s string) []string {
res := make([]string, 0)
str := s[1 : len(s)-1]
n := len(str)
for i := 1; i <= n-1; i++ { // 枚举左右2边
left := str[:i]
right := str[i:]
a := process(left)
b := process(right)
for j := 0; j < len(a); j++ {
for k := 0; k < len(b); k++ {
res = append(res, "("+a[j]+", "+b[k]+")")
}
}
}
return res
}
func process(str string) []string {
res := make([]string, 0)
n := len(str)
for i := 1; i <= n; i++ {
left := str[:i]
right := str[i:]
if judge(left, right) == true {
if i == n {
res = append(res, left+""+right)
} else {
res = append(res, left+"."+right)
}
}
}
return res
}
func judge(a, b string) bool {
if (len(a) >= 2 && a[0] == '0') ||
(len(b) >= 1 && b[len(b)-1] == '0') {
return false
}
return true
}
817.链表组件(2)¶
题目
给定链表头结点head，该链表上的每个结点都有一个 唯一的整型值 。
同时给定列表G，该列表是上述链表中整型值的一个子集。
返回列表G中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表G中）构成的集合。
示例1：输入: head: 0->1->2->3G = [0, 1, 3] 输出: 2
解释: 链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，
同理 [3] 也是一个组件，故返回 2。
示例 2：输入: head: 0->1->2->3->4 G = [0, 3, 1, 4] 输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
提示：如果N是给定链表head的长度，1 <= N <= 10000。
链表中每个结点的值所在范围为[0, N - 1]。
1 <= G.length <= 10000
G 是链表中所有结点的值的一个子集.
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n) | O(n) |
| 02 | 哈希辅助 | O(n) | O(n) |
func numComponents(head *ListNode, G []int) int {
m := make(map[int]bool)
for i := 0; i < len(G); i++ {
m[G[i]] = true
}
res := 0
for head != nil {
if m[head.Val] == true &&
(head.Next == nil || m[head.Next.Val] == false) {
res++
}
head = head.Next
}
return res
}
# 2
func numComponents(head *ListNode, G []int) int {
m := make(map[int]bool)
for i := 0; i < len(G); i++ {
m[G[i]] = true
}
res := 0
flag := false
for head != nil {
if m[head.Val] == true {
if flag == false {
res++
flag = true
}
} else {
flag = false
}
head = head.Next
}
return res
}
820.单词的压缩编码(3)¶
题目
给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如，如果这个列表是 ["time", "me", "bell"]，
我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。
对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，
来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
示例：输入: words = ["time", "me", "bell"] 输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5] 。
提示：1 <= words.length <= 2000
1 <= words[i].length <= 7
每个单词都是小写字母 。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n^2) | O(n) |
| 02 | 排序遍历 | O(n^2) | O(n) |
| 03 | 逆置排序 | O(nlog(n)) | O(n) |
func minimumLengthEncoding(words []string) int {
res := 0
m := make(map[string]bool)
for i := 0; i < len(words); i++ {
m[words[i]] = true
}
for k := range m {
for i := 1; i < len(k); i++ {
delete(m, k[i:])
}
}
for k := range m {
res = res + len(k) + 1
}
return res
}
# 2
func minimumLengthEncoding(words []string) int {
res := 0
m := make(map[string]bool)
for i := 0; i < len(words); i++ {
m[words[i]] = true
}
words = make([]string, 0)
for k := range m {
words = append(words, k)
}
sort.Slice(words, func(i, j int) bool {
return len(words[i]) < len(words[j])
})
for i := len(words) - 1; i >= 0; i-- {
if m[words[i]] == false {
continue
}
for j := i - 1; j >= 0; j-- {
if strings.HasSuffix(words[i], words[j]) == true {
m[words[j]] = false
}
}
}
for k := range m {
if m[k] == true {
res = res + len(k) + 1
}
}
return res
}
# 3
func minimumLengthEncoding(words []string) int {
res := 0
arr := make([]string, 0)
for k := range words {
arr = append(arr, reverse(words[k]))
}
sort.Strings(arr)
for i := 0; i < len(arr)-1; i++ {
length := len(arr[i])
if length <= len(arr[i+1]) && arr[i] == arr[i+1][:length] {
continue
}
res = res + length + 1
}
return res + len(arr[len(arr)-1]) + 1
}
func reverse(str string) string {
res := make([]byte, 0)
for i := len(str) - 1; i >= 0; i-- {
res = append(res, str[i])
}
return string(res)
}
822.翻转卡片游戏(1)¶
题目
在桌子上有 N 张卡片，每张卡片的正面和背面都写着一个正数（正面与背面上的数有可能不一样）。
我们可以先翻转任意张卡片，然后选择其中一张卡片。
如果选中的那张卡片背面的数字 X 与任意一张卡片的正面的数字都不同，那么这个数字是我们想要的数字。
哪个数是这些想要的数字中最小的数（找到这些数中的最小值）呢？如果没有一个数字符合要求的，输出 0。
其中, fronts[i]和backs[i]分别代表第i张卡片的正面和背面的数字。
如果我们通过翻转卡片来交换正面与背面上的数，那么当初在正面的数就变成背面的数，背面的数就变成正面的数。
示例：输入：fronts = [1,2,4,4,7], backs = [1,3,4,1,3] 输出：2
解释：假设我们翻转第二张卡片，那么在正面的数变成了 [1,3,4,4,7] ， 背面的数变成了 [1,2,4,1,3]。
接着我们选择第二张卡片，因为现在该卡片的背面的数是 2，2 与任意卡片上正面的数都不同，
所以 2 就是我们想要的数字。
提示：1 <= fronts.length == backs.length<=1000
1 <=fronts[i]<= 2000
1 <= backs[i]<= 2000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n) | O(n) |
func flipgame(fronts []int, backs []int) int {
m := make(map[int]bool)
for i := 0; i < len(fronts); i++ {
if fronts[i] == backs[i] { // 前后相同，不能选
m[fronts[i]] = true
}
}
res := math.MaxInt32
for i := 0; i < len(fronts); i++ {
if m[fronts[i]] == false { // 不相同
if fronts[i] < res {
res = fronts[i]
}
}
if m[backs[i]] == false { // 不相同
if backs[i] < res {
res = backs[i]
}
}
}
if res == math.MaxInt32 {
return 0
}
return res
}
823.带因子的二叉树(2)¶
题目
给出一个含有不重复整数元素的数组，每个整数均大于 1。
我们用这些整数来构建二叉树，每个整数可以使用任意次数。
其中：每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个？返回的结果应模除 10 ** 9 + 7。
示例 1:输入: A = [2, 4] 输出: 3
解释: 我们可以得到这些二叉树: [2], [4], [4, 2, 2]
示例 2:输入: A = [2, 4, 5, 10] 输出: 7
解释: 我们可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
提示:1 <= A.length <=1000.
2 <=A[i]<=10 ^ 9.
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^2) | O(n) |
| 02 | 动态规划 | O(n^2) | O(n) |
var mod = 1000000007
func numFactoredBinaryTrees(arr []int) int {
sort.Ints(arr)
n := len(arr)
m := make(map[int]int)
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
m[arr[i]] = i
}
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
if arr[i]%arr[j] == 0 {
c := arr[i] / arr[j]
if v, ok := m[c]; ok {
dp[i] = (dp[i] + dp[j]*dp[v]) % mod
}
}
}
}
res := 0
for i := 0; i < n; i++ {
res = (res + dp[i]) % mod
}
return res
}
# 2
var mod = 1000000007
func numFactoredBinaryTrees(arr []int) int {
sort.Ints(arr)
n := len(arr)
dp := make(map[int]int)
res := 0
for i := 0; i < n; i++ {
dp[arr[i]] = 1
for j := 0; j < i; j++ {
if arr[i]%arr[j] == 0 {
c := arr[i] / arr[j]
dp[arr[i]] = (dp[arr[i]] + dp[arr[j]]*dp[c]) % mod
}
}
res = (res + dp[arr[i]]) % mod
}
return res
}
825.适龄的朋友(2)¶
题目
人们会互相发送好友请求，现在给定一个包含有他们年龄的数组，ages[i]表示第 i 个人的年龄。
当满足以下任一条件时，A 不能给 B（A、B不为同一人）发送好友请求：
age[B]<= 0.5 * age[A]+ 7
age[B]> age[A]
age[B]> 100 &&age[A]< 100
否则，A 可以给 B 发送好友请求。
注意如果 A 向 B 发出了请求，不等于 B 也一定会向A 发出请求。而且，人们不会给自己发送好友请求。
求总共会发出多少份好友请求?
示例 1：输入：[16,16] 输出：2
解释：二人可以互发好友申请。
示例 2：输入：[16,17,18] 输出：2
解释：好友请求可产生于 17 -> 16, 18 -> 17.
示例 3：输入：[20,30,100,110,120] 输出：3
解释：好友请求可产生于 110 -> 100, 120 -> 110, 120 -> 100.
提示：1 <= ages.length<= 20000.
1 <= ages[i] <= 120.
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n^2) | O(n) |
| 02 | 数组辅助 | O(n^2) | O(n) |
func numFriendRequests(ages []int) int {
res := 0
m := make(map[int]int)
for i := 0; i < len(ages); i++ {
m[ages[i]]++
}
for k, v := range m {
for key, value := range m {
if key <= k/2+7 || key > k || (key > 100 && k < 100) {
continue
} else if k == key {
res = res + v*(value-1)
} else {
res = res + v*value
}
}
}
return res
}
# 2
func numFriendRequests(ages []int) int {
res := 0
arr := [121]int{}
for i := 0; i < len(ages); i++ {
arr[ages[i]]++
}
for a := 0; a <= 120; a++ {
countA := arr[a]
for b := 0; b <= 120; b++ {
countB := arr[b]
if a/2+7 >= b {
continue
}
if a < b {
continue
}
if a < 100 && 100 < b {
continue
}
res = res + countA*countB
if a == b {
res = res - countA
}
}
}
return res
}
826.安排工作以达到最大收益(2)¶
题目
有一些工作：difficulty[i]表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
现在我们有一些工人。worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。
每一个工人都最多只能安排一个工作，但是一个工作可以完成多次。
举个例子，如果 3 个工人都尝试完成一份报酬为 1 的同样工作，那么总收益为 $3。
如果一个工人不能完成任何工作，他的收益为 $0 。
我们能得到的最大收益是多少？
示例：输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。
提示:1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i] 的范围是[1, 10^5]
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序 | O(nlog(n)) | O(n) |
| 02 | 数组辅助 | O(n) | O(n) |
type Node struct {
difficulty int
profit int
}
func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
arr := make([]Node, 0)
for i := 0; i < len(difficulty); i++ {
arr = append(arr, Node{
difficulty: difficulty[i],
profit: profit[i],
})
}
sort.Ints(worker)
sort.Slice(arr, func(i, j int) bool {
return arr[i].difficulty < arr[j].difficulty
})
res := 0
index := 0
maxProfit := 0
for i := 0; i < len(worker); i++ {
// 找到工人收益最大
for index < len(arr) && worker[i] >= arr[index].difficulty {
maxProfit = max(maxProfit, arr[index].profit)
index++
}
res = res + maxProfit
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
res := 0
arr := make([]int, 100001) // 难度对应的最大利润
for i := 0; i < len(difficulty); i++ {
arr[difficulty[i]] = max(arr[difficulty[i]], profit[i])
}
maxProfit := arr[0]
for i := 1; i < 100001; i++ {
maxProfit = max(maxProfit, arr[i])
arr[i] = maxProfit
}
for i := 0; i < len(worker); i++ {
res = res + arr[worker[i]]
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
831.隐藏个人信息(2)¶
题目
给你一条个人信息字符串 S，它可能是一个 邮箱地址 ，也可能是一串 电话号码 。
我们将隐藏它的隐私信息，通过如下规则:
1. 电子邮箱
定义名称 name 是长度大于等于 2 （length ≥ 2），并且只包含小写字母 a-z 和大写字母 A-Z 的字符串。
电子邮箱地址由名称 name 开头，紧接着是符号 '@'，后面接着一个名称 name，
再接着一个点号 '.'，然后是一个名称 name。
电子邮箱地址确定为有效的，并且格式是 "name1@name2.name3"。
为了隐藏电子邮箱，所有的名称 name 必须被转换成小写的，
并且第一个名称name 的第一个字母和最后一个字母的中间的所有字母由 5 个 '*' 代替。
2. 电话号码
电话号码是一串包括数字0-9，以及 {'+', '-', '(', ')', ''} 这几个字符的字符串。
你可以假设电话号码包含 10 到 13 个数字。
电话号码的最后 10 个数字组成本地号码，在这之前的数字组成国际号码。
注意，国际号码是可选的。我们只暴露最后 4 个数字并隐藏所有其他数字。
本地号码是有格式的，并且如 "***-***-1111" 这样显示，这里的 1 表示暴露的数字。
为了隐藏有国际号码的电话号码，像"+111 111 111 1111"，我们以 "+***-***-***-1111" 的格式来显示。
在本地号码前面的 '+' 号和第一个 '-' 号仅当电话号码中包含国际号码时存在。
例如，一个 12 位的电话号码应当以 "+**-" 开头进行显示。
注意：像 "("，")"，" " 这样的不相干的字符以及不符合上述格式的额外的减号或者加号都应当被删除。
最后，将提供的信息正确隐藏后返回。
示例 1：输入: "LeetCode@LeetCode.com" 输出: "l*****e@leetcode.com"
解释： 所有的名称转换成小写, 第一个名称的第一个字符和最后一个字符中间由 5 个星号代替。
因此，"leetcode" -> "l*****e"。
示例 2：输入: "AB@qq.com" 输出: "a*****b@qq.com"
解释:第一个名称"ab"的第一个字符和最后一个字符的中间必须有 5 个星号
因此，"ab" -> "a*****b"。
示例 3：输入: "1(234)567-890" 输出: "***-***-7890"
解释:10 个数字的电话号码，那意味着所有的数字都是本地号码。
示例 4：输入: "86-(10)12345678" 输出: "+**-***-***-5678"
解释:12 位数字，2 个数字是国际号码另外 10 个数字是本地号码 。
注意:S.length<=40。
邮箱的长度至少是 8。
电话号码的长度至少是 10。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(n) |
| 02 | 遍历 | O(n) | O(n) |
func maskPII(S string) string {
if strings.Contains(S, "@") {
S = strings.ToLower(S)
arr := strings.Split(S, "@")
return arr[0][:1] + "*****" + arr[0][len(arr[0])-1:] + "@" + arr[1]
}
res := make([]byte, 0)
for i := 0; i < len(S); i++ {
if '0' <= S[i] && S[i] <= '9' {
res = append(res, S[i])
}
}
if len(res) == 10 {
return "***-***-" + string(res[len(res)-4:])
} else if len(res) == 11 {
return "+*-***-***-" + string(res[len(res)-4:])
} else if len(res) == 12 {
return "+**-***-***-" + string(res[len(res)-4:])
} else if len(res) == 13 {
return "+***-***-***-" + string(res[len(res)-4:])
}
return string(res)
}
# 2
func maskPII(S string) string {
if strings.Contains(S, "@") {
S = strings.ToLower(S)
arr := strings.Split(S, "@")
return arr[0][:1] + "*****" + arr[0][len(arr[0])-1:] + "@" + arr[1]
}
res := make([]byte, 0)
for i := 0; i < len(S); i++ {
if '0' <= S[i] && S[i] <= '9' {
res = append(res, S[i])
}
}
n := len(res)
str := "***-***-" + string(res[n-4:])
if n > 10 {
return "+" + strings.Repeat("*", n-10) + "-" + str
}
return str
}
833.字符串中的查找与替换(2)¶
题目
某个字符串 S 需要执行一些替换操作，用新的字母组替换原有的字母组（不一定大小相同）。
每个替换操作具有 3 个参数：起始索引 i，源字 x 和目标字 y。
规则是：如果 x 从原始字符串 S 中的位置 i 开始，那么就用 y 替换出现的 x。如果没有，则什么都不做。
举个例子，如果 S= “abcd” 并且替换操作 i = 2，x = “cd”，y = “ffff”，
那么因为 “cd” 从原始字符串 S 中的位置 2 开始，所以用“ffff” 替换它。
再来看 S = “abcd” 上的另一个例子，如果一个替换操作 i = 0，x = “ab”，y = “eee”，
以及另一个替换操作 i = 2，x = “ec”，y = “ffff”，那么第二个操作将不会执行，
因为原始字符串中S[2] = 'c'，与 x[0] = 'e' 不匹配。
所有这些操作同时发生。保证在替换时不会有任何重叠：S = "abc",
indexes = [0, 1],sources = ["ab","bc"] 不是有效的测试用例。
示例 1：输入：S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出："eeebffff"
解释："a" 从 S 中的索引 0 开始，所以它被替换为 "eee"。
"cd" 从 S 中的索引 2 开始，所以它被替换为 "ffff"。
示例 2：输入：S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
输出："eeecd"
解释："ab" 从 S 中的索引 0 开始，所以它被替换为 "eee"。
"ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。
提示：0 <= S.length <= 1000
S 仅由小写英文字母组成
0 <= indexes.length <= 100
0 <= indexes[i] < S.length
sources.length == indexes.length
targets.length == indexes.length
1 <= sources[i].length, targets[i].length <= 50
sources[i] 和 targets[i] 仅由小写英文字母组成
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 自定义排序 | O(nlog(n)) | O(n) |
| 02 | 遍历 | O(n) | O(n) |
type Node struct {
index int
source string
target string
}
func findReplaceString(S string, indexes []int, sources []string, targets []string) string {
arr := make([]Node, 0)
for i := 0; i < len(indexes); i++ {
arr = append(arr, Node{
index: indexes[i],
source: sources[i],
target: targets[i],
})
}
sort.Slice(arr, func(i, j int) bool {
return arr[i].index < arr[j].index
})
res := ""
left := 0
for i := 0; i < len(arr); i++ {
if left < arr[i].index {
res = res + S[left:arr[i].index]
left = arr[i].index
}
start := arr[i].index
end := arr[i].index + len(arr[i].source)
if end <= len(S) && S[start:end] == arr[i].source {
res = res + arr[i].target
left = end
}
}
if left < len(S) {
res = res + S[left:]
}
return res
}
# 2
func findReplaceString(S string, indexes []int, sources []string, targets []string) string {
m := make(map[int]int)
for i := 0; i < len(indexes); i++ {
if S[indexes[i]:indexes[i]+len(sources[i])] == sources[i] {
m[indexes[i]] = i
}
}
res := make([]byte, 0)
for i := 0; i < len(S); {
if v, ok := m[i]; ok {
res = append(res, targets[v]...)
i = i + len(sources[v])
} else {
res = append(res, S[i])
i++
}
}
return string(res)
}
835.图像重叠(2)¶
题目
给你两个图像 img1 和 img2 ，两个图像的大小都是 n x n ，用大小相同的二维正方形矩阵表示。
（并且为二进制矩阵，只包含若干 0 和若干 1 ）
转换其中一个图像，向左，右，上，或下滑动任何数量的单位，并把它放在另一个图像的上面。
之后，该转换的 重叠 是指两个图像都具有 1 的位置的数目。
（请注意，转换 不包括 向任何方向旋转。）
最大可能的重叠是多少？
示例 1：输入：img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]] 输出：3
解释：将 img1 向右移动 1 个单位，再向下移动 1 个单位。
两个图像都具有 1 的位置的数目是 3（用红色标识）。
示例 2：输入：img1 = [[1]], img2 = [[1]] 输出：1
示例 3：输入：img1 = [[0]], img2 = [[0]] 输出：0
提示：n == img1.length
n == img1[i].length
n == img2.length
n == img2[i].length
1 <= n <= 30
img1[i][j] 为 0 或 1
img2[i][j] 为 0 或 1
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^4) | O(n^2) |
| 02 | 遍历 | O(n^2) | O(n^2) |
func largestOverlap(img1 [][]int, img2 [][]int) int {
res := 0
n := len(img1)
arr := make([][]int, 2*n+1)
for i := 0; i <= 2*n; i++ {
arr[i] = make([]int, 2*n+1)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if img1[i][j] == 1 {
for a := 0; a < n; a++ {
for b := 0; b < n; b++ {
if img2[a][b] == 1 {
arr[i-a+n][j-b+n]++ // i-a，j-b是移动的，+n修正负数
}
}
}
}
}
}
for i := 0; i <= 2*n; i++ {
for j := 0; j <= 2*n; j++ {
res = max(res, arr[i][j])
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func largestOverlap(img1 [][]int, img2 [][]int) int {
res := 0
n := len(img1)
A := make([][2]int, 0)
B := make([][2]int, 0)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if img1[i][j] == 1 {
A = append(A, [2]int{i, j})
}
if img2[i][j] == 1 {
B = append(B, [2]int{i, j})
}
}
}
m := make(map[[2]int]int)
for i := 0; i < len(A); i++ {
for j := 0; j < len(B); j++ {
a := B[j][0] - A[i][0]
b := B[j][1] - A[i][1]
m[[2]int{a, b}]++
res = max(res, m[[2]int{a, b}])
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
837.新21点(2)¶
题目
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。
抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。
每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
示例 1：输入：N = 10, K = 1, W = 10 输出：1.00000
说明：爱丽丝得到一张卡，然后停止。
示例 2：输入：N = 6, K = 1, W = 10 输出：0.60000
说明：爱丽丝得到一张卡，然后停止。
在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。
示例 3：输入：N = 21, K = 17, W = 10 输出：0.73278
提示：0 <= K <= N <= 10000
1 <= W <= 10000
如果答案与正确答案的误差不超过 10^-5，则该答案将被视为正确答案通过。
此问题的判断限制时间已经减少。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n) | O(n) |
| 02 | 动态规划 | O(n) | O(n) |
func new21Game(N int, K int, W int) float64 {
if K == 0 {
return 1.0
}
dp := make([]float64, K+W) // 得分区间
for i := K; i <= N && i < K+W; i++ {
dp[i] = 1.0
}
/*for i := K-1; i >= 0; i--{
for j := 1; j <= W; j++{ // 每次选择1~W
dp[i] = dp[i] + dp[i+j]/float64(W)
}
}*/
dp[K-1] = 1.0 * (float64(min(N-K+1, W))) / float64(W)
for i := K - 2; i >= 0; i-- {
dp[i] = dp[i+1] - (dp[i+W+1]-dp[i+1])/float64(W)
}
return dp[0]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func new21Game(N int, K int, W int) float64 {
if K == 0 {
return 1.0
}
dp := make([]float64, K+W) // 为当前手中牌面为i点时获胜的概率
var sum float64
for i := K; i <= K+W-1; i++ {
if i <= N {
dp[i] = 1
}
sum = sum + dp[i]
}
for i := K - 1; i >= 0; i-- {
dp[i] = sum / float64(W)
sum = sum - dp[i+W] + dp[i]
}
return dp[0]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
838.推多米诺(3)¶
题目
一行中有 N 张多米诺骨牌，我们将每张多米诺骨牌垂直竖立。
在开始时，我们同时把一些多米诺骨牌向左或向右推。
每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。
同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边，由于受力平衡， 该骨牌仍然保持不变。
就这个问题而言，我们会认为正在下降的多米诺骨牌不会对其它正在下降或已经下降的多米诺骨牌施加额外的力。
给定表示初始状态的字符串 "S" 。如果第 i 张多米诺骨牌被推向左边，则 S[i] = 'L'；
如果第 i 张多米诺骨牌被推向右边，则 S[i] = 'R'；如果第 i 张多米诺骨牌没有被推动，则 S[i] = '.'。
返回表示最终状态的字符串。
示例 1：输入：".L.R...LR..L.." 输出："LL.RR.LLRRLL.."
示例 2：输入："RR.L" 输出："RR.L"
说明：第一张多米诺骨牌没有给第二张施加额外的力。
提示：0 <= N <= 10^5
表示多米诺骨牌状态的字符串只含有 'L'，'R'; 以及 '.';
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 模拟 | O(n^2) | O(n) |
| 02 | 计算 | O(n) | O(n) |
| 03 | 模拟 | O(n^2) | O(n) |
func pushDominoes(dominoes string) string {
n := len(dominoes)
arr := append([]byte{'L'}, dominoes...)
arr = append(arr, 'R') // 前面补1个L，后面补1个R
temp := make([]byte, n+2)
for string(temp) != string(arr) { // 模拟每一秒：当没有变化的时候退出
copy(temp, arr) // 存储之前1秒的情况
for i := 1; i <= n; i++ {
if arr[i] == '.' { // 当前位置为.进行判断2边情况
// 讨论2种变的情况
if temp[i-1] == 'R' && temp[i+1] != 'L' {
arr[i] = 'R' // 1、左边向右边倒，右边为R或者.
} else if temp[i+1] == 'L' && temp[i-1] != 'R' {
arr[i] = 'L' // 2、右边向左边倒，左边为L或者.
}
}
}
}
return string(arr[1 : n+1])
}
# 2
func pushDominoes(dominoes string) string {
n := len(dominoes)
arr := make([]int, n)
value := 0
for i := 0; i < n; i++ { // 1、从左往右
// 计算左边的受力，R=n，L=0，.的时候随距离减1
if dominoes[i] == 'R' {
value = n
} else if dominoes[i] == 'L' {
value = 0
} else {
value = max(0, value-1)
}
arr[i] = arr[i] + value
}
value = 0
for i := n - 1; i >= 0; i-- { // 2、从右往左
// 计算右边的受力，R=0，L=R，.的时候随距离减1
if dominoes[i] == 'L' {
value = n
} else if dominoes[i] == 'R' {
value = 0
} else {
value = max(0, value-1)
}
arr[i] = arr[i] - value
}
res := []byte(dominoes)
for i := 0; i < n; i++ {
// 哪边受力大，结果随哪边
if arr[i] > 0 {
res[i] = 'R'
} else if arr[i] < 0 {
res[i] = 'L'
} else {
res[i] = '.'
}
}
return string(res)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func pushDominoes(dominoes string) string {
s := ""
for s != dominoes { // 模拟每一秒：当没有变化的时候退出
s = dominoes
dominoes = strings.ReplaceAll(dominoes, "R.L", "X") // 把R.L这种不变的临时替换为1个不影响的X
dominoes = strings.ReplaceAll(dominoes, ".L", "LL") // 向左倒
dominoes = strings.ReplaceAll(dominoes, "R.", "RR") // 向右倒
dominoes = strings.ReplaceAll(dominoes, "X", "R.L") // 替换回来
}
return dominoes
}
841.钥匙和房间(2)¶
题目
有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，
并且房间里可能有一些钥匙能使你进入下一个房间。
在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，
每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。
钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
最初，除 0 号房间外的其余所有房间都被锁住。
你可以自由地在房间之间来回走动。
如果能进入每个房间返回 true，否则返回 false。
示例 1：输入: [[1],[2],[3],[]]输出: true
解释: 我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
示例 2：输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。
提示：1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 深度优先搜索 | O(n) | O(n) |
| 02 | 广度优先搜索 | O(n) | O(n) |
var visited []bool
var total int
func canVisitAllRooms(rooms [][]int) bool {
n := len(rooms)
total = 0
visited = make([]bool, n)
dfs(rooms, 0)
return total == n
}
func dfs(rooms [][]int, start int) {
visited[start] = true
total++
for _, room := range rooms[start] {
if visited[room] == false {
dfs(rooms, room)
}
}
}
# 2
func canVisitAllRooms(rooms [][]int) bool {
n := len(rooms)
total := 0
visited := make([]bool, n)
visited[0] = true
queue := make([]int, 0)
queue = append(queue, 0)
for len(queue) > 0 {
start := queue[0]
queue = queue[1:]
total++
for _, room := range rooms[start] {
if visited[room] == false {
visited[room] = true
queue = append(queue, room)
}
}
}
return total == n
}
842.将数组拆分成斐波那契序列(1)¶
题目
给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上，斐波那契式序列是一个非负整数列表 F，且满足：
0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
F.length >= 3；
对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
示例 1：输入："123456579" 输出：[123,456,579]
示例 2：输入: "11235813" 输出: [1,1,2,3,5,8,13]
示例 3：输入: "112358130" 输出: []
解释: 这项任务无法完成。
示例 4：输入："0123" 输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
示例 5：输入: "1101111" 输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。
提示：1 <= S.length<= 200
字符串 S 中只含有数字。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 回溯 | O(n(log(n))^2) | O(n) |
var res []int
func splitIntoFibonacci(S string) []int {
res = make([]int, 0)
dfs(S, 0, 0, 0, make([]int, 0))
return res
}
func dfs(s string, index, sum, prev int, path []int) bool {
if index == len(s) {
if len(path) >= 3 {
res = path
}
return len(path) >= 3
}
value := 0
for i := index; i < len(s); i++ {
// 0开头不满足要求(当前i=index的时候，可以为0， 避免错过1+0=1的情况)
if s[index] == '0' && i > index {
break
}
value = value*10 + int(s[i]-'0')
if value > math.MaxInt32 {
break
}
if len(path) >= 2 {
if value < sum {
continue
}
if value > sum {
break
}
}
if dfs(s, i+1, prev+value, value, append(path, value)) == true {
return true
}
}
return false
}
845.数组中的最长山脉(3)¶
题目
我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
B.length >= 3
存在 0 < i < B.length - 1 使得
B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
（注意：B 可以是 A 的任意子数组，包括整个数组 A。）
给出一个整数数组 A，返回最长 “山脉” 的长度。
如果不含有 “山脉” 则返回 0。
示例 1：输入：[2,1,4,7,3,2,5] 输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。
示例 2：输入：[2,2,2] 输出：0
解释：不含 “山脉”。
提示：0 <= A.length <= 10000
0 <= A[i] <= 10000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n) | O(n) |
| 02 | 双指针 | O(n) | O(1) |
| 03 | 中心扩展 | O(n^2) | O(1) |
func longestMountain(A []int) int {
n := len(A)
left := make([]int, len(A))
right := make([]int, len(A))
for i := 1; i < n; i++ {
if A[i-1] < A[i] {
left[i] = left[i-1] + 1
}
}
for i := n - 2; i >= 0; i-- {
if A[i+1] < A[i] {
right[i] = right[i+1] + 1
}
}
res := 0
for i := 1; i < n-1; i++ {
if left[i] > 0 && right[i] > 0 {
res = max(res, left[i]+right[i]+1)
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func longestMountain(A []int) int {
n := len(A)
left := 0
res := 0
for left+2 < n {
// left指向左侧山脚, right寻找右侧山脚
right := left + 1
if A[left] < A[left+1] {
for right+1 < n && A[right] < A[right+1] {
right++
}
if right+1 < n && A[right] > A[right+1] {
for right+1 < n && A[right] > A[right+1] {
right++
}
if right-left+1 > res {
res = right - left + 1
}
} else {
right++
}
}
left = right
}
return res
}
# 3
func longestMountain(A []int) int {
n := len(A)
res := 0
for i := 1; i < n-1; i++ {
left, right := 0, 0
for j := i - 1; j >= 0; j-- {
if A[j] < A[j+1] {
left++
} else {
break
}
}
for j := i + 1; j < n; j++ {
if A[j] < A[j-1] {
right++
} else {
break
}
}
if left > 0 && right > 0 {
res = max(res, left+right+1)
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
846.一手顺子(3)¶
题目
爱丽丝有一手（hand）由整数数组给定的牌。
现在她想把牌重新排列成组，使得每个组的大小都是 W，且由 W 张连续的牌组成。
如果她可以完成分组就返回 true，否则返回 false。
注意：此题目与 1296 重复：
示例 1：输入：hand = [1,2,3,6,2,3,4,7,8], W = 3 输出：true
解释：爱丽丝的手牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。
示例 2：输入：hand = [1,2,3,4,5], W = 4 输出：false
解释：爱丽丝的手牌无法被重新排列成几个大小为 4 的组。
提示：1 <= hand.length <= 10000
0 <= hand[i]<= 10^9
1 <= W <= hand.length
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序遍历 | O(nlog(n)) | O(1) |
| 02 | 哈希辅助 | O(nlog(n)) | O(n) |
| 03 | 哈希辅助 | O(nlog(n)) | O(n) |
func isNStraightHand(hand []int, W int) bool {
n := len(hand)
if n%W != 0 {
return false
}
if W == 1 {
return true
}
sort.Ints(hand)
for i := 0; i < n; i++ {
if hand[i] >= 0 {
count := 1
for j := i + 1; j < n; j++ {
if hand[j] > hand[i]+count {
break
}
if hand[j] >= 0 && hand[j] == hand[i]+count {
hand[j] = -1
count++
if count == W {
break
}
}
}
if count != W {
return false
}
hand[i] = -1
}
}
return true
}
# 2
func isNStraightHand(hand []int, W int) bool {
n := len(hand)
if n%W != 0 {
return false
}
if W == 1 {
return true
}
arr := make([]int, 0)
m := make(map[int]int)
for i := 0; i < len(hand); i++ {
if m[hand[i]] == 0 {
arr = append(arr, hand[i])
}
m[hand[i]]++
}
sort.Ints(arr)
for i := 0; i < len(arr); i++ {
if m[arr[i]] > 0 {
for j := 1; j < W; j++ {
value := arr[i] + j
m[value] = m[value] - m[arr[i]]
if m[value] < 0 {
return false
}
}
}
}
return true
}
# 3
func isNStraightHand(hand []int, W int) bool {
n := len(hand)
if n%W != 0 {
return false
}
if W == 1 {
return true
}
m := make(map[int]int)
for i := 0; i < len(hand); i++ {
m[hand[i]]++
}
sort.Ints(hand)
for i := 0; i < len(hand); i++ {
value := m[hand[i]]
if value > 0 {
for j := 0; j < W; j++ {
if m[hand[i]+j] < value {
return false
}
m[hand[i]+j] = m[hand[i]+j] - value
}
}
}
return true
}
848.字母移位(2)¶
题目
有一个由小写字母组成的字符串 S，和一个整数数组 shifts。
我们将字母表中的下一个字母称为原字母的 移位（由于字母表是环绕的， 'z'将会变成'a'）。
例如·，shift('a') = 'b'，shift('t') = 'u',， 以及shift('z') = 'a'。
对于每个shifts[i] = x， 我们会将 S中的前i+1个字母移位x次。
返回将所有这些移位都应用到 S 后最终得到的字符串。
示例：输入：S = "abc", shifts = [3,5,9] 输出："rpl"
解释： 我们以 "abc" 开始。
将 S 中的第 1 个字母移位 3 次后，我们得到 "dbc"。
再将 S 中的前 2 个字母移位 5 次后，我们得到 "igc"。
最后将 S 中的这 3 个字母移位 9 次后，我们得到答案 "rpl"。
提示：1 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 后缀和 | O(n) | O(n) |
| 02 | 前缀和 | O(n) | O(n) |
func shiftingLetters(S string, shifts []int) string {
arr := []byte(S)
shifts = append(shifts, 0)
for i := len(S) - 1; i >= 0; i-- {
shifts[i] = (shifts[i] + shifts[i+1]) % 26
arr[i] = 'a' + (S[i]-'a'+byte(shifts[i]))%26
}
return string(arr)
}
# 2
func shiftingLetters(S string, shifts []int) string {
sum := 0
for i := 0; i < len(shifts); i++ {
sum = (sum + shifts[i]) % 26
}
arr := []byte(S)
for i := 0; i < len(S); i++ {
count := int(S[i] - 'a')
arr[i] = byte((count+sum)%26 + 'a')
sum = ((sum-shifts[i])%26 + 26) % 26
}
return string(arr)
}
851.喧闹和富有(1)¶
题目
在一组 N 个人（编号为0, 1, 2, ..., N-1）中，每个人都有不同数目的钱，以及不同程度的安静（quietness）。
为了方便起见，我们将编号为x的人简称为 "personx"。
如果能够肯定 personx比 persony更有钱的话，我们会说richer[i] = [x, y]。注意richer可能只是有效观察的一个子集。
另外，如果 personx的安静程度为q，我们会说quiet[x] = q。
现在，返回答案answer，其中answer[x] = y的前提是，在所有拥有的钱不少于personx的人中，
persony是最安静的人（也就是安静值quiet[y]最小的人）。
示例：输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
输出：[5,5,2,5,4,5,6,7]
解释： answer[0] = 5，
person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
但是目前还不清楚他是否比 person 0 更有钱。
answer[7] = 7，
在所有拥有的钱肯定不少于 person 7 的人中(这可能包括 person 3，4，5，6 以及 7)，
最安静(有较低安静值 quiet[x])的人是 person 7。
其他的答案也可以用类似的推理来解释。
提示：1 <= quiet.length = N <= 500
0 <= quiet[i] < N，所有quiet[i]都不相同。
0 <= richer.length <= N * (N-1) / 2
0 <= richer[i][j] < N
richer[i][0] != richer[i][1]
richer[i]都是不同的。
对richer的观察在逻辑上是一致的。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(n^2) | O(n^2) |
var res []int
func loudAndRich(richer [][]int, quiet []int) []int {
arr := make(map[int][]int)
n := len(quiet)
res = make([]int, n)
for i := 0; i < n; i++ {
res[i] = -1
}
for i := 0; i < len(richer); i++ { // 有向无环图
a, b := richer[i][0], richer[i][1]
arr[b] = append(arr[b], a) // a比b更有钱
}
for i := 0; i < n; i++ {
dfs(quiet, arr, i)
}
return res
}
func dfs(quiet []int, arr map[int][]int, i int) int {
if res[i] == -1 {
res[i] = i // 首先最安静的人等于本身
for j := 0; j < len(arr[i]); j++ {
next := dfs(quiet, arr, arr[i][j]) // 递归找到arr[i][j]对应的最安静的人
if quiet[next] < quiet[res[i]] {
res[i] = next
}
}
}
return res[i]
}
853.车队(1)¶
题目
N 辆车沿着一条车道驶向位于target英里之外的共同目的地。
每辆车i以恒定的速度speed[i]（英里/小时），从初始位置position[i]（英里） 沿车道驶向目的地。
一辆车永远不会超过前面的另一辆车，但它可以追上去，并与前车以相同的速度紧接着行驶。
此时，我们会忽略这两辆车之间的距离，也就是说，它们被假定处于相同的位置。
车队是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意，一辆车也可以是一个车队。
即便一辆车在目的地才赶上了一个车队，它们仍然会被视作是同一个车队。
会有多少车队到达目的地?
示例：输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] 输出：3
解释： 从 10 和 8 开始的车会组成一个车队，它们在 12 处相遇。
从 0 处开始的车无法追上其它车，所以它自己就是一个车队。
从 5 和 3 开始的车会组成一个车队，它们在 6 处相遇。
请注意，在到达目的地之前没有其它车会遇到这些车队，所以答案是 3。
提示：0 <= N <= 10 ^ 4
0 < target<= 10 ^ 6
0 <speed[i] <= 10 ^ 6
0 <= position[i] < target
所有车的初始位置各不相同。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序 | O(nlog(n)) | O(n) |
type Node struct {
Position int
Left float64
}
func carFleet(target int, position []int, speed []int) int {
if len(position) == 0 {
return 0
}
arr := make([]Node, 0)
for i := 0; i < len(position); i++ {
arr = append(arr, Node{
Position: position[i],
Left: float64(target-position[i]) / float64(speed[i]),
})
}
sort.Slice(arr, func(i, j int) bool {
return arr[i].Position > arr[j].Position
})
res := 1
prev := arr[0].Left
for i := 1; i < len(arr); i++ {
if prev < arr[i].Left {
res++
prev = arr[i].Left
}
}
return res
}
855.考场就座¶
题目¶
在考场里，一排有N个座位，分别编号为0, 1, 2, ..., N-1。
当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。
如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)
返回ExamRoom(int N)类，它有两个公开的函数：其中，函数ExamRoom.seat()会返回一个int（整型数据），代表学生坐的位置；
函数ExamRoom.leave(int p)代表坐在座位 p 上的学生现在离开了考场。
每次调用ExamRoom.leave(p)时都保证有学生坐在座位p上。
示例：输入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
输出：[null,0,9,4,2,null,5]
解释：ExamRoom(10) -> null
seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。
seat() -> 9，学生最后坐在 9 号座位上。
seat() -> 4，学生最后坐在 4 号座位上。
seat() -> 2，学生最后坐在 2 号座位上。
leave(4) -> null
seat() -> 5，学生最后坐在 5 号座位上。
提示：1 <= N <= 10^9
在所有的测试样例中ExamRoom.seat()和ExamRoom.leave()最多被调用10^4次。
保证在调用ExamRoom.leave(p)时有学生正坐在座位 p 上。
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
856.括号的分数(3)¶
题目
给定一个平衡括号字符串S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得A + B分，其中 A 和 B 是平衡括号字符串。
(A) 得2 * A分，其中 A 是平衡括号字符串。
示例 1：输入： "()" 输出： 1
示例 2：输入： "(())" 输出： 2
示例3：输入： "()()" 输出： 2
示例4：输入： "(()(()))" 输出： 6
提示：S是平衡括号字符串，且只含有(和)。
2 <= S.length <= 50
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 栈辅助 | O(n) | O(n) |
| 03 | 分治 | O(n^2) | O(n) |
func scoreOfParentheses(S string) int {
res := 0
count := 0
for i := 0; i < len(S); i++ {
if S[i] == '(' {
count++
} else {
count--
if S[i-1] == '(' {
res = res + 1<<count
}
}
}
return res
}
# 2
func scoreOfParentheses(S string) int {
stack := make([]int, 0)
stack = append(stack, 0)
for i := 0; i < len(S); i++ {
if S[i] == '(' {
stack = append(stack, 0)
} else {
a, b := stack[len(stack)-1], stack[len(stack)-2]
stack = stack[:len(stack)-2]
stack = append(stack, b+max(2*a, 1))
}
}
return stack[0]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func scoreOfParentheses(S string) int {
return dfs(S, 0, len(S))
}
func dfs(S string, left, right int) int {
res := 0
count := 0
for i := left; i < right; i++ {
if S[i] == '(' {
count++
} else {
count--
}
if count == 0 {
if i-left == 1 {
res++
} else {
res = res + 2*dfs(S, left+1, i)
}
left = i + 1
}
}
return res
}
858.镜面反射¶
题目¶
有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为0，1，以及2。
正方形房间的墙壁长度为p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。
返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。
示例：输入： p = 2, q = 1 输出： 2
解释： 这条光线在第一次被反射回左边的墙时就遇到了接收器 2 。
提示：1 <= p <= 1000
0 <= q <= p
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(1) |
861.翻转矩阵后的得分(2)¶
题目
有一个二维矩阵A 其中每个元素的值为0或1。
移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。
在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。
返回尽可能高的分数。
示例：输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]] 输出：39
解释：转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
提示：1 <= A.length <= 20
1 <= A[0].length <= 20
A[i][j]是0 或1
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(1) |
| 02 | 遍历 | O(n^2) | O(1) |
func matrixScore(A [][]int) int {
var res int
if len(A) == 0 || len(A[0]) == 0 {
return 0
}
// 翻转行，每行第一个为0则翻转
for i := 0; i < len(A); i++ {
if A[i][0] == 0 {
for j := 0; j < len(A[i]); j++ {
A[i][j] = 1 - A[i][j]
}
}
}
// 翻转列,每列1的数量大于0则翻转
for j := 0; j < len(A[0]); j++ {
a, b := 0, 0
for i := 0; i < len(A); i++ {
if A[i][j] == 0 {
a++
} else {
b++
}
}
if a <= b {
continue
}
for i := 0; i < len(A); i++ {
A[i][j] = 1 - A[i][j]
}
}
for i := 0; i < len(A); i++ {
sum := 0
for j := 0; j < len(A[i]); j++ {
sum = sum*2 + A[i][j]
}
res = res + sum
}
return res
}
# 2
func matrixScore(A [][]int) int {
var res int
if len(A) == 0 || len(A[0]) == 0 {
return 0
}
n := len(A)
m := len(A[0])
// 首先每行第一个都为1求和，n个长度为m的1x...x
// 这样保证第一列全为1
res = res + n*(1<<(m-1))
for j := 1; j < m; j++ {
a, b := 0, 0
for i := 0; i < n; i++ {
if A[i][0] == 0 && A[i][j] == 0 { // 需要翻转
b++
} else if A[i][0] == 1 && A[i][j] == 1 { // 不需要翻转
b++
} else {
a++
}
}
// 1比0多，不需要翻转
if a <= b {
res = res + b*(1<<(m-1-j))
} else {
res = res + a*(1<<(m-1-j))
}
}
return res
}
863.二叉树中所有距离为K的结点(1)¶
题目
给定一个二叉树（具有根结点root），一个目标结点target，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
示例 1：输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2 输出：[7,4,1]
解释：所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1
注意，输入的 "root" 和 "target" 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。
提示：给定的树是非空的。
树上的每个结点都具有唯一的值0 <= node.val <= 500。
目标结点target是树上的结点。
0 <= K <= 1000.
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(n) | O(log(n)) |
var m map[int]*TreeNode // 存储值对应的父节点
var res []int
func distanceK(root *TreeNode, target *TreeNode, K int) []int {
m = make(map[int]*TreeNode)
res = make([]int, 0)
dfs(root) // 生成值对应的父节点
findDfs(K, target, nil, 0) // 遍历
return res
}
func dfs(root *TreeNode) {
if root == nil {
return
}
if root.Left != nil {
m[root.Left.Val] = root
dfs(root.Left)
}
if root.Right != nil {
m[root.Right.Val] = root
dfs(root.Right)
}
}
func findDfs(K int, node *TreeNode, prev *TreeNode, dis int) {
if node == nil {
return
}
if dis == K {
res = append(res, node.Val)
return
}
if node.Left != prev { // 防止重复
findDfs(K, node.Left, node, dis+1)
}
if node.Right != prev { // 防止重复
findDfs(K, node.Right, node, dis+1)
}
if m[node.Val] != prev { // 防止重复：搜索父节点
findDfs(K, m[node.Val], node, dis+1)
}
}
865.具有所有最深节点的最小子树(2)¶
题目
给定一个根为root的二叉树，每个节点的深度是 该节点到根的最短距离 。
如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。
一个节点的 子树 是该节点加上它的所有后代的集合。
返回能满足 以该节点为根的子树中包含所有最深的节点 这一条件的具有最大深度的节点。
注意：本题与力扣 1123 重复：
示例 1：输入：root = [3,5,1,6,2,0,8,null,null,7,4] 输出：[2,7,4]
解释： 我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。
示例 2：输入：root = [1] 输出：[1]
解释：根节点是树中最深的节点。
示例 3：输入：root = [0,1,3,null,2] 输出：[2]
解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。
提示：树中节点的数量介于1 和500 之间。
0 <= Node.val <= 500
每个节点的值都是独一无二的。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(n) | O(log(n)) |
| 02 | 递归 | O(n^2) | O(log(n)) |
func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
res, _ := dfs(root, 0)
return res
}
func dfs(root *TreeNode, level int) (*TreeNode, int) {
if root == nil {
return root, level
}
leftNode, left := dfs(root.Left, level+1)
rightNode, right := dfs(root.Right, level+1)
if left == right {
return root, left + 1
} else if left > right {
return leftNode, left + 1
}
return rightNode, right + 1
}
# 2
func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
left := dfs(root.Left)
right := dfs(root.Right)
if left == right {
return root
} else if left > right {
return subtreeWithAllDeepest(root.Left)
}
return subtreeWithAllDeepest(root.Right)
}
func dfs(root *TreeNode) int {
if root == nil {
return 0
}
left := dfs(root.Left)
right := dfs(root.Right)
return 1 + max(left, right)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
866.回文素数(1)¶
题目
求出大于或等于N的最小回文素数。
回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。
例如，2，3，5，7，11 以及13 是素数。
回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。
例如，12321 是回文数。
示例 1：输入：6 输出：7
示例2：输入：8 输出：11
示例3：输入：13 输出：101
提示：1 <= N <= 10^8
答案肯定存在，且小于2 * 10^8。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法 | O(n^(1/2)) | O(1) |
func primePalindrome(N int) int {
if 8 <= N && N <= 11 { // 特判：偶数位的回文数都可以被11整除
return 11
}
for i := 1; i < 100000; i++ {
s := strconv.Itoa(i)
temp := []byte(s)
for i := 0; i < len(s)/2; i++ {
temp[i], temp[len(s)-1-i] = temp[len(s)-1-i], temp[i]
}
target, _ := strconv.Atoi(s + string(temp[1:]))
if target >= N && isPrime(target) {
return target
}
}
return -1
}
func isPrime(n int) bool {
if n < 2 {
return false
}
for i := 2; i*i <= n; i++ {
if n%i == 0 {
return false
}
}
return true
}
869.重新排序得到2的幂(1)¶
题目
给定正整数 N，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到2 的幂，返回 true；否则，返回 false。
示例 1：输入：1 输出：true
示例 2：输入：10 输出：false
示例 3：输入：16 输出：true
示例 4：输入：24 输出：false
示例 5：输入：46 输出：true
提示：1 <= N <= 10^9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(log(n)^2) | O(1) |
func reorderedPowerOf2(N int) bool {
arr := getCount(N)
for i := 0; i < 31; i++ {
if arr == getCount(1<<i) {
return true
}
}
return false
}
func getCount(n int) [10]int {
arr := [10]int{}
for n > 0 {
arr[n%10]++
n = n / 10
}
return arr
}
870.优势洗牌(1)¶
题目
给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。
返回 A 的任意排列，使其相对于 B 的优势最大化。
示例 1：输入：A = [2,7,11,15], B = [1,10,4,11] 输出：[2,11,7,15]
示例 2：输入：A = [12,24,8,32], B = [13,25,32,11] 输出：[24,32,8,12]
提示： 1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 贪心 | O(nlog(n)) | O(n) |
func advantageCount(A []int, B []int) []int {
res := make([]int, len(A))
sort.Ints(A)
arr := make([][2]int, 0)
for i := 0; i < len(B); i++ {
arr = append(arr, [2]int{i, B[i]})
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][1] < arr[j][1]
})
left, right := 0, len(A)-1
for i := 0; i < len(A); i++ {
if A[i] > arr[left][1] { // 满足条件放前面
index := arr[left][0]
left++
res[index] = A[i]
} else { // 不满足条件放后面
index := arr[right][0]
right--
res[index] = A[i]
}
}
return res
}
873.最长的斐波那契子序列的长度(2)¶
题目
如果序列X_1, X_2, ..., X_n满足下列条件，就说它是斐波那契式的：
n >= 3
对于所有i + 2 <= n，都有X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回0 。
（回想一下，子序列是从原序列 A中派生出来的，它从 A中删掉任意数量的元素（也可以不删），
而不改变其余元素的顺序。例如，[3, 5, 8]是[3, 4, 5, 6, 7, 8]的一个子序列）
示例 1：输入: [1,2,3,4,5,6,7,8] 输出: 5
解释:最长的斐波那契式子序列为：[1,2,3,5,8] 。
示例2：输入: [1,3,7,11,12,14,18] 输出: 3
解释:最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。
提示：3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
（对于以 Java，C，C++，以及C# 的提交，时间限制被减少了 50%）
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法 | O(n^3) | O(n) |
| 02 | 动态规划 | O(n^2) | O(n^2) |
func lenLongestFibSubseq(arr []int) int {
n := len(arr)
m := make(map[int]bool)
for i := 0; i < n; i++ {
m[arr[i]] = true
}
res := 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
count := 2
a, b := arr[i], arr[j]
for m[a+b] == true {
count++
a, b = b, a+b
}
if count > res && count > 2 {
res = count
}
}
}
return res
}
# 2
func lenLongestFibSubseq(arr []int) int {
n := len(arr)
m := make(map[int]int)
for i := 0; i < n; i++ {
m[arr[i]] = i
}
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
res := 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
dp[i][j] = 2
}
}
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
index, ok := m[arr[i]-arr[j]]
if ok && arr[index] < arr[j] {
dp[j][i] = dp[index][j] + 1
if dp[j][i] > 2 && dp[j][i] > res {
res = dp[j][i]
}
}
}
}
return res
}
875.爱吃香蕉的珂珂(2)¶
题目
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。
如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
示例 1：输入: piles = [3,6,7,11], H = 8 输出: 4
示例 2：输入: piles = [30,11,23,4,20], H = 5 输出: 30
示例 3：输入: piles = [30,11,23,4,20], H = 6 输出: 23
提示：1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 二分查找 | O(nlog(n)) | O(1) |
| 02 | 内置函数 | O(nlog(n)) | O(1) |
func minEatingSpeed(piles []int, H int) int {
maxValue := piles[0]
for i := 1; i < len(piles); i++ {
maxValue = max(maxValue, piles[i])
}
left, right := 1, maxValue
for left < right {
mid := left + (right-left)/2
if judge(piles, mid, H) == true {
left = mid + 1
} else {
right = mid
}
}
return left
}
func judge(piles []int, speed int, H int) bool {
total := 0
for i := 0; i < len(piles); i++ {
total = total + piles[i]/speed
if piles[i]%speed > 0 {
total = total + 1
}
}
return total > H
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func minEatingSpeed(piles []int, h int) int {
maxValue := piles[0]
for i := 1; i < len(piles); i++ {
maxValue = max(maxValue, piles[i])
}
return sort.Search(maxValue, func(speed int) bool {
if speed == 0 { // 避免除0
return false
}
total := 0
for i := 0; i < len(piles); i++ {
total = total + piles[i]/speed
if piles[i]%speed > 0 {
total = total + 1
}
}
return total <= h
})
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
877.石子游戏(3)¶
题目
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。
这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
示例：输入：[5,3,4,5] 输出：true
解释：亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。
提示：2 <= piles.length <= 500
piles.length 是偶数。
1 <= piles[i] <= 500
sum(piles) 是奇数。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划-一维 | O(n^2) | O(n) |
| 02 | 动态规划-二维 | O(n^2) | O(n^2) |
| 03 | 数学 | O(1) | O(1) |
func stoneGame(piles []int) bool {
dp := make([]int, len(piles))
for i := 0; i < len(piles); i++ {
dp[i] = piles[i]
}
for i := len(piles) - 2; i >= 0; i-- {
for j := i + 1; j < len(piles); j++ {
dp[j] = max(piles[i]-dp[j], piles[j]-dp[j-1])
}
}
return dp[len(piles)-1] >= 0
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func stoneGame(piles []int) bool {
n := len(piles)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
dp[i][i] = piles[i]
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
// 玩家得分：自己得分-对手得分
dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1])
}
}
return dp[0][n-1] >= 0
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func stoneGame(piles []int) bool {
return true
}
880.索引处的解码字符串(2)¶
题目
给定一个编码字符串 S。请你找出 解码字符串 并将其写入磁带。
解码时，从编码字符串中 每次读取一个字符 ，并采取以下步骤：
如果所读的字符是字母，则将该字母写在磁带上。
如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写d-1 次。
现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第K个字母。
示例 1：输入：S = "leet2code3", K = 10 输出："o"
解释：解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
字符串中的第 10 个字母是 "o"。
示例 2：输入：S = "ha22", K = 5 输出："h"
解释： 解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。
示例 3：输入：S = "a2345678999999999999999", K = 1 输出："a"
解释： 解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。
提示：2 <= S.length <= 100
S只包含小写字母与数字 2 到 9 。
S以字母开头。
1 <= K <= 10^9
题目保证 K 小于或等于解码字符串的长度。
解码后的字符串保证少于2^63个字母。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 递归 | O(n) | O(1) |
func decodeAtIndex(S string, K int) string {
count := 0 // 字符个数
n := len(S)
for i := 0; i < n; i++ { // 先统计最终字符串总长数
if '0' <= S[i] && S[i] <= '9' {
value := int(S[i] - '0')
count = count * value // 重写d-1次，长度是原来的d倍
} else {
count++ // 非数字，长度+1
}
}
for i := n - 1; i >= 0; i-- {
K = K % count // 缩小范围
if K == 0 && 'a' <= S[i] && S[i] <= 'z' { // 找到目标字符
return string(S[i])
}
if '0' <= S[i] && S[i] <= '9' { // 范围缩小
value := int(S[i] - '0')
count = count / value
} else {
count-- // 长度-1
}
}
return ""
}
# 2
func decodeAtIndex(S string, K int) string {
count := 0 // 字符个数
n := len(S)
for i := 0; i < n; i++ { // 先统计最终字符串总长数
if '0' <= S[i] && S[i] <= '9' {
value := int(S[i] - '0')
prev := count
count = count * value // 重写d-1次，长度是原来的d倍
if count >= K {
return decodeAtIndex(S[:i], (K-1)%prev+1) // 缩小范围：避免求余出现0的情况
}
} else {
count++ // 非数字，长度+1
if count == K {
return string(S[i])
}
}
}
return ""
}
881.救生艇(1)¶
题目
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
示例 1：输入：people = [1,2], limit = 3输出：1 解释：1 艘船载 (1, 2)
示例 2：输入：people = [3,2,2,1], limit = 3 输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：输入：people = [3,5,3,4], limit = 5 输出：4
解释：4 艘船分别载 (3), (3), (4), (5)
提示：1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序双指针 | O(nlog(n)) | O(1) |
func numRescueBoats(people []int, limit int) int {
res := 0
sort.Ints(people)
i, j := 0, len(people)-1
for i <= j {
if people[i]+people[j] <= limit {
i++
j--
} else {
j--
}
res++
}
return res
}
885.螺旋矩阵III(2)¶
题目
在R行C列的矩阵上，我们从(r0, c0)面朝东面开始
这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。
每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。
最终，我们到过网格的所有R * C个空间。
按照访问顺序返回表示网格位置的坐标列表。
示例 1：输入：R = 1, C = 4, r0 = 0, c0 = 0 输出：[[0,0],[0,1],[0,2],[0,3]]
示例 2：输入：R = 5, C = 6, r0 = 1, c0 = 4 输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],
[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],
[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
提示：1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(n^2) |
| 02 | 遍历 | O(n^2) | O(n^2) |
// 顺时针：上右下左
// 本题：右、下、左、上
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func spiralMatrixIII(rows int, cols int, rStart int, cStart int) [][]int {
res := make([][]int, 0)
total := rows * cols
x, y := rStart, cStart
res = append(res, []int{x, y})
index := 1
if total == 1 {
return res
}
for k := 1; k < 2*(rows+cols); k = k + 2 {
for i := 0; i < 4; i++ {
step := k + i/2 // 本次移动的步数，分别是2次的倍数
for j := 0; j < step; j++ {
x = x + dx[i]
y = y + dy[i]
if 0 <= x && x < rows && 0 <= y && y < cols {
res = append(res, []int{x, y})
index++
if index == total {
return res
}
}
}
}
}
return res
}
# 2
// 顺时针：上右下左
// 本题：右、下、左、上
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func spiralMatrixIII(rows int, cols int, rStart int, cStart int) [][]int {
res := make([][]int, 0)
total := rows * cols
x, y := rStart, cStart
index := 0
step := 2
dir := 0
for index < total {
for i := 0; i < step/2; i++ { // 本次移动的步数
if 0 <= x && x < rows && 0 <= y && y < cols {
res = append(res, []int{x, y})
index++
if index == total {
return res
}
}
x = x + dx[dir]
y = y + dy[dir]
}
dir = (dir + 1) % 4
step++
}
return res
}
886.可能的二分法(3)¶
题目
给定一组N人（编号为1, 2, ..., N），我们想把每个人分进任意大小的两组。
每个人都可能不喜欢其他人，那么他们不应该属于同一组。
形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。
当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
示例 1：输入：N = 4, dislikes = [[1,2],[1,3],[2,4]] 输出：true
解释：group1 [1,4], group2 [2,3]
示例 2：输入：N = 3, dislikes = [[1,2],[1,3],[2,3]] 输出：false
示例 3：输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] 输出：false
提示：1 <= N <= 2000
0 <= dislikes.length <= 10000
dislikes[i].length == 2
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
对于 dislikes[i] == dislikes[j] 不存在 i != j
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 深度优先搜索 | O(n) | O(n) |
| 02 | 广度优先搜索 | O(n) | O(n) |
| 03 | 并查集 | O(n) | O(n) |
var arr [][]int
var m map[int]int
func possibleBipartition(n int, dislikes [][]int) bool {
m = make(map[int]int) // 分组： 0一组，1一组
arr = make([][]int, n+1)
for i := 0; i < len(dislikes); i++ {
a, b := dislikes[i][0], dislikes[i][1]
arr[a] = append(arr[a], b)
arr[b] = append(arr[b], a)
}
for i := 1; i <= n; i++ {
// 没有被分配过，分配到0一组
if _, ok := m[i]; ok == false && dfs(i, 0) == false {
return false
}
}
return true
}
func dfs(index int, value int) bool {
if v, ok := m[index]; ok {
return v == value // 已经分配，查看是否同一组
}
m[index] = value
for i := 0; i < len(arr[index]); i++ {
target := arr[index][i]
if dfs(target, 1-value) == false { // 不喜欢的人，分配到对立组：1-value
return false
}
}
return true
}
# 2
func possibleBipartition(n int, dislikes [][]int) bool {
m := make(map[int]int) // 分组： 0一组，1一组
arr := make([][]int, n+1)
for i := 0; i < len(dislikes); i++ {
a, b := dislikes[i][0], dislikes[i][1]
arr[a] = append(arr[a], b)
arr[b] = append(arr[b], a)
}
for i := 1; i <= n; i++ {
// 没有被分配过，分配到0一组
if _, ok := m[i]; ok == true {
continue
}
m[i] = 0
queue := make([]int, 0)
queue = append(queue, i)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for i := 0; i < len(arr[node]); i++ {
target := arr[node][i]
if _, ok := m[target]; ok == false {
m[target] = 1 - m[node] // 相反一组
queue = append(queue, target)
} else if m[node] == m[target] { // 已经分配，查看是否同一组
return false
}
}
}
}
return true
}
# 3
func possibleBipartition(n int, dislikes [][]int) bool {
fa = Init(n + 1)
arr := make([][]int, n+1)
for i := 0; i < len(dislikes); i++ {
a, b := dislikes[i][0], dislikes[i][1]
arr[a] = append(arr[a], b)
arr[b] = append(arr[b], a)
}
for i := 1; i <= n; i++ {
for j := 0; j < len(arr[i]); j++ {
target := arr[i][j]
if find(i) == find(target) { // 和不喜欢的人在相同组，失败
return false
}
union(arr[i][0], target) // 不喜欢的人在同一组
}
}
return true
}
var fa []int
// 初始化
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
return arr
}
// 查询
func find(x int) int {
for x != fa[x] {
fa[x] = fa[fa[x]]
x = fa[x]
}
return x
}
// 合并
func union(i, j int) {
fa[find(i)] = find(j)
}
889.根据前序和后序遍历构造二叉树(1)¶
题目
返回与给定的前序和后序遍历匹配的任何二叉树。
pre和post遍历中的值是不同的正整数。
示例：输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]
提示：1 <= pre.length == post.length <= 30
pre[]和post[]都是1, 2, ..., pre.length的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(n^2) | O(n) |
func constructFromPrePost(pre []int, post []int) *TreeNode {
if len(pre) == 0 {
return nil
}
root := &TreeNode{
Val: pre[0],
}
if len(pre) == 1 {
return root
}
index := len(pre)
for i := 0; i < len(post); i++ {
if post[i] == pre[1] {
index = i
break
}
}
root.Left = constructFromPrePost(pre[1:index+2], post[:index+1])
root.Right = constructFromPrePost(pre[index+2:], post[index+1:])
return root
}
890.查找和替换模式(2)¶
题目
你有一个单词列表words和一个模式pattern，你想知道 words 中的哪些单词与模式匹配。
如果存在字母的排列 p，使得将模式中的每个字母 x 替换为 p(x) 之后，
我们就得到了所需的单词，那么单词与模式是匹配的。
（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）
返回 words 中与给定模式匹配的单词列表。
你可以按任何顺序返回答案。
示例：输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出：["mee","aqq"]
解释："mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。
提示：1 <= words.length <= 50
1 <= pattern.length = words[i].length<= 20
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 双哈希 | O(n^2) | O(n) |
| 02 | 双哈希 | O(n^2) | O(n) |
func findAndReplacePattern(words []string, pattern string) []string {
res := make([]string, 0)
for i := 0; i < len(words); i++ {
m1, m2 := make(map[byte]byte), make(map[byte]byte)
flag := true
for j := 0; j < len(pattern); j++ {
x, y := pattern[j], words[i][j]
a, ok1 := m1[x]
b, ok2 := m2[y]
if ok1 == false && ok2 == false {
m1[x] = y
m2[y] = x
}
if (ok1 == true && ok2 == false) || (ok1 == false && ok2 == true) ||
(ok1 == true && ok2 == true && (a != y || b != x)) {
flag = false
break
}
}
if flag == true {
res = append(res, words[i])
}
}
return res
}
# 2
func findAndReplacePattern(words []string, pattern string) []string {
res := make([]string, 0)
for i := 0; i < len(words); i++ {
m1, m2 := make(map[byte]byte), make(map[byte]byte)
flag := true
for j := 0; j < len(pattern); j++ {
x, y := pattern[j], words[i][j]
if m1[x] == 0 && m2[y] == 0 {
m1[x] = y
m2[y] = x
} else if (m1[x] == y && m2[y] == x) == false {
flag = false
break
}
}
if flag == true {
res = append(res, words[i])
}
}
return res
}
894.所有可能的满二叉树(3)¶
题目
满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。
返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
答案中每个树的每个结点都必须有 node.val=0。
你可以按任何顺序返回树的最终列表。
示例：输入：7
输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],
[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
解释：
提示：1 <= N <= 20
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(2^n) | O(2^n) |
| 02 | 遍历 | O(2^n) | O(2^n) |
| 03 | 递归 | O(2^n) | O(2^n) |
var res map[int][]*TreeNode
func allPossibleFBT(n int) []*TreeNode {
res = make(map[int][]*TreeNode)
dfs(n)
return res[n]
}
func dfs(n int) []*TreeNode {
if _, ok := res[n]; !ok {
arr := make([]*TreeNode, 0)
if n == 1 {
arr = append(arr, &TreeNode{Val: 0})
} else if n%2 == 1 { // N只为奇数
for i := 0; i < n; i++ {
j := n - 1 - i
for _, left := range dfs(i) {
for _, right := range dfs(j) {
root := &TreeNode{Val: 0}
root.Left = left
root.Right = right
arr = append(arr, root)
}
}
}
}
res[n] = arr
}
return res[n]
}
# 2
func allPossibleFBT(n int) []*TreeNode {
res := make(map[int][]*TreeNode)
res[1] = []*TreeNode{{Val: 0}}
for index := 3; index <= n; index = index + 2 {
for i := 1; i < index; i = i + 2 {
j := index - 1 - i
for _, left := range res[i] {
for _, right := range res[j] {
res[index] = append(res[index], &TreeNode{
Val: 0,
Left: left,
Right: right,
})
}
}
}
}
return res[n]
}
# 3
func allPossibleFBT(n int) []*TreeNode {
if n == 1 {
return []*TreeNode{{Val: 0}}
}
res := make([]*TreeNode, 0)
for i := 1; i < n; i = i + 2 {
leftResult := allPossibleFBT(i)
rightResult := allPossibleFBT(n - 1 - i)
for _, left := range leftResult {
for _, right := range rightResult {
res = append(res, &TreeNode{
Val: 0,
Left: left,
Right: right,
})
}
}
}
return res
}
898.子数组按位或操作(2)¶
题目
我们有一个非负整数数组A。
对于每个（连续的）子数组B =[A[i], A[i+1], ..., A[j]] （i <= j），
我们对B中的每个元素进行按位或操作，获得结果A[i] | A[i+1] | ... | A[j]。
返回可能结果的数量。 （多次出现的结果在最终答案中仅计算一次。）
示例 1：输入：[0] 输出：1
解释：只有一个可能的结果 0 。
示例 2：输入：[1,1,2] 输出：3
解释：可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。
示例3：输入：[1,2,4] 输出：6
解释：可能的结果是 1，2，3，4，6，以及 7 。
提示：1 <= A.length <= 50000
0 <= A[i] <= 10^9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希辅助 | O(n^2) | O(n) |
| 02 | 哈希辅助 | O(n^2) | O(n) |
func subarrayBitwiseORs(arr []int) int {
m := make(map[int]bool)
for i := 0; i < len(arr); i++ {
m[arr[i]] = true
temp := 0
for j := i - 1; j >= 0; j-- {
if temp|arr[i] == temp { // 都为1，进行下去无意义，避免超时
break
}
temp = temp | arr[j]
m[temp|arr[i]] = true
}
}
return len(m)
}
# 2
func subarrayBitwiseORs(arr []int) int {
m := make(map[int]bool)
for i := 0; i < len(arr); i++ {
m[arr[i]] = true
for j := i - 1; j >= 0; j-- {
if arr[j]|arr[i] == arr[j] {
break
}
arr[j] = arr[j] | arr[i]
m[arr[j]] = true
}
}
return len(m)
}
900.RLE迭代器(2)¶
题目
编写一个遍历游程编码序列的迭代器。
迭代器由 RLEIterator(int[] A) 初始化，其中A是某个序列的游程编码。
更具体地，对于所有偶数 i，A[i] 告诉我们在序列中重复非负整数值 A[i + 1] 的次数。
迭代器支持一个函数：next(int n)，它耗尽接下来的 n 个元素（n >= 1）并返回以这种方式耗去的最后一个元素。
如果没有剩余的元素可供耗尽，则 next返回-1 。
例如，我们以A = [3,8,0,9,2,5]开始，这是序列[8,8,8,5,5]的游程编码。
这是因为该序列可以读作 “三个八，零个九，两个五”。
示例：输入：["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
输出：[null,8,8,5,-1]
解释：RLEIterator 由 RLEIterator([3,8,0,9,2,5]) 初始化。
这映射到序列 [8,8,8,5,5]。
然后调用 RLEIterator.next 4次。
.next(2) 耗去序列的 2 个项，返回 8。现在剩下的序列是 [8, 5, 5]。
.next(1) 耗去序列的 1 个项，返回 8。现在剩下的序列是 [5, 5]。
.next(1) 耗去序列的 1 个项，返回 5。现在剩下的序列是 [5]。
.next(2) 耗去序列的 2 个项，返回 -1。 这是由于第一个被耗去的项是 5，
但第二个项并不存在。由于最后一个要耗去的项不存在，我们返回 -1。
提示：0 <= A.length <= 1000
A.length是偶数。
0 <= A[i] <= 10^9
每个测试用例最多调用1000次RLEIterator.next(int n)。
每次调用RLEIterator.next(int n)都有1 <= n <= 10^9。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(n) |
| 02 | 前缀和+二分查找 | O(nlog(n)) | O(n) |
type RLEIterator struct {
arr []int
index int // 第几个元素
count int // 元素的第几次
}
func Constructor(encoding []int) RLEIterator {
return RLEIterator{
arr: encoding,
index: 0,
count: 0,
}
}
func (this *RLEIterator) Next(n int) int {
for this.index < len(this.arr) {
if n+this.count > this.arr[this.index] {
n = n - (this.arr[this.index] - this.count)
this.count = 0
this.index = this.index + 2
} else {
this.count = this.count + n
return this.arr[this.index+1]
}
}
return -1
}
# 2
type RLEIterator struct {
arr []int
total int
values []int
cur int
}
func Constructor(encoding []int) RLEIterator {
total := 0
arr := make([]int, 0) // 前缀和
values := make([]int, 0)
for i := 0; i < len(encoding); i = i + 2 {
if encoding[i] == 0 {
continue
}
total = total + encoding[i]
arr = append(arr, total)
values = append(values, encoding[i+1])
}
return RLEIterator{
arr: arr,
total: total,
cur: 0,
values: values,
}
}
func (this *RLEIterator) Next(n int) int {
target := this.cur + n
this.cur = target
if target > this.total {
return -1
}
left, right := 0, len(this.arr)
for left < right {
mid := left + (right-left)/2
if this.arr[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return this.values[left]
}
0801-0900-Hard¶
810.黑板异或游戏(1)¶
题目
黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。
如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。
(另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为0。）
并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。
假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。
示例：输入: nums = [1, 1, 2] 输出: false
解释: Alice 有两个选择: 擦掉数字 1 或 2。
如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。
那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。
如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。
提示：1 <= N <= 1000
0 <= nums[i] <= 2^16
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 异或 | O(n) | O(1) |
func xorGame(nums []int) bool {
n := len(nums)
res := 0
for i := 0; i < n; i++ {
res = res ^ nums[i]
}
return res == 0 || n%2 == 0
}
815.公交路线(2)¶
题目
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes[0] = [1, 5, 7]
表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6 输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 输出：-1
提示：1 <= routes.length <= 500.
1 <= routes[i].length <= 105
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 广度优先搜索 | O(n^3) | O(n) |
| 02 | 广度优先搜索 | O(n^2) | O(n^2) |
func numBusesToDestination(routes [][]int, source int, target int) int {
if source == target {
return 0
}
n := len(routes)
m := make(map[int][]int) // 该公交车经过第几条线路的数组
for i := 0; i < n; i++ {
for j := 0; j < len(routes[i]); j++ {
node := routes[i][j]
m[node] = append(m[node], i)
}
}
count := 1
queue := make([]int, 0)
queue = append(queue, source)
visited := make(map[int]bool) // 第几条线路访问情况
for len(queue) > 0 {
length := len(queue)
for i := 0; i < length; i++ {
node := queue[i]
for j := 0; j < len(m[node]); j++ {
if visited[m[node][j]] == false {
visited[m[node][j]] = true
for k := 0; k < len(routes[m[node][j]]); k++ {
if routes[m[node][j]][k] == target {
return count
}
queue = append(queue, routes[m[node][j]][k])
}
}
}
}
count++
queue = queue[length:]
}
return -1
}
# 2
func numBusesToDestination(routes [][]int, source int, target int) int {
if source == target {
return 0
}
n := len(routes)
m := make(map[int][]int) // 该公交车经过第几条线路的数组
dis := make([]int, n) // source到第i条线路的距离
arr := make([][]bool, n)
for i := 0; i < n; i++ {
arr[i] = make([]bool, n)
dis[i] = -1
}
for i := 0; i < n; i++ {
for j := 0; j < len(routes[i]); j++ {
node := routes[i][j]
m[node] = append(m[node], i)
for _, v := range m[node] {
arr[i][v] = true
arr[v][i] = true
}
}
}
queue := make([]int, 0)
for _, v := range m[source] {
dis[v] = 1
queue = append(queue, v)
}
for len(queue) > 0 { // 广度优先计算source所在公交站台，到其它站台的最小距离
node := queue[0]
queue = queue[1:]
for i := 0; i < n; i++ {
if arr[node][i] == true && dis[i] == -1 { // node可以到i，且i未访问过
dis[i] = dis[node] + 1
queue = append(queue, i)
}
}
}
res := math.MaxInt32 // 最短路径
for i := 0; i < len(m[target]); i++ { // 遍历多终点，找最小
v := m[target][i]
if dis[v] != -1 && dis[v] < res {
res = dis[v]
}
}
if res < math.MaxInt32 {
return res
}
return -1
}
827.最大人工岛¶
题目¶
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格0 变成1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的1 形成。
示例 1:输入: grid = [[1, 0], [0, 1]] 输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
示例 2:输入: grid = [[1, 1], [1, 0]] 输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
示例 3:输入: grid = [[1, 1], [1, 1]] 输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
提示：n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] 为 0 或 1
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(1) |
828.统计子串中的唯一字符(4)¶
题目
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。
注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
由于答案可能非常大，请将结果 mod 10 ^ 9 + 7 后再返回。
示例 1：输入: s = "ABC" 输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
其中，每一个子串都由独特字符构成。
所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
示例 2：输入: s = "ABA" 输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。
示例 3：输入：s = "LEETCODE" 输出：92
提示：0 <= s.length <= 10^4
s 只包含大写英文字符
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(1) |
| 02 | 遍历 | O(n) | O(n) |
| 03 | 遍历 | O(n) | O(n) |
| 04 | 遍历 | O(n) | O(1) |
var mod = 1000000007
func uniqueLetterString(s string) int {
res := 0
var j, k int
n := len(s)
for i := 0; i < n; i++ { // 计算当前字符 作为 唯一字符 的子串的次数
for j = i - 1; 0 <= j && s[i] != s[j]; j-- {
}
for k = i + 1; k < n && s[i] != s[k]; k++ {
}
res = (res + (i-j)*(k-i)) % mod // 总数：left * right
}
return res
}
# 2
var mod = 1000000007
var cur [26]int
func uniqueLetterString(s string) int {
res := 0
n := len(s)
cur = [26]int{} // 记录每个字符的下标进度
arr := [26][]int{} // 记录每个字符的所有下标列表
for i := 0; i < n; i++ {
index := int(s[i] - 'A')
arr[index] = append(arr[index], i)
}
sum := 0 // 26种字符，作为唯一字符的总次数
for i := 0; i < 26; i++ {
arr[i] = append(arr[i], n, n) // 补2个n
sum = sum + getDiff(arr, i)
}
for i := 0; i < n; i++ {
res = (res + sum) % mod
index := int(s[i] - 'A')
prev := getDiff(arr, index)
cur[index]++
sum = sum + getDiff(arr, index) - prev // 更新次数
}
return res
}
func getDiff(arr [26][]int, index int) int { // 第i+1个和第i个下标的距离
i := cur[index]
return arr[index][i+1] - arr[index][i]
}
# 3
var mod = 1000000007
func uniqueLetterString(s string) int {
res := 0
n := len(s)
arr := [26][]int{} // 记录每个字符的所有下标列表
for i := 0; i < n; i++ {
index := int(s[i] - 'A')
arr[index] = append(arr[index], i)
}
for i := 0; i < 26; i++ {
for j := 0; j < len(arr[i]); j++ {
var prev, next int
cur := arr[i][j]
if j == 0 {
prev = -1
} else {
prev = arr[i][j-1]
}
if j == len(arr[i])-1 {
next = n
} else {
next = arr[i][j+1]
}
res = (res + (cur-prev)*(next-cur)) % mod
}
}
return res
}
# 4
var mod = 1000000007
func uniqueLetterString(s string) int {
res := 0
n := len(s)
arr := [26][2]int{} // 记录每个字符的最后2个字符下标
for i := 0; i < 26; i++ {
arr[i] = [2]int{-1, -1}
}
sum := 0
for i := 0; i < n; i++ {
index := int(s[i] - 'A')
cur := i - arr[index][1]
prev := arr[index][1] - arr[index][0]
sum = sum + cur - prev
res = (res + sum) % mod
// 更新下标
arr[index][0] = arr[index][1]
arr[index][1] = i
}
return res
}
829.连续整数求和(4)¶
题目
给定一个正整数 N，试求有多少组连续正整数满足所有数字之和为 N?
示例 1:输入: 5 输出: 2
解释: 5 = 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。
示例 2:输入: 9 输出: 3
解释: 9 = 9 = 4 + 5 = 2 + 3 + 4
示例 3:输入: 15 输出: 4
解释: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
说明:1 <= N <= 10 ^ 9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^1/2) | O(1) |
| 02 | 遍历 | O(n^1/2) | O(1) |
| 03 | 遍历 | O(n^1/2) | O(1) |
| 04 | 遍历 | O(n^1/2) | O(1) |
func consecutiveNumbersSum(N int) int {
res := 1
sum := 0
for i := 1; i < N; i++ {
sum = sum + i // 1~i
left := N - sum
if left > 0 {
if left%(i+1) == 0 { // 划分为i+1个数
res++
}
} else {
break
}
}
return res
}
# 2
func consecutiveNumbersSum(N int) int {
res := 1
for i := 1; ; i++ {
N = N - i
if N > 0 {
if N%(i+1) == 0 { // 划分为i+1个数
res++
}
} else {
break
}
}
return res
}
# 3
func consecutiveNumbersSum(N int) int {
res := 1
// N=(x+1)+(x+2)+⋯+(x+k) = kx+k*(k+1)/2
// 2N=k(2x+k+1)
target := int(math.Sqrt(float64(2 * N)))
for i := 1; i < target; i++ {
left := N - i*(i+1)/2
if left%(i+1) == 0 { // 长度i+1
res++
}
}
return res
}
# 4
func consecutiveNumbersSum(N int) int {
res := 0
i := 1
for N > 0 {
if N%i == 0 {
res++
}
N = N - i
i++
}
return res
}
834.树中距离之和¶
题目¶
给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1条边。
第 i 条边连接节点edges[i][0] 和 edges[i][1]。
返回一个表示节点 i 与其他所有节点距离之和的列表 ans。
示例 1:输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] 输出: [8,12,6,10,10,10]
解释:
如下为给定的树的示意图：
0
/ \
1 2
/|\
3 4 5
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。
说明:1 <= N <= 10000
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 堆 | O(nlog(n)) | O(n) |
839.相似字符串组(1)¶
题目
如果交换字符串X 中的两个不同位置的字母，使得它和字符串Y 相等，那么称 X 和 Y 两个字符串相似。
如果这两个字符串本身是相等的，那它们也是相似的。
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)；
"rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。
注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。
形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？
示例 1：输入：strs = ["tars","rats","arts","star"] 输出：2
示例 2：输入：strs = ["omv","ovm"] 输出：1
提示：1 <= strs.length <= 300
1 <= strs[i].length <= 300
strs[i] 只包含小写字母。
strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。
备注：字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 并查集 | O(n^3) | O(n) |
func numSimilarGroups(strs []string) int {
n := len(strs)
fa = Init(n)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if judge(strs[i], strs[j]) == true { // 满足条件，连通
union(i, j)
}
}
}
return count
}
func judge(a, b string) bool {
if a == b {
return true
}
count := 0
for i := 0; i < len(a); i++ {
if a[i] != b[i] {
count++
if count > 2 {
return false
}
}
}
return true
}
var fa []int
var count int
// 初始化
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
count = n
return arr
}
// 查询
func find(x int) int {
if fa[x] == x {
return x
}
// 路径压缩
fa[x] = find(fa[x])
return fa[x]
}
// 合并
func union(i, j int) {
x, y := find(i), find(j)
if x != y {
fa[x] = y
count--
}
}
857.雇佣K名工人的最低成本(1)¶
题目
有 N名工人。第i名工人的工作质量为quality[i]，其最低期望工资为wage[i]。
现在我们想雇佣K名工人组成一个工资组。在雇佣一组 K 名工人时，我们必须按照下述规则向他们支付工资：
对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
工资组中的每名工人至少应当得到他们的最低期望工资。
返回组成一个满足上述条件的工资组至少需要多少钱。
示例 1：输入： quality = [10,20,5], wage = [70,50,30], K = 2 输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。
示例 2：输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3 输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。
提示：1 <= K <= N <= 10000，其中N = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
与正确答案误差在10^-5之内的答案将被视为正确的。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 排序+堆 | O(nlog(n)) | O(n) |
func mincostToHireWorkers(quality []int, wage []int, k int) float64 {
n := len(quality)
arr := make([][2]int, n)
for i := 0; i < n; i++ {
arr[i] = [2]int{quality[i], wage[i]}
}
sort.Slice(arr, func(i, j int) bool {
a := float64(arr[i][1]) / float64(arr[i][0])
b := float64(arr[j][1]) / float64(arr[j][0])
return a < b
})
res := math.MaxFloat64
var sum float64
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
// 枚举最低时薪或者性价比，然后在能接受最低时薪的人中选择工作质量总和最小的k个人
for i := 0; i < n; i++ {
cur := float64(arr[i][1]) / float64(arr[i][0]) // 性价比：最低工资/质量， 比率从小到大遍历
heap.Push(&intHeap, arr[i][0]) // 质量高优先淘汰
sum = sum + float64(arr[i][0]) // 质量和
if intHeap.Len() > k {
node := heap.Pop(&intHeap).(int)
sum = sum - float64(node)
}
if intHeap.Len() == k && cur*sum < res {
res = cur * sum
}
}
return res
}
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
return h[i] > h[j]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
862.和至少为K的最短子数组(2)¶
题目
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为K的非空子数组，返回-1。
示例 1：输入：A = [1], K = 1 输出：1
示例 2：输入：A = [1,2], K = 4 输出：-1
示例 3：输入：A = [2,-1,2], K = 3 输出：3
提示：1 <= A.length <= 50000
-10 ^ 5<= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 前缀和+队列 | O(n) | O(n) |
| 02 | 前缀和+堆 | O(nlog(n)) | O(n) |
func shortestSubarray(nums []int, k int) int {
res := math.MaxInt32
n := len(nums)
arr := make([]int, n+1)
for i := 1; i <= n; i++ {
arr[i] = arr[i-1] + nums[i-1]
}
queue := make([]int, 0) // 递增队列：队首坐标小，队尾坐标大
for i := 0; i <= n; i++ {
for len(queue) > 0 && arr[i] <= arr[queue[len(queue)-1]] { // 前缀和小于队尾值：出队
queue = queue[:len(queue)-1]
}
for len(queue) > 0 && arr[i]-arr[queue[0]] >= k { // 差值大于等于k
res = min(res, i-queue[0])
queue = queue[1:]
}
queue = append(queue, i)
}
if res == math.MaxInt32 {
return -1
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
var arr []int
func shortestSubarray(nums []int, k int) int {
res := math.MaxInt32
n := len(nums)
arr = make([]int, n+1) // 前缀和在堆里面参与比较，使用全局变量
for i := 1; i <= n; i++ {
arr[i] = arr[i-1] + nums[i-1]
}
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
for i := 0; i <= n; i++ {
for intHeap.Len() > 0 && arr[i]-arr[intHeap[0]] >= k {
res = min(res, i-intHeap[0])
heap.Pop(&intHeap)
}
heap.Push(&intHeap, i)
}
if res == math.MaxInt32 {
return -1
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
return arr[h[i]] < arr[h[j]]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
871.最低加油次数(3)¶
题目
汽车从起点出发驶向目的地，该目的地位于出发位置东面 target英里处。
沿途有加油站，每个station[i]代表一个加油站，它位于出发位置东面station[i][0]英里处，
并且有station[i][1]升汽油。
假设汽车油箱的容量是无限的，其中最初有startFuel升燃料。它每行驶 1 英里就会用掉 1 升汽油。
当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。
为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。
注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。
如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。
示例 1： 输入：target = 1, startFuel = 1, stations = []输出：0
解释：我们可以在不加油的情况下到达目的地。
示例 2：输入：target = 100, startFuel = 1, stations = [[10,100]] 输出：-1
解释：我们无法抵达目的地，甚至无法到达第一个加油站。
示例 3：输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：我们出发时有 10 升燃料。
我们开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，我们从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。
我们沿途在1两个加油站停靠，所以返回 2 。
提示：1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 堆 | O(nlog(n)) | O(n) |
| 02 | 动态规划 | O(n^2) | O(n) |
| 03 | 动态规划 | O(n^2) | O(n^2) |
func minRefuelStops(target int, startFuel int, stations [][]int) int {
res := 0
total := startFuel
if total >= target {
return 0
}
Heap := &IntHeap{}
heap.Init(Heap)
for i := 0; i < len(stations); i++ {
for total < stations[i][0] {
if Heap.Len() == 0 {
return -1
}
total += heap.Pop(Heap).(int)
res++
}
heap.Push(Heap, stations[i][1])
}
for total < target {
if Heap.Len() == 0 {
return -1
}
total += heap.Pop(Heap).(int)
res++
}
return res
}
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
return h[i] > h[j]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
# 2
func minRefuelStops(target int, startFuel int, stations [][]int) int {
n := len(stations)
dp := make([]int, n+1)
dp[0] = startFuel
for i := 0; i < n; i++ {
for j := i; j >= 0; j-- {
if dp[j] >= stations[i][0] {
dp[j+1] = max(dp[j+1], dp[j]+stations[i][1])
}
}
}
for i := 0; i <= n; i++ {
if dp[i] >= target {
return i
}
}
return -1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func minRefuelStops(target int, startFuel int, stations [][]int) int {
n := len(stations)
// dp[i][j]经过第i个加油站加油j次能够到达的最远距离
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, n+1)
dp[i][0] = startFuel
}
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
// 不加油
if dp[i-1][j] >= stations[i-1][0] {
dp[i][j] = dp[i-1][j]
}
// 加油
if dp[i-1][j-1] >= stations[i-1][0] {
dp[i][j] = max(dp[i][j], dp[i-1][j-1]+stations[i-1][1])
}
}
}
for i := 0; i <= n; i++ {
if dp[n][i] >= target {
return i
}
}
return -1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
878.第N个神奇数字(3)¶
题目
如果正整数可以被 A 或 B 整除，那么它是神奇的。
返回第 N 个神奇数字。由于答案可能非常大，返回它模10^9 + 7的结果。
示例 1：输入：N = 1, A = 2, B = 3 输出：2
示例2：输入：N = 4, A = 2, B = 3 输出：6
示例 3：输入：N = 5, A = 2, B = 4 输出：10
示例 4：输入：N = 3, A = 6, B = 4 输出：8
提示：1 <= N<= 10^9
2 <= A<= 40000
2 <= B<= 40000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 二分查找 | O(log(n)) | O(1) |
| 02 | 二分查找 | O(log(n)) | O(1) |
| 03 | 数学 | O(1) | O(1) |
var mod = 1000000007
func nthMagicalNumber(n int, a int, b int) int {
ab := lcm(a, b)
left := 1
right := int(math.Pow10(15))
for left <= right {
mid := left + (right-left)/2
total := mid/a + mid/b - mid/ab
if total == n {
if mid%a == 0 || mid%b == 0 {
return mid % mod
}
right = mid - 1
} else if total < n {
left = mid + 1
} else {
right = mid - 1
}
}
return left % mod
}
// 求最小公倍数
func lcm(x, y int) int {
return x * y / gcd(x, y)
}
// 求最大公约数
func gcd(a, b int) int {
if a < b {
a, b = b, a
}
if a%b == 0 {
return b
}
return gcd(a%b, b)
}
# 2
var mod = 1000000007
func nthMagicalNumber(n int, a int, b int) int {
ab := lcm(a, b)
left := 0
right := int(math.Pow10(15))
for left < right {
mid := left + (right-left)/2
total := mid/a + mid/b - mid/ab
if total >= n {
right = mid
} else {
left = mid + 1
}
}
return left % mod
}
// 求最小公倍数
func lcm(x, y int) int {
return x * y / gcd(x, y)
}
// 求最大公约数
func gcd(a, b int) int {
if a < b {
a, b = b, a
}
if a%b == 0 {
return b
}
return gcd(a%b, b)
}
# 3
var mod = 1000000007
func nthMagicalNumber(n int, a int, b int) int {
ab := lcm(a, b)
// 设 ab为A，B的最小公倍数，如果 x(x<=ab)是神奇数字，那么x+ab也是神奇数字
m := ab/a + ab/b - 1 // 有m个神奇数字小于ab
// n = m*q + r
q := n / m
r := n % m
res := q * ab % mod
if r == 0 {
return res
}
arr := []int{a, b}
for i := 0; i < r-1; i++ { // 计算剩下的r-1个神奇数字
if arr[0] <= arr[1] {
arr[0] = arr[0] + a
} else {
arr[1] = arr[1] + b
}
}
res = res + min(arr[0], arr[1])
return res % mod
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
// 求最小公倍数
func lcm(x, y int) int {
return x * y / gcd(x, y)
}
// 求最大公约数
func gcd(a, b int) int {
if a < b {
a, b = b, a
}
if a%b == 0 {
return b
}
return gcd(a%b, b)
}
879.盈利计划(3)¶
题目
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第i种工作会产生profit[i]的利润，它要求group[i]名成员共同参与。
如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模10^9 + 7的值。
示例 1：输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3] 输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。
示例 2：输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8] 输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
提示：1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^3) | O(n^3) |
| 02 | 动态规划 | O(n^3) | O(n^2) |
| 03 | 动态规划 | O(n^3) | O(n^2) |
var mod = 1000000007
func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
length := len(group)
dp := make([][][]int, length+1) // dp[i][j][k] => 在前i个工作，j个员工，利润最少为k 的计划数
for i := 0; i <= length; i++ {
dp[i] = make([][]int, n+1)
for j := 0; j <= n; j++ {
dp[i][j] = make([]int, minProfit+1)
}
}
dp[0][0][0] = 1
for i := 0; i < length; i++ {
profitValue := profit[i]
groupValue := group[i]
for j := 0; j <= n; j++ {
for k := 0; k <= minProfit; k++ {
if j < groupValue { // 人数不够
dp[i+1][j][k] = dp[i][j][k]
} else { // 人数足够
// 利润为负：说明前面j-groupValue个组可以不干活，产生利润为0
maxValue := max(0, k-profitValue) // 工作利润至少为k,而不是工作利润恰好为k
dp[i+1][j][k] = (dp[i][j][k] + dp[i][j-groupValue][maxValue]) % mod
}
}
}
}
res := 0
for j := 0; j <= n; j++ {
res = (res + dp[length][j][minProfit]) % mod
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
var mod = 1000000007
func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
length := len(group)
dp := make([][]int, n+1) // dp[j][k] => 在j个员工，利润最少为k 的计划数
for j := 0; j <= n; j++ {
dp[j] = make([]int, minProfit+1)
// 这里都为1后，就不需要求和
dp[j][0] = 1 // 对于最小工作利润为0的情况，无论当前在工作的员工有多少人，我们总能提供一种方案
}
for i := 0; i < length; i++ {
profitValue := profit[i]
groupValue := group[i]
for j := n; j >= groupValue; j-- {
for k := minProfit; k >= 0; k-- {
// 利润为负：说明前面j-groupValue个组可以不干活，产生利润为0
maxValue := max(0, k-profitValue) // 工作利润至少为k,而不是工作利润恰好为k
dp[j][k] = (dp[j][k] + dp[j-groupValue][maxValue]) % mod
}
}
}
return dp[n][minProfit]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
var mod = 1000000007
func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
length := len(group)
dp := make([][]int, n+1) // dp[j][k] => 在j个员工，利润最少为k 的累计计划数
for j := 0; j <= n; j++ {
dp[j] = make([]int, minProfit+1)
}
dp[0][0] = 1
for i := 0; i < length; i++ {
profitValue := profit[i]
groupValue := group[i]
for j := n; j >= groupValue; j-- {
for k := minProfit; k >= 0; k-- {
// 利润为负：说明前面j-groupValue个组可以不干活，产生利润为0
maxValue := max(0, k-profitValue) // 工作利润至少为k,而不是工作利润恰好为k
dp[j][k] = (dp[j][k] + dp[j-groupValue][maxValue]) % mod
}
}
}
res := 0
for j := 0; j <= n; j++ {
res = (res + dp[j][minProfit]) % mod
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
887.鸡蛋掉落(2)¶
题目
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，
从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
示例 1：输入：K = 1, N = 2 输出：2
解释：鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2：输入：K = 2, N = 6 输出：3
示例 3：输入：K = 3, N = 14 输出：4
提示：1 <= K <= 100
1 <= N <= 10000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划-超时 | O(n^3) | O(n^2) |
| 02 | 动态规划 | O(n^2) | O(n^2) |
func superEggDrop(K int, N int) int {
if K == 1 {
return N
}
if N == 1 {
return 1
}
dp := make([][]int, K+1)
for i := 0; i <= K; i++ {
dp[i] = make([]int, N+1)
}
for i := 0; i <= N; i++ {
dp[1][i] = i // 1个鸡蛋N层楼，需要移动N次
}
for i := 1; i <= K; i++ {
dp[i][1] = 1 // i个鸡蛋1层楼，只需要移动1次
}
for i := 2; i <= K; i++ {
for j := 2; j <= N; j++ {
if dp[i][j] == 0 {
dp[i][j] = N // 最多N次，默认值
}
for x := 1; x <= j; x++ { // x是目标楼层，不断尝试x,找到最小值
// dp[i][j-x] 没碎 dp[i-1][x-1] 碎了
value := max(dp[i][j-x], dp[i-1][x-1]) + 1
dp[i][j] = min(dp[i][j], value)
}
}
}
return dp[K][N]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func superEggDrop(K int, N int) int {
// dp[i][j] 有i次操作，j个鸡蛋时能测出的最高的楼层数
dp := make([][]int, K+1)
for i := 0; i <= K; i++ {
dp[i] = make([]int, N+1)
}
for j := 1; j <= N; j++ { // 操作次数
for i := 1; i <= K; i++ { // K个蛋
// dp[i][j-1](没碎)+dp[i-1][j-1](碎了)+当前
dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1
if dp[i][j] >= N {
return j
}
}
}
return N
}