今日头条研发岗笔试题
AC了3个 第四个交卷发现了一个bug 但是不知道对不对 请大佬们看看
T1:DFS搜联通快
import java.util.Scanner;
public class A {
int m,n;
int vis[][] = new int[1005][1005];
int mp[][] = new int[1005][1005];
int fx[][] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
int p = 0,q = 0,sum;
Scanner scanner;
void solve(){
scanner = new Scanner(System.in);
String s = scanner.nextLine();
String []ss = s.split(",");
n = Integer.parseInt(ss[0]);
m = Integer.parseInt(ss[1]);
for(int i=0;i<n;i++){
String str = scanner.nextLine();
String[]num = str.split(",");
for(int j=0;j<m;j++){
mp[i][j] = Integer.parseInt(num[j]);
}
}
// System.out.println(n+" "+m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mp[i][j]==1&&vis[i][j]==0){
sum = 0;
p++;
dfs(i,j);
q = Math.max(q,sum);
}
}
}
System.out.println(p+","+q);
}
void dfs(int h,int l){
sum++;
vis[h][l] = 1;
for(int i=0;i<8;i++){
int hh = fx[i][0]+h;
int ll = fx[i][1]+l;
if(check(hh,ll)){
dfs(hh,ll);
}
}
}
boolean check(int hh, int ll) {
if(hh>=0&&hh<n&&ll>=0&&ll<m&&mp[hh][ll]==1&&vis[hh][ll]==0){
return true;
}
return false;
}
public static void main(String[] args) {
new A().solve();
}
}
T2：把所有区间做个结构体排序 java写结构体排序写炸了，，浪费了好多时间
import java.util.*;
public class B {
class Node implements Comparable<Node>{
public long l;
public long r;
public Node(){
}
public Node(Long l, Long r) {
this.l = l;
this.r = r;
} @Override public int compareTo(Node o) {
if(o.l==this.l)return this.r<o.r?-1:1;
return this.l<o.l?-1:1;
}
}
ArrayList<Node> node = new ArrayList<>();
ArrayList<Node> ans = new ArrayList<>();
int n;
int m;
Scanner scanner = new Scanner(System.in);
void solve() {
m = scanner.nextInt();
n = 0;
while (m-- > 0) {
String str = scanner.next();
//System.out.println(str);
String[] str1 = str.split(";");
for (int i = 0; i < str1.length; i++) {
// System.out.println(str1[i]);
String[] s = str1[i].split(",");
node.add(new Node(Long.parseLong(s[0]), Long.parseLong(s[1])));
n++;
}
}
Collections.sort(node);
long l = node.get(0).l;
long r = node.get(0).r;
for(int i=0;i<node.size();i++){
if(node.get(i).l>r){
ans.add(new Node(l,r));
l = node.get(i).l;
r = node.get(i).r;
}else{
r = Math.max(r,node.get(i).r);
}
}
ans.add(new Node(l,r));
StringBuffer ss = new StringBuffer("");
for(int i=0;i<ans.size();i++){
ss.append(ans.get(i).l);
ss.append(",");
ss.append(ans.get(i).r);
if(i!=ans.size()-1){
ss.append(";");
}
}
System.out.println(ss.toString());
}
public static void main(String[] args) {
new B().solve();
}
}
T3： 感觉像背包，，但是有很多不好处理 ，哪位大佬能提供AC代码不？
T4： 没有AC 我的做法是记录a数组每个数左右比他小的连续的数的个数 记录b数组左右比他大的数的连续的个数 然后就是当ai是最大数 bi是最小数时算下区间个数
不知道对不对 因为代码提交的时候把bi写成ai了，，结束后才发现
没有AC的代码
#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005];
int al[100005],ar[100005];
int bl[100005],br[100005];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++)
{
scanf("%d",&b[i]);
}
al[0] = 0;
bl[0] = 0;
for(int i=1;i<n;i++)
{
if(a[i]>=a[i-1])al[i] = al[i-1]+1;
else al[i] = 0;
if(b[i]<=b[i-1])bl[i]= bl[i-1]+1;
else bl[i] = 0;
}
ar[n-1] = 0;
br[n-1] = 0;
for(int i=n-2;i>=0;i--)
{
if(a[i]>=a[i+1])ar[i] = ar[i+1]+1;
else ar[i] = 0;
if(b[i]<=b[i+1])br[i] = br[i+1]+1;
else br[i] = 0;
}
long long ans = 0;
for(int i=0;i<n;i++)
{
if(a[i]<b[i])
{
int l = min(al[i],bl[i]);
int r = min(ar[i],br[i]);
//cout<<l<<" "<<r<<endl;
ans+=(1ll+l+r+l*r*1ll);
}
}
cout<<ans<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct st
{
int l,r;
}s[100005];
bool cmp(st a, st b){
if(a.l==b.l){
return a.r<b.r;
}
return a.l<b.l;
}
int n,m;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++){
scanf("%d%d",&s[i].l,&s[i].r);
if(s[i].l>s[i].r)s[i].r+=m;
}
sort(s,s+n,cmp);
int ans = 0;
int l = 0,r = 0;
for(int i=0;i<n;i++){
if(s[i].r>m)continue;
if(s[i].l>=r){
ans++;
l = s[i].l,r = s[i].r;
}else{
if(s[i].r<r)r = s[i].r;
}
}
cout<<ans<<endl;
return 0;
}