问答题
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++) { // 下移 i 行
if (i > 0) {
for (int y = 0; y < m; y++) {
base_sum += matrix[i-1+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 + i][j + m] - matrix[x + i][j];
}
if (real_sum > result) {
result = real_sum;
}
}
}
return result;
}
2、iOS开发中常常用到KVO、Notification、Delegate、Block等技术进行消息的传递
1）请简述上述名词分别的含义
KVO是通知对象属性改变（property change）的一种机制，Foundation和其他很多苹果的框架的实现都依靠它。
Notification是一种非常好的工具，在两个不相关的对象之间广播消息，尤其是有附带信息的时候，你也不需要做其他任何事。
block是在OS X 10.6和iOS 4的时候才加进去的。Blocks替代了很多之前用delegate模式实现的地方。
delegate 是代理，就是我不想做的事情交给别人做
2）请简述在使用以上技术时，需要注意哪些问题
在代理中调用方法的时候使用的是系统的子线程，因此，当使用Delegate进行UI操作的时候，必须调用GCD的主线程方法：
dispatch_async(dispatch_get_main_queue(), <^(void)block>)，在block中写进行的UI操作代码。同时要防止强循环引用。
在通知的使用过程中Crash的原因很多情况都是注册观察者以后没有及时的注销观察者，当然这个情况在非ARC时代比较常见，但是这并不是说在现在的ARC时代就不会出现这个问题。往往一旦出现问题就很难追查，所以还是要养成及时注销的习惯。由于通知的使用极其简单，往往能够看到很多开发人员在开发过程中滥用NSNoticationCenter的现象。导致到处都是乱七八糟的通知，代码的可维护性和可读性非常差，即便是使用了宏定义也不能完全避免这些问题。比如在Debug的时候，当存在多个Observe的时候，简直就是要人命的感觉，想死的心都有了。在这方面Block和Delegate比Notification强太多了。
潜在的问题有可能出现在dealloc中对KVO的注销上。KVO的一种缺陷(其实不能称为缺陷，应该称为特性)是，当对同一个keypath进行两次removeObserver时会导致程序crash，这种情况常常出现在父类有一个kvo，父类在dealloc中remove了一次，子类又remove了一次的情况下。不要以为这种情况很少出现！当你封装framework开源给别人用或者多人协作开发时是有可能出现的，而且这种crash很难发现。不知道你发现没，目前的代码中context字段都是nil，那能否利用该字段来标识出到底kvo是superClass注册的，还是self注册的？ 回答是可以的。我们可以分别在父类以及本类中定义各自的context字符串，比如在本类中定义context为@"ThisIsMyKVOContextNotSuper";然后在dealloc中remove observer时指定移除的自身添加的observer。这样iOS就能知道移除的是自己的kvo，而不是父类中的kvo，避免二次remove造成crash
当在Block中引用某个外部变量的时候，Block内部只会进行只读拷贝，这也就意味着，即便你在使用Block之前修改了那个外部变量的值，那么在你使用的Block里面它的值依旧是最开始的那个外部变量的值。如果想要同步外部变量的值，那么就需要在block内部引用变量时，在前面加上__block关键字。（使用__block，是将变量地址传给block，不使用则传递的是变量值给block）
block本身是像对象一样可以retain，和release。但是，block在创建的时候，它的内存是分配在栈(stack)上，而不是在堆(heap)上。他本身的作于域是属于创建时候的作用域，一旦在创建时候的作用域外面调用block将导致程序崩溃。（MRC和ARC 有区别）
3）请简述以上技术使用场景
回调方法
在日常的开发过程中，我们经常会遇到一些完成之后的处理问题，比如完成网路请求之后的回调，或者页面加载完成之后的回调等。这个时候我们一般使用的是前两者方法，即Block或者Delegate。而在一对一传输回 调的时候明显Block的使用更加的简单高效，只需要在代码块中执行所需要的操作即可。在一对多的情况下，Delegate更加能够发挥出自己的优势。
跨层通信
有的时候我们需要实现在两个毫无关联的对象之间的通信，这个时候如果使用Block或者Delegate就势必会增加代码的耦合性，这样对于代码的结构来说是不健康的，因此这个时候使用Notification便是明智的选择。
UI响应事件
用户在于App的UI进行互动的时候，总会需要App进行交互响应，这个时候就毫无疑问的使用代理设计模式。而苹果官方给出的建议也是可以肯定的，在Cocoa Touch框架中我们也可以在几乎所有的UI交互控件的头文件里看到Delegate的成员变量，也正是印证了在UI响应事件上Delegate有着绝对的优势。
简单值得传递
当需要进行简单值得传递的时候，比如子控件传输给父控件所点击的IndexPath的时候，更加适合使用Block来传值。因为，如果只是为了传这一个简单的值而没有特别的业务处理而定义一个协议，然后实现协议，设置代理再写方法的话将十分麻烦，得不偿失，这个时候简单高效的Block就可以完美的替代Delegate完成任务了。
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 <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>
#include <memory.h>
#include <queue>
#include <functional>
using namespace std;
int rows, cols;
vector<string> mat;
bool visited[50][50][50][50];
struct Step
{
int manx, many;
int boxx, boxy;
int times;
bool checkman()
{
return manx >= 0 && manx < cols && many >= 0 && many < rows && mat[many][manx] == '.';
}
bool checkbox()
{
return boxx >= 0 && boxx < cols && boxy >= 0 && boxy < rows && mat[boxy][boxx] == '.';
}
bool checkvisit()
{
if (visited[manx][many][boxx][boxy])
return true;
visited[manx][many][boxx][boxy] = true;
return false;
}
};
int main(int argc, char** argv) {
cin >> rows >> cols;
mat.resize(rows);
int expectx, expecty;
Step InitStep;
for (size_t i = 0; i < rows; i++)
{
cin >> mat[i];
for (size_t j = 0; j < cols; j++)
{
if (mat[i][j] == 'S') {
InitStep.manx = j;
InitStep.many = i;
mat[i][j] = '.';
}
if (mat[i][j] == '0') {
InitStep.boxx = j;
InitStep.boxy = i;
mat[i][j] = '.';
}
if (mat[i][j] == 'E') {
expectx = j;
expecty = i;
mat[i][j] = '.';
}
}
}
InitStep.times = 0;
int dirs[4][2] = {
{ -1,0 },
{ 0,1 },
{ 1,0 },
{ 0,-1 }
};
memset(visited, 0, 50 * 50 * 50 * 50);
queue<Step> q;
q.push(InitStep);
int result = -1;
while (result == -1 && !q.empty())
{
Step front = q.front();
q.pop();
for (size_t dir = 0; dir < 4; dir++)
{
//方向 左下右上
Step nextStep = front;
nextStep.times++;
nextStep.manx += dirs[dir][0];
nextStep.many += dirs[dir][1];
if (!nextStep.checkman())
continue;
if (nextStep.manx == nextStep.boxx &&
nextStep.many == nextStep.boxy) {
nextStep.boxx += dirs[dir][0];
nextStep.boxy += dirs[dir][1];
if (!nextStep.checkbox())
continue;
}
if (nextStep.checkvisit())
continue;
if (nextStep.boxx == expectx &&
nextStep.boxy == expecty)
{
//cout << "找到"<<nextStep.times << endl;
result = nextStep.times;
break;
}
q.push(nextStep);
}
}
cout << result << 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:
代码：
int main()
{
int n, x;
cin >> n >> x;
long room[n];
for (int i = 0; i < n; i++) cin >> room[i];
x--;
int iii = x;
long min = room[x];
for (int i = x + n; i > x; i--) // 寻找分配房间 iii
if (room[i % n] < min) min = room[i % n], iii = i % n;
if (iii > x) x += n;
for (int i = iii + 1; i <= x; i++) room[i % n]--; // 处理多一轮循环
long cycle = room[iii];
for (int i = 0; i < n; i++) room[i] -= cycle; // 处理所有房间
room[iii] = cycle * n + x - iii; // 恢复分配房间人数
for (int i = 0; i < n - 1; i++) cout << room[i] << " ";
cout << room[n - 1];
return 0;
}
个人资料
推荐圈子
上一篇：
今日头条2018校招大数据方向（第二批）
猜你感兴趣的圈子：
标签： nextstep、房间、matrix、block、room、面试题
