腾讯笔试简单题解

第一题，通过找到每个点的连通是否都红，直接与运算

n,m = (int(i) for i in input().split(" "))
dic = {}
for i in range(m):
    f,t,c = (i for i in input().split(" "))
    f = int(f)
    t = int(t)
    if dic.get(f) is None: dic[f] = c=="R"
    else: dic[f] = dic[f] and c=="R"
    if dic.get(t) is None: dic[t] = c=="R"
    else: dic[t] = dic[t] and c=="R"


res = 0
for i in range(1,n+1):
    if dic.get(i) is None or dic.get(i):
        res+=1
print(res)

第二题，找有几个降序节点，超过两个返回false，不知道为什么只过了90？？？

public boolean[] canSorted (ListNode[] lists) {
	boolean[] res = new boolean[lists.length];
	Arrays.fill(res,true);
	for(int i= 0;i<lists.length;i++){
	  ListNode n = lists[i];
	  int pre=0;
	  while(n.next!=null){
		if(n.next.val<n.val){
		  pre++;
		  if(pre>=2){
			res[i] = false;
			break;
		  }
		}
		n = n.next;
	  }
	}
	return res;
}

第三题：并查集变形，记录顶级父节点拥有子节点数

class Main {
    public static void main(String[] args) {
        class Tu{
            int[][] fa;
            int cnt;
            public Tu(int n){
                this.fa = new int[n+1][2];
                for(int i=1;i<=n;i++){
                    this.fa[i][0] = i;
                    this.fa[i][1] = 1;
                }
                this.cnt = n;
            }

            public boolean isc(int f,int t){
                return this.find(f)==this.find(t);
            }

            public int find(int f){
                if(this.fa[f][0]==f){
                    return f;
                }
                int ff = find(this.fa[f][0]);
                this.fa[f][0] = ff;
                return ff;
            }
            public void ins(int f,int t){
                int ff = this.find(f);
                this.fa[t][0] = ff;
                this.fa[ff][1]++;
                this.fa[t][1] = 0;
                this.cnt--;
            }
        }

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m= in.nextInt();
        Tu tu = new Tu(n);
        for(int i=0;i<m;i++){
            int f= in.nextInt(),t= in.nextInt();
            if(!tu.isc(f,t)){
                tu.ins(f,t);
            }
        }
        int res = 1;
        if(tu.cnt>2){
            System.out.println(0);
        }else{
            for(int[] t: tu.fa){
                res*=t[1]>0?t[1]:1;
            }
            System.out.println(res);
        }
    }
}

第四题：爆搜直接超时，就不贴了

第五题：不带回溯的爆搜

class Main {
    public static char[] tt = "tencent".toCharArray();
    public static int res;
    public static int[][] mv = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        res = 0;
        int n = in.nextInt();
        int m = in.nextInt();
        char[][] ch = new char[n][m];
        in.nextLine();
        List<int[]> lst = new ArrayList<>();
        for(int i=0;i<n;i++){
            ch[i] = in.nextLine().toCharArray();
            for(int j = 0;j<m;j++){
                if(ch[i][j]=='t'){
                    lst.add(new int[]{i,j});
                }
            }
        }
        for(int[] start: lst){
            dfs(ch,start[0],start[1],0);
        }
        System.out.println(res);
    }

    public static void dfs(char[][] ch,int x,int y,int ind){
        if(ind==6){
            if(tt[ind]==ch[x][y]){
                res++;
            }
            return;
        }
        if(ch[x][y]!=tt[ind]){
            return;
        }
        for(int[] m:mv){
            int xx = x+m[0],yy = y+m[1];
            if(xx>=0 && xx<ch.length && yy>=0
                    && yy<ch[0].length){
                dfs(ch,xx,yy,ind+1);
            }
        }
    }
}