第293场周赛
第293场周赛
前言
4题A3题，，T4很明显用线段树，已经不会写线段树了，文末两段代码吧
第一题
2273.移除字母异位词后的结果数组
题解
题目：给一个字符串数组，相邻字符串不能是字母异位词(字符串A用自身的字母重新排列，变成字符串B)，如果是，则删除后者字符串
思路：
1.直接计算26长的字母数组，就很容易判断是不是异位词
2.用栈存，有可能第一个第二个第三个都是，那么用栈很方便在删除第二个又删除第三个
代码
func removeAnagrams(words []string) []string {
ans := []string{words[0]}
for _, word := range words[1:] {
cnt := [26]int{}
for _, b := range word {
cnt[b-'a']++
}
for _, b := range ans[len(ans)-1] {
cnt[b-'a']--
}
if cnt != [26]int{} { // 不是字母异位词
ans = append(ans, word)
}
}
return ans
}
第二题
2274.不含特殊楼层的最大连续楼层数
题解
别人写的代码真优雅，淦
题目：给定楼层（bottom和top），给定一个数组，数组中的元素代表这个楼层不能用，问最长的连续可用的楼层是多长
思路：排序数组后，一次遍历计算就行
代码
func maxConsecutive(bottom int, top int, special []int) int {
special = append(special, top+1)
sort.Ints(special)
left := bottom
result := 0
for _, v := range special {
if left != v {
result = max(result, v-left)
}
left = v + 1
}
return result
}
func max(i, j int) int {
if i > j {
return i
}
return j
}
func maxConsecutive(bottom, top int, a []int) (ans int) {
a = append(a, bottom-1, top+1)
sort.Ints(a)
for i := 1; i < len(a); i++ {
ans = max(ans, a[i]-a[i-1]-1)
}
return
}
第三题
2275.按位与结果大于零的最长组合
题解
题目：给一个数组，数组里面的元素任意可用进行与运算，求与运算之后大于0，参与这次运算的最长元素个数
思路：
1.大于0，说明在二进制位上，某一位，是参与运算的元素都有的
2.既然如此，直接遍历所有元素，将每个元素的二进制位进行累加
3.找某位上最大即可，就说明某位上有几个元素存在该位
代码
func largestCombination(candidates []int) int {
mp := make(map[int]int)
ans := 0
for _, v := range candidates {
for i := 0; i < 32; i++ {
if 1<<i&v > 0 {
mp[i]++
ans = max(ans, mp[i])
}
}
}
return ans
}
func max(i, j int) int {
if i > j {
return i
}
return j
}
第四题
2276.统计区间中的整数数目
题解
这种题目，一眼就是线段树，但是不搞算法竞赛ACM，学这个真心感觉没必要，性价比太低，这里直接放灵神的题解
两种做法：珂朵莉树 / 动态开点线段树（Python/Java/C++/Go）
代码
package main
import (
"github.com/emirpasic/gods/trees/redblacktree"
)
type CountIntervals struct {
*redblacktree.Tree
cnt int
}
func Constructor() CountIntervals {
return CountIntervals{redblacktree.NewWithIntComparator(), 0}
}
func (t *CountIntervals) Add(left, right int) {
// 遍历所有被 [left,right] 覆盖到的区间（部分覆盖也算）
for node, _ := t.Ceiling(left); node != nil && node.Value.(int) <= right; node, _ = t.Ceiling(left) {
l, r := node.Value.(int), node.Key.(int)
if l < left { // 合并后的新区间，其左端点为所有被覆盖的区间的左端点的最小值
left = l
}
if r > right { // 合并后的新区间，其右端点为所有被覆盖的区间的右端点的最大值
right = r
}
t.cnt -= r - l + 1
t.Remove(r)
}
t.cnt += right - left + 1
t.Put(right, left) // 所有被覆盖到的区间与 [left,right] 合并成一个新区间
}
func (t *CountIntervals) Count() int { return t.cnt }
type CountIntervals struct {
left, right *CountIntervals
l, r, cnt int
}
func Constructor() CountIntervals {
return CountIntervals{l: 1, r: 1e9}
}
func (o *CountIntervals) Add(l, r int) {
if o.cnt == o.r-o.l+1 { // o 已被完整覆盖，无需执行任何操作
return
}
if l <= o.l && o.r <= r { // 当前节点已被区间 [l,r] 完整覆盖，不再继续递归 [l,o.l,l.r,r]
o.cnt = o.r - o.l + 1
return
}
mid := (o.l + o.r) >> 1
if o.left == nil { // 动态开点
o.left = &CountIntervals{l: o.l, r: mid}
}
if o.right == nil { // 动态开点
o.right = &CountIntervals{l: mid + 1, r: o.r}
}
if l <= mid {
o.left.Add(l, r)
}
if mid < r {
o.right.Add(l, r)
}
o.cnt = o.left.cnt + o.right.cnt
}
func (o *CountIntervals) Count() int {
return o.cnt
}
