9.23 美团笔试

第二题是不是有坑，Java 通过率直接是0

第二题用python正确率是0，不知道哪里出问题了，试了好几个例子都可以通过的

第五题这都能过90吗 用例也太拉胯了

第四题类比最长上升子序列和最长等差子序列，dp[i][j]表示截止到i，以a[i]结尾上一个数为j的好序列的长度。二重for就OK。

我不该抓着第四题不放的，以为很简单，结果最后发现思路错了，直接0。导致第五题都没得时间骗点分

第二题应该是输出的时候 01：05 %2lld这样的有坑

第四题动态规划 设 dp[i][j]：当前位为vec[i]，上一位为数值大小为j的最长序列的长度。（注意j不是下标，） 由于奇数位的相同，偶数位的相同。那么上一位的上一位数字就是当前位的数字。 状态转移很容易得出： d p [ vec[i] ] [ j ] = d p [ j ] [ vec[i] ] + 1 对于每一个vec[i]，然后枚举上一位，再通过状态转移去不断更新答案即可。 #include<iostream> (30316)#include<vector> #include<unordered_map> using namespace std; int main() { int n; cin >> n; vector<int>vec(n); vector<vector<int>>dp(1000,vector<int>(1000,0)); unordered_map<int, int>map; for (int i = 0; i < n; ++i) { cin >> vec[i]; ++map[vec[i]]; } int res = 0; for (int i = 0; i < n; ++i) { res = max(res, map[vec[i]]); for (int j = 1; j < 1000; ++j) { if (j != vec[i]) { dp[vec[i]][j] = dp[j][vec[i]] + 1; } res=max(res,dp[vec[i]][j]); } } cout << res; }

第四题子序列，不知道对不对... 大佬们帮忙看一下吧，再请教一下前端、移动端的第一题怎么写，送分题感觉思路错了 int main() { int n; cin >> n; string s = ""; for (int i = 0; i < n; ++i) { char c; cin >> c; s += c; } // dp[i] 表示 考虑 [0, i] 最长递增子序列长度， 以 s[i]为结尾 的 最长好序列递增子序列长度 vector<int> dp(n); int res = 0; for(int i = 2; i < n; ++i) { for(int j = 1; j < i; ++j) { // j比较到i的前一个 if(s[i] == s[j - 1]) { // s[i] 和 s[j - 1]相同，状态转移 dp[i] = max(max(dp[i], dp[j] + 1), 3); // 至少为3，dp[i]保证为最长的 } } if(dp[i] > res) { res = dp[i]; } } cout << res; return 0; }

佬，想问问第三题的思路

xdm，投这快开始下一轮笔试了→ https://www.nowcoder.com/feed/main/detail/cf9173b346684bd3a5c002acba5f18ab

完全平方那题谁知道为啥超时吗？其他的都知道原因了

题型不一样哎 我是选择题+2道编程。岗位不同吗😅

第五题我也是有10%超时，不知道怎么优化了，第四题动态规划想不出来，直接写了个dfs，没时间剪枝了，只过了10%

第二题算时间，用例过了，但是提交只过0%，这个咋回事啊，懵了 第三题怎么个好方法，我超时了0.0； 第四题完全平方过了90%但是超时了

同a了三个，话说这么晚了还有面试机会吗。。而且笔试a三个感觉也不太够😂

java第二题卡50，第五题爆0，晕了

全a出来了吗？第四题我直接放弃了

前n项和咋优化，暴力超时了

第二题样例过了85.3不知道哪里被卡了

第二题用例用上longlong也才过46.67% T T