感觉老师出的模拟题都挺用心的.比大公司笔试的题好多了:)(特别吐槽)
题1
- 定义超级和函数F如下: F(0, n) = n,对于所有的正整数n.. F(k, n) = F(k – 1, 1) + F(k – 1, 2) + … + F(k – 1, n),对于所有的正整数k和n.
请实现下面Solution类中计算F(k, n)的函数(1 <= k, n <= 14). 例1:F(1, 3) = 6 例2:F(2, 3) = 10 例3:F(10, 10) = 167960 注意:你只需要提交Solution类的代码,你在本地可以编写main函数测试程序,但不需要提交main函数的代码. 注意不要修改类和函数的名称.
class Solution{
public:
int F(int k, int n){
vector<int> dp(n +1);
for(int i = 0; i <= n; ++i){
dp[i] = i;
}
for(int i = 1; i <= k; ++i){
for(int j = 1; j <=n; ++j){
dp[j] += dp[j-1];
}
}
return dp[n];
}
};
题2
会议要同时举行,参会人数分别为A[0], A[1], .., A[N-1]. 现有M个会议室,会议室可容纳人数分别为B[0], B[1], …, B[M-1]. 当A[i]<=B[j]时,可以把会议i安排在会议室j,每间会议室最多安排一个会议,每个会议最多只能安排一个会议室. 求最多安排多少个会议.
1 <= N, M <= 100000, 每个会议的参会人数和每间会议室的容纳人数均在1和1000之间. 请为下面的Solution类实现解决上述问题的函数assignConferenceRoom. 函数参数A和B的意义如上,返回值为最多可安排的会议数.
例1:A={2, 3}, B={1, 2},答案为1. 例2:A={3, 4, 5},B={10, 3, 2},答案为2.
class Solution {
public:
int assignConferenceRoom(vector<int>& A, vector<int>& B) {
sort(A.begin(), A.end());
sort(B.begin(), B.end());
if(B.empty())
return 0;
int count = 0;
for(int i = A.size()-1; i >=0 ;--i){
if(!B.empty() && A[i] <= B.back()){
++count;
B.pop_back();
}
}
return count;
}
};
题3
两个二叉树结构相同,且对应结点的值相同,我们称这两个二叉树等价.
例如:以下两个二叉树等价 1 1 / \ / \ 2 3 2 3 而以下两个则不等价 1 1 / \ / \ 2 3 3 2 以下两个也不等价 1 1 / \ / \ 2 3 2 2
给出两个二叉树p和q,判断它们是否等价. p和q的结点数不多于100000,每个结点的数值在1和1000000000之间.
请为下面的Solution类实现解决上述问题的isEqual函数,函数的两个参数p和q分别代表两个二叉树的根节点,如果以p和q为根的二叉树等价则函数返回true,否则返回false.
class Solution {
public:
bool isEqual(TreeNode* p, TreeNode* q) {
if(!p && !q)
return true;
if(!p || !q)
return false;
if(p->val == q->val)
return isEqual(p->left, q->left) && isEqual(p->right, q->right);
return false;
}
};
题4
//Number of Islands
class Solution {
public:
int countConnectedOnes(vector<vector<char>>& A) {
direction = \{\{1, 0\}, \{0 ,1\}, \{-1, 0\}, \{0, -1\}\};
if(A.empty())
return 0;
int rs = A.size(), cs = A[0].size();
int res = 0;
for(int i = 0; i < rs; ++i){
for(int j = 0; j <cs; ++j){
if(A[i][j] == '1'){
queue<pair<int, int>> que;
que.emplace(i, j);//BFS
A[i][j] = '0';
while(!que.empty()){
int x = que.front().first, y = que.front().second;
que.pop();
for(int i =0; i < 4; ++i){
int nx = x + direction[i][0], ny = y +direction[i][1];
if(nx < 0 || nx >= rs || ny < 0 || ny >=cs || A[nx][ny] != '1'){
continue;
}
A[nx][ny] = '0';
que.emplace(nx, ny);
}
}
++res;
}
}
}
return res;
}
private:
vector<vector<int>> direction;
};
题5
图论中,如果一个有向图从任意顶点出发无法经过若干条边回到该点,则这个图是一个有向无环图(Directed Acyclic Graph,DAG). 对于一个n个节点的有向图(节点编号从0到n-1),请判断其是否为有向无环图.
的节点数和边数均不多于100000.
请为下面的Solution类实现解决上述问题的isDAG函数,函数参数中n为图的节点数,edges是边集,edges[i]表示第i条边从edges[i].first指向edge[i].second. 如果是有向无环图返回true,否则返回false.
例1: n = 3,edges = {(0, 1), (0, 2)},函数应返回true. 例2: n = 2,edges = {(0, 1), (1, 0)},函数应返回false. 注意:你只需要提交Solution类的代码,你在本地可以编写main函数测试程序,但不需要提交main函数的代码. 注意不要修改类和函数的名称.
class Solution {
//拓扑排序
public:
bool isDAG(int n, vector<pair<int, int>>& edges) {
unordered_map<int, vector<int>> mp;
vector<int> degree(n, 0);
for(int i = 0; i < edges.size(); ++i){
mp[edges[i].first].push_back(edges[i].second);
++degree[edges[i].second];
}
queue<int> que;
int count = n;
for(int i = 0; i < n;++i){
if(degree[i] == 0){
que.push(i);//入读为0
degree[i] = -1;
--count;
}
}
//cout<<count<<endl;
while(!que.empty()){
int vertex = que.front();
que.pop();
for(int i = 0; i < mp[vertex].size() ;++i){
if(--degree[mp[vertex][i]] == 0){
que.push(mp[vertex][i]);
--count;
}
}
}
return count == 0;
}
};
题6
从数列A[0], A[1], A[2], …, A[N-1]中选若干个数,要求相邻的数不能都选,也就是说如果选了A[i], 就不能选A[i-1]和A[i+1]. 求能选出的最大和.
1 <= N <= 100000, 1 <= A[i] <= 1000 请为下面的Solution类实现解决上述问题的函数maxSum,函数参数A是给出的数列,返回值为所求的最大和.
例1:A = {2, 5, 2},答案为5. 例2:A = {2, 5, 4},答案为6.
class Solution {
public:
int maxSum(vector<int>& A) {
vector<int> dp(2, 0);
if(A.empty())
return 0;
dp[0] = A[0];//选1
for(int i = 1; i < A.size(); ++i){
int temp = dp[0];
dp[0] = max(dp[1] + A[i], dp[0]);
dp[1] = max(temp, dp[1]);
}
return max(dp[0], dp[1]);
}
};
题7
其实就是Edit Distance
//O(m * n)
class Solution {
public:
int minDistance(string word1, string word2) {
int s1 = word1.size(), s2 = word2.size();
vector<vector<int>> dp(s1+1, vector<int>(s2+1));
for(int i = 1; i <= s2;++i)
dp[0][i] = i;
for(int i = 1; i <=s1; ++i){
dp[i][0] = i;
}
for(int i = 1 ;i <= s1; ++i){
for(int j = 1; j <= s2; ++j){
if(word1[i-1] == word2[j-1]){
dp[i][j] = dp[i-1][j-1];
}
else{
dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
}
return dp[s1][s2];
}
};
class Solution {
//可将空间压缩至使用O(N);
public:
int minDistance(string word1, string word2) {
int w1 = word1.size(),w2 = word2.size();
vector<int> pre(w2+1,0);
vector<int> cur(w2+1,0);
for(int j=1;j<=w2;++j){
pre[j] = j;
}
for(int i=1;i<=w1;++i){
cur[0] = i;
for(int j=1;j<=w2;++j){
if(word1[i-1]==word2[j-1])
cur[j] = pre[j-1];
else
cur[j] = min(pre[j-1],min(cur[j-1],pre[j]))+1;
}
pre = cur;
}
return pre[w2];
}
};
题8
随着共享经济的兴起,大学城如今到处可见ofo小黄车. 小左现在打算每天都骑小黄车从宿舍去实验室. 假设大学城的地图可以简化为一个有向图,图中有N个地点(节点),用0到N-1进行编号,有些地点之间存在有向的道路(有向边). 小左的宿舍所在地点编号为0,实验室所在地点编号为N-1. 小左希望为连续的M天规划线路,使得每天从宿舍到图书馆,都至少会经过一条之前没有走过的道路(有向边). 小左想知道M的最大值,你能帮助他么?
请实现下面Solution类中的countPath函数,完成上述功能. 参数G: N*N(2 <= N <= 50)邻接矩阵,如果地点i到地点j之间有道路,则G[i][j] = 1;否则G[i][j] = 0. G[i][i]的值总是为0. 返回值:M的最大值. 如果不存在满足要求的路径则返回0.
例1: G = {{0, 1}, {1, 0}},返回值为2,因为第1天:0 –> 1,第2天 0 –> 1 –> 0 –> 1. 虽然小左第2天兜了一下圈,但他确实走了一条第1天没有走过的边1 –> 0.
例2: G = {{0, 1, 1}, {1, 0, 1}, {1, 0, 0}},返回值为4. 第1天:0 –> 2 第2天:0 –> 2 –> 0 –> 2 第3天:0 –> 1 –> 2 第4天:0 –> 1 –> 0 –> 1 –> 2
例3: G = {{0, 1, 0}, {1, 0, 0}, {0, 0, 0}},返回值为0.
//应该是可以优化一个DFS的步骤的, 迟点再进行优化
class Solution {
public:
int countPaths(vector<vector<int>> &G) {
n = G.size();
vector<bool> destCanReach(n, false);
destCanReach[n-1] = true;
DFSSearch2(G, destCanReach, n-1);
//BFS
vector<int> visited(n, 0);
queue<int> que;
if(destCanReach[0] == false)
return 0;
int count = 0;
que.push(0);
visited[0] = true;
while(!que.empty()){
int idx = que.front();
que.pop();
for(int i = 0; i < n; ++i){
if(G[idx][i] == 1){
if(destCanReach[i] == false){ //终点不可达
continue;
}
if(visited[i]){ //访问过
++count;
}
else{
que.push(i);
visited[i] = true;
if(i == n-1){
++count;
}
}
}
}
}
return count;
}
private:
int n;
void DFSSearch2(vector<vector<int>>&G , vector<bool>& dest, int idx){
for(int i = 0; i < n; ++i){
if(G[i][idx] == 1 && !dest[i]){
dest[i] = true;
DFSSearch2(G,dest, i);
}
}
}
};
````