目录
17. 电话号码的字母组合
题目描述
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
class Solution {
//构造一个char[][]
vector<vector<char>> lettersArray = {
{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
{'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
{'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}
};
//用来存储每一层选择的字母
string cs;
//用来存储最终的结果
vector<string>list;
//深度优先搜索
void dfs(int idx,string digits){
//已经进入到最后一层了，不能再往下搜索
if (idx == digits.length()) {
// 得到了一个正确的解
list.push_back(cs);
return;
}
// 先枚举这一层可以做的所有选择
vector<char> chars = lettersArray[digits[idx] - '2'];
for (char c : chars) {
cs[idx] = c;
dfs(idx+1, digits);
//来到这里，回溯
}
}
public:
vector<string> letterCombinations(string digits) {
if (digits.length()<=0) return vector<string>();
//初始化list
list = vector<string>();
//初始化cs
cs = string(digits.length(),' ');
//调用dfs
dfs(0, digits);
return list;
}
};
46. 全排列
题目描述
46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处
题目实现 - 方式一
class Solution1 {
void dfs(int idx,
vector<int>& nums,
vector<int>& levelInts,
vector<vector<int>>& result){
if (idx == nums.size()) {
result.push_back(levelInts);
return;
}
for (int i = 0; i<nums.size(); i++) {
//如果已经被使用了continue
if(count(levelInts.begin(), levelInts.end(), nums[i])) continue;
levelInts[idx] = nums[i];
dfs(idx+1, nums,levelInts,result);
//还原现场
levelInts[idx] = INT8_MAX;
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
if (nums.size() == 0) return vector<vector<int>>();
//存放每一层的选择
vector<int> levelInts = vector<int>(nums.size(),INT8_MAX);
//存放最终的结果
vector<vector<int>> result = vector<vector<int>>();
//调用dfs
dfs(0, nums,levelInts,result);
return result;
}
};
题目实现 - 方式二
class Solution2 {
void dfs(int idx,vector<int>& nums,
vector<int>& levelInts,
vector<vector<int>>& result,
vector<bool>& used){
if (idx == nums.size()) {
result.push_back(levelInts);
return;
}
for (int i = 0; i<nums.size(); i++) {
//如果已经被使用了continue
if(used[i]) continue;
levelInts[idx] = nums[i];
//标记已经被使用
used[i] = true;
dfs(idx+1, nums,levelInts,result,used);
//还原现场
used[i] = false;
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
if (nums.size() == 0) return vector<vector<int>>();
//存放每一层的选择
vector<int> levelInts = vector<int>(nums.size(),0);
//存放是否被使用过
vector<bool> used = vector<bool>(nums.size(),false);
//存放最终的结果
vector<vector<int>> result = vector<vector<int>>();
//调用dfs
dfs(0, nums,levelInts,result,used);
return result;
}
};
题目实现 - 方式三
class Solution {
void dfs(int idx,vector<int>& nums,
vector<int>& levelInts,
vector<vector<int>>& result){
if (idx == nums.size()) {
int size = (int)nums.size();
for (int i = 0;i<size;i++) {
levelInts[i] = nums[i];
}
result.push_back(levelInts);
return;
}
for (int i = idx; i<nums.size(); i++) {
swap(nums, idx,i);
dfs(idx+1, nums,levelInts,result);
//还原现场
swap(nums, idx,i);
}
}
//交换两个数据
void swap(vector<int>& nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public:
vector<vector<int>> permute(vector<int>& nums) {
if (nums.size() == 0) return vector<vector<int>>();
//存放每一层的选择
vector<int> levelInts = vector<int>(nums.size());
//存放最终的结果
vector<vector<int>> result = vector<vector<int>>();
//调用dfs
dfs(0, nums,levelInts,result);
return result;
}
};
47. 全排列 II
题目描述
47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
class Solution {
void dfs(int idx,vector<int>& nums,
vector<int>& levelInts,
vector<vector<int>>& result){
if (idx == nums.size()) {
int size = (int)nums.size();
for (int i = 0;i<size;i++) {
levelInts[i] = nums[i];
}
result.push_back(levelInts);
return;
}
for (int i = idx; i<nums.size(); i++) {
// 要保证一个数字在idx位置只会出现一次
if (isRepeat(nums, idx, i)) continue;
swap(nums, idx,i);
dfs(idx+1, nums,levelInts,result);
//还原现场
swap(nums, idx,i);
}
}
bool isRepeat(vector<int>&nums,int idx,int i){
for (int j = idx; j < i; j++) {
if (nums[j] == nums[i]) return true;
}
return false;
}
//交换两个数据
void swap(vector<int>& nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
if (nums.size() == 0) return vector<vector<int>>();
//存放每一层的选择
vector<int> levelInts = vector<int>(nums.size());
//存放最终的结果
vector<vector<int>> result = vector<vector<int>>();
//调用dfs
dfs(0, nums,levelInts,result);
return result;
}
};
22. 括号生成
题目描述
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
class Solution {
/**
* @param idx 搜索的层号
* @param leftRemain 左括号的剩余数量
* @param rightRemain 右括号的剩余数量
* @param str 用来存放每一层的选择
*/
void dfs(int idx,int leftRemain,int rightRemain,
string& str,vector<string>&list){
if (idx == str.length()){
list.push_back(str);
return;
}
// 枚举这一层所有可能的选择
// 选择一种可能之后，进入下一层搜索
// 什么情况可以选择左括号？左括号的数量 > 0
// 选择左括号，然后进入下一层搜索
if (leftRemain > 0) {
str[idx] = '(';
dfs(idx+1, leftRemain-1, rightRemain, str, list);
}
// 当左括号、右括号的数量一样时，只能选择左括号
// 什么情况可以选择右括号？(右括号的数量 > 0) && (右括号的数量 != 左括号的数量)
// 选择右括号，然后进入下一层搜索
if (rightRemain > 0 && leftRemain != rightRemain) {
str[idx] = ')';
dfs(idx+1, leftRemain, rightRemain-1, str, list);
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> list = vector<string>();
if (n < 0) return list;
string str = string(n<<1,' ');
dfs(0, n, n,str,list);
return list;
}
};
行者常至，为者常成！