途虎养车 3.16笔试Java1卷(没AC,大伙儿看个乐)

一题

一题: 删除链表中特定值的节点 不会有人拿链表写吧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;
    }

三题

对不起... 久疏战阵了 这个排列组合还真写不来... 希望有大佬讲讲