LeetCode Weekly Contest 156

事实证明生一肚子气切比赛没有什么好下场

##1207. Unique Number of Occurrences

求问数组中数字的出现次数是不是唯一的。

思路：Counter

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        c = collections.Counter(arr)
        return len(c.keys()) == len(set(c.values()))

1208. Get Equal Substrings Within Budget

两个字符串，修改一个字符的cost为对应ASCII差值的绝对值，问总cost不超过maxCost的最长子串。

思路：二分或双指针

详解：比赛没想到双指针，二分也写了半天

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        costs = list(map(lambda x: abs(ord(x[0]) - ord(x[1])), zip(s, t)))
        pre_costs = [0] * len(costs)
        for i, c in enumerate(costs):
            pre_costs[i] = (pre_costs[i-1] if i>0 else 0) + c
        ans = 0
        def sumlr(a, l, r):
            if l > r:
                return 0
            if l == 0:
                return a[r]
            return a[r] - a[l-1]
        for i, c in enumerate(pre_costs):
            l, r = i, len(pre_costs) - 1
            while l < r - 1:
                mid = (l + r) // 2
                if sumlr(pre_costs, i, mid) <= maxCost: 
                    l = mid + 1
                else: 
                    r = mid
            if r < len(pre_costs):
                while sumlr(pre_costs, i, r) > maxCost: r -= 1
                ans = max(ans, r - i + 1)
        return ans

class Solution(object):
    def equalSubstring(self, S, T, maxCost):
        N = len(S)
        A = [abs(ord(S[i]) - ord(T[i])) for i in xrange(N)]
        left = 0
        windowsum = 0
        ans = 0
        for right, x in enumerate(A):
            windowsum += x
            while windowsum > maxCost and left < N:
                windowsum -= A[left]
                left += 1
            cand = right - left + 1
            if cand > ans: ans = cand
        return ans

1209. Remove All Adjacent Duplicates in String II

出现长度为k的同一个字符组成的字符串就删掉，问最后剩下的字符串。

思路：栈模拟。

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        str_stack = []
        for i, ch in enumerate(s):
            temp_str = str_stack.pop() if str_stack else ""
            if temp_str and ch != temp_str[-1]:
                str_stack.append(temp_str)
                temp_str = ""
            temp_str += ch
            if len(temp_str) != k:
                str_stack.append(temp_str)
        return "".join(str_stack)

1210. Minimum Moves to Reach Target with Rotations

蛇可以顺逆时针旋转，往右往下移动，问迷宫最短路。

思路：BFS模拟。

吐槽：一开始不知道顺时针旋转后也可以向右移动，导致WA死。

import heapq
def bfs(mp):
    n = len(mp[0])
    init_pos = ((0, 0), (0, 1))
    target_pos = ((n-1, n-2), (n-1, n-1))
    Q = [(0, init_pos, 0)]
    vis = set()
    def inrange(xy, xy0, mp):
        n = len(mp[0])
        x, y = xy
        x0, y0 = xy0
        if not (0 <= x < n and 0 <= y < n and 0 <= x0 < n and 0 <= y0 < n):
            return False
        if mp[x][y] == 1 or mp[x0][y0] == 1:
            return False
        return True
    while Q:
        moves, cur_pos, cur_dir = heapq.heappop(Q)
        if (cur_pos, cur_dir) in vis:
            continue
        vis.add((cur_pos, cur_dir))
        if cur_pos == target_pos:
            return moves
        (x, y), (x0, y0) = cur_pos
        # move right
        if inrange((x, y+1), (x0, y0+1), mp) and (((x, y+1), (x0, y0+1)), cur_dir) not in vis:
            heapq.heappush(Q, (moves+1, ((x, y+1), (x0, y0+1)), cur_dir))
        # move down
        if inrange((x+1, y), (x0+1, y0), mp) and (((x+1, y), (x0+1, y0)), cur_dir) not in vis:
            heapq.heappush(Q, (moves+1, ((x+1, y), (x0+1, y0)), cur_dir))
        if cur_dir == 0:
            # rotate clockwise
            if inrange((x+1, y), (x0+1, y0), mp) and (((x, y), (x+1, y)), 1) not in vis:
                heapq.heappush(Q, (moves+1, ((x, y), (x+1, y)), 1))
        else:
            # rotate counterclockwise 
            if inrange((x, y+1), (x0, y0+1), mp) and (((x, y), (x, y+1)), 0) not in vis:
                heapq.heappush(Q, (moves+1, ((x, y), (x, y+1)), 0))
    return -1

class Solution:
    def minimumMoves(self, grid) -> int:
        return bfs(grid)