力扣面试题17.05.字母与数字

力扣面试题17.05.字母与数字

• 把数字与字母的差值存在哈希表

  • 用lr记录子数组的两端点
  • 判断字符串为数字串/字母串方法：
    • (c >> 6 & 1) * 2 - 1
    • 对于字符 其ASCII码的二进制形如01xxxxxx
    • 对于数字 其ASCII码的二进制形如0011xxxx
    • 观察到两者由低到高第6位有区别(最低位为0)
  • 因此将c >> 6 & 1 把第6位取出来
    • 通过*2 - 1的操作把 1->0，0->1 然后求前缀和

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