[LeetCode] Weekly Contest 84

832. Flipping an Image [E]

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]Output: [[1,0,0],[0,1,0],[1,1,1]]Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

[想法] 規則：先reverse，然後每個元素取反。

def flipAndInvertImage(self, A): """ :type A: List[List[int]] :rtype: List[List[int]] """ row = len(A) if row == 0: return A col = len(A[0]) if col == 0: return A ret = [] for i in range(row): newrow = A[i][::-1] for j in range(col): newrow[j] = (newrow[j] + 1) % 2 ret.append(newrow) return ret

833. Find And Replace in String [M]

To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = c, which doesnt match x[0] = e.

All these operations occur simultaneously. Its guaranteed that there wont be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Example 1:

Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]Output: "eeebffff"Explanation: "a" starts at index 0 in S, so its replaced by "eee"."cd" starts at index 2 in S, so its replaced by "ffff".

Example 2:

Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]Output: "eeecd"Explanation: "ab" starts at index 0 in S, so its replaced by "eee". "ec" doesnt starts at index 2 in the original S, so we do nothing.

[想法] 按照規則做就可以了，唯一可能要注意的地方就是index逆序做。

def findReplaceString(self, S, indexes, sources, targets): """ :type S: str :type indexes: List[int] :type sources: List[str] :type targets: List[str] :rtype: str """ ht = {nsources[i], targets[i]) for i, n in enumerate(indexes)} for i in reversed(sorted(ht.keys())): # print(i, ht[i][0], ht[i][1]) found = True for j in range(len(ht[i][0])): if S[i + j] != ht[i][0][j]: found = False break if found: S = S[:i] + ht[i][1] + S[i + len(ht[i][0]):] print(S) return S

835. Image Overlap [M]

Two images A and B are given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)

We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images.

(Note also that a translation does not include any kind of rotation.)

What is the largest possible overlap?

Example 1:

Input: A = [[1,1,0], [0,1,0], [0,1,0]] B = [[0,0,0], [0,1,1], [0,0,1]]Output: 3Explanation: We slide A to right by 1 unit and down by 1 unit.

[想法] 這題太難，結束的時候只有2個AC。我不會，直接看答案去吧。

834. Sum of Distances in Tree [H]

An undirected, connected tree with N nodes labelled 0...N-1 and N-1 edges are given.

The ith edge connects nodes edges[i][0] and edges[i][1] together.

Return a list ans, where ans[i] is the sum of the distances between node i and all other nodes.

Example 1:

Input: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]Output: [8,12,6,10,10,10]Explanation: Here is a diagram of the given tree: 0 / 1 2 /| 3 4 5We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)equals 1 + 1 + 2 + 2 + 2 = 8. Hence, answer[0] = 8, and so on.

Note: 1 <= N <= 10000

[想法] 鄰接矩陣（對稱陣），然後BFS填空。顯然TLE，但是不知道別的解法了，建議直接看答案。