1. 两数之和（为目标值） 3min1234567891011121314vector<int> twoSum(vector<int>& nums, int target){ umordered_map<int, int> hashtable; /* xiaoguo */ for(int i = 0; i < nums.size(); i++) { auto it = hashtable.find(target - nums[i]); if(it != hashtable.end()) return {it->second, i}; hashtable[nums[i]] = i; } return {};}

49. 字母异位词分组如何将异位词分到一组？ 对于每个字符串，对其进行字典排序，利用排序后的string作为map的key，将排序前的string推到value中 用到的数据结构为：unordered_map<string, vector> mp 最后将mp中的每个元素的second push_back到结果集ret中

48. 旋转图像对矩阵的原地旋转操作可通过转置并翻转来实现 本题要求完成90°旋转，可先求转置，再对每一行进行翻转 如果要旋转180°，可以先对列翻转，再对行翻转 如果要逆时针旋转90°，则先求转置，再对列进行翻转

207. 课程表我们可以将本题建模成一个求拓扑排序的问题：将每一门课看成一个节点，如果想要学习课程 A之前必须完成课程 B，那么我们从B到A连接一条有向边。这样以来，在拓扑排序中，B一定出现在 A的前面

42. 接雨水此题首先需知如何计算总雨水量： 总雨水量的计算需知数组中的每个数左侧和右侧的最高值，取二者较小值减去当前高度，即为当前点处能蓄水的量 如果不用空间换时间，计算每个点左右两侧的最大值都需要遍历一次所有数据 所以用两个数组leftMax和rightMax分别存储每个点左侧的最大值和右侧的最大值 最后再一次遍历计算总蓄水量

16. 最接近的三数之和相对于暴力解法，双指针能够通过首尾指针和合理移动，减少不合理情况的遍历，即a+b+c < target，则c向左移动，a+b+c > target，b向右移动 进一步可以总结出：若想要使两数之和逼近某一个目标值，可使用双指针对已排序数组进行查找

12. 整数转罗马数字12345678910111213141516// 处理上有优先级，对于当前的数，优先处理大于1000的部分，然后处理900，500，400.....（每一部分的处理方式也有固定的对应） --> 贪心算法string intToRoman(int num) { string res; vector<int> store{ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; vector<string> strs{ "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" }; int n = store.size(); for (int i = 0; i < n; i++) { while (num >= store[i]) { res.append(strs[i]); num -= store[i]; } } return res;}

回溯算法的写法：画出递归树，找到状态变量（回溯函数的参数）根据题意确立结束条件找准选择列表判断是否需要剪枝（去掉重复的集合，即去掉递归树上的某些分支）做出选择，递归调用，进入下一层撤销选择

4. 寻找两个正序数组的中位数123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354//二分查找//写一个查找第k大的函数，k值在运行过程中会慢慢减小int findKthElement(vector<int>& nums1, vector<int>& nums2, int k){ int m = nums1.size(); int n = nums2.size(); int index1 = 0; int index2 = 0; while (true) { //nums1中的指针位置已经到了末尾，直接在num2中找剩下的第k大 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]); } //边界检测，index如果加了k / 2 - 1越界了，就直接将新的index设置为数组的最后一位 int newIndex1 = min(index1 + k / 2 - 1, m - 1); int newIndex2 = min(index2 + k / 2 - 1, n - 1); int pivot1 = nums1[newIndex1]; int pivot2 = nums2[newIndex2]; if (pivot1 <= pivot2) { //更新k和index k -= newIndex1 - index1 + 1; index1 = newIndex1 + 1; } else { k -= newIndex2 - index2 + 1; index2 = newIndex2 + 1; } }}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int totalLength = nums1.size() + nums2.size(); if (totalLength % 2 == 1) { //奇数总数和偶数总数分开讨论 return findKthElement(nums1, nums2, (totalLength + 1) / 2); } else { return (findKthElement(nums1, nums2, totalLength / 2) + findKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0; }}