今日头条2018校招Android方向（第三批）

问答题

1、以下函数用于找到整数矩阵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[0].size(); j++) {
       for (int x = 0; x < n; x++) {
         real_sum += matrix[x + i][j + m] - matrix[x + i][j - 1];
       }
       if (real_sum > result) {              result = real_sum;        }
     }
   }
   return result;
 }

2、简述Activity、Window、WindowManager、View、ViewRootImpl的作用和相互之间的关系。

解析：

每个activity有个window,window被windowmanager管理.

每个window都有decorview.

每个window都有ViewRootimpl.

绘制发起从ViewRootimpl.

事件传递发起冲ViewRootimpl.

绘制传递canvas, canvas来自surface.

3、App 发展到一定程度时，页面越来越多，工程越来越大，合作开发的人也越来越多，这时就可能需要引入路由系统，实现模块间的解耦。请设计一个路由系统，使得app内页面的跳转就像浏览器访问网页一样易于管理和解耦。

编程题

1、有一个推箱子的游戏, 一开始的情况如下图:

上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置，其中 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

例子说明1:

代码：

#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;
}

2、有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;
}