微众银行笔试9.3 Java开发

第一题，HashSet

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        Set<Integer> cad = new HashSet<>();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!cad.contains(arr[i])) {
                cad.add(arr[i]);
                count++;
            } else {
                break;
            }
        }
        System.out.println(count);
    }
}

第二题，主要思路是先将输入的数组排序，然后遍历数组，如果当前元素小于等于前一个元素，则将其增加到前一个元素加一的大小，并累加所需的橡皮泥数量。

import java.util.*;
public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        long ans = 0;
        for (int i = 1; i < n; i++) {
            if (a[i] <= a[i - 1]) {
                ans += a[i - 1] - a[i] + 1;
                a[i] = a[i - 1] + 1;
            }
        }
        System.out.println(ans);
    }
}

第三题，将问题转化为求解有多少个子区间的和等于 u/v * 子区间长度。然后，前缀和。

import java.util.Scanner;
import java.util.HashMap;

public class Main3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int u = sc.nextInt();
        int v = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        long ans = 0;
        HashMap<Long, Integer> map = new HashMap<>();
        map.put(0L, 1);
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += a[i] * v - u;
            if (map.containsKey(sum)) {
                ans += map.get(sum);
                map.put(sum, map.get(sum) + 1);
            } else {
                map.put(sum, 1);
            }
        }
        System.out.println(ans);
    }
}