leetcode

class="superseo">leetcode

• 题目
• • 全排列
  • 电话号码的字母组合
• 周赛

题目 全排列

题目链接

class Solution {
 public:
  void backtrack(const vector<int>& nums, vector<vector<int>>& res, vector<int>& output, vector<bool>& mark, int first, int len) {
    if (first == len) {
      res.emplace_back(output);
      return;
    }

    for (int i = 0; i < len; i++) {
      if (!mark[i]) {
        mark[i] = true;
        output.emplace_back(nums[i]);
        backtrack(nums, res, output, mark, first + 1, len);
        mark[i] = false;
        output.pop_back();
      }
    }
  }
  vector<vector<int>> permute(vector<int>& nums) {      // 借助标记数组，使用回溯法找到所有全排列
    int n = static_cast<int>(nums.size());
    vector<vector<int>> res;
    vector<bool> mark(n, false);
    vector<int> output;
    backtrack(nums, res, output, mark, 0, n);       
    return res;
  }
};

官方题解

class Solution {
 public:
  void backtrack(vector<int>& nums, vector<vector<int>>& res, int first, int len) {
    if (first == len) {
      res.emplace_back(nums);
      return;
    }

    for (int i = first; i < len; i++) {  // [0,first−1] 是已填过的数的集合，[first,n−1] 是待填的数的集合
      swap(nums[i], nums[first]);
      backtrack(nums, res, first + 1, len);
      swap(nums[i], nums[first]);
    }
  }
  vector<vector<int>> permute(vector<int>& nums) {  // 不使用标记数组
    int n = static_cast<int>(nums.size());
    vector<vector<int>> res;
    backtrack(nums, res, 0, n);
    return res;
  }
};

电话号码的字母组合

题目链接

class Solution {
 public:
  void traverse(const vector<string>& source, string combine, int start, int end, vector<string>& res) {
    if (start == end) {  // 到达末尾，加入结果集
      res.emplace_back(combine);
      return;
    }
    for (auto letter : source[start]) {  // 依次使用各个字母
      traverse(source, combine + letter, start + 1, end, res);
    }
  }
  vector<string> letterCombinations(string digits) {
    if (digits.empty()) {
      return {};
    }
    static vector<string> dig2str = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  // 数字字母映射
    vector<string> strs;
    int idx;
    for (auto digit : digits) {  // 将数字转换成字母集合
      idx = static_cast<int>(digit - '2');
      strs.emplace_back(dig2str[idx]);
    }
    vector<string> res;
    int digit_len = static_cast<int>(digits.size());
    traverse(strs, "", 0, digit_len, res);  // 遍历
    return res;
  }
};

周赛