一题: 删除链表中特定值的节点 不会有人拿链表写吧hhh, 这个30sA了
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* 移出所有相同值的元素
* @param head ListNode类 链表头节点
* @param v int整型 移出目标值
* @return ListNode类
*/
ListNode* removeElements(ListNode* head, int v) {
if(head==nullptr) return head;
vector<int> arr;
while(head!=nullptr){
if(head->val!=v){
arr.push_back(head->val);
}
head = head->next;
}
ListNode* newHead = new ListNode(-1);
ListNode* p = newHead;
for(int i=0;i<arr.size();i++){
ListNode* cur = new ListNode(arr[i]);
p -> next = cur;
p = p->next;
}
return newHead->next;
}
};
二题, 有N个客户M家店 组成一个matrix matrix[i][j]表示客户i愿意去店铺j, 每个客户只去一家店,每个店铺只接待一个客户, 问一天总接待量为多少
没什么好的想法, 感觉涉及到图论? 一开始写了个dfs, A了40% TLE
bool vis[100000];
int ans = 0;
void dfs(int curUser,vector<vector<int> >& g,int cnt){
if(curUser==g.size()){
ans = max(ans,cnt);
return;
}
// cout<<curUser<<endl;
for(int i=0;i<g[0].size();i++){
if(vis[i]==false && g[curUser][i]==1){
vis[i] = true;
dfs(curUser+1,g,cnt+1);
vis[i] = false;
}
}
dfs(curUser+1,g,cnt);
}
然后想贪心, 觉得对于店铺而言 优先接待选择少的客户, 比如客户A愿意去5家店铺 客户B只愿意去4家, 那么优先接待B
这个倒是A了90% 但是不是正解... 希望AC的朋友评论区讲讲
int washCount(vector<vector<int> >& g) {
vector<int> k(g.size());
for(int i=0;i<g.size();i++){
int cnt = 0;
for(int j=0;j<g.size();j++){
if(g[i][j]==1) cnt++;
}
k[i] = cnt;
}
set<int> S;
int ans = 0;
for(int j=0;j<g[0].size();j++){
vector<pair<int,int>> cur;
for(int i=0;i<g.size();i++){
if(g[i][j]==1){
cur.push_back(make_pair(k[i],i));
}
}
sort(cur.begin(),cur.end());
for(int x = 0;x<cur.size();x++){
if(S.find(cur[x].second)==S.end()){
S.insert(cur[x].second);
ans++;
break;
}
}
}
return ans;
}
对不起... 久疏战阵了 这个排列组合还真写不来... 希望有大佬讲讲
#途虎笔试#