京东9-3笔试
投递岗位C++
20道选择，体感C++基础考的多，考了类、多态和派生，外加一些经典八股，数据结构，计网的握手挥手、读数据库代码等，同步异步和linux。
3道编程，有两道都是dp。
1.求残次品的个数
输入一个n，表示第二行输入的数量。第二行依次输入的n个产品的质量，已知残次品比正品轻。
这个代码就不写了，统计最大值的个数就行了。输入完成结果就跟着出来了。
2.求最小操作数
题目给出两种操作，一种是减去1，另一种是拆成两个因子。求把一个数字操作成1的最小操作数 ，拆分后两个因子都要到1 。
输入一串数，每个数都要操作，最后返回总和。
思路：接收输入的时候统计一下出现的最大数字maxv，然后计算从0到maxv的每个数的最小操作数，结果保存在dp数组里。计算过程只有两个方案，要么-1，要么直接拆。
贴一下核心代码，当时急着过，肯定不是最优代码，只保证能ac。
、
3. 求括号字符串子数组的权值和
题目定义了权值，所谓权值是一个括号串里最长有效序列的长度。比如"()(()"的权值是4，因为序列不要求连续，取首尾两对括号"()(()"即可构成一个长为4的有效序列。
现在要求字符串所有子数组的权值之和。
先上暴力,写完暴力就会意识到哪些工作是重复的,暴力只能过22%，因为时间复杂度是O(n³)
int check(string &s,int left,int right){//计算权值
stack<bool>l;
int cnt=0;
for(int i=left;i<=right;++i){//O(n)遍历统计有效括号对
if(s[i]=='(')
l.push(1);
else if(!l.empty()){
l.pop();
++cnt;
}
}
return cnt*2;
}
int test2(string &s){//接收字符串,调用check
int ans=0;
int len=s.size();
for(int i=0;i<len-1;++i)//平方级的枚举子数组
for(int j=1;j<len;++j)
ans+=check(s,i,j);
return ans;
} 再上二维dp,定义dp[i][j] i到j的有效括号个数,还要额外统计此时的左括号是否有余,我直接塞进pair里了 vector<vector<pair<int,int>>>dp
(len,vector<pair<int,int>>(len,make_pair(0,0)));
//i到j的有效括号个数为first,多出来的左括号个数为second,不为负
int res=0;
for (int i = 0; i < len;++i)
dp[i][i].second= s[i] == '(';
for (int i = 0; i < len - 1; ++i)
for (int j = i + 1; j < len; ++j){
if (s[j] == '(')//遇见( 计数+1
{
dp[i][j].first = dp[i][j - 1].first;
dp[i][j].second = dp[i][j - 1].second + 1;
}
else if (dp[i][j - 1].second > 0)//遇见)有左括号,长度+2 计数-1
{
dp[i][j].first = dp[i][j - 1].first + 2;
dp[i][j].second = dp[i][j - 1].second - 1;
}
else
dp[i][j] = dp[i][j - 1];//没有左括号,直接沿用上次的值
res += dp[i][j].first;//记得统计结果,题目要求所有子数组的权值
} 可以随机一个括号串和暴力算法比对一下,题目的范围是200000的长度,实际上暴力解法1000的长度就已经超过给定用时了，能过22%已经算运气不错了。 但是很遗憾，依然不能全过，虽然我们写了一个看起来很好理解也很美观的DP，因为这个二维DP依然是n²级别的时间复杂度，不可能过得了200000长度的数据。当然能写出来这个已经可以捞不少分了。问题在于，我们只是优化了统计括号对这个操作，但依然要枚举每个子数组，所以下一步优化的结果是一步到位，直接把dp数组定义为 dp[i]： 以i结尾的所有子数组的权值和 。那么dp[i+1]的取值只有两种可能:
- 一种是没有诞生新的括号对，比如当前是左括号，或者是右括号但左括号用尽。那所有子数组的权值和不变，沿用之前的结果，dp[i+1]=dp[i]，
- 新增括号对的情况。还是用栈记录没有配对的左括号下标，栈顶k就是离当前下标最近的左括号。那么[k...i+1]这个子数组权值要加2，且k之前的所有子数组权值和都要+2，dp[i+1]=dp[i]+2*(k+1)
更多细节参见代码，比如在1000长度的时候答案就已经快超过int范围了，所以必须改用long long
stack<int> st;
string s{};
// cin >> str;
s = ")()()";
int len = s.size();
using ll = long long;
vector<ll> dp(len + 1,0);
//dp[i] 以i结尾的所有子数组的权值和
ll ans = 0;
for(int i = 1; i <= len; i++){
dp[i] = dp[i - 1];
if(s[i - 1] == '(')
st.push(i-1);//记录左括号下标
else{
if(!st.empty()){//有左括号就配对
int cnt = st.top()+1;//栈顶是离i最近的第一个左括号的下标
//0到i,总共i+1个子数组都多了一对括号,权值都要加2
st.pop();
dp[i] = dp[i] + cnt*2;
}
}
ans = ans + dp[i];//累加
}
类似资料：