滴滴算法岗笔试A了第一道，贴代码攒人品。。。
更新一下：
许多小伙伴都发现了一个问题，就是遇到类似2 * 3 / -2、 3 * 1 + 1这种式子这套代码的输出就不对了。
一开始楼主也想过这种可能，不过鉴于太复杂所以只先写了简单版本的代码，结果发现也ac了。说明出题人可能就没考虑过这种情况。。。
这个也算是题目的一个小bug把，如果真把这种情况算进去了，那么要考虑的情况会变得无比复杂，关于这种情况的解决方案欢迎大家一起讨论哈
-----------------------------------------------------------------------------------------------------------------------------------
题目描述：
给出一个仅包含加减乘除四种运算符的算式(不含括号)，如1+2*3/4，在保持运算符顺序不变的情况下，现在你可以进行若干次如下操作：如果交换相邻的两个数，表达式值不变，那么你就可以交换这两个数。
现在你可以进行任意次操作，使得算式的数字序列字典序最小，然后输出结果，数字之间的字典序定义为若a<b则a的字典序小于b。
输入
第一行包含一个整数n，表示算式的长度，即包含n个数字和n-1个运算符。(1≤n≤100000)。
第二行包含一个含有n个非0整数和n-1个运算符的算式，整数与运算符用空格隔开，运算符包括“+，-，*，/”，整数的绝对值不超过1000。
输出
按要求输出字典序最小的表达式，数字与符号之间用空格隔开。
样例输入
6
3 + 2 + 1 + -4 * -5 + 1
样例输出
1 + 2 + 3 + -5 * -4 + 1
以下思路是个人想的，不保证是最优解。
思路：
先用两个数组来存储数字（nums）和这个数字之前的操作符（ops）。其中ops第一个元素固定是'+'，因为第一个数没有符号。例如样例就会得到如下的两个数组：
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 |
| nums | 3 | 2 | 1 | -4 | -5 | 1 |
| ops | + | + | + | + | * | + |
接着用两个指针 l 和 r，一段一段地找ops中连续的操作符，例如样例中就会得出“l=0,r=3; l=4,r=4; l=5,r=5”三段。
接着根据一套规则来确定 l 和 r 区间内哪些元素是需要进行排序，以实现字典序最小：
- 如果ops[l]是加号或减号
- 这段区间下一个操作符是'*'或者‘/’，那么要排序的区间是[l, r-1]； 想想类似5+4+3+2+1*5的情况
- 这段区间下一个操作符是'-'，那么要排序的区间是[l, r]；想想类似5+4+3+2+1-5的情况
- ops[l]是乘号
- 区间前一个操作符是'+'或者‘-’，那么要排序的区间是[l-1, r]；想想类似1+5*4*3*2*1的情况
- 区间前一个操作符是‘/’，那么要排序的区间是[l, r]；想想类似1/5*4*3*2*1的情况
- ops[l]是除号
- 不论什么情况，要排序的区间都是[l, r]；
以上遍历一套，就可以得到答案了
代码：
int Partition(vector<int>& nums, int left, int right) {
int pivot = nums[left], l = left + 1, r = right;
while (l <= r) {
if (nums[l] > pivot && nums[r] < pivot)
swap(nums[l], nums[r]);
if (nums[l] <= pivot) l++;
if (nums[r] >= pivot) r--;
}
swap(nums[left], nums[r]);
return r;
}
void QuickSort(vector<int> &nums, int lo, int hi) {
if (hi <= lo) return;
int seg = Partition(nums, lo, hi);
QuickSort(nums, lo, seg - 1);
QuickSort(nums, seg + 1, hi);
}
int main(){
int n; cin>>n;
vector<int> nums(n, 0);
vector<char> ops(n, '+');
for(int i=0; i<n-1; ++i){
cin >> nums[i];
cin >> ops[i+1];
}
cin >> nums[n-1];
int l=0, r=0;
while(r<n){
while(r<n && ops[r] == ops[l]) ++r;
--r;
if(ops[l] == '+' || ops[l] == '-'){
if(r<n-1 && (ops[r+1]=='*' || ops[r+1]=='/'))
QuickSort(nums, l, r-1);
else
QuickSort(nums, l, r);
}
else if(ops[l] == '*'){
if(l>0 && (ops[l-1]=='+' || ops[l-1]=='-'))
QuickSort(nums, l-1, r);
else
QuickSort(nums, l, r);
}
else if(ops[l] == '/'){
QuickSort(nums, l, r);
}
++r; l=r;
}
string ans = to_string(nums[0]);
for(int i=1; i<n; ++i){
ans.push_back(' ');
ans.push_back(ops[i]);
ans.push_back(' ');
ans += to_string(nums[i]);
}
cout<<ans<<endl;
return 0;
} 
查看6道真题和解析
