16. 日常算法

1. 最长回文串

题目原题
给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。
在构造过程中，请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。

示例 1:
输入:s = “abccccdd”
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> hash;
        int ret = 0;
        int num = 0;
        for (auto & c : s){
            hash[c]++;
        }
        std::cout << "cout: " << s.size() << std::endl;
        for (auto & [x, y] : hash){
            if (y % 2 == 0) ret += y;
            else ret += (y - 1);
        }
        return ret + 1 > s.size() ? ret : ret + 1;
    }
};

2.

题目原题

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量

class Solution {
public:
    // 方法：找出最长路径，中间节点作为根有最小高度
    // 1. 先用0作为根节点找出最远的节点，这个最远的节点一定是叶子节点（如果看成是一行的话一定是在两头）
    // 2. 然后用上一个节点再次做一次找最远的节点x此时皆可以找到最长的路径
    // 3. 判断路径长度是基数还是偶数
    int findParentPath(int root, vector<int> &parent, vector<vector<int>>& edges){
        vector<bool> exit(edges.size(), false);
        exit[root] = true;
        queue<int> q;
        q.push(root);
        int node = -1;

        while (!q.empty()){
            int u = q.front();
            q.pop();
            node = u;
            for (auto & v : edges[u]){
                if (!exit[v]){
                    q.push(v);
                    parent[v] = u;
                    exit[v] = true;
                }
            }
        }
        return node;
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0};
        vector<vector<int>> tree(n);
        for (auto & v : edges){
            tree[v[0]].emplace_back(v[1]);
            tree[v[1]].emplace_back(v[0]);
        }
        vector<int> parent(n, -1);
        int x = findParentPath(0, parent, tree);
        int y = findParentPath(x, parent, tree);
        parent[x] = -1;
        vector<int> path;
        while (y != -1){
            path.emplace_back(y);
            y = parent[y];
        }
        int m = path.size();
        if (m % 2 == 0){
            return {path[m/2 - 1], path[m/2]};
        }else{
            return {path[m/2]};
        }
    }
};