leetcode解题思路分析（一百五十七）1366 - 1372 题

1366. 通过投票对团队排名
      现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。
      排名规则如下：
      参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
      如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。
      给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。
      请你返回能表示按排名系统 排序后 的所有团队排名的字符串。

哈希表存储映射，然后挨个比较就完事。

class Solution {
public:string rankTeams(vector<string>& votes) {int n = votes.size();// 初始化哈希映射unordered_map<char, vector<int>> ranking;for (char vid: votes[0]) {ranking[vid].resize(votes[0].size());}// 遍历统计for (const string& vote: votes) {for (int i = 0; i < vote.size(); ++i) {++ranking[vote[i]][i];}}// 取出所有的键值对using PCV = pair<char, vector<int>>;vector<PCV> result(ranking.begin(), ranking.end());// 排序sort(result.begin(), result.end(), [](const PCV& l, const PCV& r) {return l.second > r.second || (l.second == r.second && l.first < r.first);});string ans;for (auto& [vid, rank]: result) {ans += vid;}return ans;}
};

1367. 二叉树中的链表
      给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

递归每个树节点为链表起点，然后递归查找链表是否有相匹配的树路径即可。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSubPath(ListNode* head, TreeNode* root) {if (!head) return true;if (!root) return false;return check_node(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);}bool check_node(ListNode* list_node, TreeNode* tree_node){if (!list_node)return true;if (!tree_node)return false;if (list_node->val == tree_node->val) return check_node(list_node->next, tree_node->left) || check_node(list_node->next, tree_node->right);else return false;}
};

1368. 使网格图至少有一条有效路径的最小代价
      给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
      1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
      2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
      3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
      4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
      注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。
      一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。
      你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。
      请你返回让网格图至少有一条有效路径的最小代价。

0-1BFS问题模板题，详细的算法解释在这里。

using PII = pair<int, int>;class Solution {
private:static constexpr int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};public:int minCost(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();vector<int> dist(m * n, INT_MAX);vector<int> seen(m * n, 0);dist[0] = 0;deque<int> q;q.push_back(0);while (!q.empty()) {auto cur_pos = q.front();q.pop_front();if (seen[cur_pos]) {continue;}seen[cur_pos] = 1;int x = cur_pos / n;int y = cur_pos % n;for (int i = 0; i < 4; ++i) {int nx = x + dirs[i][0];int ny = y + dirs[i][1];int new_pos = nx * n + ny;int new_dis = dist[cur_pos] + (grid[x][y] != i + 1);if (nx >= 0 && nx < m && ny >= 0 && ny < n && new_dis < dist[new_pos]) {dist[new_pos] = new_dis;if (grid[x][y] == i + 1) {q.push_front(new_pos);}else {q.push_back(new_pos);}}}}return dist[m * n - 1];}
};

1370. 上升下降字符串
      给你一个字符串 s ，请你根据下面的算法重新构造字符串：
      从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
      从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
      重复步骤 2 ，直到你没法从 s 中选择字符。
      从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
      从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
      重复步骤 5 ，直到你没法从 s 中选择字符。
      重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
      在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
      请你返回将 s 中字符重新排序后的 结果字符串 。

因为只有26字母，所以不需要用哈希，直接拿数组存，然后正着遍历一遍再反着遍历一遍即可。

class Solution {
public:string sortString(string s) {vector<int> num(26);for (char &ch : s) {num[ch - 'a']++;}string ret;while (ret.length() < s.length()) {for (int i = 0; i < 26; i++) {if (num[i]) {ret.push_back(i + 'a');num[i]--;}}for (int i = 25; i >= 0; i--) {if (num[i]) {ret.push_back(i + 'a');num[i]--;}}}return ret;}
};

1371. 每个元音包含偶数次的最长子字符串
      给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，‘e’，‘i’，‘o’，‘u’ ，在子字符串中都恰好出现了偶数次。

因为每个字母只存在奇数、偶数两种情况，所以这里用位存储其状态即可，而且只需要五位。

class Solution {
public:int findTheLongestSubstring(string s) {int ans = 0, status = 0, n = s.length();vector<int> pos(1 << 5, -1);pos[0] = 0;for (int i = 0; i < n; ++i) {if (s[i] == 'a') {status ^= 1<<0;} else if (s[i] == 'e') {status ^= 1<<1;} else if (s[i] == 'i') {status ^= 1<<2;} else if (s[i] == 'o') {status ^= 1<<3;} else if (s[i] == 'u') {status ^= 1<<4;}if (~pos[status]) {ans = max(ans, i + 1 - pos[status]);} else {pos[status] = i + 1;}}return ans;}
};

1372. 二叉树中的最长交错路径
      给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：

选择二叉树中 任意 节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。

请你返回给定树中最长 交错路径 的长度。

递归遍历一遍，考虑每个点都取一次最值，最终返回的结果就是需要的结果。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int longestZigZag(TreeNode* root) {max_len = 0;search_node(root, true, 0);search_node(root, false, 0);return max_len;}private:void search_node(TreeNode* node, bool right, int len) {max_len = max(max_len, len);if (right) {if (node->left)search_node(node->left, false, len + 1);if (node->right)search_node(node->right, true, 1);} else {if (node->left)search_node(node->left, false, 1);if (node->right)search_node(node->right, true, len + 1);}}
private:int max_len;
};