LeetCode第108场周赛题解
929. 独特的电子邮件地址
- 题目难度
Easy
每封电子邮件都由一个本地名称和一个域名组成，以 @ 符号分隔。
例如，在 alice@leetcode.com中， alice 是本地名称，而 leetcode.com 是域名。
除了小写字母，这些电子邮件还可能包含 '.' 或 '+'。
如果在电子邮件地址的本地名称部分中的某些字符之间添加句点（'.'），则发往那里的邮件将会转发到本地名称中没有点的同一地址。例如，"alice.z@leetcode.com” 和 “alicez@leetcode.com” 会转发到同一电子邮件地址。 （请注意，此规则不适用于域名。）
如果在本地名称中添加加号（'+'），则会忽略第一个加号后面的所有内容。这允许过滤某些电子邮件，例如 m.y+name@email.com 将转发到 my@email.com。 （同样，此规则不适用于域名。）
可以同时使用这两个规则。
给定电子邮件列表 emails，我们会向列表中的每个地址发送一封电子邮件。实际收到邮件的不同地址有多少？
示例：
输入：["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
输出：2
解释：实际收到邮件的是 "testemail@leetcode.com" 和 "testemail@lee.tcode.com"。
提示：
1 <= emails[i].length <= 1001 <= emails.length <= 100- 每封
emails[i]都包含有且仅有一个'@'字符。
思路：
先用'@'分割字符，前半部分用'+'分割后只保留第一部分，并将其中的'.'去除，求得local，然后将local和domain用'@'重新连接加入集合，最终集合的长度就是答案。
时间复杂度
空间复杂度
代码：
class Solution:
def numUniqueEmails(self, emails: List[str]) -> int:
ans = set()
for email in emails:
temp = email.split("@")
local = temp[0].split('+')[0]
local = local.replace('.', '')
domain = temp[1]
ans.add('@'.join([local, domain]))
return len(ans)
930. 和相同的二元子数组
- 题目难度
Medium
在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组。
示例：
输入：A = [1,0,1,0,1], S = 2
输出：4
解释：
四个子区间分别是：
[0, 2]
[0, 3]
[1, 4]
[2, 4]
提示：
A.length <= 300000 <= S <= A.length-
A[i]为0或1
思路：
一次遍历，从前往后枚举区间终点，同时用一个数组记录当前不同前缀和的数量，用f[i]代表和为i的前缀和个数。假设枚举的当前坐标是j，那么我们的目标就是计算j之前共有多少个前缀和是sum[j] - S，这个值就是f[sum[j] - S]。由于遍历过程中，每个前缀和sum[j]只用了一次，所以我们可以用一个变量s来表示，减少空间复杂度。
时间复杂度
空间复杂度
代码：
class Solution:
def numSubarraysWithSum(self, A: List[int], S: int) -> int:
s = 0
f = [0] * (len(A) + 1)
f[0] = 1
ans = 0
for i in A:
s += i
if s >= S:
ans += f[s - S]
f[s] += 1
return ans
931. 下降路径最小和
- 题目难度
Medium
给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
示例：
输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：12
解释：
可能的下降路径有：
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9][2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9][3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
和最小的下降路径是 [1,4,7]，所以答案是 12。
提示：
1 <= A.length == A[0].length <= 100-100 <= A[i][j] <= 100
思路：
动态规划入门题，和POJ1163基本相同，自底向上动态规划，（其实自顶向下也一样），状态转移方程为：A[row][col] += min(A[row + 1][col - 1], A[row + 1][col], A[row + 1][col + 1])。
时间复杂度
空间复杂度
代码：
class Solution:
def minFallingPathSum(self, A: List[List[int]]) -> int:
l = len(A)
if l == 1:
return A[0][0]
for row in range(l - 2, -1, -1):
A[row][0] += min(A[row + 1][0], A[row + 1][1])
A[row][-1] += min(A[row + 1][-1], A[row + 1][-2])
for col in range(1, l - 1):
A[row][col] += min(A[row + 1][col - 1], A[row + 1][col], A[row + 1][col + 1])
return min(A[0])
932. 漂亮数组
- 题目难度
Medium
对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得：
对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。
那么数组 A 是漂亮数组。
给定 N，返回任意漂亮数组 A（保证存在一个）。
示例 1：
输入：4
输出：[2,1,4,3]
示例 2：
输入：5
输出：[3,1,2,5,4]
提示：
1 <= N <= 1000
思路：
分治法：
- 对于一个连续的数列
1,2,3,…,n，如果按照奇偶分成两部分，1,3,5,…放到左边，2,4,6,8,…放到右边。这样重新安排后，如果i属于左边，j属于右边，A[i]+A[j]就必定是奇数，因而不存在A[k]，满足A[k]∗2=A[i]+A[j]。 - 接下来再看每一部分的内部，由于
1,3,5,…也是等差数列，所以可以经过变换再次变成1,2,3,…，且变换后的数列如果满足题目的性质，则原数列同样满足。如果我们仍然按照 1 中的策略进行奇偶分离，则可以继续分为两部分递归处理。同理2,4,6,…也可以进行变换然后递归。 - 最后递归的出口是仅有一个数字时，直接返回。
时间复杂度
空间复杂度
代码：
class Solution:
def beautifulArray(self, N: int) -> List[int]:
if N == 1:
return [1]
if N == 2:
return [1, 2]
ans = [i for i in range(1, N + 1)]
def change(A):
if len(A) <= 1:
return A
A1 = []
A2 = []
for i in range(len(A)):
if i % 2 == 0:
A1.append(A[i])
else:
A2.append(A[i])
return change(A1) + change(A2)
return change(ans)
更简单的写法：
class Solution:
def beautifulArray(self, N: int) -> List[int]:
def helper(nums):
return helper(nums[::2]) + helper(nums[1::2]) if len(nums) > 2 else nums
return helper(list(range(1,N + 1)))
