## Hypercube's LeetCode Weekly Contest 47

- Rank:
**83**/ 2554 - Score: 27 / 27
- Finish Time: 01:51:48

### Non-decreasing Array

Given an array with `n`

integers, your task is to check if it could become non-decreasing by modifying **at most** `1`

element.

We define an array is non-decreasing if `array[i] <= array[i + 1]`

holds for every `i`

(1 <= i < n).

**Example 1:**

```
Input: [4, 2, 3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
```

**Example 2:**

```
Input: [4, 2, 1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.
```

**Note:** The `n`

belongs to [1, 10000].

**Accepted**in 00:16:30

### Path Sum IV

If the depth of a tree is smaller than `5`

, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

- The hundreds digit represents the depth
`D`

of this node,`1 <= D <= 4`

. - The tens digit represents the position
`P`

of this node in the level it belongs to,`1 <= P <= 8`

. The position is the same as that in a full binary tree. - The units digit represents the value
`V`

of this node,`0 <= V <= 9`

. Given a list of`ascending`

three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

**Example 1:**

```
Input: [113, 215, 221]
Output: 12
Explanation:
The tree that the list represents is:
3
/ \
5 1
The path sum is (3 + 5) + (3 + 1) = 12.
```

**Example 2:**

```
Input: [113, 221]
Output: 4
Explanation:
The tree that the list represents is:
3
\
1
The path sum is (3 + 1) = 4.
```

**Accepted**in 00:28:39

### Beautiful Arrangement II

Given two integers `n`

and `k`

, you need to construct a list which contains `n`

different positive integers ranging from `1`

to `n`

and obeys the following requirement:

Suppose this list is [a1, a2, a3, …, an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, …, |an-1 - an|] has exactly `k`

distinct integers.

If there are multiple answers, print any of them.

**Example 1:**

```
Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.
```

**Example 2:**

```
Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
```

**Note:**

- The
`n`

and`k`

are in the range 1 <= k < n <= 10^4.

**Accepted**in 00:37:24

### Kth largest Number in Multiplication Table

Nearly every one have used the Multiplication Table. But could you find out the `k-th`

largest number quickly from the multiplication table?

Given the height `m`

and the length `n`

of a `m * n`

Multiplication Table, and a positive integer `k`

, you need to return the `k-th`

largest number in this table.

**Example 1:**

```
Input: m = 3, n = 3, k = 5
Output: 3
Explanation:
The Multiplication Table:
1 2 3
2 4 6
3 6 9
The 5-th largest number is 3 (1, 2, 2, 3, 3).
```

**Example 2:**

```
Input: m = 2, n = 3, k = 6
Output: 6
Explanation:
The Multiplication Table:
1 2 3
2 4 6
The 6-th largest number is 6 (1, 2, 2, 3, 4, 6).
```

**Note:**

- The
`m`

and`n`

will be in the range [1, 30000]. - The
`k`

will be in the range [1, m * n]

**Accepted**in 01:21:48 with 6 wrong submissions