做网站策划薪酬,拓者设计吧注册还要钱,网页制作 收集资料,中文域名注册查询LeetCode-面试题 17.05. 字母与数字【前缀和#xff0c;哈希表】题目描述#xff1a;解题思路一#xff1a;前缀和。数字为-1#xff0c;字母为1。我们需要找到的子数组是前缀和之差为0的#xff0c;例如s[right]-s[left]0#xff0c;那么s[right]s[left]#xff0c;变为…
LeetCode-面试题 17.05. 字母与数字【前缀和哈希表】题目描述解题思路一前缀和。数字为-1字母为1。我们需要找到的子数组是前缀和之差为0的例如s[right]-s[left]0那么s[right]s[left]变为找前缀和相同的了。我们用一个字典记录前缀和的最早出现下标。解题思路二用一个整数替换前缀和列表在遍历array过程中计算前缀和。其值在[-n,n]之间故数组长设为2n1。具体看注释。解题思路三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 100000 https://leetcode.cn/problems/find-longest-subarray-lcci/description/
解题思路一前缀和。数字为-1字母为1。我们需要找到的子数组是前缀和之差为0的例如s[right]-s[left]0那么s[right]s[left]变为找前缀和相同的了。我们用一个字典记录前缀和的最早出现下标。
array.length 非常大常规暴力算法难以不超时。 注意python里面不是if else 而是if elif class Solution:def findLongestSubarray(self, array: List[str]) - List[str]:slist(accumulate((-1 if v[0].isdigit() else 1 for v in array),initial0))leftright0#前缀和一般是左闭右开[left,right)first{}#记录前缀和最早出现的下标for i,v in enumerate(s):jfirst.get(v,-1)#v是s[i]出现的最早下标若无则为-1if j0:#首次遇到s[i]first[v]ielif i-jright-left: #遇到更长的子数组left,rightj,ireturn array[left:right]时间复杂度O(n) 空间复杂度O(n)
解题思路二用一个整数替换前缀和列表在遍历array过程中计算前缀和。其值在[-n,n]之间故数组长设为2n1。具体看注释。
class Solution:def findLongestSubarray(self, array: List[str]) - List[str]:leftright0#前缀和一般是左闭右开[left,right)snlen(array)#s初始化为n防止出现负数下标first[-1]*(2*n1)#记录前缀和最早出现的下标初始化为-1长为2n1的数组first[s]0#s[0]0for i,v in enumerate(array,1):#表示i从1开始计数s-1 if v[0].isdigit() else 1jfirst[s] #first[s]是s[i]出现的最早下标若无则为-1if j0:#首次遇到s[i]first[s]ielif i-jright-left: #遇到更长的子数组left,rightj,ireturn array[left:right]时间复杂度O(n) 空间复杂度O(n)
解题思路三0
