【阿里淘天笔试题汇总】2024-04-03-阿里淘天春招笔试题(第一套)-三语言题解(CPP/Python/Java)

🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新淘天近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

文章目录

• • 01.数组的最大权值
  • • 题目描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 数据范围
    • 题解
    • 参考代码
    • 02.卢小姐的城市之旅
    • • 题目描述
      • 输入格式
      • 输出格式
      • 样例输入
      • 样例输出
      • 样例解释
      • 数据范围
      • 题解
      • 参考代码
      • 03.卢小姐的元素调整之旅
      • • 问题描述
        • 输入格式
        • 输出格式
        • 样例输入
        • 样例输出
        • 数据范围
        • 题解
        • 参考代码
        • 写在最后
        • 📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

          01.数组的最大权值

          题目描述

          K小姐有一个长度为 n n n 的数组 a a a，她定义一个数组的权值为数组中不同数字的个数。

          现在，K小姐想从数组 a a a 中选出 k k k 个数字，使得这 k k k 个数字组成的新数组的权值最大。你能帮助K小姐找出最大的权值吗？

          输入格式

          第一行包含两个正整数 n n n 和 k k k（ 1 ≤ k ≤ n ≤ 1 0 5 1 \le k \le n \le 10^5 1≤k≤n≤105），表示数组 a a a 的长度和需要选择的数字个数。

          第二行包含 n n n 个正整数 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1​,a2​,…,an​（ 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai​≤109），表示数组 a a a 的元素。

          输出格式

          输出一个正整数，表示选出 k k k 个数字组成新数组的最大权值。

          样例输入

          4 3
          1 1 2 2
          

          样例输出

          2
          

          数据范围

          • 1 ≤ k ≤ n ≤ 1 0 5 1 \le k \le n \le 10^5 1≤k≤n≤105
          • 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai​≤109

            题解

            这个问题可以用贪心的思想来解决。为了使选出的 k k k 个数字组成的新数组的权值最大，我们需要尽可能选择不同的数字。

            我们可以先把原数组 a a a 中的所有数字放入一个集合中，这样就可以去掉重复的数字。然后，我们比较集合的大小和 k k k 的大小：

            • 如果集合的大小大于等于 k k k，那么我们可以直接从集合中选出 k k k 个不同的数字，此时新数组的权值就等于 k k k。
            • 如果集合的大小小于 k k k，那么我们只能选出集合中的所有数字，此时新数组的权值就等于集合的大小。

              所以，最大权值就是 k k k 和集合大小的较小值。

              时间复杂度： O ( n ) O(n) O(n)，需要遍历一次数组来建立集合。

              空间复杂度： O ( n ) O(n) O(n)，需要一个集合来存储不同的数字。

              参考代码

              • Python

                import sys
                def main():
                    n, k = map(int, sys.stdin.readline().split())
                    nums = set(map(int, sys.stdin.readline().split()))
                    print(min(len(nums), k))
                if __name__ == "__main__":
                    main()
                

                • Java

                  import java.io.*;
                  import java.util.*;
                  public class Main {
                      public static void main(String[] args) throws IOException {
                          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                          String[] nk = br.readLine().split(" ");
                          int n = Integer.parseInt(nk[0]);
                          int k = Integer.parseInt(nk[1]);
                          String[] numsStr = br.readLine().split(" ");
                          Set nums = new HashSet();
                          for (String num : numsStr) {
                              nums.add(Integer.parseInt(num));
                          }
                          System.out.println(Math.min(nums.size(), k));
                      }
                  }
                  

                  • Cpp

                    #include 
                    #include 
                    using namespace std;
                    int main() {
                        int n, k;
                        cin >> n >> k;
                        unordered_set nums;
                        for (int i = 0; i > num;
                            nums.insert(num);
                        }
                        cout 
                        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;
                        vector a(n);
                        for (int i = 0; i > a[i];
                        }
                        priority_queue pq;
                        for (int i = 0; i  a[i];
                        }
                        for (int i = 0; i > b[i];
                        }
                        sort(b.begin(), b.end());
                        vector dp(n + 1, vector(m + 1, INF));
                        for (int j = 0; j 
                            dp[0][j] = 0;
                        }
                        for (int i = 1; i 
                       		int temp = dp[i - 1][0];
                            for (int j = 1; j 
                            	temp = min(temp, dp[i - 1][j]);
                                int val = abs(a[i - 1] - b[j - 1]);
                                dp[i][j] = min(dp[i - 1][j], temp) + val;
                            }
                        }
                        int ans = *min_element(dp[n].begin(), dp[n].end());
                        cout