校招&考研复试刷题题解
校招&考研复试刷题题解
目录
基础题只有代码，有点思维量的有文字解析
力扣
力扣: 两数之和
题解
点击查看代码
class Solution {
public:
std::unordered_map<int, int> mp;
std::vector<int> twoSum(std::vector<int>& nums, int target) {
for(int i = 0; i < nums.size(); i++){
if(mp.count(target - nums[i])) return std::vector<int>{i, mp[target - nums[i]]};
else mp.emplace(nums[i], i);
}
return std::vector<int>();
}
};
力扣128: 最长连续序列
题解
\(O(NlogN)\)的解决方法很好想
- 开个
std::umorderedmap计数， 二分答案 \(O(N\log max)\) . - 先排序，然后扫一遍，\(O(N\log N)\)
- 直接用
std::set，用个指针扫一遍 \(O(N\log N)\) 本质和离散化比较像.
\(O(N \alpha(N))\)的解法
\(\alpha()\) 为阿克曼函数（Ackermann function）的反函数，实际应用中几乎可以视为常数。
点击查看代码
struct DSU{
std::vector<int> f, sz;
DSU(int n) : f(n + 1), sz(n + 1, 1) {
iota(f.begin(), f.end(), 0);
}
int find(int x){ // 路径压缩
return f[x] == x ? x : f[x] = find(f[x]);
}
bool merge(int a, int b){ // 按秩合并
int fa = find(a), fb = find(b);
if(fa == fb) return false;
if(sz[fb] > sz[fa]) std::swap(fa, fb);
f[fb] = fa;
sz[fa] += sz[fb];
return true;
}
bool same(int a, int b) { return find(a) == find(b); }
};
class Solution {
public:
std::unordered_map<int, int> mp;
int longestConsecutive(std::vector<int>& nums) {
DSU d(nums.size() + 1);
for(int i = 0; i < nums.size(); i++)
mp.emplace(nums[i], i);
for(auto x : nums)
if(mp.count(x + 1)) d.merge(mp[x], mp[x + 1]);
int ans = 0;
for(int i = 0; i < nums.size(); i++)
ans = std::max(ans, d.sz[i]);
return ans;
}
};
\(O(N)\) 解法
先用hash去重，再巧妙枚举。
点击查看代码
class Solution { // 法2
public:
std::unordered_set<int> se;
int longestConsecutive(std::vector<int>& nums) {
for(int i = 0; i < nums.size(); i++)
se.insert(nums[i]);
int ans = 0;
for(const int &x : se){
// 必须去重， 否则整多个最小值就g了
if(se.count(x - 1)) continue;
int tmp = 1, now = x;
while(se.count(++now)) tmp++;
ans = std::max(ans, tmp);
}
return ans;
}
};
力扣283移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
题解
点击查看代码
class Solution {
public:
void moveZeroes(std::vector<int>& nums) {
int i = 0, j = 0, n = nums.size();
while(i < n && j < n){
while(i < n && (nums[i] != 0)) i++;
while(j < n && (j < i || nums[j] == 0)) j++;
if(j == n || i == n) break;
std::swap(nums[i], nums[j]);
}
}
};
力扣11盛最多水的容器 Median
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明：你不能倾斜容器。
题解
考虑最大的宽度 \(l,r\) 考虑如下两种情况：
- 缩小宽度，移动高的一边
- 由于宽度减小且容器高由短板决定，所以一定不存在更优解。
- 这种情况可以全部排除。
- 缩小宽度，移动低的一边
- 宽度缩小的同时，短板可能更新，从而得到更优解。
所以一开始让宽度最大，每次缩减宽度只改变低的下标，即可找到最优解，时间复杂度为 \(O(N)\)。
点击查看代码
class Solution {
public:
int maxArea(std::vector<int>& height) {
int l = 0, r = height.size() - 1;
int ans = 0;
while(l < r){
ans = std::max(ans, std::min(height[l], height[r]) * (r - l));
if(height[l] < height[r]) l++;
else r--;
}
return ans;
}
};
力扣200岛屿数量 Median
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
题解
很基础的DFS染色
点击查看代码
const int N = 305;
class Solution {
public:
bool col[N][N];
int n, m;
vector<int> nx{1,0,-1,0};
vector<int> ny{0,1,0,-1};
inline bool inmap(int x, int y){
return (x >= 0 && x < n) && (y >= 0 && y < m);
}
void dfs(vector<vector<char>>& grid, int x,int y, int tot){
col[x][y] = tot;
for(int i = 0; i < 4; i++){
int xx = x + nx[i], yy = y + ny[i];
if(inmap(xx, yy) && !col[xx][yy] && grid[xx][yy] == '1')
dfs(grid, xx, yy, tot);
}
}
int numIslands(vector<vector<char>>& grid) {
memset(col, 0, sizeof(col));
int tot = 0;
n = grid.size(); m = grid[0].size();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!col[i][j] && grid[i][j] == '1') dfs(grid, i, j, ++tot);
}
}
return tot;
}
};
力扣207课程表
题解
点击查看代码
const int N = 2005, M = 5005;
class Solution {
public:
int head[N], ver[M], nxt[M], deg[N];
int n, m, tot = 1;
inline void add(int x, int y){
ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}
bool canFinish(int num, vector<vector<int>>& E) {
n = num; m = E.size();
memset(head, 0, (n + 1) * sizeof(int));
memset(deg, 0, (n + 1) * sizeof(int));
for(int i = 0; i < E.size(); i++){
add(E[i][1] + 1, E[i][0] + 1); deg[E[i][0] + 1]++;
}
queue<int> q;
int ans = n;
for(int i = 1; i <= n; i++) if(!deg[i]) q.emplace(i);
while(!q.empty()){
int x = q.front(); q.pop();
ans--;
for(int i = head[x]; i; i = nxt[i]){
if(--deg[ver[i]] == 0) q.push(ver[i]);
}
}
return ans == 0;
}
};
力扣-46全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序返回答案。
题解
点击查看代码
class Solution {
public:
void dfs(vector<vector<int>>& ans, vector<int>& nums, int now, int n){
if(now == n){
ans.emplace_back(nums);
return ;
}
for(int i = now; i < n; i++){
swap(nums[now], nums[i]);
dfs(ans, nums, now + 1, n);
swap(nums[now], nums[i]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
dfs(ans, nums, 0, nums.size());
return ans;
}
};
力扣53-最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
题解
点击查看代码
class Solution {
public:
int maxSubArray(std::vector<int>& nums) {
int l = 0, tmp = 0;
int ans = -1e9;
for(int r = 0; r < nums.size(); r++){
if(tmp < 0){
tmp = nums[r]; l = r;
ans = std::max(tmp, ans);
continue;
}
tmp += nums[r];
ans = std::max(ans, tmp);
}
return ans;
}
};
力扣56-合并区间
题解
如果是只要边界挨着就合并的话可以考虑前缀和差分，复杂度为区间范围
点击查看拓展思路代码
class Solution {
public:
std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& ls) {
std::vector<int> su(10005, 0);
for(int i = 0; i < ls.size(); i++){
su[ls[i][0]]++; su[ls[i][1] + 1]--;
}
for(int i = 1; i < 10004; i++) su[i] += su[i - 1];
std::vector<std::vector<int>> ans;
int l = -1, r = -1;
for(int i = 0; i < 10002; i++){
if(l == -1 && su[i] != 0) {
l = r =i; continue;
}
if(l != -1 && su[i] != 0){
r++; continue;
}
if(!su[i] && l != -1 && r != -1){
ans.emplace_back(std::vector<int> {l ,r});
l = r = -1;
}
}
return ans;
}
};
本题只合并重叠的区间，考虑先按左端点排序再枚举。
点击查看代码
class Solution { // 本题AC解法
public:
static bool cmp(std::vector<int>& x, std::vector<int>& y){
if(x[0] == y[0]) return x[1] < y[1];
return x[0] < y[0];
}
std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& ls) {
std::vector<std::vector<int>> ans;
sort(ls.begin(), ls.end(), cmp);
ls.emplace_back(std::vector<int> {10005, 10005});
int l = ls[0][0], r = ls[0][1];
for(int i = 1; i < ls.size(); i++){
if(ls[i][0] <= r) { r = std::max(r, ls[i][1]); continue; }
ans.emplace_back(std::vector<int> {l, r});
l = ls[i][0], r = ls[i][1];
}
return ans;
}
};
力扣35-搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
题解
二分模板题
点击查看代码
class Solution {
public:
int searchInsert(vector<int>& nums, int& x) {
int l = 0, r = nums.size();
while(l < r){
int mid = (l + r) >> 1;
if(nums[mid] >= x) r = mid;
else l = mid + 1;
}
return r;
}
};
力扣74-搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
题解
点击查看代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int l1 = 0, r1 = matrix.size() - 1;
int n = matrix[0].size();
while(l1 < r1){
int mid = (l1 + r1) >> 1;
if(matrix[mid][n - 1] >= target) r1 = mid;
else l1 = mid + 1;
}
int l = 0, r = n - 1;
while(l < r){
int mid = (l + r) >> 1;
if(matrix[r1][mid] >= target) r = mid;
else l = mid + 1;
}
return matrix[r1][r] == target;
}
};
力扣-4寻找两个正序数组的中位数-Hard
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 \(O(log (m+n))\) 。
题解
这是一个从 \(O(m+n)\)，到 \(O(\log m \log n)\) 再到 \(\log(\max\{m,n\})\) 的优化思路。
- 首先，很容易想到一个 \(O(m+n)\) 的解法：对两个有序序列做一个归并，然后进行二分即可。
- 难的是怎么做到 \(O(\log (m+n))\) 的复杂度，考虑优化。
- 这时脑子里忽然蹦出一个 \(O(\log m \log n)\) 的解法：
- 对其中一个序列二分其边界 \(x\)，\(x\) 表示在
nums1中有 \(x\) 个元素在中位数左边，然后写一个chack()。 check()里面对nums2做二分，找到 \(nums1[x]\) 在nums2中的位置，看是否满足中位数的条件（看在边界之前的元素个数是大于还是小于 \(\frac{m+n}{2}\)，注意一下判断总元素的奇偶这个细节）- 这种解正确性的本质是一个序列的边界是具有01单调性的，确认后，另一个序列的边界也有01单调性。
- 对其中一个序列二分其边界 \(x\)，\(x\) 表示在
- 这个复杂度已经很优了，至少在算法竞赛里是卡不掉的，因为输入输出的时间远比这个算法运行长的多。
- 现在考虑如何优化到 \(\log(m+n)\) 的复杂度。
- 此时，忽然想到，中位数一定要满足的条件(上一种解法中说的)。所以考虑二分一个数组，在另一个数组中直接按中位数的条件算出下标，具体逻辑见代码。
- 即划分数组的方法，时间复杂度为 \(O(\log \max (m,n))\)。
点击查看代码
class Solution {
public:
inline bool check(vector<int>& nums1, vector<int>& nums2, int i, int j) {
// nums_i1, nums_i, nums_j1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
int nums_i1 = (i == 0 ? INT_MIN : nums1[i - 1]);
int nums_i = (i == nums1.size() ? INT_MAX : nums1[i]);
int nums_j1 = (j == 0 ? INT_MIN : nums2[j - 1]);
int nums_j = (j == nums2.size() ? INT_MAX : nums2[j]);
return nums_i1 <= nums_j;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size(); // m > n
int n = nums2.size();
int l = 0, r = m;
// med1：前一部分的最大值
// med2：后一部分的最小值
int med1 = 0, med2 = 0;
while (l < r) {
// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
int i = (l + r + 1) >> 1;
int j = ((m + n + 1) >> 1) - i;
if (check(nums1, nums2, i, j)) l = i;
else r = i - 1;
}
int i = l;
int j = ((m + n + 1) >> 1) - i;
int nums_i1 = (i == 0 ? INT_MIN : nums1[i - 1]);
int nums_i = (i == m ? INT_MAX : nums1[i]);
int nums_j1 = (j == 0 ? INT_MIN : nums2[j - 1]);
int nums_j = (j == n ? INT_MAX : nums2[j]);
med1 = max(nums_i1, nums_j1);
med2 = min(nums_i, nums_j);
return ((m + n) & 1) ? med1 : (med1 + med2) / 2.0;
}
};
本文来自博客园，作者：CH-Yu，转载请注明原文链接：https://chuna2.787528.xyz/chuanhua-blogs/p/19409493
浙公网安备 33010602011771号