独特之路II  


难度级别 中等
经常问 亚马逊 VMware的
动态编程 矩阵

假设一个人站在第一个牢房或 “ a×b” 矩阵。 一个人只能向上或向下移动。 该人想到达目的地,而对他而言,目的地是最后一个牢房。 矩阵 或右下角。

并且如果其中有一些障碍,则该人可以识别多少条独特的路径。 通过了解唯一路径来帮助他到达目的地。

在矩阵中,障碍被视为1,空间被标记为0。

使用案列  

输入:

[
[0,0,0]
[0,1,0]
[0,0,0]
]

输出:

2

说明:

因为在整个矩阵的中间仅存在一个障碍,这仅允许两条唯一的路径:

  1. 向下→向下→右→右
  2. 右→右→下→下

独特之路IIPin

在上图中,蓝色箭头显示路径1,红色箭头显示路径2。

算法  

  1. 检查第一个为array [0] [0]的单元格是否包含1,然后将唯一路径返回为0,因为它不能向前移动。
  2. 如果array [0] [0]不包含值1,则初始化array [0] [0] = 1的值。
  3. 现在,遍历数组的第一行,如果该单元格包含1,则意味着当前单元格中存在障碍,并将该单元格的值设置为0。否则,将该单元格的值设置为上一个单元格的值是array [i] [j] = array [i] [j-1]。
  4. 现在,遍历数组的第一列,如果该单元格包含1,则意味着当前单元格中存在障碍,并将该单元格的值设置为0。否则,将该单元格的值设置为上一个单元格的值是array [i] [j] = array [i] [j-1]。
  5. 现在,从单元格数组[1] [1]开始遍历整个矩阵。
  6. 检查单元格是否不包含任何障碍,然后执行arrayi,j] =数组[i-1,j] +数组[i,j-1]。
  7. 如果单元格包含障碍,则将单元格的值设置为0,以确保它不会在任何其他路径中重复。
参见
字符串Leetcode解决方案的反向元音

说明  

因此,我们解决此问题的主要思路是,如果一个单元格中的值不为0,则意味着到达目标单元格的方式之多是达到该单元格的方式之和。单元格以及到达该单元格左侧单元格的方式总数。

因此,我们实现了一些功能,这些功能将帮助我们解决问题。 我们声明了一个函数getVal,getVal获取一些参数来执行一些操作并返回一些值,这将解决以下问题:

  1. 如果在第一行中某个单元格包含障碍,则将其值设置为0,否则它将将该单元格的值设置为前一个单元格的值,即array [i] [j] = array [i] [j-1] ]。
  2. 如果在第一行中某个单元格包含障碍,则将其值设置为0,否则它将将该单元格的值设置为前一个单元格的值,即array [i] [j] = array [i-1] [j ]。

使用案列

因此,让我们以Array = {{0,0,0},{0,1,0},{0,0,0}}为例。

数组传递给findUniquePath

Array = {{{0,0,0},{0,1,0},{0,0,0}};

因此,它的第一个单元格为array [0] [0]不等于1。

这样设置,array [0] [0] = 1;

遍历列,

I = 1

如果array [1] [0] == 0并且array [0] [0] = 1为true

所以array [1] [0] = 1;

i = 2;

如果array [2] [0] == 0并且array [1] [0] = 1为true

所以array [2] [0] = 1;

现在遍历行,

I = 1

如果array [0] [1] == 0并且array [0] [0] = 1为true

所以array [0] [1] = 1;

i = 2;

如果array [0] [2] == 0并且array [0] [1] = 1为true

所以array [0] [2] = 1;

现在从数组[1] [1]开始

i = 1,j = 1

如果array [1] [1] == 0为假

所以数组[1] [1] = 0

i = 1,j = 2

如果array [1] [2] == 0为true

参见
排序矩阵中的第K个最小元素

array [i] [j] = array [i – 1] [j] + array [i] [j – 1];

so array[1][2]=array[0][2]+array[0][1];

array[1][2]=1+1=2;

i = 2,j = 1

如果array [2] [1] == 0为true

所以数组[2] [1] = 0

i = 2,j = 2

如果array [2] [2] == 0为true

array [i] [j] = array [i – 1] [j] + array [i] [j – 1];

so array[2][2]=array[1][2]+array[2][1];

数组[2] [2] = 2 + 0;

数组[2] [2] = 2

也就是说,我们将返回值array [2] [2],这意味着2是我们所需的输出。

实施   

独特路径II的C ++程序

#include<iostream>
using namespace std;
int getVal(int x, int y)
{
    if(x==0 && y==1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int findUniquePath(int arr[3][3])
{
    if (arr[0][0] == 1)
    {
        return 0;
    }
    arr[0][0] = 1;
    for (int i = 1; i < 3; i++)
    {
        arr[i][0] = getVal(arr[i][0],arr[i-1][0]);
    }
    for (int i = 1; i < 3; i++)
    {
        arr[0][i] = getVal(arr[0][i],arr[0][i-1]);
    }
    for (int i = 1; i < 3; i++)
    {
        for (int j = 1; j < 3; j++)
        {
            if (arr[i][j] == 0)
            {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
            else
            {
                arr[i][j] = 0;
            }
        }
    }
    return arr[2][2];
}
int main()
{
    int inputValue[3][3]= {{0,0,0},
                           {0,1,0},
                           {0,0,0}};
                           
    findUniquePath(inputValue);
    cout<<findUniquePath(inputValue);;
    return 0;
}
2

独特路径II的Java程序

class uniquePath2 {
  public static int getVal(int x, int y) {
    if (x == 0 && y == 1) {
      return 1;
    } else {
      return 0;
    }
  }
  public static int findUniquePath(int array[][]) {
    if (array[0][0] == 1) {
      return 0;
    }
    array[0][0] = 1;
    for (int i = 1; i<array.length; i++) {
      array[i][0] = getVal(array[i][0], array[i - 1][0]);
    }
    for (int i = 1; i<array[0].length; i++) {
      array[0][i] = getVal(array[0][i], array[0][i - 1]);
    }
    for (int i = 1; i<array.length; i++) {
      for (int j = 1; j<array[i].length; j++) {
        if (array[i][j] == 0) {
          array[i][j] = array[i - 1][j] + array[i][j - 1];
        } else {
          array[i][j] = 0;
        }
      }
    }

    int row = array.length;
    int col = array[0].length;
    return array[row - 1][col - 1];
  }
  public static void main(String[] args) {
    int inputValue[][] = {
      {
        0, 0, 0
      }, {
        0, 1, 0
      }, {
        0, 0, 0
      }
    };
    System.out.println(findUniquePath(inputValue));
  }
}
2

独特路径的复杂度分析II  

时间复杂度

O(a×b) 其中a和b是矩阵中的行数和列数,因为每个单元格仅处理一次。

参见
打印给定整数数组的所有不同元素

空间复杂度

O(1) 因为自从我们开始使用以来,没有多余的空间被利用 动态编程.

参考