## Hypercube's LeetCode Weekly Contest 46

- Rank:
**144**/ 2389 - Score: 16 / 25
- Finish Time: 00:45:42

### Image Smoother

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less than 8 surrounding cells, then use as many as you can.

**Example 1:**

```
Input:
[[1, 1, 1],
[1, 0, 1],
[1, 1, 1]]
Output:
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
Explanation:
For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0
```

**Note:**

- The value in the given matrix is in the range of [0, 255].
- The length and width of the given matrix are in the range of [1, 150].

**Accepted**in 00:12:19 with 1 wrong submissions

### Maximum Width of Binary Tree

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a **full binary tree**, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the `null`

nodes between the end-nodes are also counted into the length calculation.

**Example 1:**

```
Input:
1
/ \
3 2
/ \ \
5 3 9
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5, 3, null, 9).
```

**Example 2:**

```
Input:
1
/
3
/ \
5 3
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5, 3).
```

**Example 3:**

```
Input:
1
/ \
3 2
/
5
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3, 2).
```

**Example 4:**

```
Input:
1
/ \
3 2
/ \
5 9
/ \
6 7
Output: 8
Explanation: The maximum width existing in the fourth level with the length 8 (6, null, null, null, null, null, null, 7).
```

**Note:** Answer will in the range of 32-bit signed integer.

**Accepted**in 00:23:44

### Equal Tree Partition

Given a binary tree with `n`

nodes, your task is to check if itâ€™s possible to partition the tree to two trees which have the equal sum of values after removing **exactly** one edge on the original tree.

**Example 1:**

```
Input:
5
/ \
10 10
/ \
2 3
Output: True
Explanation:
5
/
10
Sum: 15
10
/ \
2 3
Sum: 15
```

**Example 2:**

```
Input:
1
/ \
2 10
/ \
2 20
Output: False
Explanation: You can't split the tree into two trees with equal sum after removing exactly one edge on the tree.
```

**Note:**

- The range of tree node value is in the range of [-100000, 100000].
- 1 <= n <= 10000

**Accepted**in 00:35:42 with 1 wrong submissions

### Strange Printer

There is a strange printer with the following two special requirements:

- The printer can only print a sequence of the same character each time.
- At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

**Example 1:**

```
Input: "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".
```

**Example 2:**

```
Input: "aba"
Output: 2
Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.
```

**Hint:** Length of the given string will not exceed 100.

**Wrong Answer**