微软笔试8.26，附原题和题解。

1. 题意是找到字符串s最长子串，满足子串中每个字母出现的次数都为偶数

   借用类似前缀和的思想，遍历一边就好了。想o(n)的做法卡了一会，有点慌，

   我们考虑小写字母总共只有为26个，所以用一个维护个sum的低0 ～ 25位来表示字符串s[0] ~ s[i]中所有小写字母的奇偶性状态.（sum 二进制第 k 位为1时代表前i个字符中char(’a’ + k)出现次数为奇数）

   哈希表m记录每个状态第1次出现时下标L，当遍历到R时如果这个状态再次出现，那么R - L就是一个满足条件的子串，答案就是R- L的最大值。

   注意m[0]（sum == 0）第一次出现时也满足条件，也要比较一下。

   手动模拟下样例 “bdaaadadb”

   i = 1时，子串只有一个’b‘，sum = 二进制(0010)，没有出现过，记录下（10）第一次出现的位置m[sum] = 1, ans = 0;

   i = 2时，’b’ ‘d’ 为奇，sum = (1010), m[sum] = 2, ans = 0;

   i = 3时，‘d’‘b'’a’, sum = (1011),m[sum] = 3, ans = 0;

   i = 4时，‘d''b', sum = （1010）,发现被用过，m[sum] = 2,所以子串[m[sum] + 1, i]为满足条件的子字符串，更新ans = 4 - 2 = 2;

   i = 5, sum = (1011), 发现被用过m[sum] = 3, ans = max(2, (5 - 3)) = 2;

   i = 6, sum = (0011), ans = 2;

   i = 7, sum = (0010), 发现被用过m[sum] = 1, ans = max(2, (7 - 1)) = 6;

   ……

#include<bits/stdc++.h>
using namespace std;
string s;
unordered_map<char, int> h;//好像换个写法可以省掉h这个表。
unordered_map<int, int> m;

int solution(string &s){
    int n = s.size();
    int sum = 0, ans = 0;
    for(int i = 1; i <= n; i ++){
        char c = s[i - 1];
        ++ h[c];
        if(h[c] % 2){
            int t = c - 'a';
            sum += 1 << t;
        }else{
            int t = c - 'a';
            sum -= 1 << t;
        }
        
        if(m[sum] == 0) m[sum] = i;
        else {
            ans = max(ans, i - m[sum]);
        }
    }  //attention
    ans = max(ans, m[0]);
    return ans;
}

1. 思路：所有数对M取模，满足条件的同一个数组的元素会映射到相同位置。遍历哈希表取最大值就好了。

   注意：c ++ 取模可能为负数，所有要((x % M) + M) % M才是数学上的取模

#include<bits/stdc++.h>
using namespace std;

unordered_map<int, int> h;
vector<int> nums;

int solution(vector<int> &A, int M) {
    int ans = 0;
    for(int x : A){
        int t = ((x % M) + M) % M;
        h[t] ++;
    }
    for(auto x : h)
        ans = max(ans, x.second);
    return ans;
}

1. 感觉不是最优解,甚至不知道做对了吗，抛砖引玉，求佬们的解

   贪心 + 暴力（没法证明正确性的贪心大概率错的）：

   st[i] 记录第i个位置是否已经确定。

   nums[i]记录[1,N]每个数字是否已经用过；

   1.首先遍历一次，A[i] == B[i],直接标记一下st[i] 和nums[A[i]];

   2.再遍历一次，对于没有确定的位置，如果发现A[i] 或者 B[i]已经用过，那我们就填上(不影响答案）,并标记一下st[i];

   3.如果还有位置没发确定，我们把所有可选值用大根堆维护，每次选出最大的值，并把可以取到该值的位置标记一下，知道所有位置被标记。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

vector<bool> st;
vector<bool> nums(N, false);

int solution(vector<int> &A, vector<int> &B) {
    int n = A.size(), cnt = 0;
    st = vector<bool>(n, false);
    unordered_map<int, set<int>> h;
    priority_queue<int> hp;  //1
    for(int i = 0; i < n; i ++){ 
        if(A[i] == B[i]){
            nums[A[i]] = true;
            if(!st[i]) st[i] = true, cnt ++;
        }
    }  //2
    for(int i = 0; i < n; i ++){ 
        if((nums[A[i]] || nums[B[i]]) && !st[i])
        st[i] = true, cnt ++;
    }

    //3.init() n * log n
    for(int i = 0; i < n; i ++){ 
        if(!st[i]){
            h[A[i]].insert(i), hp.push(A[i]);
            h[B[i]].insert(i), hp.push(B[i]);
        }
    }

    //3
    while(cnt < n){
        auto t = hp.top();
        while(!hp.empty() && hp.top() == t) hp.pop();
        nums[t] = true;
        
        for(auto x : h[t]){
            if(!st[x]){
                st[t] = true;
                cnt ++;
            }
        }
    }
    
    for(int i = 1; i < N; i ++)
        if(nums[i] == false)
            return i;
    return 0;
}