解题思路
对于这道题而言，最容易想到的就是使用哈希表存储是否出现过。
此题有两点:
- 当数字与位置都相同时，应该使bulls值加一。即
if secret[i] == guess[i] {
bulls++
}
- 当数字相同位置不同时，应该使cows加一。一开始我的想法是先遍历一个列表，存储里面的值出现的个数，再遍历第二个列表找到每当出现相同的值就使cows加一，最后再减去bulls的值即可(即重复的值)。
tmp := make(map[byte]int,len(secret))
bulls,cows := 0,0
for i := 0; i < len(secret);i++{
if secret[i] == guess[i]{
bulls++
}
tmp[secret[i]-'0']++
}
for i := 0; i < len(guess); i++{
if tmp[guess[i]-'0'] != 0{
cows++
tmp[guess[i]-'0']--
}
}
看了一眼解答，方法为设两个map，当碰到不同时两个map分别相加，最后加上最小值。
func getHint(secret, guess string) string {
bulls := 0
var cntS, cntG [10]int
for i := range secret {
if secret[i] == guess[i] {
bulls++
} else {
cntS[secret[i]-'0']++
cntG[guess[i]-'0']++
}
}
cows := 0
for i := 0; i < 10; i++ {
cows += min(cntS[i], cntG[i]) //很巧妙，算是空间换时间
}
return fmt.Sprintf("%dA%dB", bulls, cows)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
解题思路
在一开始首先想到动态规划，但并没有找到递推就放弃了，然后又想到dfs但dfs在面对一个string列表时没有写过也放弃了，直接选择暴力解法。
直接对每个string进行遍历，每个string都取出子字符串对整个arr进行遍历，若存在则跳过，走完所有后将最短的字符串放入答案。
- 首先解决如何取出子字符串。
answer := make([]string, n)
for i, s := range arr {
substrings := make(map[string]bool)
for j := 0; j < len(s); j++ {
for k := j + 1; k <= len(s); k++ {
substrings[s[j:k]] = true
}
}
- 第二步将子字符串与arr中所有string进行匹配，若有则删除，无则加入答案。
for _, str := range arr {
if str == s {
continue
}
for sub := range substrings {
if len(str) >= len(sub) && strings.Contains(str, sub) {
delete(substrings, sub)
}
}
}
shortest := ""
for sub := range substrings {
if shortest == "" || len(sub) < len(shortest) || (len(sub) == len(shortest) && sub < shortest) {
shortest = sub
}
}
answer[i] = shortest
-
最后这个代码会在出现两个相同字串时出错
于是进行去重处理。
tmp := make(map[string]int)
result := make([]string, len(answer))
for _,x := range answer{
tmp[x]++
}
for i,x := range answer{
if tmp[x] > 1{
result[i] = ""
}else{
result[i] = x
}
}
return result
解题思路
- 先记录下每个元素出现的次数，可以知道若满足条件，那么该元素平方一定是大于1的。
func maximumLength(nums []int) int {
cnt := map[int]int{}
for _,x := range nums{
cnt[x]++
}
ans := cnt[1]-1 | 1 //对于x=1进行特判
delete(cnt,1)
for x := range cnt{
res := 0
for ;cnt[x] > 1; x *= x{
res += 2
}
res += cnt[x]
ans = max(ans,res-1|1) //保证一定是奇数。
}
return ans
}
