8.25微软笔试

test example过了，不确定有没有别的错。

1. 去掉一个5后得到的最大数字。我看题目说注重正确性，不在意性能，那是直接暴力法？

class Solution {
    public int solution(int N) {
        // write your code in Java 8 (Java SE 8)
        String str = String.valueOf(N);
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '5') {
                list.add(i);
            }
        }
        int res = Integer.MIN_VALUE;
        for (int idx : list) {
            StringBuilder s = new StringBuilder();
            for (int i = 0; i < str.length(); i++) {
                if (i != idx) {
                    s.append(str.charAt(i));
                }
            }
            res = Math.max(res, Integer.parseInt(s.toString()));
        }
        return res;

    }
}

2. 和为0的子数组个数。前缀和+哈希，类似：lc560

class Solution {
    public int solution(int[] A) {
        // write your code in Java 8 (Java SE 8)
        int cnt=0;
        int sum=0;
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int num:A){
            sum+=num;
            if(sum==0){
                cnt++;
            }
            if(map.containsKey(sum)){
                cnt+=map.get(sum);
            }
            if(cnt>1e9){
                return -1;
            }
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return cnt;
    }
}

3. 找等差数列，对于长度为n(n>=3)的数列，对子数组个数贡献为(n-1)*(n-2)/2

class Solution {
    public int solution(int[] A) {
        // write your code in Java 8 (Java SE 8)
        int len=A.length;
        if(len<=2){
            return 0;
        }
        int res=0;
        int d=A[1]-A[0];
        int cur=A[1];
        int n=2;
        for(int i=2;i<len;i++){
            if(A[i]-cur==d){
                cur=A[i];
                n++;
            }else{
                if(n>=3){
                    res=res+(n-1)*(n-2)/2;
                }
                d=A[i]-cur;
                cur=A[i];
                n=2;
            }
        }
        if(n>=3){
            res=res+(n-1)*(n-2)/2;
        }
        return res>1e9?-1:res;
    }
}

#微软##微软笔试#