236. 二叉树的最近公共祖先

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == p || root == q || root == nullptr)    return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left != nullptr && right != nullptr)    return root;if (left != nullptr && right == nullptr)    return left;if (left == nullptr && right != nullptr)    return right;if (left == nullptr && right == nullptr)     return nullptr;return nullptr;}
};

61. 旋转链表

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (k == 0 || head == nullptr || head->next == nullptr){return head;}int n = 1;ListNode* cur = head;while (cur->next != nullptr){cur = cur->next;n++;}int add = n - k % n;if(add == n)    return head;ListNode* dummy = new ListNode(-1);dummy->next = head;cur = dummy;while (add--){cur = cur->next;}ListNode* cur2 = cur->next;cur->next = nullptr;ListNode* cur3 = cur2;while (cur2->next != nullptr){cur2 = cur2->next;}cur2->next = dummy->next;return cur3;}
};

47. 全排列 II

class Solution {
private:vector<int> path;vector<vector<int>> res;void backtracking(vector<int>& nums, vector<bool>& used){if (nums.size() == path.size()){res.push_back(path);return;}for (int i = 0; i < nums.size(); i++){if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false){continue;}if(used[i] == false){used[i] = true;path.push_back(nums[i]);backtracking(nums, used);used[i] = false;path.pop_back();}}}public:vector<vector<int>> permuteUnique(vector<int>& nums) {res.clear();path.clear();sort(nums.begin(), nums.end());vector<bool> used(nums.size(), false);backtracking(nums, used);return res;}
};

74. 搜索二维矩阵

class Solution {
private:vector<int> path;vector<vector<int>> res;void backtracking(vector<int>& nums, vector<bool>& used){if (nums.size() == path.size()){res.push_back(path);return;}for (int i = 0; i < nums.size(); i++){if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false){continue;}if(used[i] == false){used[i] = true;path.push_back(nums[i]);backtracking(nums, used);used[i] = false;path.pop_back();}}}public:vector<vector<int>> permuteUnique(vector<int>& nums) {res.clear();path.clear();sort(nums.begin(), nums.end());vector<bool> used(nums.size(), false);backtracking(nums, used);return res;}
};

240. 搜索二维矩阵 II

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size();for (int i = 0; i < m; i++){int left = 0, right = matrix[0].size() - 1;while (left <= right){int mid = (left + right) >> 1;if (matrix[i][mid] > target){right = mid - 1;}else if (matrix[i][mid] < target){left = mid + 1;}else{return true;}}}return false;}
};

93. 复原 IP 地址

class Solution {
private:vector<string> res;void backtracking(string& s, int startIndex, int pointNum){if (pointNum == 3){if (isVaild(s, startIndex, s.size() - 1)){res.push_back(s);}return;}for (int i = startIndex; i < s.size(); i++){if (isVaild(s, startIndex, i))// 判断 [startIndex,i] 这个区间的子串是否合法{s.insert(s.begin() + i + 1, '.');// 在i的后面插入一个逗点pointNum++;backtracking(s, i + 2, pointNum);// 插入逗点之后下一个子串的起始位置为i+2pointNum--; // 回溯s.erase(s.begin() + i + 1);// 回溯删掉逗点}else{break;// 不合法，直接结束本层循环}}}//判断字符串s在左闭右闭的区间[start, end]所组成的数字是否合法bool isVaild(const string& s, int start, int end){if (start > end) return false;if (s[start] == '0' && start != end){return false;}int num = 0;for (int i = start; i <= end; i++){if (s[i] > '9' || s[i] < '0')// 遇到非数字字符不合法{return false;}num = num * 10 + s[i] - '0';if (num > 255){return false;}}return true;}public:vector<string> restoreIpAddresses(string s) {res.clear();if (s.size() < 4 || s.size() > 12)   return res;backtracking(s, 0, 0);return res;}
};