最后一题靠运气AC了。。。排名 131 / 4148
第一题：按既定顺序创建目标数组
给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：
目标数组 target 最初为空。
按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。
重复上一步，直到在 nums 和 index 中都没有要读取的元素。
请你返回目标数组。
题目保证数字插入位置总是存在。
示例 1：
输入：nums = [0,1,2,3,4], index = [0,1,2,2,1]
输出：[0,4,1,3,2]
解释：
nums index target
0 0 [0]
1 1 [0,1]
2 2 [0,1,2]
3 2 [0,1,3,2]
4 1 [0,4,1,3,2]
示例 2：
输入：nums = [1,2,3,4,0], index = [0,1,2,3,0]
输出：[0,1,2,3,4]
解释：
nums index target
1 0 [1]
2 1 [1,2]
3 2 [1,2,3]
4 3 [1,2,3,4]
0 0 [0,1,2,3,4]
示例 3：
输入：nums = [1], index = [0]
输出：[1]
思路：
调用insert方法。
代码：
|
1 2 3 4 5 6 7 |
class Solution: def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]: target = [] for i, num in zip(index, nums): target.insert(i, num) return target |
第二题：四因数
给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。
如果数组中不存在满足题意的整数，则返回 0 。
示例：
输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。
思路：
1和num本身必为因子，因此再找两个不同的因子即可。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution: def sumFourDivisors(self, nums: List[int]) -> int: ans = 0 for num in nums: count = 2 j = 0 for i in range(2, int(math.sqrt(num))+1): if num % i == 0: if num // i != i: count += 2 j = i else: # 比如4 分解成2×2，是两个相同的因子 count += 1 if count == 4: ans += (1 + num + j + num//j) return ans |
第三题：检查网格中是否存在有效路径
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。
你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。
注意：你 不能 变更街道。
如果网格中存在有效的路径，则返回 true，否则返回 false 。
示例 1：
输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m – 1, n – 1) 。
示例 2：
输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。
示例 3：
输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。
示例 4：
输入：grid = [[1,1,1,1,1,1,3]]
输出：true
示例 5：
输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true
思路：
这题一直朝一个方向搜索即可，不过要注意有以下几个坑：
1、道路可能有环，所以要用一个数组记录是否走过。
2、初始(0, 0)的位置可能是道路4，有两个方向可以走。
3、Python3默认最大递归深度为998。由于这题数据量大，用递归不设置深度会报maximum recursion depth exceeded。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
sys.setrecursionlimit(100000) # 设置一下最大递归深度 class Solution: def hasValidPath(self, grid: List[List[int]]) -> bool: up, down, left, right, non = (-1, 0), (1, 0), (0, -1), (0, 1), (0, 0) streets = [(non, non), (left, right), (up, down), (left,down),(down,right),(left,up),(up,right)] m = len(grid) n = len(grid[0]) i, j = 0, 0 visited = [[0 for i in range(n)] for j in range(m)] def dfs(i, j, f): # f表示来的时候的方向 if i < 0 or j < 0 or i >= m or j >= n or visited[i][j]: return visited[i][j] = 1 s = grid[i][j] di0, dj0 = streets[s][0] di1, dj1 = streets[s][1] if f!= (0, 0): # 初始时可以往任意方向走 if not (f[0]+di0 == 0 and f[1] + dj0 == 0) and not (f[0]+di1 == 0 and f[1] + dj1 == 0): # 判断道路能不能接上 return if i == m-1 and j == n-1: return True if dfs(i+di0, j+dj0, (di0,dj0)) or dfs(i+di1, j+dj1, (di1,dj1)): return True if dfs(0, 0, (0, 0)): return True return False |
第四题：最长快乐前缀
「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
给你一个字符串 s，请你返回它的 最长快乐前缀。
如果不存在满足题意的前缀，则返回一个空字符串。
示例 1：
输入：s = “level”
输出：”l”
解释：不包括 s 自己，一共有 4 个前缀（”l”, “le”, “lev”, “leve”）和 4 个后缀（”l”, “el”, “vel”, “evel”）。最长的既是前缀也是后缀的字符串是 “l” 。
示例 2：
输入：s = “ababab”
输出：”abab”
解释：”abab” 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。
示例 3：
输入：s = “leetcodeleet”
输出：”leet”
示例 4：
输入：s = “a”
输出：””
思路：
方法一：投机取巧。。。因为py3给的时限长所以能AC。。
方法二：KMP的next数组。
代码：
方法一：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution: def longestPrefix(self, s: str) -> str: n = len(s) i, j = 1, n-1 while j < n: if s[i:n] == s[:j]: return s[:j] i += 1 j -= 1 return '' |
方法二：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution: def longestPrefix(self, s: str) -> str: j, k = 0, -1 n = len(s) next = [-1 for i in range(n+1)] while j < n: if k == -1 or s[j] == s[k]: j += 1 k += 1 next[j] = k else: k = next[k] return s[:next[n]] |
