微软笔试8.26，附上题目和自己的解法，求大伙帮找下缺漏

Task1

题目

图片说明

思路
对撞指针。用一个数组来统计字符串中每个字母出现的次数，如果数组中每个元素出现的次数都为偶数，则代表该字符串符合题目要求。左右指针对撞，如果当前l和r所指的字符的出现次数都为偶数，则判断当前子串是否符合要求，符合则返回当前字符串长度；不符合，左右指针都向中间靠拢一步，对应的字符出现次数数组中的值减一；如果l和r所指字符出现次数都为奇数，则判断是否所指字符是否相等，如果相等则移动任意一个指针，对应次数减一；如果不相等，左右都移动然后次数减一
code

//对撞指针
    public int task1(String S) {
        int l = 0, r = S.length() - 1;
        int[] count = new int[26];
        for (int i = 0; i < S.length(); i++) {
            count[S.charAt(i) - 'a']++;
        }
        while (l < r) {
            if (count[S.charAt(l) - 'a'] % 2 == 0 && count[S.charAt(r) - 'a'] % 2 == 0 && isOk(count))
                return r - l + 1;

            if (S.charAt(l) == S.charAt(r) && count[S.charAt(l) - 'a'] % 2 != 0) {
                count[S.charAt(l) - 'a']--;
                l++;
            } else if (count[S.charAt(l) - 'a'] % 2 == 0 && count[S.charAt(r) - 'a'] % 2 == 0 && !isOk(count) ||
                    count[S.charAt(l) - 'a'] % 2 != 0 && count[S.charAt(r) - 'a'] % 2 != 0
            ) {
                count[S.charAt(l) - 'a']--;
                count[S.charAt(r) - 'a']--;
                l++;
                r--;
            } else if (count[S.charAt(l) - 'a'] % 2 != 0) {
                count[S.charAt(l) - 'a']--;
                l++;
            } else {
                count[S.charAt(r) - 'a']--;
                r--;
            }
        }
        return 0;
    }

    private boolean isOk(int[] count) {
        for (int j : count) {
            if (j % 2 == 1)
                return false;
        }
        return true;
    }

Task2

题目

图片说明

思路
用一个map来存储坐标对应的点的集合，然后遍历数组，判断map中是否含有A[i] + k * M (k=1,2,3...,A[i] + k * M <= 坐标最大值)的点，如果有就将这些点全部放在一个集合里面，记录集合的最大长度，即为所求
code

public int task2(int[] A, int M) {
        //坐标为k的点的集合
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            HashSet<Integer> set = map.getOrDefault(A[i], new HashSet<>());
            set.add(i);
            map.put(A[i], set);
            max = Math.max(max, A[i]);
        }
        int ans = 1;
        for (int i = 0; i < A.length; i++) {
            HashSet<Integer> set = new HashSet<>();
            for (int x = A[i] + M; x <= max; x = x + M) {
                if (map.containsKey(x)) {
                    //取并集
                    set.addAll(map.get(A[i]));
                    set.addAll(map.get(x));
                }
            }
            ans = Math.max(set.size(), ans);
        }
        return ans;
    }

Task3

题目

图片说明

思路
就是求A和B merge后的最小未出现的正数，不算太难，这里用list来存C

code

public int task3(int[] A, int[] B) {
      LinkedList<Integer> list = new LinkedList<>();
      for (int i = 0; i < A.length; i++) {
          list.add(Math.max(A[i], B[i]));
      }
      int ans = Integer.MAX_VALUE;
      for (int x : A) {
          if (!list.contains(x))
              ans = Math.min(x, ans);
      }
      for (int x : B) {
          if (!list.contains(x))
              ans = Math.min(x, ans);
      }
      for (int i = 1; i <= ans; i++) {
          if (!list.contains(i)) {
              ans = i;
              break;
          }
      }
      return ans;
  }