笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 99

https://leetcode.com/contest/weekly-contest-99

Surface Area of 3D Shapes

原题地址 https://leetcode.com/contest/weekly-contest-99/problems/surface-area-of-3d-shapes/

On a N * N grid, we place some 1 * 1 * 1 cubes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Return the total surface area of the resulting shapes.

Example 1:

1
2
Input: [[2]]
Output: 10

Example 2:

1
2
Input: [[1,2],[3,4]]
Output: 34

Example 3:

1
2
Input: [[1,0],[0,2]]
Output: 16

Example 4:

1
2
Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 32

Example 5:

1
2
Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 46

Note:

  1. 1 <= N <= 50
  2. 0 <= grid[i][j] <= 50

这题与Projection Area of 3D Shapes仅要求的求投影面积有所不同,因为存在凹的图形,所以依靠求投影的方法可能会失效。当然平行于xy平面部分的表面积还可以用原来的方法。我这里用一种比较直接的方法计算左侧露出的面积:对于每一排的tower,未被前排遮挡的高度即裸露出来形成表面积的部分。同理,一共需要从左到右,从右到左,从前到后,从后到前分别计算四次露出的面积:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def surfaceArea(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
N = len(grid)
back = sum(v for v in grid[0])
front = sum(v for v in grid[-1])
left = sum(grid[j][0] for j in range(N))
right = sum(grid[j][-1] for j in range(N))
base = sum(v > 0 for r in grid for v in r) * 2

for i in range(N - 1):
back += sum(max(grid[i + 1][j] - grid[i][j], 0) for j in range(N))
front += sum(max(grid[N - 2 - i][j] -
grid[N - 1 - i][j], 0) for j in range(N))
left += sum(max(grid[j][i + 1] - grid[j][i], 0) for j in range(N))
right += sum(max(grid[j][N - 2 - i] - grid[j]
[N - 1 - i], 0) for j in range(N))

return front + back + left + right + base

Groups of Special-Equivalent Strings

原题地址 https://leetcode.com/contest/weekly-contest-99/problems/groups-of-special-equivalent-strings/

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from A is a non-empty subset of A such that any string not in A is not special-equivalent with any string in A.

Return the number of groups of special-equivalent strings from A.

Example 1:

1
2
3
Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]

Example 2:

1
2
3
Input: ["aa","bb","ab","ba"]
Output: 4
Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]

Example 3:

1
2
3
Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]

Example 4:

1
2
3
Input: ["abcd","cdab","adcb","cbad"]
Output: 1
Explanation: 1 group ["abcd","cdab","adcb","cbad"]

Note:

  1. 1 <= A.length <= 1000
  2. 1 <= A[i].length <= 20
  3. All A[i] have the same length.
  4. All A[i] consist of only lowercase letters.

这里的special-equivalentST的奇数位字符组成的集合相同,偶数位字符组成的集合也相同。对于长度大于2的字符串,即sorted(S[0::2])==sorted(T[0::2]) and sorted(S[1::2])==sorted(T[1::2]),对于长度为12的字符串,直接检查是否为相等。通常的两层遍历开销太大,可以先删去重复元素,再建立一个dict存放偶数位字符集合相同的字符串,对每个字符串找到偶数位相同集合的字符串,检查其中是否还有奇数位相同的,如果有则该字符串不可能独立成新的组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def numSpecialEquivGroups(self, A):
"""
:type A: List[str]
:rtype: int
"""
d_even = {}
A = list(set(A))
res = len(A)
if A[0] <= 2:
return res
for i, w in enumerate(A):
even = tuple(sorted(A[i][0::2]))
if even in d_even:
for j in d_even[even]:
if sorted(A[i][1::2]) == sorted(A[j][1::2]):
res -= 1
break
d_even[even].append(i)
else:
d_even[even] = [i]
return res

All Possible Full Binary Trees

原题地址 https://leetcode.com/contest/weekly-contest-99/problems/all-possible-full-binary-trees/

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

1
2
3
Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:

Note:

  1. 1 <= N <= 20

很显然

  1. N为偶数时,不存在满二叉树
  2. N==1时,独立的根结点可以形成一个满二叉树
  3. N>=3时,根结点下有两棵子树,左子树的结点数可以为<N的任意奇数i,右子树的结点数则为N-1-i

这个问题满足递归定义,比较值得注意的是左右子树相同时应该避免重复计入,以及<N的子问题会被讨论多次所以需要暂时把结果存储起来访问。

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
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None


class Solution(object):
dp = {1: set([TreeNode(0)])}

def allPossibleFBT(self, N):
"""
:type N: int
:rtype: List[TreeNode]
"""
if N == 1:
return [TreeNode(0)]
if N % 2 == 0:
return []
for i in range(3, N + 1, 2):
self.dp[i] = set()
for j in range(1, i, 2):
for left in self.dp[j]:
for right in self.dp[i - 1 - j]:
r = TreeNode(0)
r.left = left
r.right = right
self.dp[i].add(r)

return list(self.dp[N])

Maximum Frequency Stack

原题地址 https://leetcode.com/contest/weekly-contest-99/problems/maximum-frequency-stack/

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

  • push(int x), which pushes an integer x onto the stack.
  • pop(), which removes and returns the most frequent element in the stack.
    • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top. Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

  1. Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
  2. It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
  3. The total number of FreqStack.push calls will not exceed 10000 in a single test case.
  4. The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
  5. The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

因为时间原因,我做的比较草率,没有事实上在栈里面删除被弹出的元素。

这里维护了一个放置元素的列表stack,记录每个元素出现的频数的字典fre,和一个返回当前最大频数元素的堆q

每次把元素x压入栈中,就把当前状态,即当前x出现的频数fre[x]和它最后一次出现的位置(列表尾部i)组成对压入一个最大堆中(因为heapq实现的是最小堆所以我这里给两个数值都取了负)。每次进行弹栈操作时,从堆中取出最大频数(下标)的元素弹出并在fre更新。一旦从堆中弹出,坐标i不会再次被压入,新压入的元素的下标也总与旧元素的相对顺序保持与栈内一致。

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 FreqStack(object):

def __init__(self):
self.stack = []
self.fre = {}
self.q = []

def push(self, x):
"""
:type x: int
:rtype: void
"""
self.stack.append(x)
self.fre[x] = self.fre.get(x, 0) + 1
heapq.heappush(self.q, (-self.fre[x], -len(self.stack) + 1))

def pop(self):
"""
:rtype: int
"""
n = len(self.stack)
max_fre, i = heapq.heappop(self.q)
self.fre[self.stack[-i]] -= 1
return self.stack[-i]




# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()

当然这题虽然看上去简单,但我一开始真的懒得动脑子就直球pop()

1
2
max_fre = max(range(n), key=lambda x: (self.stack.count(self.stack[x]), x))
return self.stack.pop(max_fre)

或者绞尽脑汁去维护相同元素组成的字典列表之类的,肯定是要TLE的,没办法,我们没文化的人就是这个样子.jpg