google面经（挂了） - 未名空间(mitbbs.com)
1. 二维matrix，含0，1。 1是障碍。
00011
11100
从左上角出发到右下角， 可以往上，往下，往右移动。
把1变成0，使得你可以从左上角到右下角。
求最小的变化数字。
一般的题目是限定只能向下走和向右走，这样的话DP大家都是知道的，就是按逆对角刷
DP：
a(i,j) = min(cost(i,j+1) + a(i,j+1), cost(i+1,j) + a(i+1,j))
这个题目说可以向上走，使得为题复杂化了。但是只需改进DP方式仍然可以解决。这次
我们从右向左逐列刷DP。对于第j列，
for i = 1 to n, a_r(i,j) = cost(i,j+1) + a(i,j+1)
for i = 1 to n, a_u(i,j) = min(a_r(i,j), cost(i-1,j) + a_u(i-1,j))
for i = n to 1, a_d(i,j) = min(a_r(i,j), cost(i+1,j) + a_d(i+1,j))
for i = 1 to n, a(i,j) = min(a_r(i,j), a_u(i,j), a_d(i,j))
a_r(i,j)记录的是从i,j向右走的最佳方式。
a_u(i,j)记录的是从i,j向上走的最佳方式。
a_d(i,j)记录的是从i,j向下走的最佳方式。注意计算a_d的时候要从下往上，e.g. for
n to 1.
这样每个点只算了三次，整体复杂性依然是线性的。
这个加强版的DP可以解决普遍的问题，不局限于矩阵的值只能是0或1。
第一题我会用flood fill + m×n 空间
http://shibaili.blogspot.com/2015/07/google-interview-questions-3.html
2个角度(dfs / bfs)
#1 找出所有路径中，含1最少的那个路径
#2 最短路径，每个路径weight为0或者1, dijkstra
Dijkstra为O(n*lgn)，可用2个queue降低复杂度为O(n)。因为edge的weight只为0或1
2。 两个区间，左闭右开。数字可以是整数或者浮点，
要你判断两个区间是否相交。
特殊例子需要你自己定义。
Read full article from google面经（挂了） - 未名空间(mitbbs.com)
1. 二维matrix，含0，1。 1是障碍。
00011
11100
从左上角出发到右下角， 可以往上，往下，往右移动。
把1变成0，使得你可以从左上角到右下角。
求最小的变化数字。
一般的题目是限定只能向下走和向右走，这样的话DP大家都是知道的，就是按逆对角刷
DP：
a(i,j) = min(cost(i,j+1) + a(i,j+1), cost(i+1,j) + a(i+1,j))
这个题目说可以向上走，使得为题复杂化了。但是只需改进DP方式仍然可以解决。这次
我们从右向左逐列刷DP。对于第j列，
for i = 1 to n, a_r(i,j) = cost(i,j+1) + a(i,j+1)
for i = 1 to n, a_u(i,j) = min(a_r(i,j), cost(i-1,j) + a_u(i-1,j))
for i = n to 1, a_d(i,j) = min(a_r(i,j), cost(i+1,j) + a_d(i+1,j))
for i = 1 to n, a(i,j) = min(a_r(i,j), a_u(i,j), a_d(i,j))
a_r(i,j)记录的是从i,j向右走的最佳方式。
a_u(i,j)记录的是从i,j向上走的最佳方式。
a_d(i,j)记录的是从i,j向下走的最佳方式。注意计算a_d的时候要从下往上，e.g. for
n to 1.
这样每个点只算了三次，整体复杂性依然是线性的。
这个加强版的DP可以解决普遍的问题，不局限于矩阵的值只能是0或1。
第一题我会用flood fill + m×n 空间
http://shibaili.blogspot.com/2015/07/google-interview-questions-3.html
2个角度(dfs / bfs)
#1 找出所有路径中，含1最少的那个路径
#2 最短路径，每个路径weight为0或者1, dijkstra
Dijkstra为O(n*lgn)，可用2个queue降低复杂度为O(n)。因为edge的weight只为0或1
bool bfs(vector<vector<int> > &grid,vector<vector<bool> > &visit,queue<pair<int,int>> &q1,queue<pair<int,int>> &q2) { while (!q1.empty()) { int row = q1.front().first; int col = q1.front().second; if (row == grid.size() - 1 && col == grid[0].size() - 1) { return true; } q1.pop(); if (row + 1 < grid.size() && !visit[row + 1][col]) { visit[row + 1][col] = true; if (grid[row + 1][col] == 0) { q1.push(make_pair(row + 1,col)); }else { q2.push(make_pair(row + 1,col)); } } if (row - 1 >= 0 && !visit[row - 1][col]) { visit[row - 1][col] = true; if (grid[row - 1][col] == 0) { q1.push(make_pair(row - 1,col)); }else { q2.push(make_pair(row - 1,col)); } } if (col + 1 < grid[0].size() && !visit[row][col + 1]) { visit[row][col + 1] = true; if (grid[row][col + 1] == 0) { q1.push(make_pair(row,col + 1)); }else { q2.push(make_pair(row,col + 1)); } } if (col - 1 >= 0 && !visit[row][col - 1]) { visit[row][col - 1] = true; if (grid[row][col - 1] == 0) { q1.push(make_pair(row,col - 1)); }else { q2.push(make_pair(row,col - 1)); } } } return false;}int findPath(vector<vector<int> > &grid) { int m = grid.size(); int n = grid[0].size(); queue<pair<int,int>> q1; queue<pair<int,int>> q2; int count = 0; q1.push(make_pair(0,0)); vector<vector<bool> > visit(m,vector<bool>(n,false)); visit[0][0] = true; while (!q1.empty()) { if (bfs(grid,visit,q1,q2)) { return count; } count++; queue<pair<int,int>> empty; q1 = q2; swap(q2,empty); } return -1;}2。 两个区间，左闭右开。数字可以是整数或者浮点，
要你判断两个区间是否相交。
特殊例子需要你自己定义。
Read full article from google面经（挂了） - 未名空间(mitbbs.com)
