首页 > 代码库 > [mock]8月8日
[mock]8月8日
第一题是整数的方阵，求其中的子方阵，和最大。返回最大和以及子方阵宽度。因为做了topcoder的题，所以比较顺手，O(n^3)的复杂度。
pair<int,int> maxiSum(vector<vector<int> > &a) { //first is n second is sum int N = a.size(); int retVal = INT_MIN; int n = 1; // fix two columns, i, j for (int i = 0; i < N; i++) { vector<int> sum(N); for (int j = i; j < N; j++) { // calc the sum per line for (int k = 0; k < N; k++) { sum[k] = sum[k] + a[k][j]; } // calc the sum of the squere with i, j int tmpSum = 0; int w = j - i; for (int m = 0; m < N; m++) { if (m < w) { tmpSum += sum[m]; } else if (m == w) { tmpSum += sum[m]; if (tmpSum > retVal) { retVal = tmpSum; n = w + 1; } } else { tmpSum += sum[m]; tmpSum -= sum[m - w - 1]; if (tmpSum > retVal) { retVal = tmpSum; n = w + 1; } } } } } return make_pair(n, retVal);}第二题，是有个0和1的矩阵，求里面每个位置到最近的0的距离（类似曼哈顿距离）。这个题一开始想动态规划什么的，都不合适，比较像洪泛，但如果从每个0或1出发，就效率很低，n^4和完全枚举是一样的。后来想到和之前topcoder的一道题挺像，可以先把0全部放到queue里面，然后逐步往外扩，便可求得。
void make(vector<vector<int> > &matrix) { int N = matrix.size(); vector<vector<int> > dist; vector<vector<bool> > visited; dist.resize(N); visited.resize(N); for (int i = 0; i < N; i++) { dist[i].resize(N); visited[i].resize(N); } queue<pair<int, int> > que; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (matrix[i][j] == 0) { dist[i][j] = 0; visited[i][j] = true; que.push(make_pair(i, j)); } } } while (!que.empty()) { pair<int, int> pp = que.front(); que.pop(); if (valid(pp.first - 1, pp.second, visited)) { dist[pp.first - 1][pp.second] = dist[pp.first][pp.second] + 1; que.push(make_pair(pp.first - 1, pp.second)); visited[][] = true; } if (valid(pp.first, pp.second - 1, visited)) { } if (valid(pp.first + 1, pp.second, visited)) { } if (valid(pp.first, pp.second + 1, visited)) { } } // copy to matrix matrix = dist;}bool valid(int i, int j, vector<vector<bool> > & visited) { // return whether we need to process this elem int N = visited.size(); if (i < 0 || j < 0 || i >= N || j >= N || visited[i][j]) { return false; } return true;}遍历四个方向的代码其实应该更精简，类似如下：
dx[] = {-1,0,1,0}dy[] = {0,1,0,-1}x + dx[i]y + dy[i]第三题当时没有想出来，是求一个数组中子段和的绝对值最小值。比如如下数组，就是1+2+ -3的绝对值最小。
{1，2，－3，－100，3}这个题目很自然会想到去用最大子段和的做法，但是（应该）不能类似动态规划降到O(n)。关键是，不满足最优子问题的特性。比如该数组中前三个元素的最优解是0，前两个元素的最优解是2，0没有用到之前最优解地方。
那么正确的做法是可以记录之前的前缀和，然后排序，就可以求得了。因为：|sum[i..j]| = |p[j] - p[i - 1]|，p是前缀和，那么排完序后，相邻的两个就能求得绝对值最小，只是要注意，i从0开始，那么p[-1]就是不包括0的情况，就是0，要在前缀和数组里加一个0.
本题的前缀和数组排序完了就是如下，里面两个0，一个开始之前p[-1]，一个p[2]，就能求出sum[0..2]=0，绝对值最小。
{-97, -94, 0, 0, 1, 3}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。