网易算法岗 4道大题题目-求第4个“01序列”解答

网易前3题答案

https://www.nowcoder.com/discuss/216249?type=1&order=0&pos=24&page=1

网易第1题

题目及答案

我的帖子：

https://www.nowcoder.com/discuss/216286?type=1&order=0&pos=27&page=1

网易第二题

小易有一个长度为n的数字数组a1，a2,….an

问你是否能用这n个数字构成一个环（首尾相连），使得环中的每一数字都小于它相邻的两个数字的和（每个数字都必须使用并且每个数字只能使用一次）

输入描述

第一行包含一个整数t (1<=t<=10)，表示测试用例的组数

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

第一行一个整数n，表示数字的个数；

第二行n个整数a1,a2,an,每两个整数之间用一个空格分隔。

输入数据保证

3<=n<=n^5

1<=ai<=10^9

输出描述

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

示例1：

输入：

1

5

17 6 17 11 17

输出

YES

示例2：

输入

1

3

1 2 4

输出

NO

网易第三题：

小易给你一个包含n个数字的数组a1，a2,….an。你可以对这个数组执行任意以下交换操作：

对于数组中的两个下标i,j（1<=I,j<=n）,如果ai+aj为奇数，就可以交换ai和aj

现在允许你使用操作次数不限，小易希望你能求出在所有通过若干次操作可以得到的数组中，字典序最小的一个是什么

输入描述：

第一行一个整数n，

第二行n个整数a1,a2,an,表示数组，每两个数字之间用一个空格分隔。

输入保证

1<=n<=10^5；1<=ai<=10^9；

输出描述：

n个整数，每两个整数之间用一个空格分隔，表示得到的字典序最小的数组

示例1：

输入

4

7 3 5 1

输出

7 3 5 1

示例2

输入

10

53941 38641 31525 75864 29026 12199 83522 58200 64784 80987

输出

12199 29026 31525 38641 53941 58200 64784 75864 80987 83522

第四题解答

https://www.nowcoder.com/discuss/216195?type=1&order=0&pos=48&page=1

网易第四题：目前还没有思路，求解答

给定01序列S，序列S是优秀的01序列，优秀的01序列定义如下：

1 如果序列S,T是优秀的，则序列S+T是优秀的，+被定义为按数学连接两个序列，即”010”+”110”=”010110”

2 如果序列S是优秀的，则序列rev(S)也是优秀的。rev(S) 被定义为按位翻转（0变1,1变0）序列S，并删去前导零。例如rev(” 1100101”)=“11010”

现在请你判断序列T是不是优秀的

输入描述

第一行数据组数T，表示有T组数据

每组数据的第一行是一个01序列，表示序列S。第二行是另一个01序列，表示序列T

1<=|S|,|T|<=1000,S,T不含前导零。

输出描述

对于每组数据，一行输出 YES或 NO，表示序列T是不是优秀的（大小写敏感）

示例

输入

1

1100

110011

输出

YES

示例2

输入

1

1000

100001111

输出

NO