【面试HOT200】数组篇

news/2024/6/15 15:10:43/文章来源:https://blog.csdn.net/qq_43840665/article/details/134813735

系列综述:
💞目的:本系列是个人整理为了秋招面试coding部分的,整理期间苛求每个算法题目,平衡可读性代码性能(leetcode运行复杂度均打败80%以上)。
🥰来源:材料主要源于【CodeTopHot200】进行的,每个知识点的修正和深入主要参考各平台大佬的文章,其中也可能含有少量的个人实验自证,所有代码均优先参考最佳性能。
🤭结语:如果有帮到你的地方,就点个赞关注一下呗,谢谢🎈🎄🌷!!!
🌈【C++】秋招&实习面经汇总篇


文章目录

    • 基础题目
      • 二分查找
        • 基础知识
        • 相关例题
      • 快速排序(模糊划分)
        • 基础知识
        • 相关例题
      • 移除元素(快慢指针)
      • 两数之和(带哈希缓存的查找)
      • 三数之和(排序+三指针)
      • 四数相加II(unordered_map的使用)
      • 有序数组的平方(双端指针)
    • 参考博客


😊点此到文末惊喜↩︎

基础题目

二分查找

基础知识
  1. 适应场景:有序无重复的数组
    • 有序:一次比较即可确定需要查找的另一半,效率高的关键
    • 无重复:一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一,需要进行左右的循环查找
    • 数组:可以进行随机存取
  2. 细节
    • 快速防溢出的除2:mid = L + ((R - L)>>1)
      • 防溢出:如果L 和 R太大,直接相加就有溢出的可能
      • 右移:等价于除法算法,但是效率高
    • 使用前闭后闭的二分区域查找,可以在查找target位置后再进行相同元素相连区域的定位操作。
  3. leetcode题目:704. 二分查找
    // *****************前闭后闭的基本二分查找,可以代替下一种*******************
    int search(vector<int>& 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表示
    }
    
相关例题
  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;
    }
    
    1. 搜索旋转排序数组
    • 整数数组 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] > target,target > nums[mid] 三项均为真或者只有一项为真时向后规约
int search(vector<int>& 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;
}
  1. 正序数组查找第k小(二分查找)
    • 给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数
    • 算法的时间复杂度应该为 O(log (m+n))
