面试资料

有效的数独请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 注意： 一个有效的数独（部分已被填充）不一定是可解的。 只需要根据以上规则，验证已经填入的数字是否有效即可。 空白格用 '.' 表示。 示例 1： 1234567891011输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","." ...

模拟栈实现一个栈，栈初始为空，支持四种操作： push x – 向栈顶插入一个数 x𝑥； pop – 从栈顶弹出一个数； empty – 判断栈是否为空； query – 查询栈顶元素。 现在要对栈进行 𝑀 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。 输入格式第一行包含整数 𝑀，表示操作次数。 接下来 𝑀 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。 输出格式对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。 其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。 数据范围1≤M≤100000,1≤x≤10^9所有操作保证合法。 输入样例：123456789101110push 5querypush 6popquerypopemptypush 4queryempty 输出样例：1234555YES4NO 用数组模拟栈 12345678910111213141516171819202122232425262728293 ...

双链表实现一个双链表，双链表初始为空，支持 5 种操作： 在最左侧插入一个数； 在最右侧插入一个数； 将第𝑘 个插入的数删除； 在第 𝑘 个插入的数左侧插入一个数； 在第 𝑘 个插入的数右侧插入一个数 现在要对该链表进行 𝑀 次操作，进行完所有操作后，从左到右输出整个链表。 注意:题目中第 𝑘 个插入的数并不是指当前链表的第 𝑘 个数。例如操作过程中一共插入了 𝑛 个数，则按照插入的时间顺序，这 𝑛 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 𝑛 个插入的数。 输入格式第一行包含整数 𝑀，表示操作次数。 接下来 𝑀 行，每行包含一个操作命令，操作命令可能为以下几种： L x，表示在链表的最左端插入数 𝑥。 R x，表示在链表的最右端插入数 𝑥。 D k，表示将第 𝑘 个插入的数删除。 IL k x，表示在第 𝑘 个插入的数左侧插入一个数。 IR k x，表示在第 𝑘 个插入的数右侧插入一个数。 输出格式共一行，将整个链表从左到右输出。 数据范围1≤M≤100000所有操作保证合法。 输入样例：123456789101110R 7D ...

单链表实现一个单链表，链表初始为空，支持三种操作： 向链表头插入一个数； 删除第 k 个插入的数后面的一个数； 在第 k 个插入的数后插入一个数。 现在要对该链表进行 𝑀 次操作，进行完所有操作后，从头到尾输出整个链表。 注意:题目中第 𝑘 个插入的数并不是指当前链表的第 𝑘 个数。例如操作过程中一共插入了 𝑛 个数，则按照插入的时间顺序，这 𝑛 个数依次为：第 11 个插入的数，第 22 个插入的数，…第 𝑛 个插入的数。 输入格式第一行包含整数 𝑀，表示操作次数。 接下来𝑀 行，每行包含一个操作命令，操作命令可能为以下几种： H x，表示向链表头插入一个数 𝑥。 D k，表示删除第 𝑘 个插入的数后面的数（当 𝑘 为 0 时，表示删除头结点）。 I k x，表示在第 𝑘 个插入的数后面插入一个数𝑥（此操作中 k𝑘 均大于 0）。 输出格式共一行，将整个链表从头到尾输出。 数据范围1≤M≤100000所有操作保证合法。 输入样例：123456789101110H 9I 1 1D 1D 0H 6I 3 6I 4 5I 4 5I 3 4D 6 输出样 ...

区间合并给定 n 个区间 [li,ri]，要求合并所有有交集的区间。 注意如果在端点处相交，也算有交集。 输出合并完成后的区间个数。 例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。 输入格式第一行包含整数 n。 接下来 n 行，每行包含两个整数 l 和 r。 输出格式共一行，包含一个整数，表示合并区间完成后的区间个数。 数据范围1≤n≤100000,−10^9≤li≤ri≤10^9 输入样例：12345651 22 45 67 87 9 输出样例：13 将区间的左右端点存储起来，将左端点排序后分类讨论。 12345678910111213141516171819202122232425262728293031323334353637#include<iostream>#include<vector>#include<algorithm>using namespace std;vector<pair<int,int>> a,res;int main(){ int n; cin&g ...

