卡碼網(wǎng)圖論更新了可以去看看，模擬筆試第四題就是深搜/廣搜還不太會

LeetCode 392 判斷子序列

---

其實就是最長公共子序列翻版

代碼如下：

class Solution {public boolean isSubsequence(String s, String t) {int[][] dp = new int[s.length() + 1][t.length() + 1];int result = 0;for (int i = 1; i <= s.length(); i++) {for (int j = 1; j <= t.length(); j++) {if (s.charAt(i-1) == t.charAt(j-1))dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);else dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);if (result < dp[i][j]) result = dp[i][j];}}return result == s.length();}
}

模擬美團(tuán)筆試第一題 小美的排列詢問

---

簡單模擬

代碼如下：

#include <iostream>using namespace std;int main() {int n;cin >> n;int a[n];for (int i = 0; i < n; i++) cin >> a[i];int x, y;cin >> x >> y;for (int i = 0; i < n; i++) {if (a[i] == x || a[i] == y) {if (i + 1 < n && (a[i+1] == x || a[i+1] == y) && a[i+1] != a[i]) {cout << "Yes" << endl;return 0;} else break;}}cout << "No" << endl;
}

第二題 小美走公路

---

簡單模擬

代碼如下：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;long long a[n];long long sum = 0;for (int i = 0; i < n; i++) {cin >> a[i];sum += a[i];}    int x, y;cin >> x >> y;if (x > y) {long long t = y;y = x;x = t;}if (x == y) {cout << 0 << endl;return 0;}long long cost = 0;for (int i = x; i < y; i++) {cost += a[i];}cost = min(cost, sum - cost);cout << cost << endl;
}

第三題 小美的蛋糕切割

---

二維前綴和

代碼如下：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;long long a[n];long long sum = 0;for (int i = 0; i < n; i++) {cin >> a[i];sum += a[i];}    int x, y;cin >> x >> y;if (x > y) {long long t = y;y = x;x = t;}if (x == y) {cout << 0 << endl;return 0;}long long cost = 0;for (int i = x; i < y; i++) {cost += a[i];}cost = min(cost, sum - cost);cout << cost << endl;
}