第一道：给定四个点(1,6) (2,5) (3,7) (4,10)，用一条直线y=ax+b去最好的拟合这些点，令均方误差最小。
感觉之前在腾讯实习笔试时遇到过，代码如下：
vector<int> x = { 1, 2, 3, 4 };
vector<int> y = { 6, 5, 7, 10 };
int n = x.size();
double a = 0, b = 0, lr = 0.001;
while (true)
{
double g_a = 0, g_b = 0;
for (int i = 0; i < n; i++) {
g_a += 2 * x[i] * (a*x[i] + b - y[i]);
g_b += 2 * (a*x[i] + b - y[i]);
}
g_a /= n; g_b /= n;
a = a - lr * g_a;
b = b - lr * g_b;
double loss = 0;
for (int i = 0; i < n; i++) {
loss += pow((a * x[i] + b - y[i]), 2);
}
//loss卡在4.2就降不下去
if (loss < 4.2) break;
}
cout << a << endl;
cout << b << endl; 笔试时候用的中心扩展，只A了64%，参考力扣516写的动态规划，把dp数组单字母的情况初始化为0，应该可以AC吧。
string s;
cin >> s;
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
cout << dp[0][n-1] << endl; 没想明白，为了分数，手动写了个规律，只能过42%。
现在复盘来看，是把元素分成两部分，每部分交换n(n-1)/2次即可。
个人理解例如1-2-3-4-5-6-7 可以变成3-2-1-7-6-5-4，由于是个圆圈，所以就是逆序了。
int n;
cin >> n;
vector<int> res(n + 1, 0);
res[1] = 0; res[2] = 1; res[3] = 1;
if (n > 3) {
int l = n / 2;
int r = n / 2 + n % 2;
res[n] = l*(l - 1) / 2 + r*(r - 1) / 2;
}
cout << res[n] << endl; 
全部评论
(7) 回帖