Halo

A magic place for coding

0%

网易面试算法题分享

Intro

  碰巧帮一个朋友看了一道网易今年的校招面试算法题,觉得挺有意思的,这里分享一下自己的做法,如果觉得有问题的欢迎指出!


Problem

  小易有一个长度为$n$的数字数组$a_1, a_2, \cdots, a_n$,问:是否能用这$n$个数字构成一个环(首尾相连),使得环中的每一个数字都小于它相邻的两个数字的和(每个数字都必须使用并且每个数字只能使用一次)

输入描述

第一行包含一个整数$t(1 \le t \le 10)$,表示测试用例的组数

每个测试用例的输入如下:

第一行一个整数$n$,表示数字的个数;

第二行$n$个整数$a_1, a_2, \cdots, a_n$,每两个整数之间用一个空格分隔。

输入数据保证

$3 \le n \le 10^5$

$1 \le a_i \le 10^9$

输出描述

输出应该包含$t$行,对于每组用例,若能输出“YES“,否则输出”NO“。

Example1:

1
2
3
4
5
6
7
Input:
1
5
17 6 17 11 17

Output:
YES

Example2:

1
2
3
4
5
6
7
Input:
1
3
1 2 4

Output:
NO

Analyze

  这是一道有关于数组的题目,针对的是数字类型的数据。首先这道题目问的是一个是或不是的答案,并不是要我们输出所有可能的结果,一般这类题目并不需要我们把所有的情况都列举出来,所以穷举的方法大概率会超时。

  确认好方向后,我们就来根据题目的要求进行思考。这道题目的要求就是,每个元素的左右两边元素之和比它本身大。这个要求一眼看上去很复杂,因为可能性有很多。我们不妨先换个思路,先看看题目给出来的case的特点。我们把case1的数字构成一个环,会发现顺序是6->11->17->17->17。当然这个顺序是一个环,但是如果你从最小的元素开始看,就会发现者实际上是一个递增的有序数组

  这个有序是一个切入点,因为如果这个条件是可以基于有序来判断的,那么我们的工作就变得非常简单。对于一个有序递增数组的某一个元素$a_i$,它的后一个元素$a_{i+1}$肯定比它大,因此$a_{i+1} + a_{i-1} \gt a_i$必然成立。而题目要求的是一个环,所以说在有序数组的基础上,我们只需要判断数组的首尾能否构成这个环就可以了。因为数组的最后一个元素$a_n$是整个数组中最大的元素,$a_{n-1} + a_1$很有可能比它小,所以我们只需要判断$a_{n-1}+a_1$和$a_n$的关系即可,如果满足题目要求则输出YES,否则输出NO。


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
vector<int> arr;
int caseNum;
cin >> caseNum;

while (caseNum--) {
int n;
cin >> n;
int temp;
for (int i = 0; i < n; i++) {
cin >> temp;
arr.push_back(temp);
}

sort(arr.begin(), arr.end());

if (arr[0] + arr[n - 2] > arr[n - 1]) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
}

Summary

  要在面试时快速地解题不但需要很强的coding能力,而且还需要对不同题型的题目有一定的敏锐程度。以这题为例,敏锐程度体现在,对于数组类型的题目,我们优先考虑排序的做法。又比如说其他的一些求最小值最大值的题目,我们是可以优先考虑贪心算法的。本道题的分析到这里,希望能帮助到大家,谢谢!

Welcome to my other publishing channels