DAY19 2026.04.05
LeetCode51 N皇后 [回溯、递归]
回溯法。棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度。当row==n时，说明走到了叶子节点，收割结果
判断位置是否合法：不同行、不同列、不同斜线（判断左上斜、右上斜）。每一层递归只会选for循环里的一个元素往下，所以不用判断同行情况
LeetCode4 寻找两个正序数组的中位数 [二分查找]
思路一：利用额外辅助数组，将两数组按升序合并后，再找中位数
思路二：二分。在nums1和nums2中分别设置i、j分割点，当nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]时，说明此时i和j左侧部分是整个的左半部分，即可找到中位
分割点 i 的取值范围，这里 i 主要是表示在 nums1 中选取多少个元素到左半部分。当i = 0时，不选任何nums1的元素到左半部分 ；当i = 1时，选 nums1[0] 到左半部分；当i = m时，选所有 nums1 的元素到左半部分。因此要处理好nums1[i-1]、nums1[i]、nums2[j-1]、nums2[j]的边界情况
i的位置靠二分查找，j的位置由i推导而来，当nums1[i-1] > nums2[j]时，说明“绳头”过右，需要往左移动，right = i+1；当nums2[j-1] > nums1[i]时，说明“绳头”过左，需要往右移动，left = i+1
LeetCode146 LRU缓存 [链表、哈希]
双向链表+哈希表。使用双向链表来存储Node，使用哈希表来保证get和put是O(1)时间复杂度。初始有头尾虚拟节点
int get(int key)，如果关键字key存在于哈希表中，则返回关键字的值，同时将该Node删除并插入到head后；否则返回-1
void put(int key, int value)，如果关键字key已存在于哈希表中，则将该Node删除并插入到head后；如果不存在，则头插新Node在head后，同时判断当前大小是否超过规定容量。若超过，tail前的节点删除