316. 去除重复字母 Remove Duplicate Letters
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"
输出："abc"
示例 2：
输入：s = "cbacdcbc"
输出："acdb"
提示：
1 <= s.length <= 10^4s由小写英文字母组成
代码1：贪心算法
package main import "fmt" func removeDuplicateLetters(s string) string { stack := []byte{} count := [26]int{} visited := [26]bool{} for i := 0; i < len(s); i++ { count[s[i]-'a']++ } for i := 0; i < len(s); i++ { count[s[i]-'a']-- if visited[s[i]-'a'] { continue } for len(stack) > 0 && stack[len(stack)-1] > s[i] && count[stack[len(stack)-1]-'a'] > 0 { visited[stack[len(stack)-1]-'a'] = false stack = stack[:len(stack)-1] } stack = append(stack, s[i]) visited[s[i]-'a'] = true } return string(stack) } func main() { s := "bcabc" fmt.Println(removeDuplicateLetters(s)) s = "cbacdcbc" fmt.Println(removeDuplicateLetters(s)) }
代码2：暴力枚举
package main import "fmt" func removeDuplicateLetters(s string) string { lastPos := [26]int{} for i := 0; i < len(s); i++ { lastPos[s[i]-'a'] = i } visited := [26]bool{} res := []byte{} for i := 0; i < len(s); i++ { if visited[s[i]-'a'] { continue } for len(res) > 0 && res[len(res)-1] > s[i] && lastPos[res[len(res)-1]-'a'] > i { visited[res[len(res)-1]-'a'] = false res = res[:len(res)-1] } res = append(res, s[i]) visited[s[i]-'a'] = true } return string(res) } func main() { s := "bcabc" fmt.Println(removeDuplicateLetters(s)) s = "cbacdcbc" fmt.Println(removeDuplicateLetters(s)) }
输出：
abc
acdb
318. 最大单词长度乘积 Maximum-product-of-word-lengths
给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
示例 1：
输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16
解释：这两个单词为 "abcw", "xtfn"。
示例 2：
输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4
解释：这两个单词为 "ab", "cd"。
示例 3：
输入：words = ["a","aa","aaa","aaaa"]
输出：0
解释：不存在这样的两个单词。
提示：
2 <= words.length <= 10001 <= words[i].length <= 1000words[i]仅包含小写字母
代码1：位运算 + 哈希表
package main import "fmt" func maxProduct(words []string) int { n := len(words) max := func(x, y int) int { if x > y { return x } return y } hash := make(map[int]int, n) for _, word := range words { mask := 0 for _, ch := range word { mask |= 1 << (uint)(ch-'a') } hash[mask] = max(hash[mask], len(word)) } res := 0 for mask1, len1 := range hash { for mask2, len2 := range hash { if mask1&mask2 == 0 { res = max(res, len1*len2) } } } return res } func main() { words := []string{"abcw", "baz", "foo", "bar", "xtfn", "abcdef"} fmt.Println(maxProduct(words)) words = []string{"a", "ab", "abc", "d", "cd", "bcd", "abcd"} fmt.Println(maxProduct(words)) words = []string{"a", "aa", "aaa", "aaaa"} fmt.Println(maxProduct(words)) }
代码2：暴力枚举
package main import "fmt" func maxProduct(words []string) int { n := len(words) res := 0 for i := 0; i < n; i++ { for j := i + 1; j < n; j++ { if hasNoCommonChar(words[i], words[j]) { res = max(res, len(words[i])*len(words[j])) } } } return res } func hasNoCommonChar(word1, word2 string) bool { for i := 0; i < len(word1); i++ { for j := 0; j < len(word2); j++ { if word1[i] == word2[j] { return false } } } return true } func max(x, y int) int { if x > y { return x } return y } func main() { words := []string{"abcw", "baz", "foo", "bar", "xtfn", "abcdef"} fmt.Println(maxProduct(words)) words = []string{"a", "ab", "abc", "d", "cd", "bcd", "abcd"} fmt.Println(maxProduct(words)) words = []string{"a", "aa", "aaa", "aaaa"} fmt.Println(maxProduct(words)) }
输出：
16
4
0
Go1.21 新增 min、max 内置函数，示例如下：
var x, y int m := min(x) // m == x m := min(x, y) // m 是 x 和 y 中较小的那个 m := max(x, y, 10) // m 是 x 和 y 中较大的一个，但至少是10 c := max(1, 2.0, 10) // c == 10.0（浮点类型） f := max(0, float32(x)) // f 的类型是 float32 var s []string _ = min(s...) // 无效：不允许使用 slice 参数 t := max("", "foo", "bar") // t == "foo" (string 类型)
升级到V1.21后，不再需要每次用到max, min就要自定义。
对于一些特殊值和清空，例如：浮点参数、负零、NaN和无穷大。min、max 函数结果适用以下规则：
x y min(x, y) max(x, y)
-0.0 0.0 -0.0 0.0
-Inf y -Inf y
+Inf y y +Inf
NaN y NaN NaN
第一行：负零比（非负）零小。
第二行：负无穷大比任何其他数字都小。
第三行：正无穷大于任何其他数字。
第四行：如果有任何一个参数是 NaN，结果就是 NaN。
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
