9 1腾讯第二次后台笔试题 100 100 0 90 0

第一题好像是奇偶性的问题

import java.util.*;

/**
 * 100%
 * 分别统计两个数组的奇数偶数个数，然后交叉取最小值，相加得出结果
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] nArray = new int[n];
        int[] mArray = new int[m];
        for (int i = 0; i < n; i++) {
            nArray[i] = in.nextInt();
        }
        for (int i = 0; i < m; i++) {
            mArray[i] = in.nextInt();
        }

        Main main = new Main();
        int result = main.getResult(nArray, mArray);
        System.out.println(result);
    }

    private int getResult(int[] nArray, int[] mArray) {
        int adN = 0;
        int deN = 0;
        for (int value : nArray) {
            if (value % 2 == 0) {
                deN++;
            } else {
                adN++;
            }
        }

        int adM = 0;
        int deM = 0;
        for (int value : mArray) {
            if (value % 2 == 0) {
                deM++;
            } else {
                adM++;
            }
        }

        int result1 = Math.min(adN, deM);
        int result2 = Math.min(deN, adM);

        return result1 + result2;
    }
}

第二题用户排队满意度问题

import java.util.*;

/**
 * 100%
 * 满意度最低的那题
 * 将a(j - 1) + b(n - j) 拆开成value =（a - b)j - a + bn,j表示位置，将value最大的排在最前面，就可以得到结果
 * 用优先队列做贪心算法(a - b) * postion - a + b * n,postion表示位置
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        Queue<Person> queue = new PriorityQueue<>((i, j) -> (int) ((j.a - j.b) - (i.a - i.b)));
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            queue.offer(new Person(a, b));
        }

        long result = 0;
        int postion = 1;
        while (!queue.isEmpty()) {
            Person tmp = queue.poll();
            long qValue = (tmp.a - tmp.b) * postion - tmp.a + tmp.b * n;
            result += qValue;
            postion++;
        }

        System.out.println(result);
    }
}

class Person {
    long a;
    long b;

    public Person(long a, long b) {
        this.a = a;
        this.b = b;
    }
}

第四题期末考试状态最好时间段

import java.util.*;

/**
 * 期末考试状态最好的哪一题
 * 90% 不知为何最后10%的错误是什么
 * 用dp的思想，dp[i]表示i天是状态最差的那一天，然后找出i天连续的左边比i天大的下标用dl[i]存起来，
 * 再找出i天连续的右边比i天大的下标用dr[i]存起来,最后dp[i] = sum(Array(dl[i]) ~ Array(dr[i]) * Array(i),
 * 最后再找出max(dp[i])
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nArray = new int[n];
        for (int i = 0; i < n; i++) {
            nArray[i] = in.nextInt();
        }

        Main main = new Main();
        System.out.println(main.gerResult(nArray));
    }

    private long gerResult(int[] nArray) {
        long result = Long.MIN_VALUE;

        //模仿leecode 84. Largest Rectangle in Histogram的dp思想,暴力双for也可以，不过会超时
        int[] dl = new int[nArray.length];
        for (int i = 0; i < nArray.length; i++) {
            int index = i;
            while (index != 0 && nArray[i] < nArray[index - 1]) {
                index = dl[index - 1];
            }
            dl[i] = index;
        }

        //同上
        int[] dr = new int[nArray.length];
        for (int i = nArray.length - 1; i >= 0; i--) {
            int index = i;
            while (index != nArray.length - 1 && nArray[i] < nArray[index + 1]) {
                index = dr[index + 1];
            }
            dr[i] = index;
        }

        //这里做了先变动dp[i]因为只用一次，所以不创建数组了，直接用
        for (int i = 0; i < nArray.length; i++) {
            long tmpSum = 0;

            //TODO 这里的for可以优化出一个缓存，时间关系，所以没做
            for (int j = dl[i]; j <= dr[i]; j++) {
                tmpSum += nArray[j];
            }

            long tmpValue = tmpSum * nArray[i];
            if (tmpValue > result) {
                result = tmpValue;
            }
        }

        return result;
    }
}