哈希表
59 有效变位词
力扣https://leetcode-cn.com/problems/dKk3P7/
func isAnagram(s string, t string) bool {
if len(s) != len(t) || s == t {
//需要字符数相同但是字符顺序不相同
return false
}
varmap := make(map[uint8]int)
for i := 0; i < len(s); i++ {
varmap[s[i]]++
varmap[t[i]]--
}
for _, v := range varmap {
if v != 0 {
return false
}
}
return true
}
60 变位词组
力扣https://leetcode-cn.com/problems/sfvd7V/
//抽象字符串的表示
func getNumberOfStr(str string)string{
var arr [26]int
for i:=0;i<len(str);i++{
arr[str[i]-'a']++
}
var snum string
for i:=0;i<len(arr);i++{
tmp:= strconv.Itoa(arr[i])
snum = snum + tmp + "#"
}
return snum
}
func groupAnagrams(strs []string) [][]string {
var res [][]string
strmap:=make(map[string][]string)
for i:=0;i<len(strs);i++{
strmap[getNumberOfStr(strs[i])] = append(strmap[getNumberOfStr(strs[i])] ,strs[i])
}
for _,v:=range strmap{
res = append(res,v)
}
return res
}
61 外星语言是否排序
力扣https://leetcode-cn.com/problems/lwyVBB/
//a是否小于b
func compareByOrder(a,b string,score map[uint8]int)bool{
lengtha:=len(a)
lengthb:=len(b)
if lengtha<lengthb{
for i:=0;i<lengtha;i++{
ascore:=score[a[i]]
bscore:=score[b[i]]
if ascore>bscore{
return false
}else if ascore==bscore{
continue
}else{
return true
}
}
return true
}else {
for i:=0;i<lengthb;i++{
ascore:=score[a[i]]
bscore:=score[b[i]]
if ascore>bscore{
return false
}else if ascore==bscore{
continue
}else{
return true
}
}
if lengtha==lengthb{
return true
}
return false
}
}
func isAlienSorted(words []string, order string) bool {
score:=make(map[uint8]int)
for i:=0;i<len(order);i++{
score[order[i]] = i
}
// 抽象字符顺序的分数
for i:=0;i<len(words)-1;i++{
if !compareByOrder(words[i],words[i+1],score){
return false
}
}
return true
}
62 最小时间差
力扣https://leetcode-cn.com/problems/569nqc/
//核心是时间的计算
func findMinDifference(timePoints []string) int {
if len(timePoints) > 24*60 {
return 0
}
var mins []int
for _, t := range timePoints {
time := strings.Split(t, ":")
h, _ := strconv.Atoi(time[0])
m, _ := strconv.Atoi(time[1])
mins = append(mins, h*60+m)
}
sort.Ints(mins)
mins = append(mins, mins[0]+24*60)
res := 24 * 60
for i := 1; i < len(mins); i++ {
res = min(res, mins[i]-mins[i-1])
}
return res
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
栈
63 后缀表达式后缀表达式https://leetcode-cn.com/problems/8Zf90G/
func calnum(a,b,fu string)int{
a1,_:=strconv.Atoi(a)
b1,_:=strconv.Atoi(b)
switch fu {
case "+":
return a1+b1
case "-":
return a1-b1
case "*":
return a1*b1
case "/":
return a1/b1
default:
return 0
}
}
func evalRPN(tokens []string) int {
fumap:=make(map[string]bool)
fumap["+"] = true
fumap["-"] = true
fumap["*"] = true
fumap["/"] = true
var res int
var arr []string
for i:=0;i<len(tokens);i++{
if fumap[tokens[i]]{
res = calnum(arr[len(arr)-2],arr[len(arr)-1],tokens[i])
arr = arr[0:len(arr)-2]
arr = append(arr,strconv.Itoa(res))
}else{
arr = append(arr,tokens[i])
}
}
if len(arr)>0{
res,_ = strconv.Atoi(arr[0])
}
return res
}
64 小行星碰撞
力扣https://leetcode-cn.com/problems/XagZNi/
func pushAsteroid(res []int,asteroid int)[]int{
if len(res)==0{
res = append(res,asteroid)
return res
}
if res[len(res)-1]*asteroid > 0 ||res[len(res)-1]*asteroid < 0 && res[len(res)-1] < 0 {
//同相,直接放入
res = append(res,asteroid)
}else{
//逆向,肯定会撞
index:=len(res) - 1
for index>=0&&(res[index]*asteroid<0){
tmp:=res[index] + asteroid
if tmp*res[index]>0{
//新加入的被撞碎了,原先的没有影响
return res[0:index+1]
}else if tmp*res[index]==0{
//互相碎了
return res[0:index]
}else{
//新加入的撞碎了原先的
index--
res = res[0:index+1]
}
}
res = append(res,asteroid)
}
return res
}
func asteroidCollision(asteroids []int) []int{
var res []int
for i:=0;i<len(asteroids);i++{
res = pushAsteroid(res,asteroids[i])
}
return res
}
65 每日温度
力扣https://leetcode-cn.com/problems/iIQa4I/
func dailyTemperatures(temperatures []int) []int {
res:=make([]int,len(temperatures))
index:=[]int{}
for i:=0;i<len(temperatures);i++{
for len(index)>0&&temperatures[i]>temperatures[index[len(index)-1]]{
res[index[len(index)-1]] = i-index[len(index)-1]
index = index[:len(index)-1]
}
index = append(index,i)
}
return res
}