1. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入:[eat", "tea", "tan", "ate", "nat", "bat"]
输出:[[ate","eat","tea"],["nat","tan"],["bat"]]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
以下程序实现了这一功能，请你填补空白处内容：
···c++
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<vector<string>> groupAnagrams(vector<string> &strs) { vector<vector<string>> res; unordered_map<string, vector<string>> ht; for (const auto &str : strs) { int counts[26] = {0}; for (char c : str) { counts[c - 'a']++; } string key; for (int i : counts) { ________________; } ht[key].push_back(str); } for (const auto &t : ht) { res.push_back(t.second); } return res; } }; ```
出处：
https://edu.csdn.net/practice/25797440
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<vector<string>> groupAnagrams(vector<string> &strs) { vector<vector<string>> res; unordered_map<string, vector<string>> ht; for (const auto &str : strs) { int counts[26] = {0}; for (char c : str) { counts[c - 'a']++; } string key; for (int i : counts) { key.push_back(i + '#'); key.push_back('0'); } ht[key].push_back(str); } for (const auto &t : ht) { res.push_back(t.second); } return res; } }; string vectorToString(vector<string> vect) { stringstream ss; ss << "["; for (size_t i = 0; i < vect.size(); i++) { ss << vect[i]; ss << (i < vect.size() - 1 ? "," : "]"); } return ss.str(); } int main() { Solution s; vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"}; for (auto str:s.groupAnagrams(strs)) cout << vectorToString(str)<< " "; cout << endl; return 0; }
输出：
[bat] [tan,nat] [eat,tea,ate]
2. 计算右侧小于当前元素的个数
给你`一个整数数组 nums ，按要求返回一个新数组 counts 。
数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1：
输入：nums = [5,2,6,1]
输出：
1. [2,1,1,0] 2. 解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2：
输入：nums = [-1]
输出：[0]
示例 3：
输入：nums = [-1,-1]
输出：[0,0]
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
出处：
https://edu.csdn.net/practice/25797441
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: struct BSTNode { int val; int count; BSTNode *left; BSTNode *right; BSTNode(int x) : val(x), left(NULL), right(NULL), count(0) {} }; void BST_insert(BSTNode *node, BSTNode *insert_node, int &count_small) { if (insert_node->val <= node->val) { node->count++; if (node->left) { BST_insert(node->left, insert_node, count_small); } else { node->left = insert_node; } } else { count_small += node->count + 1; if (node->right) { BST_insert(node->right, insert_node, count_small); } else { node->right = insert_node; } } } vector<int> countSmaller(vector<int> &nums) { vector<int> result; vector<BSTNode *> node_vec; vector<int> count; for (int i = nums.size() - 1; i >= 0; i--) { node_vec.push_back(new BSTNode(nums[i])); } count.push_back(0); for (int i = 1; i < node_vec.size(); i++) { int count_small = 0; BST_insert(node_vec[0], node_vec[i], count_small); count.push_back(count_small); } for (int i = node_vec.size() - 1; i >= 0; i--) { delete node_vec[i]; result.push_back(count[i]); } return result; } };
输出：
[2,1,1,0]
3. 加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9
出处：
https://edu.csdn.net/practice/25797442
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<int> plusOne(vector<int> &digits) { int carry = 1; vector<int> res; for (int i = digits.size() - 1; i >= 0; i--) { int d = digits[i] + carry; res.push_back(d % 10); carry = d / 10; } if (carry > 0) { res.push_back(carry); } reverse(res.begin(), res.end()); return res; } }; string vectorToString(vector<int> vect) { stringstream ss; ss << "["; for (size_t i = 0; i < vect.size(); i++) { ss << to_string(vect[i]); ss << (i < vect.size() - 1 ? "," : "]"); } return ss.str(); } int main() { Solution s; vector<int> digits = {1,2,3}; cout << vectorToString(s.plusOne(digits))<< endl; digits = {9,9,9}; cout << vectorToString(s.plusOne(digits))<< endl; return 0; }
输出：
[1,2,4]
[1,0,0,0]
