【面试HOT200】数组篇

系列综述：
💞目的：本系列是个人整理为了秋招面试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)/2
        if (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;
        else
            hi = 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

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

linux删除 buff/cache缓存

linux删除 buff/cache缓存

1.查看当前内存占用 free -h如图&#xff0c;缓存占用了将近9G&#xff0c;接下来进行清理 释放页缓存 echo 1 > /proc/sys/vm/drop_caches释放dentries和inodes echo 2 > /proc/sys/vm/drop_caches释放所有缓存 echo 3 > /proc/sys/vm/drop_caches再次查看&#…
阅读更多...
MQ

MQ

目录 MQ优点 异步 解耦 削峰填谷 mq的缺点 MQ常见的几种模式 Kafka、ActiveMQ、RabbitMQ、RocketMQ 区别 MQ优点 mq是一种常见的中间件&#xff0c;在项目中经常用到&#xff0c;它具有异步、解耦、削峰填谷的作用。 异步 比如下单流程&#xff0c;A服务—>B服务&a…
阅读更多...
为什么称FreeRTOS为轻量级OS，和Linux相比，有哪些具体的区别？

为什么称FreeRTOS为轻量级OS，和Linux相比，有哪些具体的区别？

要理解它们&#xff0c;就要看这些最终的概念是怎么来的&#xff0c;其实这些都是在不同资源&#xff08;硬件&#xff09;上处理不同场景问题所得的结果。 FreeRTOS一般跑在几十Mhz&#xff0c;几十KB的硬件上&#xff0c;比如Cortex-M系列MCU上&#xff0c;资源很有限&#…
阅读更多...
论文精读--GPT4

论文精读--GPT4

现有的所有模型都无法做到在线学习&#xff0c;能力有限&#xff0c;而让大模型拥有一个tools工具库&#xff0c;则可以使大模型变成一个交互式的工具去协调调用API完成任务&#xff0c;同时GPT4还联网了&#xff0c;可以不断地更新自己的知识库 多模态模型&#xff0c;接受文…
阅读更多...
面经分享（Flask,轻量级Web框架）

面经分享（Flask,轻量级Web框架）

1. Flask的核心特点 a. 轻量级&#xff1a;核心简洁&#xff0c;只提供了基本的功能&#xff0c;其他高级功能可以通过插件或扩展来添加。 b. 灵活性&#xff1a;允许开发者选择适合自己项目的组件和工具&#xff0c;没有强制的项目结构和设计模式。 c. 易于扩展&#xff1a;提…
阅读更多...
JVM 内存溢出排查

JVM 内存溢出排查

说明&#xff1a;记录一次JVM内存溢出的排查过程&#xff1b; 场景 项目开发完成后&#xff0c;首次提交到测试环境。测试、产品同事反馈页面先是操作响应慢&#xff0c;抛出超时异常&#xff0c;最后直接无法使用。查看日志后得知是内存溢出。 重启服务后&#xff0c;我对前…
阅读更多...
接口测试实战教程（加密解密攻防）

接口测试实战教程（加密解密攻防）

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 关注公众号【互联网杂货铺】&#xff0c;回复 1 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、对称加密 对称加密算法是共享密钥加密算法&#xff0c;在加…
阅读更多...
RuntimeError: Error compiling objects for extension虚拟环境和系统环境——添加、删除、修改环境变量

RuntimeError: Error compiling objects for extension虚拟环境和系统环境——添加、删除、修改环境变量

前言&#xff1a;因为一个报错RuntimeError: Error compiling objects for extension 没有配置cl.exe环境变量&#xff0c;我的应用场景是需要搞定虚拟环境变量配置 RuntimeError: Error compiling objects for extension手把手带你解决&#xff08;超详细&#xff09;-CSDN博…
阅读更多...
Mybatis 之 useGeneratedKeys

Mybatis 之 useGeneratedKeys

数据库中主键基本都设置为自增&#xff0c;当我们要插入一条数据想要获取这条数据的 Id 时&#xff0c;就可使用 Mybatis 中的 useGeneratedKeys 属性。 背景 这里以 苍穹外卖 中的 新增菜品 功能为例&#xff0c;有 菜品表(dish table)和 口味表(dish_flavor table)&#xf…
阅读更多...
HTML标签之有序列表，无序列表，自定义链表

HTML标签之有序列表，无序列表，自定义链表

无序列表 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-width, i…
阅读更多...
从零开始学数据分析之数据分析概述

从零开始学数据分析之数据分析概述

当今世界对信息技术的依赖程度在不断加深&#xff0c;每天都会有大量的数据产生&#xff0c;我们经常会感到数据越来越多&#xff0c;但是要从中发现有价值的信息却越来越难。 这里所说的信息&#xff0c;可以理解为对数据集处理之后的结果&#xff0c;是从数据集中提炼出的可用…
阅读更多...
redis 高可用与 持久化

redis 高可用与 持久化

目录 一 redis 高可用 &#xff08;一&#xff09;redis高可用技术 1&#xff0c;持久化 2&#xff0c;主从复制 3&#xff0c;哨兵 4&#xff0c;Cluster集群 二 redis 持久化 &#xff08;一&#xff09;持久化相关概念介绍 1&#xff0c;持久化的功能 2&…
阅读更多...
Pygame基础9-射击

Pygame基础9-射击

简介 玩家用鼠标控制飞机&#xff08;白色方块&#xff09;移动&#xff0c;按下鼠标后&#xff0c;玩家所在位置出现子弹&#xff0c;子弹匀速向右飞行。 代码 没有什么新的东西&#xff0c;使用两个精灵类表示玩家和子弹。 有一个细节需要注意&#xff0c;当子弹飞出屏幕…
阅读更多...
实战 | YOLOv8自定义数据集训练实现手势识别 (标注+训练+预测 保姆级教程--含数据集)

实战 | YOLOv8自定义数据集训练实现手势识别 (标注+训练+预测 保姆级教程--含数据集)

导 读 本文将手把手教你用YoloV8训练自己的数据集并实现手势识别。 安装环境 【1】安装torch, torchvision对应版本，这里先下载好，直接安装 pip install torch-1.13.1+cu116-cp38-cp38-win_amd64.whlpip install torchvision-0.14.1+cu116-cp38-cp38-win_amd64.whl 安装好…
阅读更多...
剑指offer打卡 JZ7 重建二叉树

剑指offer打卡 JZ7 重建二叉树

在牛客网刷的&#xff0c;还是跟leetcode一样非acm模式&#xff0c;由于急着暑期实习题量不固定&#xff0c;八股算法轮刷 打卡内容偏个人笔记&#xff0c;本人水平一般(代码随想录稀里糊涂刷了一遍)&#xff0c;从小白开始分析(甚至会分析语法)&#xff0c;尽量一题多解深入探…
阅读更多...
VSCode好用插件

VSCode好用插件

由于现在还是使用vue2&#xff0c;所以本文只记录vue2开发中好用的插件。 美化类插件不介绍了&#xff0c;那些貌似对生产力起不到什么大的帮助&#xff0c;纯粹的“唯心主义”罢了&#xff0c;但是如果你有兴趣的话可以查看上一篇博客&#xff1a;VSCode美化 1. vuter 简介&…
阅读更多...
LabelConvert: 目标检测和图像分割数据集格式转换工具

LabelConvert: 目标检测和图像分割数据集格式转换工具

LabelConvert LabelConvert是一个目标检测和图像分割的数据集格式转换工具&#xff0c;支持labelme、labelImg与YOLO、VOC和COCO 数据集格式之间的相互转换。 支持的转换格式 安装 pip install label_convert具体使用方法 由于文章篇幅所限&#xff0c;请移步LabelConvert官…
阅读更多...
左值与右值，以及c++11的相关特性。

左值与右值，以及c++11的相关特性。

目录 左值 右值 左值引用总结&#xff1a; 右值引用总结&#xff1a; 右值引用使用场景和意义&#xff1a; 1、左值引用的使用场景&#xff1a; 编译器优化1&#xff1a; 2、移动构造与移动赋值&#xff1a; 3、右值引用的使用场景&#xff1a; 编译器优化2&#xff1a…
阅读更多...
MATLAB科研绘图与学术图表绘制从入门到精通

MATLAB科研绘图与学术图表绘制从入门到精通

&#x1f482; 个人网站:【 摸鱼游戏】【神级代码资源网站】【工具大全】&#x1f91f; 一站式轻松构建小程序、Web网站、移动应用&#xff1a;&#x1f449;注册地址&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交…
阅读更多...
软件资源分享六：EPLAN Electric P8 2024 | Eplan 2024 中文版软件介绍+保姆级安装教程

软件资源分享六：EPLAN Electric P8 2024 | Eplan 2024 中文版软件介绍+保姆级安装教程

原文链接&#xff1a;安装激活教程 EPLAN Electric P8 2024 | Eplan 2024 中文版软件介绍安装教程 EPLAN 2024是一款电气设计软件&#xff0c;它可以用于自动化系统的设计、文档编制和维护。EPLAN可以对电气设计的各个方面进行完整的支持&#xff0c;包括电气控制系统、机械设…
阅读更多...
最新文章

Copyright @ 2022~2023