面试资料

最长连续不重复子序列给定一个长度为 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++) ...

差分矩阵输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c。 请你将进行完所有操作后的矩阵输出。 输入格式第一行包含整数 n,m,q。 接下来 n行，每行包含 m个整数，表示整数矩阵。 接下来 q行，每行包含 55 个整数 x1,y1,x2,y2,c，表示一个操作。 输出格式共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。 数据范围1≤n,m≤1000,1≤q≤100000,1≤x1≤x2≤n,1≤y1≤y2≤m,−1000≤c≤1000,−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000 输入样例：12345673 4 31 2 2 13 2 2 11 1 1 11 1 2 2 11 3 2 3 23 1 3 4 1 输出样例：1232 3 4 14 3 4 12 2 2 2 二维版的差分。 同样也是二维版前缀和的逆运算 123456789101112 ...

差分输入一个长度为 n 的整数序列。 接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r][�,�] 之间的每个数加上 c。 请你输出进行完所有操作后的序列。 输入格式第一行包含两个整数 n 和 m。 第二行包含 n 个整数，表示整数序列。 接下来 m行，每行包含三个整数 l，r，c，表示一个操作。 输出格式共一行，包含 n 个整数，表示最终序列。 数据范围1≤n,m≤100000,1≤l≤r≤n,−1000≤c≤1000,−1000≤整数序列中元素的值≤1000−1000≤整数序列中元素的值≤1000 输入样例：123456 31 2 2 1 2 11 3 13 5 11 6 1 输出样例：13 4 5 3 4 2 差分是前缀和的逆运算，用于快速计算一段区间内加上某一个常数 构建a的差分数组b,同时a是b的前缀和数组。 b[l]+c后，a数组变为a[l]+c,a[l+1]+c...a[r]+c,a[r+1]+c...a[n]+c b[r+1]-c后，a数组变为a[l]+c,a[l+1]+c...a[r]+c,a[r+1]+c-c...a[n]+c ...

子矩阵的和输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式第一行包含三个整数 n，m，q。 接下来 n 行，每行包含 m 个整数，表示整数矩阵。 接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。 输出格式共 q 行，每行输出一个询问的结果。 数据范围1≤n,m≤1000,1≤q≤200000,1≤x1≤x2≤n,1≤y1≤y2≤m,−1000≤矩阵内元素的值≤1000 输入样例：12345673 4 31 7 2 43 6 2 82 1 2 31 1 2 22 1 3 41 3 3 4 输出样例：123172721 二维版的前缀和 12345678910111213141516171819202122232425262728#include<iostream>using namespace std;const int N = 1005;int a[N][N];int s[N][N];int main() ...

前缀和输入一个长度为 n 的整数序列。 接下来再输入 m 个询问，每个询问输入一对 l,r。 对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。 输入格式第一行包含两个整数 n和 m。 第二行包含 n个整数，表示整数数列。 接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。 输出格式共 m行，每行输出一个询问的结果。 数据范围1≤l≤r≤n,1≤n,m≤100000,−1000≤数列中元素的值≤1000 输入样例：123455 32 1 3 6 41 21 32 4 输出样例：1233610 前缀和模板题。 前缀和数组s[i]表示a[1]+...+a[i-1](这个题下标从1开始) [l,r]的区间和等于a[1]+...a[l-1]+a[l]+...+a[r]-(a[1]+...+a[l-1])也就是s[r+1]-s[l]。 构造前缀和数组是线性时间复杂度，每次查询是常数时间复杂度。 123456789101112131415161718192021#include<iostream>#include<vector>using ...

高精度除法给定两个非负整数（不含前导 00） A，B，请你计算 A/B 的商和余数。 输入格式共两行，第一行包含整数 A，第二行包含整数 B。 输出格式共两行，第一行输出所求的商，第二行输出所求余数。 数据范围1≤A的长度≤100000,1≤B≤10000,B 一定不为 0 输入样例：1272 输出样例：1231 因为除法是从高位开始算，加减法和乘法都是从低位开始，所以除法其实不用倒序存储数据。但是为了和前边保持一致，同样采用倒序存储。 1234567891011121314151617181920212223242526272829#include<iostream>#include<vector>#include<algorithm>using namespace std;vector<int> div(vector<int> a,int b,int &r){ vector<int> c; for(int i=a.size()-1;i>=0;i--){ ...

高精度乘法给定两个非负整数（不含前导 00） A和 B，请你计算 A×B 的值。 输入格式共两行，第一行包含整数 A，第二行包含整数 B。 输出格式共一行，包含 A×B 的值。 数据范围1≤A的长度≤1000001≤的长度≤100000,0≤B≤100000≤≤10000 输入样例：1223 输出样例：16 大数乘小数的模板。 大数的每一位和小数相乘，将得到的乘积相加。 123456789101112131415161718192021222324252627282930#include<iostream>#include<vector>using namespace std;vector<int> mul(vector<int> a,int b){ vector<int> c; int t=0; for(int i=0;i<a.size();i++){ t+=a[i]*b; c.push_back(t%10); t/=10; & ...

高精度减法给定两个正整数（不含前导 00），计算它们的差，计算结果可能为负数。 输入格式共两行，每行包含一个整数。 输出格式共一行，包含所求的差。 数据范围1≤整数长度≤1051≤整数长度≤105 输入样例：123211 输出样例：121 1234567891011121314151617181920212223242526272829303132333435363738394041#include<iostream>#include<vector>using namespace std;bool cmp(vector<int> a,vector<int> b){ //如果a大于等于b返回true if(a.size()!=b.size()) return a.size()>b.size(); for(int i=a.size()-1;i>=0;i--){ if(a[i]!=b[i]) return a[i]>b[i]; } return true ...

最小覆盖子串给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。 示例 1： 123输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。 示例 2： 123输入：s = "a", t = "a"输出："a"解释：整个字符串 s 是最小覆盖子串。 示例 3: 1234输入: s = "a", t = "aa"输出: ""解释: t 中两个字符 &#x ...

串联所有单词的字串给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。 示例 1： 123456输入：s = "barfoothefoobarman", words = ["foo","bar"]输出：[0,9]解释：因为 words.length == 2 ...