临时工找工作网站做美缝,创建网站建设,wordpress restapi接口,企业网站建设绪论系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试coding部分的#xff0c;整理期间苛求每个算法题目#xff0c;平衡可读性与代码性能#xff08;leetcode运行复杂度均打败80%以上#xff09;。 #x1f970;来源#xff1a;材料主要源于… 系列综述 目的本系列是个人整理为了秋招面试coding部分的整理期间苛求每个算法题目平衡可读性与代码性能leetcode运行复杂度均打败80%以上。 来源材料主要源于【CodeTopHot200】进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证所有代码均优先参考最佳性能。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 基础题目二分查找基础知识相关例题 快速排序模糊划分基础知识相关例题 移除元素快慢指针两数之和带哈希缓存的查找三数之和排序三指针四数相加IIunordered_map的使用有序数组的平方双端指针 参考博客 点此到文末惊喜↩︎
基础题目
二分查找
基础知识
适应场景有序无重复的数组 有序一次比较即可确定需要查找的另一半效率高的关键无重复一旦有重复元素使用二分查找法返回的元素下标可能不是唯一需要进行左右的循环查找数组可以进行随机存取 细节 快速防溢出的除2mid L ((R - L)1) 防溢出如果L 和 R太大直接相加就有溢出的可能右移等价于除法算法但是效率高 使用前闭后闭的二分区域查找可以在查找target位置后再进行相同元素相连区域的定位操作。 leetcode题目704. 二分查找// *****************前闭后闭的基本二分查找可以代替下一种*******************
int search(vectorint nums, int target) {
// 0. 健壮性检查if(nums.size() 0) return -1;
// 1. 定义边界指针指向遍历数组区域的边界位置int left 0;int right nums.size() - 1; // 定义target在左闭右闭的区间里
// 2. 基本算法步骤的循环 while (left right) { // 前闭后闭用// 划分中间int mid left ((right - left)1); // 防止溢出 等同于(left right)/2if (target nums[mid]) { // 目标值在左区间right mid - 1; } else if (target nums[mid]) { // 目标值在右区间left mid 1; } else { // 找到目标值即相等时return mid; // 数组中找到目标值直接返回下标}}
// 3. 添加进行左右边界的定位操作// ...return left;// left为相等值未找到时应插入的位置也可使用-1表示
}相关例题
leetcode题目35. 在排序数组中查找元素的第一个和最后一个位置 先通过基本二分法查找目标元素出现的位置然后使用while(边界判断 值判断)获得target值的区间 ··· // 基本二分查找
// 寻找相似相邻区间的左右边界
int l mid;
int r mid;
if(nums[mid] ! target){return res;
}else{while (vec[left] target left 0) {--left;}while (vec[right] target right vec.size() - 1) {right;}
}
res[0]l;
res[1]r;
return res;
}搜索旋转排序数组 整数数组 nums 按升序排列但是可以进行循环移位然后进行target的查找使用时间复杂度为 O(log n) 的算法 思路 nums[0] nums[mid]0 - mid不包含旋转且nums[0] target nums[mid] 时 high 向前规约nums[mid] nums[0]0 - mid包含旋转target nums[mid] nums[0] 时向前规约target 在旋转位置到 mid 之间nums[mid] nums[0]nums[mid] nums[0] target 时向前规约target 在 0 到旋转位置之间其他情况向后规约nums[mid] nums[0]nums[0] targettarget nums[mid] 三项均为真或者只有一项为真时向后规约
int search(vectorint nums, int target) {int lo 0, hi nums.size() - 1;while (lo hi) {int mid (lo hi) / 2;if ((nums[0] target) ^ (nums[0] nums[mid]) ^ (target nums[mid]))lo mid 1;elsehi mid;}return lo hi nums[lo] target ? lo : -1;
}正序数组查找第k小二分查找 给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数算法的时间复杂度应该为 O(log (mn))
class Solution {
public:int findKthElm(vectorint nums1,vectorint nums2,int k){assert(1kknums1.size()nums2.size());int lemax(0,int(k-nums2.size())),rimin(k,int(nums1.size()));while(leri){int mle(ri-le)/2;if(nums2[k-m-1]nums1[m]) lem1;//这为什么只写一个条件因为这是二分的排除条件不是目标的符合条件相当于排除条件最后的结果才是符合条件的结果else rim;}//循环结束时的位置le即为所求位置第k小即为max(nums1[le-1]),nums2[k-le-1])但是由于le可以为0、k,所以//le-1或者k-le-1可能不存在所以下面单独判断下int nums1LeftMaxle0?INT_MIN:nums1[le-1];int nums2LeftMaxlek?INT_MIN:nums2[k-le-1];return max(nums1LeftMax,nums2LeftMax);}double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int nnums1.size()nums2.size();if(n1){//两个数组长度和为奇数return findKthElm(nums1,nums2,(n1)1);}else{//为偶数return (findKthElm(nums1,nums2,n1)findKthElm(nums1,nums2,(n1)1))/2.0;}}
};快速排序模糊划分
基础知识
基本思想 选择基准在待排序列中按照某种方式挑出一个元素作为 “基准”pivot分割操作以该基准在序列中的实际位置把序列分成两个子序列。此时在基准左边的元素都比该基准小在基准右边的元素都比基准大递归地对两个序列进行快速排序直到序列为空或者只有一个元素。 特点 不产生有序子序列但每次排序后会将基准元素放到最终位置上每次排序划分子区间越相近越能发挥快排优势每次可将无序线性表划分成小值区、pivot和大值区 算法
int partition(vectorint vec, int left, int right) {// 将第一个元素随机化避免有序数组导致的划分失衡int idx left rand() % (right - left 1);swap(vec[left], vec[idx]);// 初始化划分元素的位置和值int pos left;int pivot vec[left];// 算法部分while (left right) {// 从后向前找 小于 基准元素的while (vec[right] pivot left right) --right;// 从前向后找 大于 基准元素的while (vec[left] pivot left right) left;swap(vec[left], vec[right]);}swap(vec[left], vec[pos]);return left;
}void QuickSort(vectorint vec, int left, int right) {if (left right) return ;int pivot partition(vec, left, right);QuickSort(vec, left, pivot-1);QuickSort(vec, pivot1, right);
}相关例题 数组中的第K个最大元素 题目给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。思路 快排划分时间复杂度O(N) 空间复杂度O(1)堆求解时间复杂度O(NlogK) 空间复杂度O(K)
// 快排划分
int findKthLargst(vectorint nums, int k) {// 划分函数(key从大到小)auto partition [](int left, int right)-int{// 随机化避免划分失败int idx left rand() % (right-left1);swap(nums[left], nums[idx]);// 划分元素的位置和值int pos left;int pivot nums[left];while (left right) {while (nums[right] pivot left right) --right;while (nums[left] pivot left right) left;swap(nums[left], nums[right]);}// 划分转移swap(nums[left], nums[pos]);return left;};// 算法int left 0;int right nums.size()-1;// 找到正序数组中的第k大while (left right) {int mid partition(left, right);if (k mid1) {return nums[mid];} else if (k mid1) {left mid1;} else {right mid-1;}}return 0;
}
// 堆处理
int findKthLargest(vectorint nums, int k) {priority_queueint pq;for (auto i : nums) {pq.push(i);}for (int i 0; i k-1; i) {pq.pop();}return pq.top();
}移除元素快慢指针
leetcode题目27. 移除元素 要求使用快慢指针以O(n)的时间复杂度和O(1)的空间复杂度进行处理注意点 快指针fast用于条件判断慢指针slow用于位置保存尽量使用for循环避免结尾迭代条件的忘记 int removeElement(vectorint nums, int val) {int slow 0, fast 0; // 定义快慢指针for (; fast nums.size(); fast) {// 快指针进行判断判断if (nums[fast] ! val) {nums[slow] nums[fast];slow;}}nums.resize(slow);return slow;
}两数之和带哈希缓存的查找
leetcode1. 两数之和思路 每次获取一个元素先判断是否成功如果不成功则将元素放入哈希缓存表中 vectorint twoSum(vectorint nums, int target) {vectorint res;unordered_mapint, int umap;for (int i 0; i nums.size(); i) {auto itr umap.find(target-nums[i]);if (itr ! umap.end()) {res.emplace_back(i);res.emplace_back(itr-second);}umap[nums[i]] i;}return res;
}三数之和排序三指针
15. 三数之和 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。答案中不可以包含重复的三元组。 思路 固定一个指针进行问题的降维然后另外两个指针进行区间的运算
vectorvectorint threeSum(vectorint nums) {const int len nums.size();vectorvectorint res;sort(nums.begin(), nums.end());// 健壮性检查 if (nums.size() 3 || nums[0] 0 || nums[nums.size()-1] 0)return res;// 算法部分// 找出a b c 0// a nums[i], b nums[left], c nums[right]for (int i 0; i nums.size(); i) {// 排序后若第一个元素大于零则表示后面元素不可能凑成三元组if (nums[i] 0) return res;// 正确去重方法比较i和i1会遗漏掉第一个元素作为首元素的情况if (i 0 nums[i] nums[i - 1]) continue;// 确定剩余两个元素的区间int left i 1;int right nums.size() - 1;while (left right) {if (nums[i] nums[left] nums[right] 0) right--;else if (nums[i] nums[left] nums[right] 0) left;else {// 压入第一个然后对后面的去重res.push_back(vectorint{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后对b 和 c去重while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;// 找到答案时双指针同时收缩right--;left;}}}return res;
}注意点 去重操作 if (nums[i] nums[i 1]) continue;会导致[-1,-1,2]情况的遗漏if (i 0 nums[i] nums[i - 1]) continue;优先判断左部分不会影响右部分
四数相加IIunordered_map的使用
leetcode题目四数相加 记录去重和常数级查找通过unordered_set解决 int fourSumCount(vectorint A, vectorint B, vectorint C, vectorint D) {unordered_mapint, int umap; //key:ab的数值value:ab数值出现的次数// 遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中for (int a : A) {for (int b : B) {umap[a b];}}int count 0; // 统计abcd 0 出现的次数// 在遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话// 就把map中key对应的value也就是出现次数统计出来。for (int c : C) {for (int d : D) {int val -(cd);if (umap.count(val) 0) {count umap[val];}}}return count;
}有序数组的平方双端指针
leetcode题目977. 有序数组的平方 思路 正常思路从0开始向中间 辅助空间逆向思路left和right两个指针分别从两端向中间进行夹逼
vectorint sortedSquares(vectorint nums) {// 健壮性检查// 初始化const int len nums.size();int left 0;int right len-1;vectorint res(len);// 算法部分for (int index len-1; left right; --index) {if (nums[left] * nums[left] nums[right] *nums[right]) {res[index] nums[left] * nums[left];left;} else {res[index] nums[right] *nums[right];--right;}}return res;
}少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 「代码随想录」 codetop前200 力扣LeetCode旋转数组——极简 Solution
