LeetCode 周赛 311

第一题 2413. Smallest Even Multiple

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

显而易见的：

func smallestEvenMultiple(n int) int {
    if n%2==1{
		return n*2
	}else{
		return n
	}
}

第二题 2414. Length of the Longest Alphabetical Continuous Substring

最近恰好做过dp的题目，所以立马dp：

• 状态定义为 下标i -> 以i结尾的string中，字母序连续的字符串最大长度
• 状态转移 s[i]和s[i-1]连续，那么在前面基础上+1，如果不连续，则置为1

最后，遍历i，拿最大长度即可。

func longestContinuousSubstring(s string) int {
	dp := make([]int, len(s))
	dp[0] = 1
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1]+1 {
			dp[i] = dp[i-1] + 1
		} else {
			dp[i] = 1
		}
	}
	res := 1
	for i := 0; i < len(dp); i++ {
		if res < dp[i] {
			res = dp[i]
		}
	}
	return res
}

第三题 2415. Reverse Odd Levels of Binary Tree

基本上一次bfs遍历搞定（而且没法更少了），空间上存储每一层即可。

func reverseOddLevels(root *TreeNode) *TreeNode {
	var nextRoots []*TreeNode
	nextRoots = append(nextRoots, root)
	pass(nextRoots)
	return root
}

func pass(roots []*TreeNode) {
	var nextRoots []*TreeNode
	for _, root := range roots {
		if root == nil {
			return
		}
		nextRoots = append(nextRoots, root.Left)
		nextRoots = append(nextRoots, root.Right)
	}
	reverseOddLevels1(nextRoots)
}

func reverseOddLevels1(roots []*TreeNode) {
	var values []*int
	var nextRoots []*TreeNode
	for _, root := range roots {
		if root == nil {
			return
		}
		values = append(values, &root.Val)
		nextRoots = append(nextRoots, root.Left)
		nextRoots = append(nextRoots, root.Right)
	}
	for i := 0; i < len(values)/2; i++ {
		tmpv := *values[i]
		*values[i] = *values[len(values)-i-1]
		*values[len(values)-i-1] = tmpv
	}
	pass(nextRoots)
}

第四题 2416. Sum of Prefix Scores of Strings

惭愧，这道题我没做出来，本来以为是并查集的问题，后来发现不是。

String Hash解法

计算出每个word的每个substring，用map计数。然后按照得分的定义计算即可

import (
	"strings"
)

func sumPrefixScores(words []string) []int {
	res := make([]int, len(words))
	hmap := map[string]int{}
	prefix := make([]strings.Builder, len(words))
	for i := 0; i < 1000; i++ {
		for j := 0; j < len(words); j++ {
			if i >= len(words[j]) {
				continue
			}
			prefix[j].WriteByte(words[j][i])
			hmap[prefix[j].String()]++
		}
		for j := 0; j < len(words); j++ {
			if i >= len(words[j]) {
				continue
			}
			if val, ok := hmap[prefix[j].String()]; ok {
				res[j] += val
			}
		}
	}
	return res
}

trie树

计算出每个word的substring，用trie树（字典树）计数。然后按照得分的定义计算即可。

因为字典树在添加的时候，可以做到每个prefix都能计数到的；在按照prefix取值的时候，也能很快的取到。

type Trie struct {
	val     int
	subTire []Trie
}

func newTrie() *Trie {
	return &Trie{
		val:     0,
		subTire: make([]Trie, 26),
	}
}

func (t *Trie) Add(s string) {
	curT := t
	curT.val++
	for i := 0; i < len(s); i++ {
		if curT.subTire == nil {
			curT.subTire = make([]Trie, 26)
		}
		curT = &curT.subTire[int(s[i]-'a')]
		curT.val++
	}
}

func sumPrefixScores(words []string) []int {
	trie := newTrie()
	for _, word := range words {
		trie.Add(word)
	}
	res := make([]int, len(words))
	for index, word := range words {
		curT := trie
		for i := 0; i < len(word); i++ {
			curT = &curT.subTire[int(word[i]-'a')]
			res[index] += curT.val
		}
	}
	return res
}

---

https://leetcode.com/contest/weekly-contest-311/