| 0241 | [为运算表达式设计优先级](https://leetcode.cn/problems/different-ways-to-add-parentheses/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0241.%20%E4%B8%BA%E8%BF%90%E7%AE%97%E8%A1%A8%E8%BE%BE%E5%BC%8F%E8%AE%BE%E8%AE%A1%E4%BC%98%E5%85%88%E7%BA%A7.md) | 递归、记忆化搜索、数学、字符串、动态规划 | 中等 |

| 0241 | [为运算表达式设计优先级](https://leetcode.cn/problems/different-ways-to-add-parentheses/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0241.%20%E4%B8%BA%E8%BF%90%E7%AE%97%E8%A1%A8%E8%BE%BE%E5%BC%8F%E8%AE%BE%E8%AE%A1%E4%BC%98%E5%85%88%E7%BA%A7.md) | 递归、记忆化搜索、数学、字符串、动态规划 | 中等 |

- 标签：递归、记忆化搜索、数学、字符串、动态规划

- 难度：中等

**描述**：给定一个由数字和运算符组成的字符串 `expression`。

**要求**：按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以按任意顺序返回答案。

**说明**：

- 生成的测试用例满足其对应输出值符合 $32$ 位整数范围，不同结果的数量不超过 $10^4$。

- $1 \le expression.length \le 20$。

- `expression` 由数字和算符 `'+'`、`'-'` 和 `'*'` 组成。

- 输入表达式中的所有整数值在范围 $[0, 99]$。

**示例**：

- 示例 1：

输入：expression = "2-1-1"

输出：[0,2]

解释：

((2-1)-1) = 0

(2-(1-1)) = 2

- 示例 2：

输入：expression = "2*3-4*5"

输出：[-34,-14,-10,-10,10]

解释：

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

给定的字符串 `expression` 只包含有数字和字符，可以写成类似 `x op y` 的形式，其中 $x$、$y$ 为表达式或数字，$op$ 为字符。

则我们可以根据字符的位置，将其递归分解为 $x$、$y$ 两个部分，接着分别计算 $x$ 部分的结果与 $y$ 部分的结果。然后再将其合并。

class Solution:

def diffWaysToCompute(self, expression: str) -> List[int]:

res = []

if len(expression) <= 2:

res.append(int(expression))

return res

for i in range(len(expression)):

ch = expression[i]

if ch == '+' or ch == '-' or ch == '*':

left_cnts = self.diffWaysToCompute(expression[ :i])

right_cnts = self.diffWaysToCompute(expression[i + 1:])

for left in left_cnts:

for right in right_cnts:

if ch == '+':

res.append(left + right)

elif ch == '-':

res.append(left - right)

else:

res.append(left * right)

return res

- **时间复杂度**：$O(C_n)$，其中 $n$ 为结果数组的大小，$C_n$ 是第 $k$ 个卡特兰数。

- **空间复杂度**：$O(C_n)$。

- 标签：数组、数学、分治

- 难度：中等

**描述**：给定一个整数 $n$。

**要求**：返回长度为 $n$ 的任一漂亮数组。

**说明**：

- **漂亮数组**（长度为 $n$ 的数组 $nums$ 满足下述条件）：

- $nums$ 是由范围 $[1, n]$ 的整数组成的一个排列。

- 对于每个 $0 \le i < j < n$，均不存在下标 $k$（$i < k < j$）使得 $2 \times nums[k] == nums[i] + nums[j]$。

- $1 \le n \le 1000$。

- 本题保证对于给定的 $n$ 至少存在一个有效答案。

**示例**：

- 示例 1：

输入：n = 4

输出：[2,1,4,3]

- 示例 2：

输入：n = 5

输出：[3,1,2,5,4]

根据题目要求，我们可以得到以下信息：

1. 题目要求 $2 \times nums[k] == nums[i] + nums[j], (0 \le i < k < j < n)$ 不能成立，可知：等式左侧必为偶数，只要右侧和为奇数则等式不成立。

2. 已知：奇数 + 偶数 = 奇数，则令 $nums[i]$ 和 $nums[j]$ 其中一个为奇数，另一个为偶数，即可保证 $nums[i] + nums[j]$ 一定为奇数。这里我们不妨令 $nums[i]$ 为奇数，令 $nums[j]$ 为偶数。

3. 如果数组 $nums$ 是漂亮数组，那么对数组 $nums$ 的每一位元素乘以一个常数或者加上一个常数之后，$nums$ 仍是漂亮数组。

- 即如果 $[a_1, a_2, ..., a_n]$ 是一个漂亮数组，那么 $[k \times a_1 + b, k \times a_2 + b, ..., k \times a_n + b]$ 也是漂亮数组。

那么，我们可以按照下面的规则构建长度为 $n$ 的漂亮数组。

1. 当 $n = 1$ 时，返回 $[1]$。此时数组 $nums$ 中仅有 $1$ 个元素，并且满足漂亮数组的条件。

2. 当 $n > 1$ 时，我们将 $nums$ 分解为左右两个部分：`left_nums`、`right_nums`。如果左右两个部分满足：

1. 数组 `left_nums` 中元素全为奇数（可以通过 `nums[i] * 2 - 1` 将 `left_nums` 中元素全部映射为奇数）。

2. 数组 `right_nums` 中元素全为偶数（可以通过 `nums[i] * 2` 将 `right_nums` 中元素全部映射为偶数）。

3. `left_nums` 和 `right_nums` 都是漂亮数组。

3. 那么 `left_nums + right_nums` 构成的数组一定也是漂亮数组，即 $nums$ 为漂亮数组，将 $nums$ 返回即可。

class Solution:

def beautifulArray(self, n: int) -> List[int]:

if n == 1:

return [1]

nums = [0 for _ in range(n)]

left_cnt = (n + 1) // 2

right_cnt = n - left_cnt

left_nums = self.beautifulArray(left_cnt)

right_nums = self.beautifulArray(right_cnt)

for i in range(left_cnt):

nums[i] = 2 * left_nums[i] - 1

for i in range(right_cnt):

nums[left_cnt + i] = 2 * right_nums[i]

return nums

- **时间复杂度**：$O(n \times \log n)$，其中 $n$ 为数组 $nums$ 的长度。

- **空间复杂度**：$O(n \times \log n)$。