2020/9/5 18:30 搜狗自闭笔试题
1、不知道为什么差5%过不去，找了半天没找到，第一题太玄学了
95%代码
class Solution1 {
public:
int numberofprize(int a, int b, int c) {
// write code here
unsigned long long x = max(max(a, b), c);
unsigned long long z = min(min(a, b), c);
unsigned long long y = a + b + c - x - z;
unsigned long long ans = z;
x -= z;
y -= z;
if (x >= y * 3) {
ans += y;
x -= (3 * y);
ans += (x / 5);
}
else ans += ((x + y) / 4);
return ans;
}
};
2、这个直接遍历判断行不行，答案最少是2，不考虑没房子的情况
100%代码
class Solution2 {
public:
int getHouses(int t, int* xa, int xalen) {
// write code here
int ans = 2;
for (int i = 2; i < xalen; i += 2) {
double len = xa[i] - xa[i + 1] / 2.0 - (xa[i - 2] + xa[i - 1] / 2.0);
if (len > t) {
ans += 2;
}
if (len == t) {
ans++;
}
}
return ans;
}
};
3、 算是dp吧，最近刚学，班门弄斧了
f[ i ][ j ]：表示前 j 个数字最后一个数字是 i 的方案数量
之后的思路，打字也说不清楚，可以好好想想f[ i ][ j ]的意义
记得初始化，
最后求 n 的答案，就是先将 i = 0 1 2 3 4 5 6 7 8 9 的f[ i ][ n ]全加起来，记为ans
注意以上过程中没有判重，如果方案中存在原数据，那也只可能存在一个
所以，答案就是ans或者ans-1
至于要不要减一，就要看能不能再生成这个密码
我找了一个小规律：
如果所有数据挨着的差值大于1
比如说：9 4 6 2
这种，是肯定不可能的，
假如说：9已经有了，然后下一位就只能是 （9+4）/ 2 ，不可能跟4相同的
这种情况是不会出现重复的。
如果差值小于等于1
比如：4 5 4 3 4
4有了，下一个数字，可以是5
5 下一个数字可以是4·····
这种情况是有重复的，需要减一 100%代码
class Solution3 {
public:
long long f[10][55] = { 0 };
long long getPasswordCount(string s) {
// write code here
int n = s.size();
for (int i = 0; i < 10; i++) f[i][1] = 1;
for (int i = 2; i <= n; i++) {
int t = s[i - 1] - '0';
for (int j = 0; j < 10; j++) {
f[(t + j) / 2][i] += f[j][i - 1];
if ((t + j) & 1) f[(t + j) / 2 + 1][i] += f[j][i - 1];
}
}
long long ans = 0;
for (int i = 0; i < 10; i++) ans += f[i][n];
for (int i = 1; i < n; i++) {
if (abs(s[i] - s[i - 1]) > 1) {
return ans;
}
}
return ans - 1;
}
};
查看13道真题和解析