首页 / 面试 / 面试算法———回溯经典题目
面试算法———回溯经典题目
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了面试算法———回溯经典题目，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7381字，纯文字阅读大概需要11分钟。
内容图文
文章目录
方法论：
- 看题五分钟，不会做，看解析；
- 先看中文站，再看国际站；
- 选择最优解析；
- 回头再来写
面试四步走：
- 和面试官，探讨题目限制条件；
- 说说可能解，选择最优解；
- 码字；
- 跑测试用例
分治模板
C/C++
int divide_conquer(Problem *problem, int params) {
// recursion terminator
if (problem == nullptr) {
process_result
return return_result;
}
// process current problem
subproblems = split_problem(problem, data)
subresult1 = divide_conquer(subproblem[0], p1)
subresult2 = divide_conquer(subproblem[1], p1)
subresult3 = divide_conquer(subproblem[2], p1)
...
// merge
result = process_result(subresult1, subresult2, subresult3)
// revert the current level status
return 0;
}
50.Pow(x, n)
题目：实现 pow(x, n) ，即计算 x 的 n 次幂函数。
可能解：
- O(n)暴力解
- O(longn)快速幂+递归
# 1.暴力解，会超出时间限制
class Solution {
public:
double myPow(double x, int n) {
double res = 1;
long long N = n;
if (N < 0) {
N = -N;
x = 1/x;
}
for (long long i = 0; i < N; i++){
res *= x;
}
return res;
}
};
# 2. 快速幂+递归
class Solution {
public:
double myPow(double x, int n) {
long long N = n;
if (N < 0) {
N = -N;
x = 1/x;
}
return fastPow(x, N);
}
private: double fastPow(double x, long long n) {
// terminator
if (n == 0) return 1.0;
// process current logic + drill down
double half = fastPow(x, n/2);
// restore current logic
return n % 2 == 0 ? half * half : half * half * x;
}
};
169. 多数元素
题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ? n/2 ? 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
可能解：
- 因为给定数组总存在多数元素，因此，可以将数组排序，然后
num.size() / 2一定是多数元素； - 利用hashmap记录元素个数；
- 随机选取数组中的值，如果该值个数超过一半，那么就是所求值；
- 利用分治求解；
- 利用Moore 投票；
# 2 hashmap求解
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> umap;
for (int num : nums){
umap[num]++;
if (umap[num] > nums.size() / 2) return num;
}
return -1;
}
};
# 3. 随机求解
class Solution {
public:
int majorityElement(vector<int>& nums) {
while(1){
int candidate = nums[rand() % nums.size()];
int count = 0;
for (int num : nums){
if (num == candidate)
++count;
}
if (count > nums.size() / 2) return candidate;
}
}
};
# 4.利用分治求解
class Solution {
public:
int majorityElement(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
private:
int helper(vector<int>& nums, int left, int right){
// helper(nums, l, r)，返回[l, r]中出现最多的数
// terminator
if (left == right) return nums[left];
// process current problem
int mid = left + ((right - left) >> 1);
int lm = helper(nums, left, mid);
int rm = helper(nums, mid + 1, right);
// merge and revert current status
if (lm == rm) return lm;
return count(nums.begin() + left, nums.begin() + mid + 1, lm) > count(nums.begin() + mid + 1, nums.begin() + right + 1, rm) ? lm : rm;
}
};
# Moore投票
class Solution {
public:
int majorityElement(vector<int>& nums) {
int count = 0;
int major = -1;
for (auto c : nums){
if (count == 0){
major = c;
}
count += (major == c) ? 1 : -1;
}
return major;
}
};
78.子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
思路：子集的另一种解法，在这里有中新解法，给定数组nums，对于其中的每个元素，我们可以通过选或者不选的形式来写递归；
class Solution {
void generateSub(const vector<int>& nums, vector<vector<int>>& res, vector<int>& path, int start){
// terminator
if (start == nums.size()) {
res.push_back(path);
return;
}
// not pick up the number at this index
generateSub(nums, res, path, start+1 );
// pick the number at this index
path.push_back(nums[start]);
generateSub(nums, res, path, start+1 );
path.pop_back();
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
generateSub(nums, res, path, 0);
return res;
}
};
17.电话号码的字母组合
题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
可能解：
- 回溯解法：递归树中，每个节点可能的选择，就是手机数字上面的3或4个可选字母；
- 队列求解；17.电话号码字母组合，队列图解 My Java solution with FIFO queue
# 解法1
class Solution {
private:
const string letterMap[10] = {
"", //0
"", //1
"abc", // 2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
// 变化的是index， 和选路
void findCombination(const string& digits, vector<string>& res, string& s, int start){
if (start == digits.size()){
res.push_back(s);
return;
}
char c = digits[start];
string letters = letterMap[c - '0'];
// 选择列表
for (int i = 0; i < letters.size(); i++){
// 做选择
s = s + letters[i];
findCombination(digits, res, s, start+1);
s.erase(s.end() -1);
}
return;
}
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits == "")
return res;
string s = "";
findCombination(digits, res, s, 0);
return res;
}
};
# 解法2
class Solution {
private:
const string letterMap[10] = {
"", //0
"", //1
"abc", // 2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
// 变化的是index， 和选路
void findCombination(const string& digits, vector<string>& res, string& s, int start){
if (start == digits.size()){
res.push_back(s);
return;
}
char c = digits[start];
string letters = letterMap[c - '0'];
// 选择列表
for (int i = 0; i < letters.size(); i++){
// 做选择
s = s + letters[i];
findCombination(digits, res, s, start+1);
s.erase(s.end() -1);
}
return;
}
public:
vector<string> letterCombinations(string digits) {
deque<string> dq;
if (digits.size() == 0) return {};
dq.push_back("");
for (int i = 0; i < digits.size(); i++) {
string letters = letterMap[digits[i] - '0'];
while (dq.front().size() == i) {
string tmp = dq.front();
dq.pop_front();
for (char s : letters){
dq.push_back(tmp + s);
}
}
}
vector<string> res(dq.begin(), dq.end());
return res;
}
};
51.N皇后
题目：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
思路：
- 定义
columns集合，判断当前列是否摆放皇后； - 定义
dia1集合，判断对角1是否有皇后，定义的规则是横坐标 - 纵坐标是否相等； - 定义
dia2集合，判断对角线2是否有皇后，定义规则是横坐标 + 纵坐标是否相等； - 其他就是回溯套路：遍历当前节点的可选项，判断是否符合要求，符合就进入下一层，不符合就
continue；
# 更加偏向于下面代码
class Solution {
private:
void putQueen(vector<vector<string>>& res, vector<int>& queen, int n, int start, unordered_set<int> columns, unordered_set<int> dia1, unordered_set<int> dia2){
if (start == n){
res.push_back( generateBoard(n, queen));
return;
}
for(int i = 0; i < n ; i++){
if (columns.find(i) != columns.end() || dia1.find(start - i) != dia1.end() || dia2.find(start + i) != dia2.end()){
continue;
}
queen.push_back(i);
columns.insert(i);
dia1.insert(start - i);
dia2.insert(start + i);
putQueen(res, queen, n, start + 1, columns, dia1, dia2);
columns.erase(i);
dia1.erase(start - i);
dia2.erase(start + i);
queen.pop_back();
}
}
vector<string> generateBoard(int n, vector<int>& queen){
vector<string> board( n, string(n, '.'));
for (int i = 0; i < n; i++){
board[i][queen[i]] = 'Q';
}
return board;
}
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
unordered_set<int> columns;
unordered_set<int> dia1;
unordered_set<int> dia2;
vector<int> queen;
putQueen(res, queen, n, 0, columns, dia1, dia2);
return res;
}
};
参考
- 极客时间-算法训练营-覃超
- C++ 6 Solutions for majority-element
- 17.电话号码字母组合，队列图解
- leetcode中文站
- leetcode国际站 (将力扣中文链接，后面的-cn去掉，就是该题的国际站)
内容总结
以上是互联网集市为您收集整理的面试算法———回溯经典题目全部内容，希望文章能够帮你解决面试算法———回溯经典题目所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】