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();
*/
原文地址：https://blog.csdn.net/meihaoshy/article/details/144297765
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！