算法核心不在于框架用得有多熟练,更多在于逻辑和思维方式,很多情况都需要变换间接建模。本文将通过一个经典的面试题来描述思维过程,引导最终问题建模。 最近招聘市场各路神仙出没,小K也打算去凑一下热闹。 热身运动,小K先和面试官过了几招,不分胜负。 这招怎么化解呢,等小K先思考2分钟。 一般是先想一下有没有可以套用的算法框架,如果不能发现很明显的算法,可以先分析问题的规律,然后再尝试变换间接建模。我们先尝试把所有能发现的规律都找出来。 int i, j; i = 0; j = matrix[0].size() - 1; bool flag = false; while (i < matrix[0].size() && j >= 0) { if (matrix[i][j] > x) { --j; } else if (matrix[i][j] < x) { ++i; } else { return true; } } return false; } 按行二分,缩小列
int i, j, mid; i = up; j = matrix.size() - 1; while (i < j) { mid = (i + j) / 2; if (x < matrix[mid][right]) { j = mid - 1; } else if (x > matrix[mid][right]) { i = mid + 1; } else { i = j = mid; } } if (matrix[i][right] < x) ++i; return i; }
ofstream cout('a.in'); int s = 0; for (int i = 0; i < 5000; ++i) { for (int j = 0; j < 5000; ++j) { cout << s + i + j << ' '; } s += 4999; cout << endl; } }
|
|