leetcode面试题 17.05. 字母与数字

107 阅读 0 评论 71 点赞

我是靠谱客的博主幸福牛排，这篇文章主要介绍leetcode面试题 17.05. 字母与数字，现在分享给大家，希望可以做个参考。

https://leetcode-cn.com/problems/find-longest-subarray-lcci/

哈希表存状态，解题思路与leetcode525类似，详情见注释

leetcode525解

复制代码

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int cur=0;//当前位置
        int maxL=0;//最长串的长度
        int loc=0;//最长串的起始位置
        unordered_map<int,int> mp;//哈希表，key值记录当前的cur值，value则是表示在array里的序号
        mp[0] = -1;//初始的cur在0，它的value值置为-1
        vector<string> ret;//需要返回的向量数组
        for(int i=0;i<array.size();i++)
        {
            char ch = array[i][0];//根据当前字符串的第一个字符就可以判断这个字符串是数字还是字母
            if(ch<='9'&&ch>='0')//是数字的情况
                cur--;
            else 
                cur++;
            if(mp.count(cur)>0)//对应的cur值有存在哈希表就不用写，否则把对应的cur值和序号写入哈希表
            {
                int len = i-mp[cur];//存在这个cur，就记录下当前的序号和之前序号的距离，这个距离就是这一段具有相同字母和数字数目的连续子串的长度
                if(len>maxL)//如果比最长的长度长就更新maxL和loc
                {
                    maxL = len;
                    loc = mp[cur]+1;//loc的位置会比真实的位置小1，要加上去
                }
            }
            else 
                mp[cur] = i;//不存就写入
        }
        while(maxL!=0)//根据起始位置和长度，就可以把字符串放进来了
        {
            ret.push_back(array[loc++]);
            maxL--;
        }
        return ret;
    }
};

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
38
class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int cur=0;//当前位置
        int maxL=0;//最长串的长度
        int loc=0;//最长串的起始位置
        unordered_map<int,int> mp;//哈希表，key值记录当前的cur值，value则是表示在array里的序号
        mp[0] = -1;//初始的cur在0，它的value值置为-1
        vector<string> ret;//需要返回的向量数组
        for(int i=0;i<array.size();i++)
        {
            char ch = array[i][0];//根据当前字符串的第一个字符就可以判断这个字符串是数字还是字母
            if(ch<='9'&&ch>='0')//是数字的情况
                cur--;
            else 
                cur++;
            if(mp.count(cur)>0)//对应的cur值有存在哈希表就不用写，否则把对应的cur值和序号写入哈希表
            {
                int len = i-mp[cur];//存在这个cur，就记录下当前的序号和之前序号的距离，这个距离就是这一段具有相同字母和数字数目的连续子串的长度
                if(len>maxL)//如果比最长的长度长就更新maxL和loc
                {
                    maxL = len;
                    loc = mp[cur]+1;//loc的位置会比真实的位置小1，要加上去
                }
            }
            else 
                mp[cur] = i;//不存就写入
        }
        while(maxL!=0)//根据起始位置和长度，就可以把字符串放进来了
        {
            ret.push_back(array[loc++]);
            maxL--;
        }
        return ret;
    }
};