19届今日头条笔试题（8-12）
2018-08-14 本文已影响0人
yelie
1、世界杯开幕式会在球场C举行，球场C的球迷看台可以容纳MN个球迷。在球场售票完成后，现官方想统计此次开幕式一共有多少个球队球迷群体，最大的球队球迷群体有多少人。
经调研发现，球迷群体在选座时有以下特性：
同球队的球迷群体会选择相邻座位，不同球队的球迷群体会选择不相邻的座位（注解：相邻包括前后相邻，左右相邻，斜对角相邻）
给定一个MN的二维球场，0代表该位置没有坐人，1代表该位置已有选择，希望输出球队群体个数P，最大的球队群体人数Q
输入描述：
第一行，2个数字，M及N，使用英文逗号分隔
接下来M行，每行N的数字，使用英文逗号分隔
输出描述：
一行，2个数字，P及Q，使用英文逗号分隔
其中P表示球队群体个数，Q表示最大的球队群体人数
例：输入
10，10
0,0,0,0,0,0,0,0,0,0
0,0,0,1,1,0,1,0,0,0
0,1,0,0,0,0,0,1,0,1
1,0,0,0,0,0,0,0,1,1
0,0,0,1,1,1,0,0,0,1
0,0,0,0,0,0,1,0,1,1
0,1,1,0,0,0,0,0,0,0
0,0,0,1,0,1,0,0,0,0
0,0,1,0,0,1,0,0,0,0
0,1,0,0,0,0,0,0,0,0
输出：6,8
很明显，这道题可以使用广度优先或深度优先搜索来解决，类似的题可以参考《剑指offer》上的“机器人的运动范围”（https://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8）一题。
import java.util.Scanner;
public class test1 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str = scan.nextLine();
String[] arr = str.split(",");
int row = Integer.parseInt(arr[0]);
int col = Integer.parseInt(arr[1]);
int[][] seat = new int[row][col];
for (int i = 0; i < row; i++){
str = scan.nextLine();
arr = str.split(",");
for (int j = 0; j < col; j++){
seat[i][j] = Integer.parseInt(arr[j]);
if (seat[i][j] != 0 || seat[i][j] != 1) // 防止输入除0或1之外的数字
return;
}
}
resolve(row, col, seat);
}
public static void resolve(int row, int col, int[][] seat) {
int count = 0;
int max = 0;
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (seat[i][j] == 0) continue;
int temp = connect(seat, i, j, row, col);
if (temp > max) max = temp;
count++;
}
}
System.out.println(count+","+max);
}
//深度优先搜索
public static int connect(int[][] seat, int i, int j, int row, int col){
if (i < 0 || i >= row || j <0 || j >= col) return 0;
if (seat[i][j] == 0) return 0;
seat[i][j] = 0;
return 1 + connect(seat, i, j+1, row, col) + connect(seat, i, j-1, row, col) +
connect(seat, i-1, j-1, row, col) + connect(seat, i-1, j+1, row, col) +
connect(seat, i-1, j, row, col) + connect(seat, i+1, j+1, row, col) +
connect(seat, i+1, j-1, row, col) + connect(seat, i+1, j, row, col);
}
}
2、为了提高文章质量，每一篇文章（假设全部都是英文）都会有m民编辑进行审核，每个编辑独立工作，会把觉得有问题的句子通过下表记录下来，比如[1,10]，1表示病句的第一个字符，10表示病句的最后一个字符。也就是从1到10着10个字符组成的句子，是有问题的。
现在需要把多名编辑有问题的句子合并起来，送个总编辑进行最终的审核。比如编辑A指出的病句是[1,10]，[32,45];编辑B指出的病句是[5,16]，[78,94]那么[1,10]和[5,16]是有交叉的，可以合并成[1,16][32,45][78,94]
输入描述：
编辑数量m，之后每行是每个编辑的标记的下表组合，第一个和最后一个下标用英文逗号分隔，每组下标之间用分号分隔
输出描述：
合并后的下标集合，第一个和最后一个下标用英文逗号分隔，每组下标之间用分号分隔。返回结果是从小到大递增排列
例：输入
3
1,10;32,45
78,94;5,16
80,100;200,220;16,32
输出： 1,45;78,100;200,220
这道题记得好像在LeetCode上做过。我定义了一个区间类，然后将区间类对象存入列表中，并定义一个比较器，将区间对象按照起始值进行排序，最后按顺序将重叠的区间对象合并为一个。
import java.util.*;
public class test2 {
// 自定义区间类
public static class Interval{
public int begin;
public int end;
public Interval(int begin, int end){
this.begin = begin;
this.end = end;
}
public String toString(){
return String.format(begin+"-"+end);
}
}
// 比较器
public static class MyComparator implements Comparator<Object>{
public int compare(Object o1,Object o2){
Interval s1 = (Interval) o1;
Interval s2 = (Interval) o2;
return s1.begin - s2.begin;
}
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int person = Integer.parseInt(scan.nextLine());
String str = null;
List<Interval> list = new ArrayList<Interval>();
for (int i = 0; i < person; i++){
str = scan.nextLine();
String[] arr = str.split(";");
for (int j = 0; j < arr.length; j++){
String[] temp = arr[j].split(",");
int begin = Integer.parseInt(temp[0]);
int end = Integer.parseInt(temp[1]);
Interval interval = new Interval(begin,end);
list.add(interval);
}
}
//必须要对list中的区间进行排序
Collections.sort(list,new MyComparator());
merge(list);
}
public static void merge(List<Interval> list){
List<Interval> result = new ArrayList<>();
Interval pre = null;
for (Interval item : list){
if (pre == null || item.begin > pre.end){
result.add(item);
pre = item;
}
else if (item.end > pre.end){
pre.end = item.end;
}
}
for (Interval item : result){
System.out.println(item.begin+","+item.end+";");
}
}
}
3、小a和小b玩一个游戏，有n张卡牌，每张上面有两个正整数x，y。取一张牌时，个人积分增加x，团队积分增加y。求小a，小b各取若干张牌，使得他们的个人积分相等，且团队积分最大。
输入描述：
第一行n
接下来n行，每行两个正整数x，y
输出描述：
一行一个整数
表示小a的积分和小b的积分相等时，团队积分的最大值
例：输入
4
3 1
2 2
1 4
1 4
输出：10
说明：当a抽取（2,2），b抽取（1,4），（1,4）时，两人个人积分都是2，团队积分最大，为10分
一开始上手我用的是暴力解法......写到一半的时候仔细想了想，这题不就是背包问题（https://www.nowcoder.com/questionTerminal/bf877f837467488692be703735db84e6）的变形嘛，用动态规划就可以了。
该题的转移方程为dp[i][j]=max(d[i-1][j],d[i-1][j-x[i-1]) + y[i-1], d[i-1][j+x[i-1]] + y[i-1])，其中dp[i][j]表示两人从前i张卡片中进行抽取，且个人积分差j时团队积分的最大值。
\\动态规划
import java.util.Scanner;
public class test3 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] key = new int[num];
int[] value = new int[num];
int max = 0;
for (int i = 0; i < num; i++) {
int inputKey = scan.nextInt();
int inputValue = scan.nextInt();
key[i] = inputKey;
value[i] = inputValue;
max = max>inputKey?max:inputKey;
}
int[][] result = dp(num, max, key, value);
System.out.print(result[num][0]);
}
public static int[][] dp(int num, int max, int[] key, int[] value){
int[][] result = new int[num+1][max+1];
for (int j = 0; j <= max; j++) result[0][j] = 0;
for (int i = 1; i <= num; i++){
for (int j = 0; j <= max; j++){
int temp1=0, temp2=0;
if (j-key[i-1]>=0) temp1 = result[i-1][j-key[i-1]] + value[i-1];
if (j+key[i-1]<=max) temp2 = result[i-1][j+key[i-1]] + value[i-1];
result[i][j] = Math.max(Math.max(result[i-1][j], temp1),temp2);
if (i == 1 && j == 0) result[i][j] = 0;
}
}
return result;
}
}
4、两个长度为n的序列a，b。问有多少个区间[l，r]满足max(a[l,r])<min(b[l,r])即a区间的最大值小于b区间的最小值数据范围：n<1e5，a(i),b(i)<1e9
输入描述：
第一行一个整数n
第二行n个数，第i个为a(i)
第三行n个数，第i个为b(i)
0<1<=r<n
输出描述：
一行一个整数，表示答案
例1：输入
3
3 2 1
3 3 3
输出： 3
对两个区间从左到右进行扫描，分别维护一个左端扫描起始位置和右端扫描结束位置以及a的最大值和b的最小值。期初两个标记都在I处，然后开始移动右端flag，每移动一个位置只需要将最大值和最小值和该位置的值做判断，直到该区间的a的最大值大于等于b的最小值时，左端flag向右移动一个位置，右端flag回到此时左端flag的位置，以此类推直到r处。
import java.util.Scanner;
public class test4 {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr1 = new int[num];
int[] arr2 = new int[num];
for (int i = 0; i < num; i++){
arr1[i] = scan.nextInt();
}
for (int i = 0; i < num; i++){
arr2[i] = scan.nextInt();
}
System.out.println(resolve(arr1, arr2, 0, 0, 0, 0));
}
public static int resolve(int[] arr1, int[] arr2, int start, int end, int maxIndex, int minIndex) {
if (start > end || end >= arr1.length) return 0;
int max = arr1[maxIndex]>arr1[end]?maxIndex:end;
int min = arr2[minIndex]<arr2[end]?minIndex:end;
if (arr1[max] >= arr2[min]) return resolve(arr1,arr2,start+1,start+1, start+1, start+1);
return 1+((end==arr1.length-1)?resolve(arr1,arr2,start+1,start+1, start+1, start+1):resolve(arr1,arr2,start,end+1,max,min));
}
}
5、小明在抖音里关注了N个主播，每个主播每天的开播时间是固定的，分别在S时刻开始开播，t时间结束。小明无法同时观看两个主播的直播。一天被分成了M个时间单位。请问小明每天最多能完整观看多少场直播？
输入描述：
第一行一个整数，代表N
第二行一个整数，代表M
第三行空格间隔的N*2个整数，代表s，t
输出描述：
一行一个整数，表示答案
例1：输入
3
10
0 3 3 7 7 0
输出：3
例2： 输入
3
10
0 5 2 7 6 9
输出：2
备注：数据范围1<=N<=10^5
2<=M<=10^6
0<=s(i),t(i)<M (s(i)!=t(i))
s(i)>t(i)代表时间跨天，但直播时长不会超过一天
又是一个和时间区间有关的题，因此我的想法是维护所关注主播个数（n）个列表，同样自定义一个区内类，先将各个主播的区间对象存入一个临时列表，按照开播时间进行排序。然后从小到大取出区间对象，从n个列表中的第一个开始，仅存入第一个不为空的列表以及此前列表中与该区间对象不冲突的列表中（列表中的区间对象的结束时间都小于等于该区间对象的起始时间），最后n个列表中对象最多的个数即为所求。
import java.util.*;
public class test5 {
// 自定义区间类
public static class Interval{
public int begin;
public int end;
public Interval(int begin, int end){
this.begin = begin;
this.end = end;
}
public String toString(){
return String.format(begin+"-"+end);
}
}
public static class MyComparator implements Comparator<Object> {
public int compare(Object o1,Object o2){
Interval s1 = (Interval) o1;
Interval s2 = (Interval) o2;
return s1.begin - s2.begin;
}
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int over = scan.nextInt();
List<Interval> list = new ArrayList<>();
for (int i = 0; i < num; i++){
int start = scan.nextInt();
int end = scan.nextInt();
list.add(new Interval(start,end));
}
Collections.sort(list,new MyComparator());
List<Interval>[] arr = (ArrayList<Interval>[])new ArrayList[num];
for (int i = 0; i < num; i++){
arr[i] = new ArrayList<>();
}
for (Interval item : list){
for (int j = 0; j < num; j++){
if (arr[0].isEmpty()){
arr[0].add(item);
break;
}
if (arr[j].isEmpty()){
break;
}
else if (arr[j].get(arr[j].size()-1).end > item.begin){
continue;
}
else {
arr[j].add(item);
continue;
}
}
}
int max = 0;
for (List<Interval> item : arr){
max = max>item.size()?max:item.size();
}
System.out.println(max);
}
}
