携程3.4笔试题

两道题都可以用DFS。 第一题：
class Solution{
public:
    static pair<int, int> getNum(string s, int index){
        int res = 0;
        while(isdigit(s[index])){
            res = res*10 + (s[index]-'0');
            index++;
        }
        return make_pair(res, index);
    }
    int getResult(string s){
        stack<char> kuohaoStack;
        stack<char> operStack;
        stack<int> numStack;
        for(int i=0; i<s.size(); ++i){
            if(s[i]=='(' && kuohaoStack.empty()){
            kuohaoStack.push(s[i]);
            }else if(s[i]=='(' && (!kuohaoStack.empty())){
            int tmpLeft = i; int tmpRight = i;
            while(s[tmpRight] != ')'){
            tmpRight++;
            }
            string sonString = "";
            for(int j=tmpLeft; j<=tmpRight; ++j){
                sonString += s[j];
            }
            int res = getResult(sonString);     //使用DFS, 先计算出子式的值，再将该值插入原字符串中
            s.erase(tmpLeft, tmpRight-tmpLeft+1);
            string newNum = to_string(res) + " ";
            s.insert(i, &newNum[0]);
            }
        }
    
        char oper;      //到达这里时只剩下一个最基础的式子: 形如(* x y ... z), 下面直接处理这个式子就可以得到答案
        for(int i=0; i<s.size(); ++i){
            if(isdigit(s[i])){
                pair<int, int> tmp = getNum(s, i);
                numStack.push(tmp.first);
                i = tmp.second - 1;
            }else if(s[i]=='+' || s[i]=='-' || s[i]=='*'){
                oper = s[i];
            }
        }
        if(oper == '+'){
            int res = 0;
            while(!numStack.empty()){
                res += numStack.top();
                numStack.pop();
            }
            return res;
        }else if(oper == '-'){
            int res = 0;
            while(!numStack.empty()){
            if(numStack.size() != 1){
                res -= numStack.top();
                numStack.pop();
            }else{
                res += numStack.top();
                numStack.pop();
            }  }
            return res;
        }else if(oper == '*'){
            int res = 1;
            while(!numStack.empty()){
                res *= numStack.top();
                numStack.pop();
            }  return res;
      }
    }
};

第二题参考了大佬的做法，也是使用DFS。
class Solution{
public:
    int maxAmount(vector<int>& packets, int n){
        int res = fun(packets, 0, n+1);
        return res;
    }
    int fun(vector<int>& packets, int start, int n){
        int len = packets.size() - start;
        if(n == 1){  //如果n==1，则未分完的红包都给最后这个人
            int res = 0;
            for(int i=start; i<packets.size(); ++i){
                res += packets[i];
            }
            return res;
        }
        int res = 0;
        int curSum = 0;
        for(int i=1; i<=len-n+1; ++i){  //至少要留出最少n-1个小红包给剩下的n-1个人，所以i <= len-n+1
            curSum += packets[start+i-1];
            string s = to_string(start+i) + " " + to_string(n-1);
            int nextMin = 0;
            if(m.find(s) != m.end())
                nextMin = m[s];
            else{
                nextMin = fun(packets, start+i, n-1);  //DFS
                m.insert(make_pair(s, nextMin));
            }
            res = max(res, min(curSum, nextMin));
       }
       return res;
  }
public:
    map<string, int> m;
};