[20180812] 今日头条笔试
今日头条AC了前两道,后面一个多小时一道没A出,但是第4题和第5题的测试用例都过了,结果case率0%,哎,凉凉了~~
我分享一下思路,静待大神解惑
1.第一题是一个连通域的问题,找出一个矩阵中有多少个连通域,最大的连通域包含多少个元素
直接dfs解决就可以了(并不会重复,因为检测到1后就设置为0)
java实现
public class TouTiaoqz01 { static int cout=0; public static void findQ(int i,int j,int[][]a){ if(i-1>=0&&a[i-1][j]==1){ cout++; a[i-1][j]=0; findQ(i-1,j,a); } if(i-1>=0&&j+1<a[0].length&&a[i-1][j+1]==1){ cout++; a[i-1][j+1]=0; findQ(i-1,j+1,a); } if(j+1<a[0].length&&a[i][j+1]==1){ cout++; a[i][j+1]=0; findQ(i,j+1,a); } if(i+1<a.length&&j+1<a[0].length&&a[i+1][j+1]==1){ cout++; a[i+1][j+1]=0; findQ(i+1,j+1,a); } if(i+1<a.length&&a[i+1][j]==1){ cout++; a[i+1][j]=0; findQ(i+1,j,a); } if(i+1<a.length&&j-1>=0&&a[i+1][j-1]==1){ cout++; a[i+1][j-1]=0; findQ(i+1,j-1,a); } if(j-1>=0&&a[i][j-1]==1){ cout++; a[i][j-1]=0; findQ(i,j-1,a); } if(i-1>=0&&j-1>=0&&a[i-1][j-1]==1){ cout++; a[i-1][j-1]=0; findQ(i-1,j-1,a); } } public static void findPQ(int[][]a){ List<Integer> res= new ArrayList<>(); for(int i=0;i<a.length;i++){ for(int j=0;j<a[0].length;j++){ if(a[i][j]==1){ cout=1; a[i][j]=0; findQ(i,j,a); System.out.println(i+","+j+","+cout); res.add(cout); } } } System.out.println(res.size()+","+ Collections.max(res)); } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int m,n; String temp; temp=scanner.nextLine(); String[] mn=temp.split(","); m=Integer.parseInt(mn[0]); n=Integer.parseInt(mn[1]); int a[][]=new int[m][n]; for(int i=0;i<m;i++){ temp=scanner.nextLine(); String[] str=temp.split(","); for(int j=0;j<n;j++){ a[i][j]=Integer.parseInt(str[j]); } } findPQ(a); } }
2. 第二道题是一个合并线段的问题
先对线段的头坐标排序,然后遍历一遍就可以了
python实现
def merge_tuple(tuple_list): tuple_list=sorted(tuple_list,key=lambda x:x[0]) res=[] i=0 while i<len(tuple_list): start_index=tuple_list[i][0] end_index=tuple_list[i][1] while i<len(tuple_list) and end_index>=tuple_list[i][0]: end_index=max(end_index,tuple_list[i][1]) i+=1 res.append((start_index,end_index)) print(';'.join(str(item[0])+','+str(item[1]) for item in res)) if __name__=='__main__': m=input() tuple_list=[] for i in range(int(m)): s=input() temp=s.split(';') for item in temp: index=item.split(',') tuple_list.append((int(index[0]),int(index[1]))) merge_tuple(tuple_list)
3. 从一个数组中找出两个不相交的子集,使得这两个子集的和相等,找出全部满足条件子集对
这是我对第3道题的理解,没想出来怎么解
4.找出两个数组的对应下标相等的子集a,b,并且满足max(a)<min(b)
这道题我的思路就是将问题分解为两部分,一部分为窗口长度(1层for循环),一部分为对指定窗口长度进行遍历,计算满足条件的个数(知道会超时,但是竟然case%=0%)
def find_num(a,b,i): res=0 for j in range(len(a)): if j+i<=len(a) and max(a[j:j+i])<min(b[j:j+i]): res+=1 return res def find_max(a,b): cout=0 for i in range(1,len(a)+1): cout+=find_num(a,b,i) return cout if __name__=='__main__': n=input() a_str=input() b_str=input() a=[int(i) for i in a_str.split(' ')] b=[int(i) for i in b_str.split(' ')] print(find_max(a,b))
5. 给出一些线段,从中选取尽量多的线段,并使得选取的线段不重叠
很明显用dp+for解决,测试案例也通过了,但是case%=0%
def find_max(st_list): st_list=sorted(st_list,key=lambda x:x[0]) dp=[] dp.append((0,-1)) for i in range(len(st_list)): temp=0 for j in range(i+1): end_index=st_list[i][1] if dp[j][1]<=st_list[i][0]: if temp<=dp[j][0]+1: temp = max(temp, dp[j][0] + 1) if temp==dp[j][0]+1 and dp[j][1]>0:end_index =min(dp[j][1],end_index) dp.append((temp,end_index)) print(dp[-1][0]) if __name__=='__main__': n=input() m=input() n,m = int(n),int(m) st=input() st=st.split(' ') st_list=[] for i in range(n): st_list.append((int(st[2*i]),int(st[2*i+1]))) find_max(st_list)#字节跳动##内推##笔试题目##题解#