蚂蚁笔试,比较简单(0319春招实习笔试真题解析)

2
5
1 2 3 4 5
4
2 2 1 1

4
2

##思路 数组和为偶数的本质是奇数的个数为偶数。每次操作后都要满足这个条件。 对一个数做 ±1：代价是 1 次操作，会改变它的奇偶性。 删除一个元素：代价是 1 次操作，会直接移除它（同时改变奇数计数）。 我们希望尽可能多操作，所以要尽量少用高代价的方式。 初始时统计数组中奇数的个数 cnt_odd： 如果 cnt_odd 是偶数：可以直接开始删除元素，最多删 n 次（但要保证每次删完后奇数个数仍为偶数）。 如果 cnt_odd 是奇数：必须先做 1 次 ±1 操作，把某个奇数变成偶数（让 cnt_odd 变为偶数），之后再开始删除元素。 之后每次删除只能删偶数元素（否则奇数个数会再次变成奇数，不满足条件），直到没有偶数可删为止。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
         int t = scanner.nextInt();
for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
             int cntOdd = 0, cntEven = 0;
for (int j = 0; j < n; j++) {
                int num = scanner.nextInt();
if (num % 2 == 1) {
                     cntOdd++; 
                } else {
                     cntEven++; 
                 }            
 }
            int res = 0;
if (cntOdd % 2 == 1) {
                res += 1;
                 cntOdd--;
                cntEven++;
            }
             res += cntEven;
            System.out.println(res);
         }
     }
 }

这里没有三角形

在线做题链接：https://niumacode.com/

题目描述

应企业要求，本场考试编程题禁止离开页面，不支持本地IDE，请使用考试系统提供的在线自测进行调试，调试后务必点击“保存并提交”按钮提交代码。

给定一个正整数  ()，表示需要构造的数组长度；构造一个长度为  的数组 ，使其满足以下条件：

• ；
• 任意选择三个不同下标 ，设相应的数组元素按非降序排列为 ，则有 ，即无法组成三角形。

输入描述

在一行上输入一个整数  ()，表示数组长度。

输出描述

若存在满足条件的数组，则输出一行  个整数 ；否则，输出 。 如果在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例 1

输入

3

输出

1 2 4

思路与代码

对于给定的 n，我们需要构造一个长度为 n 的数组，使得任意三个不同下标对应的数，按非降序排列后满足 x + y 小于等于 z，即无法构成三角形。这样的数组必须满足递增序列中每一项不小于前两项之和，且为尽可能长的序列，应取斐波那契数列（从 1, 1 开始）。计算可知，在 10^9 范围内最多能构造 44 项。因此，当 n 小于 44 时，输出斐波那契数列的前 n 项；否则输出 -1。

import java.util.Scanner;
public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();

if (n > 44) {
            System.out.println(-1);
         } else {
            long[] a = new long[n];
             a[0] = 1;
if (n > 1) {
                a[1] = 1;
            }
for (int i = 2; i < n; i++) {
                a[i] = a[i - 1] + a[i - 2];
            }
for (int i = 0; i < n; i++) {
                System.out.print(a[i]);
if (i < n - 1) {
                    System.out.print(" ");
                 }
             }
           System.out.println();
         }
     }
}

第三题

在线做题链接：https://niumacode.com/

题目描述

给定一个长度为  的数组 。你可以进行如下操作至多一次（也可以不进行任何操作）：

• 选择一个下标  和任意整数 ，将区间  中的每个元素减少 ，同时将区间  中的每个元素增加 。

请你最小化操作结束后数组中的逆序对个数，并输出这个最小值。

【名词解释】 逆序对：在序列中，若存在两个下标  满足  且 ，则称  为一个逆序对。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数  () 表示数据组数，每组测试数据描述如下：

• 第一行输入一个整数  () 表示数组长度；
• 第二行输入  个整数  () 表示数组 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述

对于每一组测试数据，新起一行，输出一个整数，表示最小的逆序对个数。

示例 1

输入

2
5
2 1 5 3 4
4
4 3 2 1

输出

1
2

说明

样例解释：

* 对于第一组数据，选择 $i = 3$，以及一个整数 $1$。数组变为 $\{1, 0, 4, 4, 5\}$ 此时逆序对仅有 $(1, 2)$ 可以证明没有其他操作可以使逆序对更小。

思路与代码

我们可以通过一次操作将数组分为前后两段，分别减去和加上同一个数 x，从而只改变跨过分割点的逆序对，而不改变段内的逆序对。取 x 足够大可以使所有左边元素小于右边元素，跨段逆序对变为 0，此时总逆序对等于前缀内部和后缀内部逆序对之和。因此，问题转化为求所有可能分割点 i 下，前缀 [1,i] 的逆序对个数与后缀 [i+1,n] 的逆序对个数之和的最小值。使用树状数组预处理前缀和后缀逆序对即可，时间复杂度 O(nlogn)，满足题目要求。

import java.util.*;

public class Main {
    static class BIT {
        int n;
        int[] bit;

        BIT(int n) {
            this.n = n;
            bit = new int[n + 2];
        }

        void add(int i, int v) {
while (i <= n) {
                bit[i] += v;
                i += i & -i;
            }
        }

        int sum(int i) {
            int s = 0;
while (i > 0) {
                s += bit[i];
                i -= i & -i;
            }
return s;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
while (t-- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }

if (n == 1) {
                System.out.println(0);
continue;
            }


            BIT bit = new BIT(n);
            long[] pre = new long[n + 1];
for (int i = 1; i <= n; i++) {
                int val = a[i - 1];
                pre[i] = pre[i - 1] + (bit.sum(n) - bit.sum(val));
                bit.add(val, 1);
            }


            bit = new BIT(n);
            long[] suf = new long[n + 2];
for (int i = n; i >= 1; i--) {
                int val = a[i - 1];
                suf[i] = suf[i + 1] + bit.sum(val - 1);
                bit.add(val, 1);
            }


            long ans = Long.MAX_VALUE;
for (int i = 1; i < n; i++) {
                ans = Math.min(ans, pre[i] + suf[i + 1]);
            }
            System.out.println(ans);
        }

    }
}

我们是一个针对技术岗（前后端开发、测试、测开、大数据开发、大模型、ai等相关岗位）校招一对一进阶提高的工作室。我们从2020年2月份开始，迄今整整六年的时间，带领900+学员斩获4000+中大厂offer，参加活动的同学人均5个中大厂offer以上，以下是我们活动内容的介绍！

万诺coding

我们主要是针对有一定基础的同学提供全程一对一笔试、面试辅导，针对每个同学不同的情况定制内容，包括但不限于“笔试及面试算法”/“基础八股/“项目及实习梳理”/“面试技巧”/“面试复盘”等内容。

摸底测试：如果有兴趣深入了解我们的活动，需要先参加我们的“摸底测试”（类似面试），方便我们了解你的具体情况（主要是code能力和计算机素养），定制出相应的辅导计划。摸底测试后，我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。 

承诺保offer：通过摸底测试后，我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。

有兴趣的同学可以扫码添加我们的微信（whynotlab）