每日算法系列【LeetCode 面试题 17.05】字母与数字

godweiyang

发布于 2020-03-24 11:01:36

5380

发布于 2020-03-24 11:01:36

文章被收录于专栏：算法码上来

题目描述

给定一个放有字符和数字的数组，找到最长的子数组，且包含的字符和数字的个数相同。

返回该子数组，若不存在这样的数组，返回一个空数组。

示例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

题解

回忆之前做过的一道题目：每日算法系列【LeetCode 523】连续的子数组和，是不是有点相似？那道题是要求是否含有总和为的整数倍的连续子数组。而本题要求的是最长的子数组，满足数字和字母个数相等。

我们可以把字母抽象成，数字抽象成，那么子数组的总和含义就是数字个数与字母个数的差值。假设子数组是满足字母个数和数字个数相等的，那么这段子数组总和必然是。如果我们用前缀和来进行优化的话，，也就是说和的值是相等的。

所以我们只需要求一遍前缀和，如果没有在之前出现过，那就保存一下最开始出现的下标是。否则的话就看一下当前子数组长度和历史最优的长度谁大，然后决定更不更新。

实际实现中 c++ 还是可以采用 unordered_map 来当作哈希表保存下标。

时间复杂度是。

代码

c++

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int n = array.size();
        unordered_map<int, int> mp;
        mp[0] = -1;
        int cnt = 0, l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            cnt += isdigit(array[i][0]) ? 1 : -1;
            if (mp.find(cnt) != mp.end()) {
                if (r-l < i-mp[cnt]) {
                    l = mp[cnt] + 1;
                    r = i + 1;
                }
            } else {
                mp[cnt] = i;
            }
        }
        return vector<string>(array.begin()+l, array.begin()+r);
    }
};

python

class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        mp = {0: -1}
        cnt, l, r = 0, 0, 0
        for i, s in enumerate(array):
            cnt += 1 if s[:1].isdigit() else -1
            if cnt in mp:
                if r-l < i-mp[cnt]:
                    l = mp[cnt] + 1
                    r = i + 1
            else:
                mp[cnt] = i
        return array[l:r]

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-02-23，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

c++

本文分享自算法码上来微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

c++

登录后参与评论

0 条评论

热度