[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)#字节跳动##内推##笔试题目##题解#
