腾讯百度阿里华为常见算法面试题TOP100(6)：回溯、二分查找、二叉树

之前总结过字节跳动TOP50算法面试题：

字节跳动常见算法面试题top50整理_沉迷单车的追风少年-CSDN博客_字节算法面试题

回溯

46.全排列

class Solution {
private:vector<vector<int> > ans;void dfs(vector<int>& nums, vector<int>& temp, int index) {if (temp.size() == nums.size()) {ans.push_back(temp);return;}for (int i = 0; i < nums.size(); i++) {if (find(temp.begin(), temp.end(), nums[i]) == temp.end()) {temp.push_back(nums[i]);dfs(nums, temp, i);temp.pop_back();}}}
public:vector<vector<int>> permute(vector<int>& nums) {vector<int> temp;dfs(nums, temp, 0);return ans;}
};

78.子集

class Solution {
private:vector<vector<int> > ans;void dfs(vector<int>& nums, vector<int>& temp, int index) {if (find(ans.begin(), ans.end(), temp) == ans.end()) {ans.push_back(temp);}if (index >= nums.size()) {return;}for (int i = index; i < nums.size(); i++) {temp.push_back(nums[i]);dfs(nums, temp, i + 1);temp.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {vector<int> temp;dfs(nums, temp, 0);return ans;}
};

17.电话号码的字母组合

class Solution {
private:vector<string> ans;vector<string> sList={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //字符表void backtrack(string& digits, string temp, int index) {if (index == digits.size()) {ans.push_back(temp);return;}string s = sList[digits[index] - '0'];// for循环横向遍历,递归纵向遍历for (int i = 0; i < s.size(); i++) {temp.push_back(s[i]);backtrack(digits, temp, index + 1);temp.pop_back();}}
public:vector<string> letterCombinations(string digits) {if (digits.empty()) {return {};}backtrack(digits, {}, 0);return ans;}
};

39.组合总和

class Solution {
private:vector<vector<int> > ans;void backtrack(vector<int>& candidates, int& target, vector<int> temp, int cursum, int index) {if (cursum == target) {ans.push_back(temp);return;}for (int i = index; i < candidates.size(); i++) {// 剪枝if (cursum + candidates[i] > target) {break;}temp.push_back(candidates[i]);backtrack(candidates, target, temp, cursum + candidates[i], i);temp.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());backtrack(candidates, target, {}, 0, 0);return ans;}
};

22.括号生成

class Solution {
private:vector<string> ans;void backtrack(int left, int right, int n, string s) {if (left == n && right == n) {  // 左右都拼完了终止ans.push_back(s);return;}if (left < n) {     // 左边括号没拼满拼接左边backtrack(left + 1, right, n, s + '(');}if (right < left) {  // 右边括号比左边少拼接右边backtrack(left, right + 1, n, s + ')');} }
public:vector<string> generateParenthesis(int n) {// DFS+回溯// left代表左边拼了的括号数// right代表右边拼的括号数backtrack(0, 0, n, "");return ans;}
};

79.单词搜索

class Solution {
private:// 剪枝操作,当找到路径的时候终止 bool flag = false;
public:bool exist(vector<vector<char>>& board, string word) {if (board.empty() || board.size() == 0 || board[0].size() == 0)return false;// DFS+回溯+剪枝for (int i = 0; i<board.size(); i++) {for (int j = 0; j<board[0].size(); j++) {if (dfs(board, i, j, word, 0))return true;}}return false;}// 传入引用直接在原位置上进行操作，不需要新建变量与赋值，节省时间开销和空间开销bool dfs(vector<vector<char>>& board, int i, int j, const string& word, int cur) {// 先列出终止条件if (cur == word.size()) {flag = true;return true;}// 回溯中心处理环节if (i < 0 || i>=board.size() || j < 0 || j >= board[0].size() || word[cur] != board[i][j])return false;// 分别标记上下左右每次搜索是否成功bool flag1, flag2, flag3, flag4;if (!flag) {// 先将board[i][j]拿出来用board[i][j] = '.';flag1 = dfs(board, i+1, j, word, cur+1);flag2 = dfs(board, i-1, j, word, cur+1);flag3 = dfs(board, i, j+1, word, cur+1);flag4 = dfs(board, i, j-1, word, cur+1);// 再将board[i][j]放回去,还原回溯现场board[i][j] = word[cur];// 任意一个方向成功即为此处搜索成功，返回truereturn flag1 ||flag2 || flag3 || flag4;}return true;}
};

131.分割回文串

class Solution {
public:vector<vector<string>> partition(string &s) {backtravel(s, 0, s.size()-1);return ans;}
private:vector<vector<string> > ans;vector<string> temp;void backtravel(const string &s, const int &left, const int &right) {//到字符串末尾了，将本次结果记录下来if (left > right) {ans.push_back(temp);return;}//从index为a开始截取长度为1,2,3..的子串进行验证，成功则用剩下的部分递归for (int i = 1; i <= right - left + 1; i++) {if (isHuiwen(s.substr(left, i))) {temp.push_back(s.substr(left, i));// 以上一次成功的位置为起点再次进行递归backtravel(s, left+i, right);temp.pop_back();}}}bool isHuiwen(const string &s) {int left = 0, right = s.size() - 1;while (left <= right) {if (s[left] != s[right])return false;left++;right--;}return true;}
};

51.N皇后

class Solution {
private:vector<vector<string>> ans;    // n 为输入的棋盘大小// row 是当前递归到棋盘的第几行了void backtrack(int n, int row, vector<string> chessboard) {if (row == n) {ans.push_back(chessboard);return;}for (int col = 0; col < n; col++) {if (isVaild(chessboard, row, col)) {chessboard[row][col] = 'Q';backtrack(n, row + 1, chessboard);chessboard[row][col] = '.';}}}// 判断是否合法bool isVaild(vector<string> chessboard, int row, int col) {// 同列不能用皇后for (int i = 0; i < row; i++) {if (chessboard[i][col] == 'Q') {return false;}}// 斜45不能用皇后for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (chessboard[i][j] == 'Q') {return false;}}// 斜135不能用皇后for (int i = row - 1, j = col + 1; i >= 0 && j < chessboard.size(); i--, j++) {if (chessboard[i][j] == 'Q') {return false;}}return true;}
public:vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n, string(n, '.'));backtrack(n, 0, chessboard);return ans;}
};

二分搜索

35.搜索插入位置

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;} else {return mid;}}return right + 1;}
};

74.搜索二维矩阵

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {// 选择左下角开始比较if(matrix.size()==0)return false;int i = 0; int j = matrix[0].size()-1;while (i<matrix.size()&&j>=0) {if ( matrix[i][j]>target ) {j--;}else if (matrix[i][j]<target) {i++;}else {return true;}}return false;}
};

34.在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);// 情况一: target在数组范围的左边或者右边if (leftBorder == -2 || rightBorder == -2) {return {-1, -1};}// 情况三: target在数组范围内且存在if (rightBorder - leftBorder > 1) {return {leftBorder + 1, rightBorder - 1};}// 情况二: target在数组范围内但是不存在return {-1, -1};}
private:int getRightBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}int getLeftBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}
};

33.搜索旋转排序数组

class Solution {
public:int search(vector<int>& nums, int target) {int ans = -1;// 二分// 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.int left = 0;int right = nums.size() - 1;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > nums[right]) {  // 无序在右半段if (target < nums[mid] && target >= nums[left]) {    // 判断target是否在有序的半段right = mid - 1;} else {left = mid + 1;}} else {    // 无序在左半段if (target > nums[mid] && target <= nums[right]) {   // 判断target是否在有序的半段left = mid + 1;} else {right = mid - 1;}}}return ans;}
};

153.寻找旋转排序数组中的最小值

class Solution {
public:int findMin(vector<int>& nums) {int left = 0;int right = nums.size() - 1;while (left < right) {// 取中间值int mid = (right + left) / 2;// 如果中间值小于最大值，则最大值减小if (nums[mid] < nums[right]) {right = mid;} else { // 如果中间值大于最大值，则最小值变大left = mid + 1;}}return nums[left];}
};