9.12 网易笔试 - 移动端共 4 题，过了 3 题

# 第一题：大意是给一棵树，输出有几个节点满足恰好有两个子节点

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

const int N = 110, M = 110;

int n, m;
int h[N], e[M], ne[M], idx;
int son_cnt[N];
bool is_leaf[N];
bool din[N];
int root, res;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u) {
    if (son_cnt[u] == 0) return;
    else if (son_cnt[u] == 1) {
        int son = e[h[u]];
        if (is_leaf[son]) return;
        else dfs(son);
    } else if (son_cnt[u] == 2) {
        int left = e[h[u]];
        int right = e[ne[h[u]]];

        if (is_leaf[left] && is_leaf[right]) {
            ++ res;
            return;
        }
        if (!is_leaf[left]) dfs(left);
        if (!is_leaf[right]) dfs(right);
    }

}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < N; ++ i) is_leaf[i] = true;

    while (m -- ) {
        int a, b;
        char left_right[10];
        scanf("%d%s%d", &a, left_right, &b);
        add(a, b);
        is_leaf[a] = false;
        din[b] = true;
        ++ son_cnt[a] ;
    }

    for (int i = 1; i <= n; ++ i) {
        if (!din[i]) {
            root = i; break;
        }
    }

    dfs(root);

    printf("%d\n", res);
}

# 第二题：求回文子串的个数

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

const int N = 1e5 + 10;

int res;
char a[N];
bool f[N][N];

int main() {
    scanf("%s", a);
    int Len = strlen(a);
    for (int i = 0; i < Len; ++ i) f[i][i] = true;

    for (int len = 2; len <= Len; ++ len) {
        for (int i = 0; i <= Len - 1 - len + 1; ++ i) {
            if (len == 2 && a[i] == a[i + 1]) {
                ++ res ;
                f[i][i + 1] = true;
            } else if (a[i] == a[i + len - 1] && f[i + 1][i + len - 2]) {
                ++ res ;
                f[i][i + len - 1] = true;
            }
        }
    }
    printf("%d\n", res);
}

# 第三题：求包含偶数个'a', 'b', 'c', 'x', 'y', 'z' 的最长字串

LeetCode 中好像有，忘记怎么做了，0 分

# 第四题：在一个数组中，求满足相加后可以被 7 整除的最大和

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

const int N = 1e5 + 10;

int n;
int a[N];

unordered_map<int, int> dfs(int left, int right) {
    unordered_map<int, int> um;
    if (left == right) {
        um[a[left] % 7] = a[left];
        return um;
    }
    int mid = left + right >> 1;
    auto um1 = dfs(left, mid);
    auto um2 = dfs(mid + 1, right);
    for (auto t1 : um1) um[t1.first] = max(um[t1.first], t1.second);
    for (auto t2 : um2) um[t2.first] = max(um[t2.first], t2.second);

    for (auto t1 : um1) {
        for (auto t2 : um2) {
            if (!um.count((t1.first + t2.first) % 7)) {
                um[(t1.first + t2.first) % 7] = t1.second + t2.second;
            } else {
                um[(t1.first + t2.first) % 7] = max(um[(t1.first + t2.first) % 7], t1.second + t2.second);
            }
        }
    }
    
     
    // 卧槽..第二天看面经的时候
    // 发现笔试时这里忘记返回 um 了，是怎么 AC 的...
    // 是不是 C++ 没有指定返回值，会默认返回唯一可能的数据？
    return um;
}

int main() {
    while (scanf("%d", a + n) != EOF) ++ n ;
    int res = dfs(0, n - 1)[0];
    if (res == 0) res = -1;
    printf("%d\n", res);
}

#网易笔试##笔经##C/C++##网易#