#include <iostream> #include <vector> #include <string> #include <unordered_map> using namespace std; vector<string> letterCombinations(string digits){ vector<string> res; if (digits.empty()) { return res; } unordered_map<char, string> mapping = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} }; string combination; backtrack(res, combination, digits, 0, mapping); return res; } void backtrack(vector<string>& res, string& combination, string& digits, int index, unordered_map<char, string>& mapping) { if (index == digits.size()) { res.push_back(combination); return; } } int main() { string digits = "23"; vector<string> res = letterCombinations(digits); for (string s : res) { cout << s << " "; } cout << endl; return 0; }

这段代码是一个 C++ 实现的电话号码的字母组合问题。给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。具体地，每个数字可以表示多个字母，不同数字之间的字母组合排列方式要求按照数字的顺序进行。代码中使用了回溯算法来解决该问题。其中 `letterCombinations` 函数用来生成所有的字母组合，`backtrack` 函数用来进行回溯操作。在 `letterCombinations` 函数中，首先根据数字字符和字母的映射关系创建了一个 `unordered_map` 对象 `mapping`。然后定义了一个空字符串 `combination` 和一个空 vector `res` 来保存最终结果。最后调用了 `backtrack` 函数来生成所有的字母组合。在 `backtrack` 函数中，首先判断是否达到了数字字符串的末尾，如果是，则将当前的 `combination` 字符串保存到 `res` 中。否则，遍历当前数字字符所能表示的所有字母，依次加入到 `combination` 字符串中，然后递归调用 `backtrack` 函数，添加下一个数字字符所能表示的字母。递归完成后，需要将 `combination` 字符串还原到上一个状态，以便进行下一次回溯。最终返回 `res` 数组即可。

相关问题

#pragma once #include <iostream> #include <vector> #include <fstream> #include <algorithm> #include <unordered_map> using namespace std; class User_Gxy { public: string username_Gxy; string password_Gxy; User_Gxy(string _username, string _password) : username_Gxy(_username), password_Gxy(_password) {} }; class UserManager { private: vector<User_Gxy> users; string userFile; struct RatingRecord { int movieId; string movieName; float rating; RatingRecord(int _movieId, string _movieName, float _rating) : movieId(_movieId), movieName(_movieName), rating(_rating) {} }; unordered_map<string, vector<RatingRecord>> ratingRecords; public: UserManager(string _userFile) : userFile(_userFile) {} void loadUsers_Gxy(); void saveUsers_Gxy(); void registerUser_Gxy(string username, string password); bool loginUser_Gxy(string username, string password); void addRatingRecord_Gxy(string username, int movieId, string movieName, float rating); void viewRatingRecords_Gxy(string username); void rateMovie_Gxy(string username, int movieId, string movieName, float musicRating, float visualRating, float storyRating, float performanceRating); }; 代码解释

这段代码是一个用户管理和评分记录系统，其中包含两个类：User_Gxy和UserManager。

User_Gxy类表示一个用户，具有username_Gxy（用户名）和password_Gxy（密码）属性。构造函数用于初始化这些属性。

UserManager类用于管理用户和评分记录，包含一个私有的users向量、一个userFile字符串和一个ratingRecords无序映射。users向量用于存储用户对象，userFile字符串用于指定用户数据的文件路径，ratingRecords无序映射用于存储用户的评分记录。构造函数用于初始化userFile。

UserManager类具有以下成员函数：
- loadUsers_Gxy(): 从指定的文件中加载用户数据到users向量中。
- saveUsers_Gxy(): 将users向量中的用户数据保存到指定的文件中。
- registerUser_Gxy(): 注册一个新用户，并将其添加到users向量中。
- loginUser_Gxy(): 用户登录验证，检查给定的用户名和密码是否匹配。
- addRatingRecord_Gxy(): 添加一条评分记录到指定用户的评分记录中。
- viewRatingRecords_Gxy(): 查看指定用户的所有评分记录。
- rateMovie_Gxy(): 为指定用户对一部电影进行评分，并添加评分记录到对应的评分记录中。

这些函数的具体实现需要根据需求进一步完成。

#include <iostream> #include <vector> #include <unordered_map> #include <queue> #include <algorithm> using namespace std; struct WordFreq { string word; int freq; bool operator<(const WordFreq& other) const { return freq == other.freq ? word > other.word : freq < other.freq; } }; vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> freq; for (const auto& word : words) { freq[word]++; } priority_queue<WordFreq, vector<WordFreq>> pq; for (const auto& [word, f] : freq) { pq.push({word, f}); if (pq.size() > k) { pq.pop(); } } vector<string> result(k); for (int i = k - 1; i >= 0; i--) { result[i] = pq.top().word; pq.pop(); } return result; } int main() { int k; cin >> k; vector<string> words; string word; while (cin >> word) { if (word == "end") { break; } words.push_back(word); } auto result = topKFrequent(words, k); for (const auto& word : result) { cout << word << " "; } cout << endl; return 0; }

这段代码实现了前 k 个出现次数最多的单词的查找，使用了堆排序的思想，时间复杂度为 O(Nlogk)，其中 N 为单词个数。

具体实现过程如下：

1. 首先使用哈希表统计每个单词出现的频率。

2. 然后使用优先队列（堆）存储单词和对应的频率，队列中最多只保存 k 个元素。

3. 遍历哈希表中的每个元素，将其插入优先队列中，如果队列中元素数量超过 k，则将队列中频率最小的元素弹出。

4. 最后，将优先队列中的 k 个单词按频率从大到小排序，并返回结果。

以下是代码解释：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

// 定义一个结构体，用于存储单词和对应的频率
struct WordFreq {
  string word;
  int freq;
  bool operator<(const WordFreq& other) const {
      // 如果频率相同，按字母顺序从小到大排序；否则按频率从大到小排序
      return freq == other.freq ? word < other.word : freq > other.freq;
  }
};

vector<string> topKFrequent(vector<string>& words, int k) {
  // 哈希表用于统计每个单词出现的频率
  unordered_map<string, int> freq;
  for (const auto& word : words) {
      freq[word]++;
  }

  // 优先队列用于存储单词和对应的频率，队列中最多只保存 k 个元素
  priority_queue<WordFreq, vector<WordFreq>> pq;
  for (const auto& [word, f] : freq) {
      pq.push({word, f});
      if (pq.size() > k) {
          pq.pop();
      }
  }

  // 将优先队列中的 k 个单词按频率从大到小排序，并返回结果
  vector<string> result(k);
  for (int i = k - 1; i >= 0; i--) {
      result[i] = pq.top().word;
      pq.pop();
  }
  return result;
}

int main() {
  int k;
  cin >> k;

  vector<string> words;
  string word;
  while (cin >> word) {
      if (word == "end") {
          break;
      }
      words.push_back(word);
  }

  auto result = topKFrequent(words, k);
  for (const auto& word : result) {
      cout << word << " ";
  }
  cout << endl;

  return 0;
}

希望能够帮到你！