面试资料

加油站在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。 这个题上学期的算法课老师出过一个简易版的，只有一个数组既是gas又是cost。而且测试数据很简单所以直接ac了。这个题就直接写不出来了 123456789101112131415161718192021222324class Solution {public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int n = gas.size(); int cur_gas = 0; int start_index = 0 ...

数的范围给定一个按照升序排列的长度为 n的整数数组，以及 q 个查询。 对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。 如果数组中不存在该元素，则返回 -1 -1。 输入格式第一行包含整数 n 和 q，表示数组长度和询问个数。 第二行包含 n 个整数（均在 1∼100001∼10000 范围内），表示完整数组。 接下来 q 行，每行包含一个整数 k，表示一个询问元素。 输出格式共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。 如果数组中不存在该元素，则返回 -1 -1。 数据范围1≤n≤1000001≤q≤100001≤k≤10000 经典的二分模板题。 题目要找k的左边界和右边界。 二分查找找的是边界。 1f(a[mid]<=k) //找的就是<=k的边界，也就是下面图片从最左边到 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>using namespace s ...

O(1) 时间插入、删除和获取随机元素实现RandomizedSet 类： RandomizedSet() 初始化 RandomizedSet 对象 bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。 bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。 int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。 要求常数时间下插入和删除元素所以考虑哈希表。随机返回集合中的一项也就是可以对集合随机访问，但是哈希表不能做到这点，所以还要引入顺序表来支持随机访问。 这个题的处理方式很像静态链表，就是用数组构建的链表，链表在空间上是连续的。 设置哈希表hash<元素值，下标>，动态数组a。a的下标对应hash的下标，a的元素值对应hash的元素值。 对应关系 ...

除自身以外数组的乘机给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。 这个题最显然的解法就是把所有元素全乘起来，然后除以nums[i]，但是除法会出现除数为0的情况，而且题目要求不能用除法。 类似前缀和，这个题用的是前缀积。 设置前缀积数组l[]和后缀积r[]数组，分别存放nums[i]和nums[i]之后所有数的乘积（不包括nums[i]）。 注意，后缀积需要逆序求。 12345678910111213141516class Solution {public: vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int> l(n,1),r ...

逆序对的数量给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。 逆序对的定义如下：对于数列的第 i 个和第 j个元素，如果满足 i<j且 a[i]>a[j]，则其为一个逆序对；否则不是。 输入格式第一行包含整数 n，表示数列的长度。 第二行包含 n 个整数，表示整个数列。 输出格式输出一个整数，表示逆序对的个数。 数据范围1≤n≤100000，数列中的元素的取值范围 [1,109] 归并排序合并时可以判断i<j且 a[i]>a[j]。 写递归先确定函数的返回值是什么，显然递归函数的返回值应该是逆序对的个数。 然后确定返回条件：数组只有一个元素时，逆序对个数为0，返回0. 逆序对的总个数等于两部分的逆序对之和，而每个部分的逆序对个数为mid-i+1。最后将ans返回 123456789101112131415161718192021222324252627282930313233#include<iostream>using namespace std;const int N = 1e5+10;int a[N];int t[N];long ...

归并排序给定你一个长度为 n 的整数数列。 请你使用归并排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 归并排序的思想是分治，先将数组一分为二，分为[l,mid]和[mid+1,r]重复这个操作直到分为只有一个元素，即l==r时return。 数组两两合并，由于是从只有一个元素开始返回，所以保证每次都是两个有序数组合并。 1234567891011121314151617181920212223242526#include<iostream>using namespace std;const int N = 1e5+10;int a[N];int t[N];void merge(int l,int r){ if(l==r) return; int mid=l+r>>1,i=l,j=mid+1,k=0; merge(l,mid); merge(mid+1,r); while(i<=mid&&j<=r){ if(a[i]<a[j]) t[k++]= ...

第k个数给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k个数。 输入格式第一行包含两个整数 n 和 k。 第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整数数列。 输出格式输出一个整数，表示数列的第 k 小数。 最暴力的做法是把数组全部排序然后输出。 但其实可以不用全部排序，只排列一部分就能得到答案。 每趟排序后pivot左边的数全部小于等于pivot，右边的数全部大于等于pivot。所以每趟排序后判断j 和k的关系，决定排序哪一边。 1234567891011121314151617181920212223242526#include<iostream>#define N 100000using namespace std;int a[N];int quick_select(int l,int r,int k){ if(l==r) return a[l]; int x=a[l+r>>1]; int i=l-1,j=r+1; while(i<j) ...

快速排序快速排序有三个地方容易写错，今天终于全弄明白了。 先来看代码 1234567891011121314151617181920212223242526#include<iostream>using namespace std;const int N = 1e5+10;int a[N];void quick_sort(int l,int r){ if(l==r) return; int i=l-1,j=r+1; int mid=a[l+r>>1];//易错点1 while(i<j){ while(a[--j]>mid); while(a[++i]<mid); if(i<j) //易错点2 swap(a[i],a[j]); } quick_sort(l,j); quick_sort(j+1,r);//易错点3}int main(){ int n; cin>>n ...

H指数给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，**h 指数** 是其中最大的那个。 这个H指数的定义非常绕。第一次做的时候有思路，代码就是写不出来。 翻译过来就是nums[i]大于等于[i,n-1]的长度，求满足这个条件的长度最大值。 要使长度为n-i最大，则i取最小值。 123456789101112class Solution {public: int hIndex(vector<int>& nums) { sort(nums.begin(),nums.end()); int n=nums.size(); for(int i=0;i<n;i++){ if( ...

跳跃游戏 II给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处: 0 <= j <= nums[i] i + j < n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 这个有点难度，不会写。 要求最小跳跃次数，也就是每次尽可能多走。 元素nums[i]的覆盖范围是**[i,i+nums[i]]**,也就是从i位置能跳到的位置，每次跳跃到覆盖范围最大的位置就可以保证步数最小。 设置覆盖范围的右端点为end，i==end时，说明覆盖范围遍历完，跳跃次数+1.同时在遍历过程中，求出覆盖范围内的元素的最大覆盖范围，并更新end，也就是跳跃整个最大覆盖范围。 12345678910111213141516171819class Solution {public: int jump(vector<in ...