腾讯实习生后台开发笔试——03.31

题目

给定2小时5道题，晚上8点到10点。

给定无向图，边为是红色或白色，若一个点的全部边都是红色的，才是“好点”，问“好点”的个数
给定一个链表数组，每个链表是否可以通过一次“切断”并“重组”操作变为有序的。

这里的切断是指将当前链表分为两半；这里重组是将分开的链表重新组合。如：[2,3,1] $\stackrel{切断}{\rightarrow}$ [2,3]，[1] $\stackrel{重组}{\rightarrow}$ [1,2,3]，此时链表就有序了。
给定字符矩阵，在其中搜索特定的字符串序列（以任意一点为起点，然后通过上下左右连续的移动构成）。这个字符串序列是"tencent"，问构成该字符串的方案个数。
给定无向图，有多少种方案能通过一次加边使其完全连通？
给定n个数字的序列（ $n <= 400$ ），将其分为k段，每一段的数字全部异或，各个段的异或相加之和为最终值，问分为k段后最终值可能的取值的最大数

题解

因为可以开idea，这里直接看的idea的历史记录拿的源代码，可能写的比较丑陋。狠狠地网瘾。

在加边的时候，一旦有白色的边，这两个点就都不是好点

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt(), m = in.nextInt();
        boolean[] st = new boolean[n + 1];
        for (int i = 1; i <= n; ++i) st[i] = true;

        while ((m--) != 0) {
            int u = in.nextInt(), v = in.nextInt();
            String s = in.next();
            if (s.equals("W")) {
                st[u] = st[v] = false;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) ans += (st[i] ? 1 : 0);
        System.out.println(ans);
    }
}

暴力跑一遍，若升序则为一段，否则新开一段。若段数超过2则无解，若剩下两段无法合并则也无解

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public boolean[] canSorted(ListNode[] lists) {
        int n = lists.length;
        boolean[] ans = new boolean[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = true;
            ListNode head = lists[i];
            int cnt = 1, l = head.val, r = head.val, tl = -1, tr = -1;

            while (head != null) {
                if (cnt == 1) {
                    if (r <= head.val) {
                        r = head.val;
                    } else {
                        ++cnt;
                        tl = head.val;
                        tr = head.val;
                    }
                } else {
                    if (tr <= head.val) {
                        tr = head.val;
                    } else {
                        ans[i] = false;
                        break;
                    }
                }
                head = head.next;
            }

            if (cnt == 2 && !(r <= tl || tr <= l)) ans[i] = false;
        }
        return ans;
    }
}

dfs

import java.util.Scanner;

public class Main {
    static int n, m, sh;
    static String[] g;
    static String ans = "tencent";

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        g = new String[n];
        sh = 0;

        for (int i = 0; i < n; ++i) g[i] = in.next();

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= m; ++j) {
                dfs(i, j, 0);
            }
        }
        System.out.println(sh);
    }

    public static int[] nx = {0, 1, 0, -1}, ny = {1, 0, -1, 0};

    public static void dfs(int x, int y, int idx) {
        if (x < 0 || x >= n || 0 < y || y >= m) return;
        if (ans.charAt(idx) != g[x].charAt(y)) return;
        if (idx == 6) {
            ++sh;
            return;
        }

        for (int i = 0; i < 4; ++i) {
            int tx = x + nx[i], ty = y + ny[i];
            dfs(tx, ty, idx + 1);
        }
    }
}

并查集维护连通块大小，若最终连通块个数大于2无解，若连通块个数等于2则分别取一点计算方案，若连通块个数等于1则方案个数为 $C_n^2$

腾讯实习生后台开发笔试——03.31

题目

题解

全站热榜