携程实习笔试3-4

第一题,给算式求值,算式有三种,(+ a b c)返回a+b+c的值,(- a b c d)返回a-b-c-d的值,(* a b )返回a * b的值,然后各种嵌套这几个算式。
示例输入
(+ 3 4)
(- 9 4 5)
(- (* 4 5) 4 5)
(* (+ 2 3)(- 100 (+ 20 10)))
输出
7
0
11
350
写了半天把自己绕晕了,结束后改出来一个版本,也没法测试了,样例倒是过了。
#include<iostream>
#include<string>
#include<stack>
using namespace std;

int main()
{
    string ss;
    while (getline(cin, ss)){
        int n = ss.size();
        stack<char> stac;
        stack<int> num;
        for (int i = 0; i < n; ++i){
            char c = ss[i];
            if (c == ' ') continue;
			else if (c == '(') num.push(-1);
            else if (c == '+' || c == '-' || c == '*') stac.push(c);
            else if (c == ')'){
                if (stac.top() == '+'){
					int tmp = 0;
                    while (num.top() != -1){
                        tmp += num.top();
                        num.pop();
                    }
					num.pop();
                    num.push(tmp);
                }
                else if (stac.top() == '-'){
                    int tmp = 0;
					int pre;
                    while (num.top() != -1){
                        tmp += num.top();
						pre = num.top();
                        num.pop();
                    }
					num.pop();
                    num.push(2*pre-tmp);
                }
                else{
                    int tmp = 1;
                    while (num.top() != -1){
                        tmp *= num.top();
                        num.pop();
                    }
					num.pop();
                    num.push(tmp);
                }
                stac.pop();
            }
            else if ( ss[i]>='0' && ss[i]<='9'){
                int tmp = 0;
                while (i < n && ss[i]>='0' && ss[i]<='9'){
                    tmp = (ss[i]-'0') + tmp*10;
               		i++;
                }
				--i;
                num.push(tmp);
            }
        }
        cout << num.top() << endl;
    }
    return 0;
    
}
第二题发红包,给一个序列的红包,请你分割成n+1份(每份要连续),使得其中钱最少的那一份尽可能多。
例题序列为[1,2,3,4,5,6,7,8,9],分割成6份,答案是6。
[1,2,3],[4,5],[6],[7],[8],[9]
我赶脚就是二分这个结果,贪心看看按照这个结果能不能分出n+1份及以上,不能就右边界往左,能就左边界往右,然而0%...
        int m = packets.size();
        int right = 0;
    for (int i = 0; i < m; ++i) right += packets[i];
    int left = 0;
    while (left < right){
        int mid = left + (right - left) / 2;
        int cnt = 0;
        int sum = 0;
        for (int i = 0; i < m; ++i){
            sum += packets[i];
            if (sum >= mid){
                cnt++;
                sum = 0;
            }
        }
        if (cnt >= n+1) left = mid;
        else right = mid - 1;
    }        
        return left;
有大佬可以帮忙看看吗

#携程##笔试题目#
全部评论
请问你是技术岗的吗,面试一共几题呀?
点赞 回复
分享
发布于 2022-03-14 18:54

相关推荐

1 5 评论
分享
牛客网
牛客企业服务