58同城笔试

前言

挺基础的三道题，第一题求区间并集，可以使用哈希表判断也可以使用双指针，第二题中缀表达式转后缀表达式，相信大家都学过，第三题普通dp，要注意不能连续不选。

第一题

搜索场景下，搜索引擎针对帖子建立倒排索引，即单词对应出现该单词的所有文档列表，倒排索引的具体结构如下:

单词1->文档1的ID;文档2的ID;文档3的ID...即单词1出现在文档1、2、3...中

单词2->文档2的ID;文档5的ID;文档7的ID...即单词2出现在文档2、5、7...中

具体可以简化为每个单词对应一个倒排链，即int数组，数组中存储值为从小到大排序好的无重复的帖子ID。

现在用户希望查询同时出现单词1与单词2的帖子，即输入为两个单词的倒排链数组，输出同时包含这两个单词的帖子ID，帖子ID按照从大到小排序

示例1

输入

[1,2,3,7],[2,5.7]

输出

[7,2]

思路与代码

核心思想是通过哈希集合来快速查找交集元素，并通过排序操作来得到降序的交集结果。这有助于有效地找到两个向量的共同元素并以逆序的方式进行展示。

vector<int> intersectionAndSort(vector<int>& docList1,vector<int>& docList2) {
    unordered_set<int> st1;
    for(int i = 0;i < docList1.size();i++) {
        st1.emplace(docList1[i]);
    }
    vector<int> ans;
    for(int doc : docList2) {
        if(st1.count(doc)) {
            ans.push_back(doc);
        }
    }
    sort(ans.rbegin(),ans.rend());
    return ans;
}

第二题

从存储系统中拉取数据的时候，经常需要加一些过滤条件来获取想要的数据，因此很多存储系统都支持过滤器功能。假设某存储系统支持与或非三种过滤逻辑以及括号，业务拉取数据的时候只需要输入过滤字符串就可以实现数据过滤拉取。 为了方便的处理运算符的优先级，通常需要把用户输入的过滤字符串(中缀表达式)转化成后缀表达式并输出，请写一个程序实现上述功能。

逻辑符号定义:
逻辑与&
逻辑或
逻辑非!
左括号( 右括号),左右括号需要配合使用
优先级:
0>!>&>1

示例1

输入

"exp1 & (exp2|exp3)/!exp4"

输出

"exp1 exp2 exp3| & exp4 !"

思路与代码

这个代码的核心思想是通过栈来处理不同操作符的优先级和括号的嵌套，将中缀表达式转换为后缀表达式，以便更容易进行计算。

1. 遍历输入的中缀表达式字符串，根据不同情况执行以下操作：
• 如果是操作符（如'!', '&', '|')，则根据操作符的优先级，将队列中的操作符弹出并添加到结果字符串中，直到满足运算符的优先级要求，然后将当前操作符添加到队列中。
• 如果是左括号'('，直接添加到队列中。
• 如果是右括号')'，则弹出队列中的操作符并添加到结果字符串，直到遇到左括号'('。
• 如果是空格字符' '，跳过。
• 否则，将操作数添加到结果字符串中。
2. 最后，将队列中剩余的操作符依次弹出并添加到结果字符串中。

string convertInfix2Postfix(string s) {
    int n = s.size();
    string ans;
    deque<char> dq;
    unordered_map<char,int> priority;
    unordered_set<char> op = {'(',')','!','&','|'};
    priority['!'] = 3;
    priority['&'] = 2;
    priority['|'] = 1;
    for(int i = 0;i < n;i++) {
        if(s[i] == '!' || s[i] == '&' || s[i] == '|') {
            while(!dq.empty() && dq.back() != '(' &&  priority[dq.back()] >= priority[s[i]]) {
                if(ans.size() != 0 && ans[ans.size() - 1] != ' ') {
                    ans += " ";
                }
                ans += dq.back();
                dq.pop_back();
            }
            dq.push_back(s[i]);
        }else if(s[i] == '(') {
            dq.push_back(s[i]);
        }else if(s[i] == ')') {
            while(dq.back() != '(') {
                if(ans.size() != 0 && ans[ans.size() - 1] != ' ') {
                    ans += " ";
                }
                ans += dq.back();
                dq.pop_back();
            }
            dq.pop_back();
        }else if(s[i] == ' ') {
            continue;    
        }else {
            int j = i;
            if(ans.size() != 0 && ans[ans.size() - 1] != ' ') {
                ans += " ";
            }
            while(j < n && !op.count(s[j])) {
                ans += s[j];
                j++;
            }
            i = j - 1;
        }
    }
    while(!dq.empty()) {
        if(ans.size() != 0 && ans[ans.size() - 1] != ' ') {
            ans += " ";
        }
        ans += dq.back();
        dq.pop_back();
    }
    return ans;
}

第三题

现在有一辆货车需要从A地出发到达B地，中间会经过一系列城市，如果需要入城补给，则需要缴纳-定的过路费，现给出中间城市的过路费数组toll，toll[i]表示第i个城市 (不包含起点和终点城市)的过路费，求最少支付的过路费总额。

注意:1.货车可以跳过某些城市不进城，但是不能连续跳过两个城市 2.出发和到达城市都不需要计算过路费

示例1

输入

[1,2,3)

输出

2

说明

出发后跳过第0个城市，在第1个城市进行补给，然后跳过第2个城市，一共花费2

思路与代码

这段代码的核心思想是使用动态规划来找到最小收费路径。

1. 使用循环遍历每个收费站（从1到n），更新dp[i][0]和dp[i][1]：
• dp[i][0]表示在第i个站不停车，那么它的费用与上一个站停车的费用相同，即dp[i][0] = dp[i-1][1]。
• dp[i][1]表示在第i个站停车，那么它的费用是上一个站停车和不停车的费用中的较小值再加上当前站的收费，即dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + toll[i-1]。
2. 最后，返回在最后一个站点停车和不停车的最小费用中的较小值，即min(dp[n][0], dp[n][1])，这就是通过一系列收费站时的最小收费。

int minTolls(vector<int>& toll) {
    int n = toll.size();
    vector<vector<int>> dp(n + 1,vector<int>(2,INT_MAX));
    dp[0][0] = 0;
    dp[0][1] = 0;
    for(int i = 1;i <= n;i++) {
        dp[i][0] = dp[i-1][1];
        dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + toll[i-1];
    }
    return min(dp[n][0],dp[n][1]);
}