一：寻找两个正序数组的中位数

image-20251023172116711

1. 二分查找

寻找两个数组的中位数即是寻找第 k 小的数，那么对于每一个数组求k / 2 - 1，小的一个元素的左边值应当被排除，更新K值和索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int total = m + n;
        if (total & 1) return GetKvalue(nums1, nums2, (total + 1) / 2);
        else return ((GetKvalue(nums1, nums2, total / 2) + GetKvalue(nums1, nums2, total / 2 + 1)) / 2.0);
    }
    int GetKvalue(vector<int>& nums1, vector<int>& nums2, int k)
    {
        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0;
        int index2 = 0;
        while (true)
        {
            if (index1 == m) return nums2[index2 + k - 1];
            if (index2 == n) return nums1[index1 + k - 1];
            if (k == 1) return min(nums1[index1], nums2[index2]);
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pre1 = nums1[newIndex1];
            int pre2 = nums2[newIndex2];
            if (pre1 <= pre2)
            {
                k = k - (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else
            {
                k = k - (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
};

image-20251023172429622

2. 划分数组

这个题有点难，将两个数组进行划分，通常左边的最大值如果小于右边的最小值，那么中位数即可判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if (m > n) return findMedianSortedArrays(nums2, nums1);     // 保证第一个数组小
        int left = 0, right = m;        // 二分范围
        int median1 = 0;
        int median2 = 0;
        while (left <= right)
        {
            int i = (left + right) >> 1;        // 第一个数组的中间值
            int j = ((m + n + 1) >> 1) - i;       // 第二个数组的中间值
            int i_1 = i == 0 ? INT_MIN : nums1[i - 1];
            int iNew = i == m ? INT_MAX : nums1[i];
            int j_1 = j == 0 ? INT_MIN : nums2[j - 1];
            int jNew = j == n ? INT_MAX : nums2[j];
            if (i_1 <= jNew)
            {
                median1 = max(i_1, j_1);
                median2 = min(iNew, jNew);
                left = i + 1;
            } else
                right = i - 1;
        }
        return (m + n) & 1 ? median1 : (median1 + median2) / 2.0;
    }
};

image-20251023172444654

二：N 皇后

image-20251023172517079

1. 基于集合的回溯

使用回溯需要三步，选择、递归、撤销选择，在选择时需要避免行、列以及两个斜线不能冲突

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int len;
    vector<vector<string>> result;
    unordered_set<int> col;
    unordered_set<int> diaR;
    unordered_set<int> diaL;
    vector<vector<string>> solveNQueens(int n) {
        len = n;
        vector<string> board(len, string(n, '.'));
        recursion(0, board);
        return result;
    }
    void recursion(int row, vector<string> &board)
    {
        if (row == len)
        {
            result.emplace_back(board);     // 全部填充
            return;
        } 
        for (int i = 0; i < len; ++i)       // 对当前行遍历可行的列
        {
            if (col.count(i) || diaR.count(row - i) || diaL.count(row + i)) continue;       // 冲突则下一列
            board[row][i] = 'Q';        // 选择
            col.insert(i);
            diaR.insert(row - i);
            diaL.insert(row + i);
            recursion(row + 1, board);      // 递归
            board[row][i] = '.';        // 撤销
            col.erase(i);
            diaR.erase(row - i);
            diaL.erase(row + i);
        }
    }
};

image-20251023172548556

2. 基于位运算的回溯

这里使用二进制来表示每一列和斜边的位置情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int len;
    vector<vector<string>> result;
    vector<vector<string>> solveNQueens(int n) {
        len = n;
        vector<string> board(len, string(n, '.'));
        recursion(0, 0, 0, 0, board);
        return result;
    }
    void recursion(int row, int col, int digR, int digL, vector<string> &board)
    {
        if (row == len)
        {
            result.emplace_back(board);    
            return;
        } 
        int avail = ((1 << len) - 1) & (~(col | digR | digL));		// 可用位置
        while (avail != 0)
        {
            int p = avail & (-avail);		// 最低位的可用位置
            int colT = 0;
            int temp = p;
            while ((temp >>= 1) > 0) ++colT;		// 对应列
            board[row][colT] = 'Q';
            int next_col = col | p;		// 新的二进制
            int next_digR = (digR | p) >> 1;
            int next_digL = (digL | p) << 1;
            recursion(row + 1, next_col, next_digR, next_digL, board);
            board[row][colT] = '.';
            avail &= (~p);		// 取消可用位置
        }
    }
};

image-20251023172645628

三：二叉树中的最大路径和

image-20251023172723506

1. 递归

这里主要需要使用一个常数来记录最大值，因为不能回溯，而返回值不能叠加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int result = INT_MIN;
    int maxPathSum(TreeNode* root) {
        recursion(root);
        return result;
    }
    int recursion(TreeNode* node)
    {
        if (node == nullptr) return 0;
        int leftVal = max(recursion(node->left), 0);
        int rightVal = max(recursion(node->right), 0);
        result = max(result, node->val + leftVal + rightVal);
        return node->val + max(leftVal, rightVal);
    }
};

image-20251023172746258