笔试——3.31腾讯笔试

整体难度尚可，ac了三道半，第四题没什么时间了没怎么看。

第一题

#include<bits/stdc++.h>
using namespace std;

vector<vector<pair<int, int>>>arr;
vector<int>visited;
//res 1 white 0
int cnt = 0;

void dfs(int x)
{
    if (visited[x])return;
    visited[x] = 1;
    if (arr[x].size() == 0)
    {
        cnt++;
        return;
    }
    bool good = true;
    for (int i = 0; i < arr[x].size(); i++)
    {
        if (arr[x][i].second == 0)
        {
            good = false;
            break;
        }
        dfs(arr[x][i].first);
    }
    if (good)cnt++;
    //visited[x]=0;
}

int main()
{
    int n, m;
    cin >> n >> m;
    arr.resize(n + 1);
    visited.resize(n + 1, 0);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        char ch;
        cin >> u >> v >> ch;
        if (ch == 'R')
        {
            arr[u].emplace_back(v, 1);
            arr[v].emplace_back(u, 1);
        }
        else
        {
            arr[u].emplace_back(v, 0);
            arr[v].emplace_back(u, 0);
        }
    }
    for (int i = 1; i <= n; i++)
        dfs(i);
    cout << cnt;
}

第二题

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return bool布尔型vector
     */
    vector<bool> canSorted(vector<ListNode*>& lists) {
        // write code here
        vector<bool>res;
        for (int i = 0; i < lists.size(); i++)
        {
            bool tempres = true;
            ListNode* head = lists[i];
            int maxval = head->val;
            ListNode* cur = head, * nxt = cur->next;
            while (cur && cur->val >= maxval)
            {
                maxval = cur->val;
                cur = cur->next;
            }
            while (cur && cur->next)
            {
                if (cur->next->val<cur->val || cur->next->val>maxval)
                    tempres = false;
                cur = cur->next;
            }
            res.push_back(tempres);
        }
        return res;

    }
};

第三题

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

vector<int>fa;
vector<int>visited;
vector<vector<int>>arr;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    return fa[x];
}

void add(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
        fa[fx] = fy;
}

void dfs(int x)
{
    if (visited[x] == 1)return;
    visited[x] = 1;
    for (int i = 0; i < arr[x].size(); i++)
    {
        add(x, arr[x][i]);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    arr.resize(n + 1);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        arr[u].push_back(v);
        arr[v].push_back(u);
    }
    fa.resize(n + 1);
    visited.resize(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        dfs(i);
    }
    unordered_map<int, int>map;
    int fa1 = INT_MAX, fa2 = INT_MAX;
    for (int i = 1; i <= n; i++)
    {
        int father = find(i);
        if (map.find(father) == map.end())
        {
            map[father] = 1;
            if (fa1 == INT_MAX)fa1 = father;
            else if (fa2 == INT_MAX)fa2 = father;
        }
        else map[father]++;
    }
    if (map.size() > 2)cout << 0;
    else cout << map[fa1] * map[fa2];


}

第四题

第五题

#include<bits/stdc++.h>
#include<string>
#include<unordered_map>
using namespace std;

vector<vector<int>>arr;
vector<vector<int>>visited;
int dst[7] = { 1,2,3,4,2,3,1 };
int res = 0;


void dfs(int row, int col, int index)
{
    if (index == 6)
    {
        if (arr[row][col] == dst[index])
        {
            res++;
        }
        return;
    }
    if (arr[row][col] != dst[index] || arr[row][col] == -1)return;
    //visited[row][col] = 1;
    dfs(row - 1, col, index + 1);
    dfs(row + 1, col, index + 1);
    dfs(row, col - 1, index + 1);
    dfs(row, col + 1, index + 1);
    //visited[row][col] = 0;
}

int main()
{
    //tencent:1234231     t1 e2 n3 c4 e2 n3 t1
    int n, m;
    cin >> n >> m;
    arr.resize(n + 2);
    visited.resize(n + 2);
    for (int i = 0; i <= n + 1; i++)
    {
        arr[i].resize(m + 2, -1);
        visited[i].resize(m + 2, 0);
    }
    for (int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
        for (int j = 1; j <= m; j++)
        {
            if (str[j - 1] == 't')arr[i][j] = 1;
            else if (str[j - 1] == 'e')arr[i][j] = 2;
            else if (str[j - 1] == 'n')arr[i][j] = 3;
            else if (str[j - 1] == 'c')arr[i][j] = 4;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j++)
        {
            dfs(i, j, 0);
        }
    }
    cout << res;
}