区间和假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。 现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。 接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r][�,�] 之间的所有数的和。 输入格式第一行包含两个整数 n 和 m。 接下来 n 行，每行包含两个整数 x 和 c。 再接下来 m 行，每行包含两个整数 l 和 r。 输出格式共 m 行，每行输出一个询问中所求的区间内数字和。 数据范围−10^9≤x≤10^9,1≤n,m≤10^5,−10^9≤l≤r≤10^9,−10000≤c≤10000 输入样例：12345673 31 23 67 51 34 67 8 输出样例：123805 数轴的长度是10的9次方级别，需要进增加和查询的点的数量是10的5次方级别。这些点在数轴上的分布非常稀疏，如果直接使用前缀和会超时。 考虑把这些稀疏的点通过一个映射关系映射到一块连续的区域，操作次数就会变为10的5次方级别，再使用前缀和就可以了。 把所有需要进行增加和查询的点记录到all数组里，对数组进行排序。 用二分找到这个点 ...

二进制中1的个数给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 11 的个数。 输入格式第一行包含整数 n。 第二行包含 n 个整数，表示整个数列。 输出格式共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 11 的个数。 数据范围1≤n≤1000001,0≤数列中元素的值≤1090≤数列中元素的值≤109 输入样例：1251 2 3 4 5 输出样例：11 1 2 1 2 将十进制数与1后右移1位直到十进制数为0可以实现十进制转二进制。 123456789101112131415161718192021#include<iostream>#include<vector>using namespace std;int main(){ int n; cin>>n; vector<int> a(n+1); vector<int> res; for(int i=0;i<n;i++) cin>>a[i]; for(i ...

判断子序列给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。 请你判断 a 序列是否为 b 序列的子序列。 子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。 输入格式第一行包含两个整数 n,m。 第二行包含 n个整数，表示 a1,a2,…,an。 第三行包含 m 个整数，表示 b1,b2,…,bm。 输出格式如果 a 序列是 b 序列的子序列，输出一行 Yes。 否则，输出 No。 数据范围1≤n≤m≤105,−109≤ai,bi≤109 输入样例：1233 51 3 51 2 3 4 5 输出样例：1Yes 设置两个指针i,j分别指向a，b开头，如果对应元素相等，i++否则j++.循环结束后判断i的位置确定是否满足 12345678910111213141516171819202122/*while循环版*/#include<iostream>#include<vector>using namespace s ...

数组元素的目标和给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。 数组下标从 00 开始。 请你求出满足 A[i]+B[j]=x=的数对 (i,j)。 数据保证有唯一解。 输入格式第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。 第二行包含 n 个整数，表示数组 A。 第三行包含 m个整数，表示数组 B。 输出格式共一行，包含两个整数 i 和 j。 数据范围数组长度不超过 105105。同一数组内元素各不相同。1≤数组元素≤1091≤数组元素≤109 输入样例：1234 5 61 2 4 73 4 6 8 9 输出样例：11 1 方法一用哈希表记录x-a[i]的下标，如果b中元素在哈希表中出现过说明b[j]+a[i]==x。题目保证有唯一解，输出完直接返回。 1234567891011121314151617181920212223#include<iostream>#include<vector>#include<unordered_map>using namespace std ...

最长连续不重复子序列给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。 输入格式第一行包含整数 n。 第二行包含 n 个整数（均在 0∼1050∼105 范围内），表示整数序列。 输出格式共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。 数据范围1≤n≤105 输入样例：1251 2 2 3 5 输出样例：13 维护一个滑动窗口和哈希表，哈希表记录窗口内数字出现的频率 右指针一直向右滑动将元素加入哈希表 如果右指针指向的元素在窗口内出现次数超过1次，左指针向右移动缩小窗口直到每个元素只出现一次。记录窗口长度取最大值 123456789101112131415161718192021#include<iostream>#include<vector>using namespace std;int main(){ int n; cin>>n; vector<int> a(n+1),h(n+1,0); for(int i=0;i<n;i++) ...