牛客网shopee 2019校招部分编程题汇总

文章目录

• Shopee的办公室(二）
• Shopee的零食柜
• 实现字通配符*
• 建物流中转站

周六晚上就要shopee笔试啦！刷完牛客网shopee 2019校招部分编程题汇总之后内心拔凉拔凉的。
https://github.com/seawood/Leetcode-JianzhiOffer

Shopee的办公室(二）

典型的动态规划

//牛客Shopee 2019校招部分编程题汇总
//编程题1：shopee的办公室(二)
#include 
using namespace std;
int main(){int x,y,n;cin >> x>>y>>n;bool** mark = new bool*[x+1];long long** re = new long long*[x+1];for(int i = 0; i < x+1;++i){mark[i] = new bool[y+1];re[i] = new long long[y+1];}for(int i = 0; i < x+1;++i)for(int j = 0; j < y+1;++j){mark[i][j] = false;re[i][j]=0;}for(int i = 0;i<n;++i){int xi,yi;cin>>xi>>yi;mark[xi][yi]=true;}for(int i = 0; i < x+1;++i)re[i][0]=1;for(int j = 0;j < y+1;++j)re[0][j] = 1;for(int i = 1; i < x+1;++i)for(int j = 1; j < y+1;++j)if(!mark[i][j])re[i][j] = re[i-1][j]+re[i][j-1];long long result = re[x][y];for(int i = 0;i < x+1;++i){delete[] mark[i];delete[] re[i];}cout<<result<<endl;return 0;
}

Shopee的零食柜

在maxNum和sumNum之间二分查找

//牛客Shopee 2019校招部分编程题汇总
//编程题2：shopee的零食柜
#include 
#include 
#include 
using namespace std;
bool judge(const int& stepLen, const vector<int>& num, int steps) {int tempSum = 0, cur = 0, i = 0, len = num.size();for (i = 0; i < len; ++i) {tempSum += num[i];if (tempSum > stepLen) {cur++;tempSum = num[i];}if (cur >= steps)break;}return i == len;
}
int main() {int n, m;cin >> n >> m;if (n <= 0)return 0;vector<int> num;int maxNum = 0, sumNum = 0, temp;for (int i = 0; i < n; ++i) {cin >> temp;num.push_back(temp);maxNum = max(maxNum, temp);sumNum += temp;}int left = maxNum, right = sumNum, ans = right, mid;while (left <= right) {mid = (left + right) / 2;if (judge(mid, num, m)) {right = mid - 1;ans = min(ans, mid);}elseleft = mid + 1;}cout << mid << endl;  //cout<return 0;
}

实现字通配符*

递归

//牛客Shopee 2019校招部分编程题汇总
//编程题3：实现字通配符*
#include 
#include 
#include 
using namespace std;
void match(set<pair<int,int>>& ans, const string& pattern, const string& target,int pattern_cur_pos, int target_cur_pos, const int& start){if(pattern_cur_pos == (int)pattern.size()){if(target_cur_pos-start>0)ans.insert(make_pair(start, target_cur_pos-start));return;}if(target_cur_pos == (int)target.size())return;if(pattern[pattern_cur_pos] == '*'){match(ans, pattern, target, pattern_cur_pos+1, target_cur_pos+1, start);match(ans, pattern, target, pattern_cur_pos, target_cur_pos+1, start);match(ans, pattern, target, pattern_cur_pos+1, target_cur_pos, start);}else if(pattern[pattern_cur_pos] == target[target_cur_pos])match(ans, pattern, target, pattern_cur_pos+1, target_cur_pos+1, start);
}
int main(){string pattern, target;cin>>pattern>>target;set<pair<int,int>> ans;for(int i = 0; i < target.size(); ++i)match(ans, pattern, target, 0, i, i);if(ans.size() == 0)cout<<-1<<" "<<0<<endl;else{for(auto &i : ans)cout<<i.first<<" "<<i.second<<endl;}return 0;
}

建物流中转站

同一行/同一列的元素与某个元素的距离在行/列上是一样的

//牛客Shopee 2019校招部分编程题汇总
//编程题4：建物流中转站
#include 
#include 
using namespace std;
int main(){int n;cin>>n;int** num = new int*[n];for(int i = 0; i < n;++i)num[i] = new int[n];int *rowSum = new int[n], *colSum = new int[n];for(int i = 0; i <n;++i)for(int j = 0; j <n ;++j){cin>>num[i][j];rowSum[i]+=num[i][j];colSum[j]+=num[i][j];}int *rowDis = new int[n],*colDis = new int[n];for(int i = 0; i < n; ++i){rowDis[i]=0;colDis[i]=0;for(int j = 0; j < n;++j){rowDis[i]+=rowSum[j]*abs(j-i);colDis[i]+=colSum[j]*abs(j-i);}}int res = INT_MAX;for(int i = 0; i < n; ++i)for(int j = 0; j < n;++j){if(num[i][j]==0)res = min(res, rowDis[i]+colDis[j]);}delete[] rowSum;delete[] colSum;delete[] rowDis;delete[] colDis;for(int i = 0; i < n;++i)delete[] num[i];cout<<res<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！