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();
 */