LeetCode Hot100 61~70

动态规划

61. 分割回文串

class Solution {
private:vector<vector<int>> f;vector<vector<string>> ret;vector<string> ans;int n;public:void dfs(const string& s, int i) {if (i == n) {ret.push_back(ans);return;}for (int j = i; j < n; ++j) {if (f[i][j]) {ans.push_back(s.substr(i, j - i + 1));dfs(s, j + 1);ans.pop_back();}}}vector<vector<string>> partition(string s) {n = s.size();f.assign(n, vector<int>(n, true));for (int i = n - 1; i >= 0; --i) {for (int j = i + 1; j < n; ++j) {f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];}}dfs(s, 0);return ret;}
};

62. N皇后

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> ans;vector<int> queens(n); // 皇后放在 (r,queens[r])vector<int> col(n), diag1(n * 2 - 1), diag2(n * 2 - 1); // vector<int> 效率比 vector<bool> 高auto dfs = [&](auto&& dfs, int r) {if (r == n) {vector<string> board(n);for (int i = 0; i < n; i++) {board[i] = string(queens[i], '.') + 'Q' + string(n - 1 - queens[i], '.');}ans.push_back(board);return;}// 在 (r,c) 放皇后for (int c = 0; c < n; c++) {int rc = r - c + n - 1;if (!col[c] && !diag1[r + c] && !diag2[rc]) { // 判断能否放皇后queens[r] = c; // 直接覆盖，无需恢复现场col[c] = diag1[r + c] = diag2[rc] = true; // 皇后占用了 c 列和两条斜线dfs(dfs, r + 1);col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场}}};dfs(dfs, 0);return ans;}
};

二分

63. 搜索插入的位置

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

64. 搜索二维矩阵

class Solution {
public:bool searchMatrix(vector<vector<int>> matrix, int target) {auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {return b < a[0];});if (row == matrix.begin()) {return false;}--row;return binary_search(row->begin(), row->end(), target);}
};

65. 搜索矩阵中的位置

class Solution { 
public:int binarySearch(vector<int>& nums, int target, bool lower) {int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}vector<int> searchRange(vector<int>& nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {return vector<int>{leftIdx, rightIdx};} return vector<int>{-1, -1};}
};

66. 搜索矩阵

class Solution {
public:int search(vector<int>& nums, int target) {int n = (int)nums.size();if (!n) {return -1;}if (n == 1) {return nums[0] == target ? 0 : -1;}int l = 0, r = n - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) return mid;if (nums[0] <= nums[mid]) {if (nums[0] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[n - 1]) {l = mid + 1;} else {r = mid - 1;}}}return -1;}
};

67. 搜索数组最小值

class Solution {
public:int findMin(vector<int>& nums) {int low = 0;int high = nums.size() - 1;while (low < high) {int pivot = low + (high - low) / 2;if (nums[pivot] < nums[high]) {high = pivot;}else {low = pivot + 1;}}return nums[low];}
};

68. 搜索两个数组的中位数

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int size = nums1.size() + nums2.size();vector<int> ans(size , 0);int i = 0;int j = 0;int k = 0;while (i < nums1.size() && j < nums2.size()) {if (nums1[i] <= nums2[j]) {ans[k++] = nums1[i++];}else {ans[k++] = nums2[j++];}}while(i < nums1.size()) {ans[k++] = nums1[i++];}while(j < nums2.size()) {ans[k++] = nums2[j++];}return (double)(ans[size/2] + ans[(size-1)/2])/2.0;}
};

69. 有效的括号

class Solution {
public:bool isValid(string s) {// 因为我们使用栈的话必须要保证匹配 // 如果是左边的几种类型我们才入栈// 如果是右边的我们就往栈里面匹配 // 如果最后全部匹配完了 栈为空则我们返回true // 如果不为空 或者最后字符串遍历完毕了栈中还有数据则为假stack<char> stack;for (int i = 0; i < s.size() ; i++){if (s[i] == '(' || s[i] == '[' || s[i] == '{'){stack.push(s[i]);}else{if (stack.empty()){return false;}if (s[i] == ')'){if (stack.top() != '('){return false;}else{if (stack.empty()){return false;}stack.pop();}}else if (s[i] == ']'){if (stack.top()!='['){return false;}else{stack.pop();}}else{if (stack.top() != '{'){return false;}else{stack.pop();}}}}                           if (stack.empty()){return true;}         else{return false;}}
};

70. 最小栈

class MinStack {
public:MinStack() {}void push(int val) {_stk.push(val);if (_stkmin.empty()){_stkmin.push(val);}else{if (_stkmin.top() > val){_stkmin.push(val);}else{_stkmin.push(_stkmin.top());}}}void pop() {_stk.pop();_stkmin.pop();}int top() {return _stk.top();}int getMin() {return _stkmin.top();}private:stack<int> _stk;stack<int> _stkmin;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/