309周赛&86双赛

前言

最近对自己太放纵了，属实是有点不太行。

接下来要上强度了！

309 是miHoYo冠名周赛

T1

image-20220906175248073

思路

T1又是很简单的数组题，我们只需要判断两个元素出现位置中间隔的元素是否与给定的距离表相等即可。

而且哦，这种位置的选择，我们可以通过hash表的方式很容易的完成。尤其是前后位次关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def checkDistances(self, s: str, distance):
        hashmap={}
        for i,j in enumerate(s):
            # 记录第一次出现的位置
            if j not in hashmap.keys():
                hashmap[j]=i
            else:
                # 判断第二次与第一次的差值是否等于距离表
                val=i-hashmap[j]
                if val-1!=distance[ord(j)-ord("a")]:
                    return False
        return True

这题是不是很像两数之和？
那我们干脆一起把86双的T1一起讲了吧

image-20220906175257692

呐，这鬼题也是，判断连续的，我们只需要看这个值是否被记录过就好了

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findSubarrays(self, nums: List[int]) -> bool:
        # 要tm连续啊
        # 逆天
        hashmap={}
        for i in range(len(nums)-1):
            val=nums[i]+nums[i+1]
            if val in hashmap.keys():
                return True
            hashmap[val]=1
        return False

T2

image-20220906175309036

思路

关键词：方法数！想到了什么？爬楼梯？斐波那契数列？没错，这种方法数，一般都有递推公式。这题也不例外。考虑两个方向，于是每次dp就能从左和从右。由于负数轴需要映射，为了简化操作，我们可以不用数组。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        MOD = 10 ** 9 + 7
        @cache
        def f(x: int, left: int) -> int:
            if abs(x - endPos) > left: return 0
            if left == 0: return 1  # 成功到达终点，算一种方案
            return (f(x - 1, left - 1) + f(x + 1, left - 1)) % MOD
        return f(startPos, k)

亦或是采用BFS进行广度搜索，得到所有可能的结果(相当于遍历，核心与DP相同)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

MOD = 10**9 + 7
class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        # BFS模拟全局搜索
        pre = defaultdict()
        pre[startPos] = 1
        while k:
            nex = defaultdict()
            for pos in pre:
                # 每次都会更新下一次的方向
                # 并且都会进行一个累加，表示重新走过
                # 更新往左与往右的方案数
                nex[pos + 1] += pre[pos]
                nex[pos - 1] += pre[pos]
            for pos in nex:
                nex[pos] %= MOD
            pre = nex
            k -= 1
        return pre[endPos] % MOD

解法二：数学！

正着走:XX，负着走K−XK-X，距离DD

我们有:

X+(−(K−X))=DX=D+K2X+(-(K-X))=D \\ X=\frac{D+K}{2}

于是，转换为求解：从KK中取XX个正数。

CK1/2(D+K)C^{1/2(D+K)}_K

那，关于Python如何求组合数，其实有一个内置函数comb

