微软8.26笔试，这是想养一太平洋的鱼吗

三题感觉都不难，比上次简单。。。

第一题：给一个数，从中移除一个‘5’，求剩下的数的最大值。暴力即可。

import java.util.*;

public class Test01 {
    public static void main(String[] args) {
        Test01 s = new Test01();

        int N = -54325;
        int res = s.solution(N);
        System.out.println(res);
    }
    public int solution(int N) {
        int res = -1000000;
        HashSet<String> set = new HashSet<>();
        String sb = String.valueOf(N);
        for(int i = 0; i < sb.length(); ++i){
            char c = sb.charAt(i);
            if(c=='5'){
                String s = sb.substring(0,i)+sb.substring(i+1,sb.length());
                set.add(s);
            }
        }
        for(String s : set){
            res = Math.max(res, Integer.valueOf(s));
        }
        return res;
    }
}

第二题：给定数组A，返回和为0的子数组数目，子数组之间可以包含。前缀和+hash表。结果大于1e9返回-1.

import java.util.*;

public class Test02 {
    public static void main(String[] args) {
        Test02 s = new Test02();
        int[] A = new int[100000];
        for (int i = 0; i < A.length; i++) {

        }
        int res = s.solution(A);
        System.out.println(res);

    }
    public int solution(int[] A) {
        double res = 0;
        int n = A.length;
        int[] f = new int[n+1];
        for(int i = 1; i <= n; ++i){
            f[i] = f[i-1]+A[i-1];
        }
        HashMap<Integer, Double> map = new HashMap<>();
        for(int i = 1; i <= n; ++i){
            map.put(f[i], map.getOrDefault(f[i],0.0)+1);
        }
        for(int num : map.keySet()){
            double times = map.get(num);
            if(times>1){
                if(num==0){
                    res += times + times*(times-1)/2;
                }else{
                    res += times*(times-1)/2;
                }
                if(res > 1000000000) return -1;
            }
        }
        return (int) res;
    }
}

第三题：给定数组A，求长度大于2并且成等差数列的子数组个数，同样子数组之间可以包含。结果大于1e9返回-1.

差分数组，因为-2e9<=A[i]<=2e9,为了防止溢出，差分数组f取了double

public class Test03 {
    public static void main(String[] args) {
        Test03 s = new Test03();
        //int[] A = {(int)2e+9, (int)-2e+9, (int)2e9, (int)-2e+9, (int)2e9};
        int[] A = {0,1};
        //int[] A = new int[60000];
        
        int res = s.solution(A);
        System.out.println(res);
    }
    public int solution(int[] A) {
        double res = 0;
        int n = A.length;
        if(n < 3) return 0;
        double[] f = new double[n];
        f[0] = A[0];
        for(int i = 1; i < n; ++i){
            f[i] = (double)A[i]-(double)A[i-1];//记得强转double，否则按int算可能溢出
        }
        for(int i = 1; i < n-1; ){//注意差分数组从索引1开始
            if(f[i]==f[i+1]){
                int j = i+2;
                while(j<n && f[j]==f[i]){
                    j++;
                }
                double len = j-i;
                res += len*(len-1)/2;
                if(res > 1e9) return -1;
                i = j;
            }else{
                i++;
            }
        }
        return (int) res;
    }
}

#微软笔试#