| LeetCode | 您所在的位置：网站首页 › 三个数的和的立方 › LeetCode |
|
LeetCode-面试题 17.05. 字母与数字【前缀和，哈希表】
题目描述：解题思路一：前缀和。数字为-1，字母为1。我们需要找到的子数组是前缀和之差为0的，例如s[right]-s[left]=0，那么s[right]=s[left]，变为找前缀和相同的了。我们用一个字典记录前缀和的最早出现下标。解题思路二：用一个整数替换前缀和列表，在遍历array过程中计算前缀和。其值在[-n,n]之间故数组长设为2n+1。具体看注释。解题思路三：0
题目描述：
给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。 返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。 示例 1: 输入: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”,“H”,“I”,“J”,“K”,“L”,“M”] 输出: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”] 示例 2: 输入: [“A”,“A”] 输出: [] 提示： array.length List[str]: s=list(accumulate((-1 if v[0].isdigit() else 1 for v in array),initial=0)) left=right=0#前缀和一般是左闭右开[left,right) first={}#记录前缀和最早出现的下标 for i,v in enumerate(s): j=first.get(v,-1)#v是s[i]出现的最早下标，若无则为-1 if jright-left: #遇到更长的子数组 left,right=j,i return array[left:right] 时间复杂度：O(n) 空间复杂度：O(n) 解题思路二：用一个整数替换前缀和列表，在遍历array过程中计算前缀和。其值在[-n,n]之间故数组长设为2n+1。具体看注释。 class Solution: def findLongestSubarray(self, array: List[str]) -> List[str]: left=right=0#前缀和一般是左闭右开[left,right) s=n=len(array)#s初始化为n防止出现负数下标 first=[-1]*(2*n+1)#记录前缀和最早出现的下标，初始化为-1长为2n+1的数组 first[s]=0#s[0]=0 for i,v in enumerate(array,1):#表示i从1开始计数 s+=-1 if v[0].isdigit() else 1 j=first[s] #first[s]是s[i]出现的最早下标，若无则为-1 if jright-left: #遇到更长的子数组 left,right=j,i return array[left:right]时间复杂度：O(n) 空间复杂度：O(n) 解题思路三：0 |
| CopyRight 2018-2019 实验室设备网 版权所有 |