首页 > 代码库 > leetCode系列----Unique Paths II
leetCode系列----Unique Paths II
这道题题目的意思是找图中的路径的数量。
一开始想着把这个图构造成一棵树（二叉树），这样看叶子节点有多少个是终点就可以判断有多少条路径了。
于是做了一个结构体：
struct baseData {
int x; //横向偏移
int y; //纵向偏移
baseData* bottom; //下方链接
baseData* right; //右方链接
};
还有一个 vector<baseData*> toDo; 用来存储没有遍历过的节点
接下来就处理toDo，直至其中不包含任何元素。处理过程如下：
baseData* head =newbaseData();
head->x =0;
head->y =0;
toDo.push_back(head);
while (toDo.size()>0) {
//取出最上面的一个指针
baseData* top = toDo[toDo.size()-1];
toDo.pop_back();
//如果是终点，则进行下一次循环
if (top->x == XNUMBER-1 && top->y == YNUMBER-1) {
PATHCOUNT++;
continue;
}
//右侧一个是0
if (top->y<XNUMBER-1 && obstacleGrid[top->x][top->y+1]==0) {
baseData* right = new baseData();
right->x = top->x;
right->y = top->y+1;
toDo.push_back(right);
top->right = right;
}else{
top->right =NULL;
}
//下侧一个是0
if (top->x<YNUMBER-1 && obstacleGrid[top->x+1][top->y]==0) {
baseData* bottom = new baseData();
bottom->x = top->x+1;
bottom->y = top->y;
toDo.push_back(bottom);
top->bottom = bottom;
}else{
top->bottom =NULL;
}
//释放访问过的存储空间
//delete top;
}
return PATHCOUNT;
刚开始没有释放处理过的节点的内存，结果除了 堆栈溢出的问题。于是做了delete top的处理。
但是又报了一个，超时的问题。这一下子，这样的做法就完全行不通了。分析了一下,应该是频繁的new 和 delete消耗了大量的时间，尤其是当数据量比较大时尤为明显。
于是换了一个思路，既然只要一个数目。那么终点的路径数目取决于其左侧和上侧的路径的数目之和，这样就减少很多时间和上的开销。
实现如下：
int XNUMBER = obstacleGrid.size();
int YNUMBER = obstacleGrid[0].size();
vector<vector<int>> grid(obstacleGrid.size(),vector<int>(obstacleGrid[0].size()));
//计算第一个
grid[0][0] = obstacleGrid[0][0] ==0 ? 1:0;
//计算第一行
for (int i=1; i<YNUMBER; i++) {
if (obstacleGrid[0][i]==0) {
grid[0][i] = grid[0][i-1];
}else{
grid[0][i] =0;
}
}
//计算第一列
for (int j=1;j<XNUMBER ; j++) {
if (obstacleGrid[j][0]==0) {
grid[j][0] = grid[j-1][0];
}else{
grid[j][0] =0;
}
}
//计算其他
for (int i=1; i<XNUMBER; i++) {
for (int j=1; j<YNUMBER; j++) {
if (obstacleGrid[i][j]==0) {
grid[i][j] = grid[i-1][j]+grid[i][j-1];
}else{
grid[i][j]=0;
}
}
}
return grid[XNUMBER-1][YNUMBER-1];
leetCode系列----Unique Paths II