เส้นทางที่ไม่ซ้ำกัน II  


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน VMware
การเขียนโปรแกรมแบบไดนามิก มดลูก

สมมติว่าชายคนหนึ่งยืนอยู่ในห้องขังแรกหรือมุมบนซ้ายของ “ ก×ข” เมทริกซ์ ผู้ชายสามารถขยับขึ้นหรือลงเท่านั้น บุคคลนั้นต้องการไปให้ถึงจุดหมายและปลายทางสำหรับเขาคือเซลล์สุดท้ายของ เมทริกซ์ หรือมุมล่างขวา

และหากมีอุปสรรคบางอย่างในนั้นบุคคลนั้นสามารถระบุเส้นทางที่ไม่ซ้ำกันได้กี่เส้นทาง ช่วยให้เขาไปถึงจุดหมายปลายทางโดยรู้ว่าไม่มีเส้นทางที่ไม่ซ้ำใคร

อุปสรรค์ถือเป็น 1 และช่องว่างถูกทำเครื่องหมายเป็น 0 ในเมทริกซ์

ตัวอย่าง  

Input:

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

Output:

2

คำอธิบาย:

เนื่องจากมีสิ่งกีดขวางเพียงตัวเดียวเท่านั้นที่อยู่ตรงกลางของเมทริกซ์ทั้งหมดซึ่งอนุญาตให้มีเส้นทางที่ไม่ซ้ำกันสองเส้นทางเท่านั้น: -

  1. ลง→ลง→ขวา→ขวา
  2. ขวา→ขวา→ลง→ลง

เส้นทางที่ไม่ซ้ำกัน IIหมุด

ในภาพด้านบนลูกศรสีน้ำเงินแสดงเส้นทาง 1 และลูกศรสีแดงแสดงเส้นทาง 2

ขั้นตอนวิธี  

  1. ตรวจสอบว่าเซลล์แรกที่เป็นอาร์เรย์ [0] [0] มี 1 หรือไม่จากนั้นส่งคืนเส้นทางที่ไม่ซ้ำกันเป็น 0 เนื่องจากไม่สามารถเคลื่อนไปข้างหน้าได้มากกว่านี้
  2. หากอาร์เรย์ [0] [0] ไม่มีค่า 1 ให้เริ่มต้นค่าของอาร์เรย์ [0] [0] = 1
  3. ตอนนี้ทำซ้ำในแถวแรกของอาร์เรย์และถ้าเซลล์นี้มี 1 หมายความว่าเซลล์ปัจจุบันมีอุปสรรค์อยู่และตั้งค่าของเซลล์เป็น 0 มิฉะนั้นให้ตั้งค่าของเซลล์นี้ตามเซลล์ก่อนหน้านี้ คืออาร์เรย์ [i] [j] = array [i] [j-1]
  4. ตอนนี้ให้วนซ้ำในคอลัมน์แรกของอาร์เรย์และถ้าเซลล์นี้มี 1 หมายความว่าเซลล์ปัจจุบันมีอุปสรรค์อยู่และตั้งค่าของเซลล์เป็น 0 มิฉะนั้นให้ตั้งค่าของเซลล์นี้เหมือนเซลล์ก่อนหน้านี้ คืออาร์เรย์ [i] [j] = array [i] [j-1]
  5. ตอนนี้ทำซ้ำในเมทริกซ์ทั้งหมดโดยเริ่มจากอาร์เรย์ของเซลล์ [1] [1]
  6. ตรวจสอบว่าเซลล์ไม่มีอุปสรรค์หรือไม่จากนั้นทำ arrayi, j] = array [i-1, j] + array [i, j-1]
  7. หากเซลล์มีอุปสรรค์ให้ตั้งค่าของเซลล์เป็น 0 เพื่อให้แน่ใจว่าเซลล์นั้นจะไม่เกิดซ้ำในเส้นทางอื่น
ดูสิ่งนี้ด้วย
Reverse Vowels ของ String Leetcode Solution

คำอธิบาย  

ดังนั้นแนวคิดหลักของเราในการแก้คำถามนี้คือถ้าเซลล์ไม่มีค่าเป็น 0 หมายความว่าเรามีหลายวิธีในการไปถึงเซลล์ปลายทางของเราคือผลรวมของวิธีการเข้าถึงเซลล์ที่อยู่ด้านบน เซลล์และผลรวมของจำนวนวิธีในการเข้าถึงเซลล์ทางซ้ายของเซลล์นั้น

