leetcode

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

题目链接

class Solution {
 public:
  void backtrack(const vector& nums, vector>& res, vector& output, vector& 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> permute(vector& nums) {      // 借助标记数组，使用回溯法找到所有全排列
    int n = static_cast(nums.size());
    vector> res;
    vector mark(n, false);
    vector output;
    backtrack(nums, res, output, mark, 0, n);       
    return res;
  }
};

官方题解

class Solution {
 public:
  void backtrack(vector& nums, vector>& 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> permute(vector& nums) {  // 不使用标记数组
    int n = static_cast(nums.size());
    vector> res;
    backtrack(nums, res, 0, n);
    return res;
  }
};

题目链接

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