1
2
3
4
5
6
7
class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        MOD=10**9+7
        d=abs(endPos-startPos)
        if (k-abs(endPos-startPos))&1 or k<abs(endPos-startPos):
            return 0
        return comb(k,(d+k)//2)%MOD

不用Comb的话，我们可以这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def comb(m,n):

    if m>n or type(m)!=int or type(n)!=int:
        # 必须是整数且满足大小关系
        return None

    return rank(n)//(rank(m)*rank(n-m))

def rank(n):
    if n==0 or n==1:
        return 1
    ans=1
    for i in range(2,n+1):
        ans*=i
    return int(ans)
    
class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        MOD=10**9+7
        d=abs(endPos-startPos)
        if (k-abs(endPos-startPos))&1 or k<abs(endPos-startPos):
            return 0
        return comb(k,(d+k)//2)%MOD

T3

image-20220906175316163

思路

位运算+双指针优化

其实看到这个连续就应该想到用双指针了。

当然，我的解法会遍历左右指针所有值，导致复杂度为：O(nm)O(nm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def longestNiceSubarray(self, nums) -> int:
        # 滑动窗口
        left=right=0
        ans=0
        n=len(nums)
        while right<n:
            i=breakPoint=left
            change=False
            while i<right:
                if nums[right]&nums[i]!=0:
                    # 只要是有一个够不成了
                    # 我们从构不成的位置重新构建子串
                    # 首先的尝试就是跳过
                    breakPoint=i
                    change=True
                    # 子串肯定比原串小
                    # 所以不需要考虑，下次的截断点就是bp+1
                i+=1
                # 加入
            left=breakPoint+1 if change or breakPoint!=left else left
            ans=max(ans,len(nums[left:right+1]))
            right+=1
        return ans

用位运算的话，复杂度上其实也差不多啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestNiceSubarray(self, nums) -> int:
        # 滑动窗口
        left=right=0
        ans=0
        n=len(nums)
        or_=0
        
        while right<n:
            while or_&nums[right]:
                or_^=nums[left]
                left+=1
                # 加入
            or_|=nums[right]
            ans=max(ans,right-left+1)
            right+=1
        return ans

当然，最后写的漂亮点，就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestNiceSubarray(self, nums) -> int:
        ans=left=or_=0
        # or_用来存放运算结果
        # 加入：or_| x
        # 剔除: or_^ x
        for right,x in enumerate(nums):
            while or_&x:
                # 此时需要剔除了
                or_^=nums[left]
                left+=1
            or_|=x
            ans=max(ans,right-left+1)
        return ans

T4

image-20220906175321646

思路

初见这个题的时候，想到的应该是贪心，谁有空就给谁，谁的时间最短谁就空闲。

于是我写了个不能AC的解:

超！！！！我这个解随便改改逻辑就AC了！！！！！！

超！！！！

我也做出T4了！！！！

这是离AK最近的一次！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution:
    def mostBooked(self, n: int, meetings):
        st=[[] for i in range(n)]
        val=[0 for i in range(n)]
        n=len(meetings)
        i=0
        now=0
        meetings.sort(key=lambda x:x[0])
        change=[None,None]

        while i<n:

            if change[0]!=None:
                s,e=change
            else:
                s, e = meetings[i]
                if now<=s:
                    # 提前
                    now=s
                else:
                    e+=now-s
                    s=now
                    
                

            # 时间到了
            for _ in st:
                if _ and _[0]<=now:
                    _.pop()

            # 有无空闲
            for l,j in enumerate(st):
                if j==[]:
                    val[l]+=1
                    j.append(e)
                    now=s
                    i+=1
                    change[0]=None
                    break
            else:
                now=min([i[0] for i in st])
                now=max(now,s)
                change=[now,now+(e-s)]

        check=val[0]
        idx=0
        for i,j in enumerate(val):
            if j>check:
                check=j
                idx=i
        return idx


两个堆来回倒实现任务队列！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

from heapq import heappop
from heapq import heappush

class Solution:
    def mostBooked(self, n: int, meetings):

        # 当会议室未占用，会有限提供资源给开始时间早的。
        # 两个堆来模拟，一个表示可用的会议室，另一个表示正在开会的会议室

        cnt=[0]*n
        idle=list(range(n)) # 可用的会议室
        using=[]# (结束时间，会议室编号)
        meetings.sort() # 必要的排序

        for st,end in meetings:
            # 在st时刻前正在开会的会议室，把结束的弹出来
            while using and using[0][0]<=st:
                # 首先将使用栈中的内容弹出来
                # 并且将结束时间放入idle中，表示可用任务队列
                heappush(idle,heappop(using)[1])

            if len(idle)==0:
                # 如果当前没有可用的
                # 需要等到最近一个结束
                e,i=heappop(using)
                # 补上时间
                end+=e-st
            else:
                # 将当前空闲的弹出去(其实也是索引最小值)
                # 将最短时间的出堆
                i=heappop(idle)

            cnt[i]+=1
            # 将当前结束时间和索引加入最小堆中
            # 每次取都是最小(最近一个结束的)
            heappush(using,(end,i))

        ans=0
        for i,c in enumerate(cnt):
            if c>cnt[ans]:
                ans=i
        return ans

O(n+mlogn+mlogn)

建堆+排+插入堆

86 双赛

T3和T4很有意思

T2

带余除法

当n>4,2<n−2n>4,2<n-2，下面的表达式一定成立

n=q∗b+r,0<=r<bn=q*b+r,0<=r<b

这题完全就是脑筋急转弯
告诉你了，这玩意在n-2进制上必定为12

1
return False

T3

image-20220906175340017

这题不难看出是位运算，难得是如何进行。

不是没有想过枚举，但是会不会有一种更加高效的手段拿来实现这个算法？很可惜，似乎是没有的。

所幸的是，位运算枚举还是挺快的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def maximumRows(self, mat: List[List[int]], cols: int) -> int:
        '''
        位运算

        枚举所有选择情况
        实际上，二进制数就能表征所有的选择情况
        二进制数还能用来表征更高位的数据
        譬如之前的毒药和小鼠
        '''
        ans=0
        mask=[sum(v<<j for j,v in enumerate(row)) for row in mat]
        # 刚好就能够表示0-1覆盖情况
        # 例如：5-> 101
        # 6->110
        for set in range(1<<len(mat[0])):
            # 这样就能表征所有的情况
            if set.bit_count()!=cols:
                # 剪枝
                # 不满足列的情况就丢弃
                continue
            # 某一行 and 选择列如果还等于他自己
            # 那就说明可以覆盖
            # 1的时候恰好是1 0的时候不用管他
            cnt=0
            for row in mask:
                if row &set==row:
                    cnt+=1
            ans=max(ans,cnt)
        return ans

T4

image-20220905204610760

这题的关键字：连续consecutive

所以，双指针搭建滑动窗口不失为一种好的选择。

当然，这类似背包问题，是存在一个限制条件的。

我们可以用单调队列来处理这种情况，通过维护单调队列，及时清理无用数据，保证队首是最大元素的同时，考虑是否加入和剔除元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:

        ans=s=left=0
        q=deque()

        for right,(t,c) in enumerate(zip(chargeTimes,runningCosts)):

            # 处理右端点
            while q and t>=chargeTimes[q[-1]]:
                # 只要当前的时间大于队列的时间
                # 就要维护队列的单调性
                q.pop()

            # 将这个端点加入
            q.append(right)
            s+=c # 总的cost

            # 处理左端点
            while q and chargeTimes[q[0]]+(right-left+1)*s>budget:
                # 太多了！ 最大的滚出去！
                if q[0]==left:
                    q.popleft()
                s-=runningCosts[left]
                # 一直找啊找直到找到最大的那个
                left+=1
            # 这样 超出区间的一个就是我们的一个连续的子序列了
            # 这样的方式能保证：
            # 如果后面加进来的值比较大
            # 我们可以直接剔除掉串
            
            # 如果后面加进来的值比较小
            # 我们就无须对其进行维护
            
            # 举个栗子
            # tar: 10
            # List: 4 3 1 2
            # q:4 3 1
            
            # 插入2
            # 此时q: 4 3 2
            
            # 发现超了
            # 我们就去掉最大的
            # 剩下的q: 3 2
            # 重新开始一段
            
            # tar:10
            # List: 1 3 4 2
            
            # 插入2时:
            # q: 4
            # 插入2一定会炸
            # 那么我们就从4的位置开始新的子串
            # 直接定位到了最大的位置
            # 因为当x上溢
            # x+1一定上溢
            
            # 而且，单调队列维护的是坐标索引
            # 方便我们定位
            ans=max(ans,right-left+1)
        return ans

我们可以反思一下，什么时候可以用单调队列？

  • 我们每次不符合条件的弹出都是最值
  • 维护一个最值，使其满足限制条件

怎么使用单调队列？

  • 及时弹出无用元素

在滑动窗口维护最值问题，可以考虑单调队列：

  • 判断队列单调性，不满足时，队尾出队
  • 增大窗口，队尾入队，更新统计值
  • 判断是否满足条件，不满足则缩小窗口，队首出队