ดังนั้นเราจึงใช้ฟังก์ชันบางอย่างที่จะช่วยเราในการแก้ปัญหาของเรา เราประกาศฟังก์ชัน getVal, getVal ได้รับอาร์กิวเมนต์บางอย่างดำเนินการบางอย่างและส่งคืนค่าบางอย่างซึ่งจะช่วยแก้ปัญหาต่อไปนี้:

  1. หากอยู่ในแถวแรกเซลล์มีอุปสรรค์จะตั้งค่าเป็น 0 มิฉะนั้นจะกำหนดค่าของเซลล์นั้นเหมือนกับเซลล์ก่อนหน้าที่เป็นอาร์เรย์ [i] [j] = array [i] [j-1 ].
  2. หากอยู่ในแถวแรกเซลล์มีอุปสรรค์จะตั้งค่าเป็น 0 มิฉะนั้นจะกำหนดค่าของเซลล์นั้นเหมือนกับเซลล์ก่อนหน้าที่เป็นอาร์เรย์ [i] [j] = array [i-1] [j ].

ตัวอย่าง

ลองยกตัวอย่าง Array = {{0,0,0}, {0,1,0}, {0,0,0}};

อาร์เรย์จะถูกส่งไปยัง findUniquePath

อาร์เรย์ = {{0,0,0}, {0,1,0}, {0,0,0}};

ดังนั้นเซลล์แรกที่เป็นอาร์เรย์ [0] [0] จึงไม่เท่ากับ 1

ตั้งค่าอาร์เรย์ [0] [0] = 1;

วนซ้ำคอลัมน์

i = 1

ถ้าอาร์เรย์ [1] [0] == 0 และอาร์เรย์ [0] [0] = 1 เป็นจริง

ดังนั้นอาร์เรย์ [1] [0] = 1;

ผม = 2;

ถ้าอาร์เรย์ [2] [0] == 0 และอาร์เรย์ [1] [0] = 1 เป็นจริง

ดังนั้นอาร์เรย์ [2] [0] = 1;

ตอนนี้ทำซ้ำไปเรื่อย ๆ

i = 1

ถ้าอาร์เรย์ [0] [1] == 0 และอาร์เรย์ [0] [0] = 1 เป็นจริง

ดังนั้นอาร์เรย์ [0] [1] = 1;

ผม = 2;

ถ้าอาร์เรย์ [0] [2] == 0 และอาร์เรย์ [0] [1] = 1 เป็นจริง

ดังนั้นอาร์เรย์ [0] [2] = 1;

ตอนนี้เริ่มจากอาร์เรย์ [1] [1]

ผม = 1, j = 1

ถ้าอาร์เรย์ [1] [1] == 0 เป็นเท็จ

ดังนั้นอาร์เรย์ [1] [1] = 0

ผม = 1, j = 2

ถ้าอาร์เรย์ [1] [2] == 0 เป็นจริง

ดูสิ่งนี้ด้วย
K-th องค์ประกอบที่เล็กที่สุดในเมทริกซ์ที่เรียงลำดับ

อาร์เรย์ [i] [j] = อาร์เรย์ [i - 1] [j] + อาร์เรย์ [i] [j - 1];

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

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

ผม = 2, j = 1

ถ้าอาร์เรย์ [2] [1] == 0 เป็นจริง

ดังนั้นอาร์เรย์ [2] [1] = 0

ผม = 2, j = 2

ถ้าอาร์เรย์ [2] [2] == 0 เป็นจริง

อาร์เรย์ [i] [j] = อาร์เรย์ [i - 1] [j] + อาร์เรย์ [i] [j - 1];

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

อาร์เรย์ [2] [2] = 2 + 0;

อาร์เรย์ [2] [2] = 2

นั่นคือเราจะส่งคืนอาร์เรย์ค่า [2] [2] ซึ่งหมายความว่า 2 คือเอาต์พุตที่เราต้องการ

การดำเนินงาน  

โปรแกรม C ++ สำหรับ Unique Paths II

#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

โปรแกรม Java สำหรับ Unique Paths II

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 คือจำนวนแถวและคอลัมน์ในเมทริกซ์ที่มอบให้กับเราเนื่องจากแต่ละเซลล์ถูกประมวลผลเพียงครั้งเดียว

ดูสิ่งนี้ด้วย
พิมพ์องค์ประกอบที่แตกต่างทั้งหมดของอาร์เรย์จำนวนเต็มที่ระบุ

ความซับซ้อนของอวกาศ

O (1) เนื่องจากไม่มีการใช้พื้นที่เพิ่มเติมเนื่องจากเราใช้งานอยู่ การเขียนโปรแกรมแบบไดนามิก.

อ้างอิง