class Solution {
public:int findKthElm(vector<int>& nums1,vector<int>& nums2,int k){assert(1<=k&&k<=nums1.size()+nums2.size());int le=max(0,int(k-nums2.size())),ri=min(k,int(nums1.size()));while(le<ri){int m=le+(ri-le)/2;if(nums2[k-m-1]>nums1[m]) le=m+1;//这为什么只写一个条件?!因为这是二分的排除条件,不是目标的符合条件,相当于排除条件,最后的结果才是符合条件的结果else ri=m;}//循环结束时的位置le即为所求位置,第k小即为max(nums1[le-1]),nums2[k-le-1]),但是由于le可以为0、k,所以//le-1或者k-le-1可能不存在所以下面单独判断下int nums1LeftMax=le==0?INT_MIN:nums1[le-1];int nums2LeftMax=le==k?INT_MIN:nums2[k-le-1];return max(nums1LeftMax,nums2LeftMax);}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n=nums1.size()+nums2.size();if(n&1){//两个数组长度和为奇数return findKthElm(nums1,nums2,(n>>1)+1);}else{//为偶数return (findKthElm(nums1,nums2,n>>1)+findKthElm(nums1,nums2,(n>>1)+1))/2.0;}}
};

快速排序(模糊划分)

基础知识
  1. 基本思想
    • 选择基准:在待排序列中,按照某种方式挑出一个元素,作为 “基准”(pivot)
    • 分割操作:以该基准在序列中的实际位置,把序列分成两个子序列。此时,在基准左边的元素都比该基准小,在基准右边的元素都比基准大
    • 递归地对两个序列进行快速排序,直到序列为空或者只有一个元素。
  2. 特点
    • 不产生有序子序列,但每次排序后会将基准元素放到最终位置上
    • 每次排序划分子区间越相近越能发挥快排优势
    • 每次可将无序线性表划分成小值区pivot大值区
  3. 算法
int partition(vector<int> &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(vector<int> &vec, int left, int right) {if (left > right) return ;int pivot = partition(vec, left, right);QuickSort(vec, left, pivot-1);QuickSort(vec, pivot+1, right);
}

在这里插入图片描述

相关例题
    1. 数组中的第K个最大元素
    • 题目:给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
    • 思路
      • 快排划分:时间复杂度:O(N) 空间复杂度:O(1)
      • 堆求解:时间复杂度:O(Nlog⁡K) 空间复杂度:O(K)
// 快排划分 
int findKthLargst(vector<int>& nums, int k) {// 划分函数(key:从大到小)auto partition = [&](int left, int right)->int{// 随机化:避免划分失败int idx = left + rand() % (right-left+1);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 == mid+1) {return nums[mid];} else if (k > mid+1) {left = mid+1;} else {right = mid-1;}}return 0;
}
// 堆处理
int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq;for (auto &i : nums) {pq.push(i);}for (int i = 0; i < k-1; ++i) {pq.pop();}return pq.top();
}

移除元素(快慢指针)

  1. leetcode题目:27. 移除元素
    • 要求:使用快慢指针以O(n)的时间复杂度和O(1)的空间复杂度进行处理
    • 注意点
      • 快指针fast用于条件判断,慢指针slow用于位置保存
      • 尽量使用for循环避免结尾迭代条件的忘记
    int removeElement(vector<int>& 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;
    }
    

两数之和(带哈希缓存的查找)

  1. leetcode1. 两数之和
  2. 思路
    • 每次获取一个元素,先判断是否成功,如果不成功则将元素放入哈希缓存表中
    vector<int> twoSum(vector<int>& nums, int target) {vector<int> res;unordered_map<int, 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;
    }
    

三数之和(排序+三指针)

  1. 15. 三数之和
    • 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
    • 答案中不可以包含重复的三元组。
  2. 思路
    • 固定一个指针进行问题的降维,然后另外两个指针进行区间的运算
      请添加图片描述
vector<vector<int>> threeSum(vector<int>& nums) {const int len = nums.size();vector<vector<int>> 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和i+1会遗漏掉第一个元素作为首元素的情况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(vector<int>{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;
}
  1. 注意点
    • 去重操作
      • if (nums[i] == nums[i + 1]) continue;会导致[-1,-1,2]情况的遗漏
      • if (i > 0 && nums[i] == nums[i - 1]) continue;优先判断左部分,不会影响右部分

四数相加II(unordered_map的使用)

  1. leetcode题目:四数相加
    • 记录去重常数级查找通过unordered_set解决
      在这里插入图片描述
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {unordered_map<int, int> umap; //key:a+b的数值,value:a+b数值出现的次数// 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中for (int a : A) {for (int b : B) {umap[a + b]++;}}int count = 0; // 统计a+b+c+d = 0 出现的次数// 在遍历大C和大D数组,找到如果 0-(c+d) 在map中出现过的话// 就把map中key对应的value也就是出现次数统计出来。for (int c : C) {for (int d : D) {int val = -(c+d);if (umap.count(val) > 0) {count += umap[val];}}}return count;
    }
    

有序数组的平方(双端指针)

  1. leetcode题目:977. 有序数组的平方
    在这里插入图片描述
  2. 思路:
    • 正常思路:从0开始向中间 + 辅助空间
    • 逆向思路:left和right两个指针分别从两端向中间进行夹逼
vector<int> sortedSquares(vector<int>& nums) {// 健壮性检查// 初始化const int len = nums.size();int left = 0;int right = len-1;vector<int> 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;
}


少年,我观你骨骼清奇,颖悟绝伦,必成人中龙凤。
不如点赞·收藏·关注一波

🚩点此跳转到首行↩︎

参考博客

  1. 「代码随想录」
  2. codetop前200
  3. 力扣(LeetCode)
  4. 旋转数组——极简 Solution

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1035097.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

对【AI技术创业】有哪些机会进行分析和引导

文章目录 方向一&#xff1a;行业解决方案,以下是一些常见的行业解决方案&#xff1a;方向二&#xff1a;智能产品和服务,以下是一些智能产品和服务的示例&#xff1a;方向三&#xff1a;教育和培训 1.智能客户服务&#xff1a; 利用自然语言处理&#xff08;NLP&#xff09;和…

京东云16核64G云服务器租用优惠价格500元1个月,35M带宽

京东云16核64G云服务器租用优惠价格500元1个月、5168元一年&#xff0c;35M带宽&#xff0c;配置为&#xff1a;16C64G-450G SSD系统盘-35M带宽-8000G月流量 华北-北京&#xff0c;京东云活动页面 yunfuwuqiba.com/go/jd 活动链接打开如下图&#xff1a; 京东云16核64G云服务器…

Transformers in Vision:A Survey 阅读笔记

ACM上的一篇综述&#xff0c;讨论Transformer在CV上的应用。 摘要&#xff1a; Among their salient benefits,Transformers enable modeling long dependencies between inputsequence elements and support parallel processing of sequence as compared to recurrent networ…

echarts 地图 自己圈地图 乡镇街道

这个是方式是我实在不愿意做的&#xff01; 如果有现成的最好&#xff0c;没有办法的情况下再用这个东西。 今天公司有一个项目&#xff0c;地方划分了一块区域&#xff0c;但是国家没有审核&#xff0c;但是项目里面用到了一个地图展示数据&#xff01;然后就需要我们自己把…

【爬虫框架Scrapy】01 开启Scrapy之路

爬虫基础专栏&#xff1a;http://t.csdnimg.cn/r9gt9 前言 如果你没有爬虫基础&#xff0c;相信我&#xff0c;不要进行下去&#xff0c;没什么意义&#xff0c;你会撞的头破血流&#xff0c;最后破灭你那本就不多的兴趣选择放弃&#xff01;&#xff01;&#xff01; OK&…

3D检测:从pointnet,voxelnet,pointpillar到centerpoint

记录centerpoint学习笔记。目前被引用1275次&#xff0c;非常高。 地址&#xff1a;Center-Based 3D Object Detection and Tracking (thecvf.com) GitHub - tianweiy/CenterPoint CenterPoint&#xff1a;三维点云目标检测算法梳理及最新进展&#xff08;CVPR2021&#xff…

重读Java设计模式: 深入探讨建造者模式,构建复杂对象的优雅解决方案

引言 在软件开发中&#xff0c;有时需要构建具有复杂结构的对象&#xff0c;如果直接使用构造函数或者 setter 方法逐个设置对象的属性&#xff0c;会导致代码变得冗长、难以维护&#xff0c;并且容易出错。为了解决这个问题&#xff0c;我们可以使用建造者模式。 一、建造者…

HarmonyOS实战开发-slider组件的使用

介绍 本篇Codelab主要介绍slider滑动条组件的使用。如图所示拖动对应滑动条调节风车的旋转速度以及缩放比例。 相关概念 slider组件&#xff1a;滑动条组件&#xff0c;通常用于快速调节设置值&#xff0c;如音量调节、亮度调节等应用场景。 环境搭建 软件要求 DevEco Stu…

基于YOLOV5+Pyqt5农作物叶片病害检测系统

1、引言 农作物病害的精准检测与识别是推动农业生产智能化与现代化发展的重要举措。随着计算机视觉技术的发展&#xff0c;深度学习方法已得到快速应用&#xff0c;利用卷积神经网络进行农作物病害检测与识别成为近年来研究的热点。基于传统农作物病害识别方法&#xff0c;分析…

EXCEL VBA将word里面的指定的关键词替换掉后并标记红色字体

EXCEL VBA将word里面的指定的关键词替换掉后并标记红色字体 Sub 开关() Call 新建副本 Call ReplaceAndHighlightInFolder End Sub Sub 新建副本()fpath ThisWorkbook.Path & "\"Dim MyFile As ObjectSet MyFile CreateObject("Scripting.FileSystemObjec…

MySQL数据库(数据库连接池)

文章目录 1.批处理应用1.基本介绍2.批处理演示1.创建测试表2.修改url3.编写java代码 3.批处理源码分析 2.数据库连接池1.传统连接弊端分析2.数据库连接池基本介绍1.概念介绍2.数据库连接池示意图3.数据库连接池种类 3.C3P0连接池1.环境配置1.导入jar包2.将整个lib添加到项目中3…

商业分析师BA与数据分析有什么关系?

文章主题:BA工作与数据分析 分享嘉宾&#xff1a;丛珊 职业&#xff1a;某事业单位BA分析师 在实际工作中&#xff0c;需求分析工作可以有多种分类方法&#xff0c;对于大型、集成型信息系统的需求分析&#xff0c;通常可以区分为业务需求、功能需求、数据需求、性能需求与安…

在java开发中平方怎么表示?平方表示的方法有哪几种?

在java开发中平方怎么表示&#xff1f;平方表示的方法有哪几种&#xff1f; 在我们计算一个数的几次方的时候。我们按照课堂中老师的教法就是在一个数的右上角写上一个小小的数字用来表示一个数的几次方&#xff0c;那么大家知道“在java开发中平方怎么表示吗&#xff1f;“和…

【区块链 链外交易】SoK Off The Chain Transactions

SoK Off The Chain Transactions 摘要 本文对区块链进行了简单介绍,分析目前区块链的缺点——交易吞吐量和速度慢的原因,在此基础上引出解决此问题的方法,也是本轮将要论述的主题——链外交易。之后介绍了链外交易的基本概念和结构,并对两种类型的链外交易:通道和信任链…

在线版的超级马里奥 Super Mario HTML5

原本是在csdn资源找个代码学习的&#xff0c;无奈下载了几份都是垃圾代码(下载了几份都是) 废话不多说&#xff0c;直接上干活。代码、音效、图片、样式都包含 <!doctype html> <html> <head> <meta charsetutf-8 /> <title>Super Mario HTML5 …

VScode-配置文件

导入配置文件 ShiftCtrlp 输入&#xff1a; import 选择文件 点击确认 导出配置文件 设置选择导出 确认导出 保存为本地文件 保存文件

Uibot6.0 (RPA财务机器人师资培训第6天 )发票验真机器人案例实战

类似于小北的这篇博客&#xff1a;Uibot (RPA设计软件&#xff09;Mage AI智能识别&#xff08;发票识别&#xff09;———课前材料五_uibot 添加mageai-CSDN博客https://blog.csdn.net/Zhiyilang/article/details/135591297?spm1001.2014.3001.5501训练网站&#xff1a;泓江…

前端学习<二>CSS基础——13-CSS3属性:Flex布局图文详解

前言 CSS3中的 flex 属性&#xff0c;在布局方面做了非常大的改进&#xff0c;使得我们对多个元素之间的布局排列变得十分灵活&#xff0c;适应性非常强。其强大的伸缩性和自适应性&#xff0c;在网页开中可以发挥极大的作用。 flex 初体验 我们先来看看下面这个最简单的布局…

什么是CSS?

一.CSS&#xff08;层叠样式表&#xff09;&#xff1a;是一种用于描述网页内容任何呈现的样式的语言&#xff0c;它和html&#xff08;超文本标记语言&#xff09;一起用于创建网页和Wed应用程序。 W3C标准&#xff1a;网页主要由三部分组成 结构&#xff1a;html 表现&#x…

B+树:高效管理大规模数据的关键工具

引言 数据库技术已经成为现代信息社会的重要支柱&#xff0c;无论是互联网巨头、金融机构、医疗系统还是智能设备&#xff0c;都离不开数据库的支持。数据库的性能和效率直接关系到这些系统的稳定性和用户体验&#xff0c;而数据库存储结构则是决定其性能的核心因素之一 B树作…