LeetCode第110场周赛题解
937. 重新排列日志文件
- 题目难度
Easy
你有一个日志数组 logs。每条日志都是以空格分隔的字串。
对于每条日志，其第一个字为字母数字标识符。然后，要么：
- 标识符后面的每个字将仅由小写字母组成，或；
- 标识符后面的每个字将仅由数字组成。
我们将这两种日志分别称为字母日志和数字日志。保证每个日志在其标识符后面至少有一个字。
将日志重新排序，使得所有字母日志都排在数字日志之前。字母日志按字母顺序排序，忽略标识符，标识符仅用于表示关系。数字日志应该按原来的顺序排列。
返回日志的最终顺序。
示例 ：
输入：["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
输出：["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]
提示：
0 <= logs.length <= 1003 <= logs[i].length <= 100-
logs[i]保证有一个标识符，并且标识符后面有一个字。
思路：
首先将日志分为两类，把每个日志用空格分割字符串，判断第二项第一个字符是不是数字，是则归为数字日志，否则归为字母日志，然后将字母日志截取内容并按照内容排序，最后连接两个日志列表即可。
时间复杂度
空间复杂度
代码：
class Solution:
def reorderLogFiles(self, logs: List[str]) -> List[str]:
alp = []
num = []
for log in logs:
if log.split(' ')[1][0] in "1234567890":
num.append(log)
else:
alp.append(log)
alp = sorted(alp, key=lambda x: x[x.find(' ') + 1:])
return alp + num
938. 二叉搜索树的范围和
- 题目难度
Medium
给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。
示例 1：
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32
示例 2：
输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23
提示：
- 树中的结点数量最多为
10000个。 - 最终的答案保证小于
2^31。
思路：
直接递归加剪枝，如果当前结点root的值root.val小于L，那么区间肯定完全包含在root的右子树中，如果当前结点root的值root.val大于R，那么区间肯定完全包含在root的左子树中，如果当前结点root的值root.val在区间内，则应该分别在左右子树中搜索，将得到的结果加和。
时间复杂度
空间复杂度
代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
if not root:
return 0
if root.val > R:
return self.rangeSumBST(root.left, L, R)
elif root.val < L:
return self.rangeSumBST(root.right, L, R)
else:
return root.val + self.rangeSumBST(root.left, L, R) + self.rangeSumBST(root.right, L, R)
939. 最小面积矩形
- 题目难度
Medium
给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形，就返回 0。
示例 1：
输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4
示例 2：
输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2
提示：
1 <= points.length <= 5000 <= points[i][0] <= 400000 <= points[i][1] <= 40000- 所有的点都是不同的。
思路：
本题暴力枚举矩形对角线两个点会超时，能通过的第一种方法是遍历横坐标，当遍历横坐标x的时候，遍历对应的纵坐标，从纵坐标中选择两个点y1, y2，查询之前遍历的横坐标有没有对应纵坐标相同的点，如果有的话，就可以构成一个矩形，具体代码见https://blog.csdn.net/qq_17550379/article/details/84102001。
本题最快的解法是，先按照坐标排序，用dicx[x]来记录横坐标x对应的所有纵坐标，用dicy[y]来记录纵坐标y对应的所有横坐标，当我们遍历到坐标(x, y)时，我们从后往前枚举矩形的底和高，如果找到符合要求的矩形，就是以当前点为右上点的面积最小的矩形了，所以也就不用继续枚举了，这样相当于实现了一个最优的剪枝。
时间复杂度 这只是个粗略的上界，由于有剪枝，所以远达不到这个复杂度。
空间复杂度
代码：
解法1
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
points.sort()
dicx = {}
dicy = {}
minans = 0
for p in points:
x, y = p[0], p[1]
if x not in dicx or y not in dicy:
if x not in dicx:
dicx[x] = [y]
else:
dicx[x].append(y)
if y not in dicy:
dicy[y] = [x]
else:
dicy[y].append(x)
continue
minl = x - dicy[y][-1]
for ny in dicx[x][::-1]:
h = y - ny
if 0 < minans < h * minl:
break
for nx in dicy[y][::-1]:
l = x - nx
if nx in dicy[ny]:
if l * h < minans or minans == 0:
minans = l * h
else:
break
dicx[x].append(y)
dicy[y].append(x)
return minans
940. 不同的子序列 II
- 题目难度
Hard
给定一个字符串 S，计算 S 的不同非空子序列的个数。
因为结果可能很大，所以返回答案模 10^9 + 7.
示例 1：
输入："abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
示例 2：
输入："aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
示例 3：
输入："aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
提示：
-
S只包含小写字母。 1 <= S.length <= 2000
思路：
动态规划：顺序遍历字符串，用dp[c]表示遍历到当前位时，以字母c为结尾的不同子字符串个数，ans表示在当前位之前的所有不同子字符串的个数，那么新的dp[c]就应该等于之前的子字符串后面加上c和单个的字母c这两种情况加和，即ans + 1。更新当前位ans时，要加上dp[c]再减去之前的dp[c]，因为之前的dp[c]被重复计算了，比如字符串abab，在遍历第二个a时，第一个单独的a被重复计算了，在遍历第二个b时，单独的b和ab被重复计算了。
时间复杂度
空间复杂度
代码：
class Solution:
def distinctSubseqII(self, S: str) -> int:
mod = 1000000007
ans = 0
dp = [0] * 26
for c in S:
index = ord(c) - 97
old = dp[index]
dp[index] = (ans + 1) % mod
ans = (ans + dp[index] - old) % mod
return ans
