今日头条2018.8.12笔试题总结

 今日头条笔试题1（经典的floodfill问题）：

具体可以参考leetcode 200题：Number of Islands

1. 一个球场C的球迷看台可容纳M*N个球迷。官方想统计一共有多少球迷群体，最大的球迷群体有多少人。

球迷选座特性：1.

1.同球迷群体会选择相邻座位，不同球迷群体选择不相邻的座位。（相邻包括前后相邻、左右相邻、斜对角相邻）；

2.给定一个M*N的二位球场，0代表该位置没人，1代表该位置有人，希望输出球队群体个数P,最大的球队群体人数Q。

输入：

第一行，2个数字，M  N，使用英文逗号隔开

接下来M行，每行N个数字，使用英文逗号隔开

输出：

一行 ，2数字，P   Q

package com.casm.test;

import java.util.Scanner;

/**
 * @author yangyang
 * 2018年8月14日上午10:26:36
 * 此题是2018年8.12 今日头条的笔试题第一题：该问题是经典的floodfill问题
 * 具体可以参考leetcode 200题：Number of Islands
 */

public class Main {
	//定义一个8*2的二维数组 记录八个方向
	static int[][] d=new int[][] {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
	//定义全局变量 记录临时的最大球迷数
	static int temp=0;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String[] mn=in.nextLine().split(",");
		int m=Integer.parseInt(mn[0]);
		int n=Integer.parseInt(mn[1]);
		//二维数组
		int[][] nums=new int[m][n];
		for(int i=0;i<m;i++)
		{
			String[] temp=in.nextLine().split(",");
			for(int j=0;j<n;j++)
			{
				nums[i][j]=Integer.parseInt(temp[j]);
			}
		}
		//标记位
		boolean[][] flag=new boolean[m][n];
		//定义res记录球迷群体数
		int res=0;
		//定义max记录最大球迷数
		int max=0;
		//遍历二维数组的每个点
		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++)
			{
				//如果当前点为1代表有球迷 且标记位为false代表没标记过
				if(nums[i][j]==1&&!flag[i][j])
				{
					//res和temp+1
					res++;
					temp++;
					//开始dfs深度优先遍历
					dfs(nums,i,j,flag);
				}
				//取最大值
				max=Math.max(max, temp);
				//初始化temp
				temp=0;
			}
		System.out.println(res+","+max);
	}

    //深度优先遍历dfs函数，dfs的本质是递归
	private static void dfs(int[][] nums, int x, int y, boolean[][] flag) {
		//首先标记为true
		flag[x][y]=true;
		//开始遍历8个方向
		for(int k=0;k<8;k++)
		{
			int newx=x+d[k][0];
			int newy=y+d[k][1];
			//同时满足三个条件：1.在边界内（注意这个条件必须放在前面 不然可能数组边界异常！）
			// 				   2.值为1，即是球迷
			//                 3.未被标记过
			if(isbound(newx,newy,nums)&&nums[newx][newy]==1&&flag[newx][newy]==false)
			{				
				temp++;
				//递归调用
				dfs(nums, newx, newy, flag);
			}
			
		}
	}

	//判断边界条件
	private static boolean isbound(int x, int y, int[][] nums) {
		
		return x>=0&&x<nums.length&&y>=0&&y<nums[0].length;
	}

}

今日头条笔试第二题：

考点：区间合并（关于区间合并问题请参考我的另一篇博客https://blog.csdn.net/ustcyy91/article/details/81669176）
 * 类似：参考leetcode56. Merge Intervals

合并区间关键在于寻找是否存在前一个区间的结束值大于后一个区间的开始值，若存在，则这两个区间就可以合并。理解这个并不难，但对数据的处理有一个小技巧，就是将所有区间的开始值和结束值都排好序，这样在合并区间的时候会更简单一些，这也是区间问题常用的套路，排序过后就是合并过程了，具体过程看代码吧。

package com.casm.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author yangyang
 *
 * 2018年8月14日下午1:54:39
 * 今日头条笔试题 第二题
 * 考点：区间合并
 * 类似：参考leetcode56. Merge Intervals
 */
public class MergeInteval {

	public static void main(String[] args) {
		ArrayList<Interval> list=new ArrayList<>();
		Scanner sc=new Scanner(System.in);
		int n=Integer.parseInt(sc.nextLine());
		for(int i=0;i<n;i++)
		{
			String[] temp=sc.nextLine().split(";");
			for(int j=0;j<temp.length;j++)
			{
				String[] temp2=temp[j].split(",");
				list.add(new Interval(Integer.parseInt(temp2[0]), Integer.parseInt(temp2[1])));
			}
		}
		int[] starts=new int[list.size()];
		int[] ends=new int[list.size()];
		for(int i=0;i<list.size();i++)
		{
			starts[i]=list.get(i).start;
			ends[i]=list.get(i).end;
		}
		list.clear();
		//区间合并的关键是 排序starts 和ends数组
		Arrays.sort(starts);
		Arrays.sort(ends);
		//区间合并的核心代码（必背）
		for(int i=0,j=0;i<starts.length;i++){
            if(i==starts.length-1||starts[i+1]>ends[i]){
                list.add(new Interval(starts[j],ends[i]));
                j=i+1;
            }
	}
		for(int i=0;i<list.size();i++) {
			System.out.print(list.get(i).start+","+list.get(i).end);
			System.out.print(";");
			}
		}
			

}

//自定义数据结构
class Interval{
	int start;
	int end;
	public Interval(int start, int end) {
		this.start = start;
		this.end = end;
	}	
}

第四题：

暴力搜索：时间复杂度O（N*N） 可以优化

package com.casm.test;

import java.util.Scanner;

public class JRTT3 {

	public static void main(String[] args) {
		int res=0;
		Scanner sc=new Scanner(System.in);
		int n=Integer.parseInt(sc.nextLine());
		int[] a=new int[n];
		int[] b=new int[n];
		String[] sa=sc.nextLine().split(" ");
		String[] sb=sc.nextLine().split(" ");
		for(int i=0;i<n;i++)
		{
			a[i]=Integer.parseInt(sa[i]);
			b[i]=Integer.parseInt(sb[i]);
		}
		for(int i=0;i<n;i++)
			for(int j=i;j<n;j++)
			{
				if(getMax(a,i,j)<getMin(b,i,j))
					res++;
			}
		System.out.println(res);
	}

	private static int getMin(int[] b, int i, int j) {
		int min=Integer.MAX_VALUE;
		for(int k=i;k<=j;k++)
		{
			min=Math.min(min, b[k]);
		}
		return min;
	}

	private static int getMax(int[] a, int i, int j) {
		int max=Integer.MIN_VALUE;
		for(int k=i;k<=j;k++)
		{
			max=Math.max(max, a[k]);
		}
		return max;
	}

}

第五题：