问答题
以下函数用于找到整数矩阵matrix中，元素之和最大的n行m列的子矩阵的元素之和。请指出程序代码中错误的地方（问题不止一处，请尽量找出所有你认为错误的地方），并在不新增代码行的情况下将问题修复。
int maxSubmatrixSum(std::vector<std::vector<int>> matrix,
int n, int m) {
int base_sum;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
base_sum += matrix[i][j];
}
}
int result = 0;
for (int i = 0; i + n < matrix.size(); i++) {
if(i > 0){
for (int y = 0; y < m; y++){
base_sum += matrix[i + n][y] - matrix[i - 1][y];
}
}
int real_sum = base_sum;
if (real_sum > result) {
result = real_sum;
}
for (int j = 0; j + m < matrix.size(); j++) {
for (int x = 0; x < n; x++) {
real_sum += matrix[x][j + m] - matrix[x][j - 1];
}
if (real_sum > result) {
result = real_sum;
}
}
}
return result;
}
修改后代码：
int maxSubmatrixSum(std::vector<std::vector<int>> matrix,
int n, int m) {
int base_sum;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
base_sum += matrix[i][j];
}
}
int result = 0;
for (int i = 0; i + n < matrix.size(); i++) {
if(i > 0){
for (int y = 0; y < m; y++){
base_sum += matrix[i + n][y] - matrix[i - 1][y];
}
}
int real_sum = base_sum;
if (real_sum > result) {
result = real_sum;
}
for (int j = 0; j + m < matrix.size(); j++) {
for (int x = 0; x < n; x++) {
real_sum += matrix[x][j + m] - matrix[x][j - 1];
}
if (real_sum > result) {
result = real_sum;
}
}
}
return result;
}
2、二阶魔方又叫小魔方，是2*2*2的立方形结构。每一面都有4个块，共有24个块。每次操作可以将任意一面逆时针或者顺时针旋转90°，如将上面逆时针旋转90°操作如下。
Nero在小魔方上做了一些改动，用数字替换每个块上面的颜色，称之为数字魔方。魔方上每一面的优美度就是这个面上4个数字的乘积，而魔方的总优美度就是6个面优美度总和。
现在Nero有一个数字魔方，他想知道这个魔方在操作不超过5次的前提下能达到的最大优美度是多少。
魔方展开后每一块的序号如下图：
输入描述:
输入一行包含24个数字，按序号顺序给出魔方每一块上面的数字。所有数大小范围为[-100,100]。
输出描述:
输出一行包含一个数字，表示最大优美度。
输入例子1:
2 -3 -2 3 7 -6 -6 -7 9 -5 -9 -3 -2 1 4 -9 -1 -10 -5 -5 -10 -4 8 2
输出例子1:
8281
例子说明1:
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mp[6][24] = {
// {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23},
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 21, 20, 10, 11, 12, 13, 18, 16, 19, 17, 15, 14, 22, 23},
{1, 3, 0, 2, 23, 22, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 9, 8},
{0, 21, 2, 23, 4, 5, 6, 1, 9, 15, 10, 11, 12, 3, 8, 14, 16, 7, 18, 13, 20, 17, 22, 19},
{20, 1, 22, 3, 10, 4, 0, 7, 8, 9, 11, 5, 2, 13, 14, 15, 6, 17, 12, 19, 16, 21, 18, 23},
{0, 1, 11, 5, 4, 16, 12, 6, 2, 9, 10, 17, 13, 7, 3, 15, 14, 8, 18, 19, 20, 21, 22, 23},
{10, 4, 2, 3, 18, 5, 6, 7, 8, 0, 19, 11, 12, 13, 14, 1, 16, 17, 15, 9, 21, 23, 20, 22}
};
const int face[6][4] = {
{0, 1, 2, 3},
{4, 5, 10, 11},
{6, 7, 12, 13},
{8, 9, 14, 15},
{16, 17, 18, 19},
{20, 21, 22, 23}
};
LL ans;
void flip(vector<int> &a, int index)
{
vector<int> b(a);
for (vector<int>::size_type i = 0; i < a.size(); i++)
b[i] = a[mp[index][i]];
a = b;
}
LL getSum(vector<int> &arr)
{
LL ret = 0;
for (int i = 0; i < 6; i++) {
LL s = 1;
for (int j = 0; j < 4; j++)
s *= arr[face[i][j]];
ret += s;
}
return ret;
}
void dfs(int dep, vector<int> arr)
{
ans = max(ans, getSum(arr));
if (dep == 5) {
return ;
}
for (int i = 0; i < 6; i++) {
vector<int> a(arr);
flip(a, i);
dfs(dep + 1, a);
flip(a, i);
flip(a, i);
dfs(dep + 1, a);
}
}
void debug()
{
for (int i = 0; i < 6; i++) {
int a[24];
memset(a, 0, sizeof(a));
cout << i << ":" << endl;
for (int j = 0; j < 24; j++)
a[mp[i][j]]++;
for (int j = 0; j < 24; j++)
printf("%d ", a[j]);
puts("");
}
}
int main()
{
// debug();
// freopen("in1", "r", stdin);
while (true) {
bool isBreak = true;
vector<int> arr(24);
for (int i = 0; i < 24; i++)
if (cin >> arr[i])
isBreak = false;
else
break;
if (isBreak)
break;
ans = -0x3f3f3f3f3f;
dfs(0, arr);
cout << ans << endl;
}
return 0;
}
上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置，其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置，你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;
..S0.. -> ...S0.
注意不能将箱子推动到'#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。
输入描述:
第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);
后面为n行字符串,每行字符串有m字符, 表示游戏盘面;
输出描述:
一个数字,表示最少几步能完成游戏,如果不能,输出-1;
输入例子1:
3 6
.S#..E
.#.0..
......
输出例子1:
11
代码：
#include <bits/stdc++.h>
using namespace std;
const int dirx[] = {-1, 0, 1, 0};
const int diry[] = {0, 1, 0, -1};
int n, m;
struct Point {
int x, y;
Point() {}
Point(int x, int y) : x(x), y(y) {}
bool operator == (const Point &other) const {
return x == other.x && y == other.y;
}
};
struct Node {
Point peo, box;
int step;
Node() {}
Node(Point peo, Point box, int step = 0) :
peo(peo), box(box), step(step) {}
bool operator < (const Node &other) const {
return step > other.step;
}
};
struct Peo {
Point point;
int step;
Peo() {}
Peo(Point point, int step = 0) :
point(point), step(step) {}
};
bool check(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs(Point src, Point des, Point box, vector<string> &mp)
{
queue<Peo> que;
vector<vector<bool> > used(n, vector<bool>(m, false));
que.push(src);
used[src.x][src.y] = true;
int ret = -1;
while (!que.empty()) {
auto now = que.front();
que.pop();
if (now.point == des) {
ret = now.step;
break;
}
for (int k = 0; k < 4; k++) {
int tx = now.point.x + dirx[k];
int ty = now.point.y + diry[k];
if (check(tx, ty) && mp[tx][ty] == '.' && !(Point(tx, ty) == box) && !used[tx][ty])
que.emplace(Point(tx, ty), now.step + 1), used[tx][ty] = true;
}
}
return ret;
}
int main()
{
// freopen("in", "r", stdin);
while (cin >> n >> m) {
string str;
vector<string> mp;
Point initS, initE, initZ;
for (int i = 0; i < n; i++) {
cin >> str;
mp.push_back(str);
for (int j = 0; j < str.size(); j++) {
if (str[j] == 'S') {
initS = Point(i, j);
mp[i][j] = '.';
break;
}
}
for (int j = 0; j < str.size(); j++) {
if (str[j] == 'E') {
initE = Point(i, j);
mp[i][j] = '.';
break;
}
}
for (int j = 0; j < str.size(); j++) {
if (str[j] == '0') {
initZ = Point(i, j);
mp[i][j] = '.';
break;
}
}
}
vector<vector<bool> > used(n * m + 1000, vector<bool>(n * m + 1000, false));
priority_queue<Node> que;
que.emplace(initS, initZ);
used[initS.x * n + initS.y][initZ.x * n + initZ.y] = true;
int ans = 0x3f3f3f3f;
int cnt = 0;
for (int k = 0; k < 4; k++)
if (check(initE.x + dirx[k], initE.y + diry[k]) && mp[initE.x + dirx[k]][initE.y + diry[k]] == '.')
++cnt;
while (!que.empty()) {
auto now = que.top();
que.pop();
if (now.box == initE) {
cnt--;
ans = min(now.step, ans);
if (cnt == 0)
break;
else
continue;
}
for (int k = 0; k < 4; k++) {
int tmpSx = now.box.x + dirx[k];
int tmpSy = now.box.y + diry[k];
int tmpZx = now.box.x + dirx[(k + 2) % 4];
int tmpZy = now.box.y + diry[(k + 2) % 4];
if (!check(tmpSx, tmpSy) || !check(tmpZx, tmpZy))
continue;
if (mp[tmpSx][tmpSy] != '.')
continue;
if (mp[tmpZx][tmpZy] != '.')
continue;
if (used[now.box.x * m + now.box.y][tmpZx * m + tmpZy])
continue;
int step = bfs(now.peo, Point(tmpSx, tmpSy), now.box, mp);
if (step == -1)
continue;
que.emplace(now.box, Point(tmpZx, tmpZy), step + now.step + 1);
used[now.box.x * m + now.box.y][tmpZx * m + tmpZy] = true;
}
}
cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
}
return 0;
}
4、有n个房间，现在i号房间里的人需要被重新分配，分配的规则是这样的：先让i号房间里的人全都出来，接下来按照 i+1, i+2, i+3, ... 的顺序依此往这些房间里放一个人，n号房间的的下一个房间是1号房间，直到所有的人都被重新分配。
现在告诉你分配完后每个房间的人数以及最后一个人被分配的房间号x，你需要求出分配前每个房间的人数。数据保证一定有解，若有多解输出任意一个解。
输入描述:
第一行两个整数n, x (2<=n<=10^5, 1<=x<=n)，代表房间房间数量以及最后一个人被分配的房间号；
第二行n个整数 a_i(0<=a_i<=10^9) ，代表每个房间分配后的人数。
输出描述:
输出n个整数，代表每个房间分配前的人数。
输入例子1:
3 1
6 5 1
输出例子1:
4 4 4
例子说明1:
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n, k;
while (~scanf("%d%d", &n, &k)) {
vector<LL> arr;
LL theMin = 0x3f3f3f3f3f;
for (int i = 0; i < n; i++) {
LL x;
scanf("%lld", &x);
arr.push_back(x);
theMin = min(theMin, x);
}
if (arr[k - 1] == theMin) {
for (vector<LL>::size_type i = 0; i < arr.size(); i++) {
if (i == k - 1)
printf("%lld", 1LL * theMin * n);
else
printf("%lld", arr[i] - theMin);
putchar(i == arr.size() - 1 ? '\n' : ' ');
}
} else {
int i, d;
for (i = k - 1, d = 0; theMin != arr[(i + n) % n]; i--, d++)
arr[(i + n) % n] = arr[(i + n) % n] - theMin - 1;
arr[(i + n) % n] = 1LL * theMin * n + d;
if ((i + n) % n != k) {
for (--i; (i + n) % n != k; i--)
arr[(i + n) % n] = arr[(i + n) % n] - theMin;
arr[(i + n) % n] = arr[(i + n) % n] - theMin;
}
for (vector<LL>::size_type i = 0; i < arr.size(); i++)
printf("%lld%c", arr[i], i == arr.size() - 1 ? '\n' : ' ');
}
}
return 0;
}
问答题
1、在生产环境，我们常常要存储一些像服务参数、功能开关之类的键值。传统的做法是把配置都写到文件里，然后同步到线上每台机器上。随着机器变多，配置文件变得难以管理，并且容易出现不一致的情况。我们希望设计一个配置服务来解决这个问题。
统一配置服务可能会存在以下问题：由于是非常核心的服务，如果存在单节点问题对服务可用性影响非常大；线上可能读取非常频繁，尽可能提供高性能的服务同时，也要考虑横向扩容能力；需要保证配置在期望的时间内下发与更新；
请设计一个存储服务，包含但不限于以下角色：服务端（可能由多个节点组成），客户端（读取、写入一个配置），其他（如旁路的监控等）；
系统假设：
1、存储量都在1GB以内，单机内存可以存储下；
2、每秒写入在 1000 以内
3、每秒读取在 1000000 以上
4、使用尽量少的节点
5、无论什么时候，服务总是可以读写
6、允许故障期间读到老的配置数据
7、故障恢复后，数据保持同步
解析：
典型的zookeeper适用场景。配置信息在集群中各节点共享，数据内容动态变化。
服务端：一个leader，多个follower，多个observer。主备模式。一般总量在奇数3到5台。
leader负责读写，客户端所有写操作都传到leader 上完成，其他节点可以提供读操作。横向扩展增加机器可以提高读性能，但不提高集群的事务处理能力。各节点数据实时一致。数据一致性和崩溃恢复由ZAB协议保证。
集群中每个节点向leader注册watcher监听，数据更新时leader广播机制向集群广播更新数据，来实现数据一致性。若leader宕掉，监听节点收到通知，并进行leader选举，采用过半机制提高集群性能。
个人资料
推荐圈子
上一篇：
今日头条2018校招ios方向（第三批）
猜你感兴趣的圈子：
标签： arr、point、int、box、matrix、面试题
