[数据结构与算法]记leetcode周赛第一次ak（虽然很多bug）2022.1.22周赛

思路：
排序+三个一组

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(reverse = True)
        sum = 0
        for i in range(len(cost)):
            if (i + 1) % 3 != 0:
                sum += cost[i]
        return sum

思路：
还原hidden数组，看极差判断即可

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        n = len(differences)
        hidden = [0] * (n + 1)
        for i in range(1, n + 1):
            hidden[i] = hidden[i - 1] + differences[i - 1]
        #print(hidden)
        if max(hidden) - min(hidden) > upper - lower:
            return 0
        else:
            return (upper - lower) - (max(hidden) - min(hidden)) + 1

思路：
queue， visited，bfs，上下左右，然后层次遍历，加入符合条件的下一层
判断该层的结果（排序：价格，行，列）
到达长度就退出

class Solution:
    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        # bfs
        ans = []
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        #print(visited)
        q = deque()
        q.append(start)
        visited[start[0]][start[1]] = True
        while q:
            levelLen = len(q)
            #print(levelLen)
            tempans = []
            # 同一层的
            for _ in range(levelLen):
                now = q.popleft()
                #print(now)
                # 加入
                if pricing[0] <= grid[now[0]][now[1]] <= pricing[1]:
                    tempans.append([now[0], now[1], grid[now[0]][now[1]]])

                # bfs
                X = [-1, 0, 1, 0]
                Y = [0, -1, 0, 1]
                for i in range(4):
                    nextX = now[0] + X[i]
                    nextY = now[1] + Y[i]
                    # 在界内且不是墙且未遍历
                    if 0 <= nextX < m and 0 <= nextY < n and grid[nextX][nextY] != 0 and visited[nextX][nextY] is False:
                        q.append([nextX, nextY])
                        visited[nextX][nextY] = True
            # 整合这一层的结果
            tempans.sort(key = lambda k: (k[2], k[0], k[1]))
            for item in tempans:
                ans.append([item[0], item[1]])
                # 满了就退出
                if len(ans) == k:
                    return ans
        return ans

思路：
首先特殊情况判断，s个数奇数or为0or为2
连续两个S后的P可用
进行组合乘法（注意最后的P处理，卡了5次bug）

class Solution {
public:
    int numberOfWays(string corridor) {
        int sum = 0;
        for(int i = 0; i < corridor.size(); i++) {
            if(corridor[i] == 'S') ++sum;
        }
        if(sum % 2 == 1 || sum == 0) return 0;
        if(sum == 2) return 1;
        
        long long res = 1;
        int cnts = 0;
        for(int i = 0; i < corridor.size(); i++) {
            //cout << i << endl;
            if(corridor[i] == 'S') {
                if(cnts < 2) ++cnts;
                else cnts = 1;
            }
            else if(corridor[i] == 'P') {
                // 若满足两个seat在前面
                if(cnts == 2) {
                    int cntp = 1;
                    while(i + 1 < corridor.size() && corridor[++i] == 'P') cntp++;
                    if(i == corridor.size() - 1) break;
                    res *= cntp + 1;
                    res %= 1000000007;
                    i--;
                }
            }
        }
        
        res %= 1000000007;
        return res;
        
    }
};

总结：
Anyway， 人生第一次ak吧