前言
4题A3题，，T4很明显用线段树，已经不会写线段树了，文末两段代码吧
第一题
2273.移除字母异位词后的结果数组
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.不含特殊楼层的最大连续楼层数
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.按位与结果大于零的最长组合
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.统计区间中的整数数目
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 }
