20230420-上海广策信息技术笔试记录

1.小括号的有效性判断

LC的简单题，不知道为什么一直有3道用例错，枯了。

bool isValid(string s) {stack<int> st;for(int i = 0; i < s.size(); i++){// prevent cases like '))'if(st.empty()){st.push(s[i]);}else if(s[i] == '{' || s[i] == '[' || s[i] == '('){st.push(s[i]);}else if(!st.empty() && s[i] == '}' && st.top() == '{'){st.pop();   }else if(!st.empty() && s[i] == ')' && st.top() == '('){st.pop();}else if(!st.empty() && s[i] == ']' && st.top() == '['){st.pop();}else{return false;}}return st.empty();}

2.统计n的阶乘结果末尾0的个数

想法：两步，一.实现大数乘法，二.通过阶乘乘法求出阶乘结果字符串，然后遍历统计字符串末尾0的个数。

然而暴力解法肯定过不了，不过当时大数乘法几个月没写了，唉。。。

先放个大数乘法的实现吧：

string multiply(string num1, string num2) {if(num1 == "0" || num2 == "0")return "0";vector<int> res(num1.size() + num2.size(), 0); for(int j = num2.size() - 1; j >= 0; j--){for(int i = num1.size() - 1; i >= 0; i--){int a = num1[i] - '0';int b = num2[j] - '0';int tmp = res[i + j + 1] + a * b;res[i + j + 1] = tmp % 10;res[i + j] += tmp / 10;}}string ans;int i = 0;while(res[i] == 0 && i < res.size()){i++;}for(; i < res.size(); i++){ans.push_back(res[i] + '0');}return ans;}

真正答案：

https://blog.51cto.com/woodpecker/1955915

3.不用不用if,条件表达式，switch等判断比较a,b较大者

请写一个程序，不用if,条件表达式，switch等判断
语句，找出两个整数a,b中的较大者。(a≠b)
·若a>b,输出a large
·若a<b,输出b large
示例1

输入：a=1,b=2
输出："b large"

示例2

输入：a=2,b=1
输出："a large"

脑筋急转弯，半天想不出来，其实当时也想到位运算的。。

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){int a = 0, b = 1;vector<string> res = {"a large", "b large"};int c = a - b;c = c >> (sizeof(int) * 8 - 1); //取得相减结果的二进制最高位, 0为正，1为负cout << res[c] << endl;  
}

答案出处：https://blog.csdn.net/weixin_37823499/article/details/125786533

4.特殊的排序

特定一个字符串s，该字符串仅由字母与数字组成，即a-z,A-Z,0-9组成，

现在要求字母部分按降序排序，数字部分按照升序排
序，并且不改变之前字母和数字所在的位置，即字母之
创在该位置，排序后在该位置的依旧是字母。
要求不得使用编程语言自带的排序函数
示例：
输入，special——sort(ba3e2d59c)
输出，ed2c3b59a

思路：AC，其实就是自己实现一个快速排序，分别把数字字符串和字母字符串遍历提取出来，然后再遍历主串，数字串和字母串设两个指针在开头，主串遍历到字母则字母串指针值拷进去，然后前进一位；主串遍历到数字则数字串指针值拷进去，然后前进一位；

挺简单的，难怪只有10分。

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){string cas = "ba3e2d59c";string num, str;for(int i = 0; i < cas.size(); i++){if(isalpha(cas[i])){str.push_back(cas[i]);}else{num.push_back(cas[i]);}}//题目忘记截代码了 方便期间省略了排序代码sort(num.begin(),num.end());sort(str.begin(),str.end());int i = str.size() - 1, j = 0;for(int k = 0; k < cas.size(); k++){if(isalpha(cas[k])){cas[k] = str[i--];}else{cas[k] = num[j++];}}cout << cas << endl;
}

总结:我太菜了