ວິທີແກ້ໄຂ Leetcode ທີ່ເປັນເອກະລັກ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance ເຟສບຸກ Goldman Sachs ກູໂກ ວຽກຄະນິດສາດ Microsoft Oracle Qualtrics Salesforce SnapChat Uber VMware Walmart Labs
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ບັນຫາ Unique Paths Leetcode Solution ລະບຸວ່າທ່ານໄດ້ຮັບສອງຕົວເລກທີ່ສະແດງເຖິງຂະ ໜາດ ຂອງຕາຂ່າຍໄຟຟ້າ. ການໃຊ້ຂະ ໜາດ ຂອງ ຕາຂ່າຍໄຟຟ້າ, ຄວາມຍາວ, ແລະຄວາມກວ້າງຂອງຕາຂ່າຍໄຟຟ້າ. ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາ ຈຳ ນວນເສັ້ນທາງທີ່ເປັນເອກະລັກຈາກເບື້ອງຊ້າຍດ້ານເທິງຂອງຕາຂ່າຍໄຟຟ້າໄປຫາມຸມຂວາລຸ່ມ. ມີຂໍ້ ຈຳ ກັດອີກຢ່າງ ໜຶ່ງ ກ່ຽວກັບທິດທາງການເຄື່ອນໄຫວ, ໃນຈຸດເວລາໃດກໍ່ຕາມ, ຄົນເຮົາສາມາດເຄື່ອນໄຫວໄດ້ພຽງແຕ່ໃນທິດທາງລົງຫລືດ້ານຂວາ.

ຍົກຕົວຢ່າງ

row: 2, column: 2
2

ຄຳ ອະທິບາຍ: ມີພຽງສອງທາງທີ່ຈະເຮັດໄດ້ ສຳ ເລັດວຽກງານ. ກ່ອນອື່ນທ່ານຈະຍ້າຍໄປທາງຂວາຫລືລຸ່ມ. ຖ້າທ່ານຍ້າຍໄປທາງຂວາທ່ານສາມາດຍ້າຍລົງລຸ່ມໄດ້. ຖ້າທ່ານໄດ້ຍ້າຍລົງ, ຫຼັງຈາກນັ້ນທ່ານສາມາດຍ້າຍພຽງແຕ່ໃນທິດທາງລຸ່ມ. ສະນັ້ນ, ມີພຽງ 2 ວິທີເທົ່ານັ້ນທີ່ເປັນໄປໄດ້.

ວິທີແກ້ໄຂ Leetcode ທີ່ເປັນເອກະລັກ

row: 2, column: 3
3

ຄຳ ອະທິບາຍ: ມີ 6 ວິທີທີ່ຈະໄປເຖິງຈຸດ ໝາຍ. ພິຈາລະນາຖ້າທ່ານຍ້າຍໄປທາງຂວາ, ຫຼັງຈາກນັ້ນບັນຫາໄດ້ຖືກຫຼຸດລົງເປັນຕົວຢ່າງຂ້າງເທິງແລະທ່ານມີ 2 ວິທີທີ່ຈະໄປຮອດມຸມຂວາລຸ່ມ. ຖ້າທ່ານຕ້ອງການລົງ, ຫຼັງຈາກນັ້ນທ່ານມີວິທີດຽວທີ່ຈະໄປເຖິງມຸມຂວາລຸ່ມ. ດັ່ງນັ້ນ, ຈຳ ນວນວິທີການທັງ ໝົດ ທີ່ຈະໄປເຖິງທີ່ສຸດແມ່ນ 3.

ວິທີການຂອງ Brute Force ສຳ ລັບວິທີແກ້ໄຂ Leetcode ທີ່ເປັນເອກະລັກ

ປັນຫາທີ່ເປັນເອກະລັກຂອງ Leetcode Solution ສາມາດແກ້ໄຂໄດ້ຢ່າງຕໍ່ເນື່ອງ. ຄືກັນກັບທີ່ພວກເຮົາໄດ້ເຮັດໃນຕົວຢ່າງທີສອງ, ບ່ອນທີ່ພວກເຮົາຫຼຸດຜ່ອນບັນຫາທີ່ມອບໃຫ້ເປັນ 2 ໂຄງການຍ່ອຍ. ສິ່ງດຽວກັນແມ່ນສິ່ງທີ່ພວກເຮົາຈະເຮັດໃນການແກ້ໄຂບັນຫານີ້. ເມື່ອໃດທີ່, ພວກເຮົາຍ້າຍໄປທາງຂວາ, ຫຼັງຈາກນັ້ນບັນຫາຈະຖືກຫຼຸດລົງເປັນໂຄງການຍ່ອຍ (ແຖວ, ຖັນ -1). ຖ້າພວກເຮົາໄດ້ຍ້າຍໄປໃນທິດທາງທີ່ຫຼຸດລົງ, ບັນຫາຈະຖືກຫຼຸດລົງເປັນ (ແຖວ -1, ຖັນ). ພວກເຮົາສາມາດລະຫັດວິທີແກ້ໄຂບັນຫານີ້ຄືນໄດ້ງ່າຍ. ແຕ່ສິ່ງນີ້ຈະເກີນ ກຳ ນົດເວລາເພາະວ່າການແກ້ໄຂບັນຫາແມ່ນບໍ່ມີປະສິດຕິຜົນສູງສຸດ.

ລະຫັດ ສຳ ລັບວິທີການ ກຳ ລັງແຮງງານ

ລະຫັດ C ++

#include <bits/stdc++.h>
using namespace std;

int uniquePaths(int m, int n) {
    if(n==1 || m==1)return 1;
    return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (2 ^ ສູງສຸດ (m, n)), ເນື່ອງຈາກຄວາມສັບສົນທີ່ໃຊ້ເວລາເລກ ກຳ ລັງຍ້ອນການເຮັດວຽກທີ່ເອີ້ນຄືນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (ສູງສຸດ (m, n), ຊ່ອງທີ່ໃຊ້ໂດຍ compiler stack. ນີ້ຂື້ນກັບລະດັບຄວາມສູງຂອງຕົ້ນໄມ້ທີ່ເອີ້ນຄືນ.

ວິທີການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ວິທີການທີ່ໄດ້ອະທິບາຍຂ້າງເທິງນີ້ພາຍໃຕ້ການແກ້ໄຂບັນຫາສາມາດຈົດ ຈຳ ໄດ້ງ່າຍ. ເນື່ອງຈາກວ່າ ໜ້າ ທີ່ເອີ້ນຄືນແມ່ນຂື້ນກັບສອງຕົວແປເຊິ່ງແຖວ, ແລະຖັນ. ດັ່ງນັ້ນພວກເຮົາສ້າງ 2D DP array ແລະເກັບມ້ຽນຜົນຂອງແຕ່ລະລັດ. ສິ່ງນີ້ຈະຊ່ວຍປັບປຸງຄວາມສັບສົນຂອງເວລາໃຫ້ດີຂື້ນເພາະວ່າພວກເຮົາບໍ່ໄດ້ແກ້ໄຂບັນຫາດຽວກັນ.

ລະຫັດການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ສຳ ລັບເສັ້ນທາງທີ່ເປັນເອກະລັກ Leetcode Solution

ລະຫັດ C ++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> dp;
int uniquePathsUtil(int m, int n) {
    if(m == 1 || n == 1) return 1;
    if(dp[m][n] != -1)
        return dp[m][n];
    return dp[m][n] = uniquePathsUtil(m-1, n) + uniquePathsUtil(m, n-1);
}

int uniquePaths(int m, int n) {
    dp.clear();
    dp.assign(m+1, vector<int>(n+1, -1));
    return uniquePathsUtil(m, n);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    private static int uniquePathsUtil(int m, int n, int[][] dp) {
        if(m == 1 || n == 1) return 1;
        if(dp[m][n] != 0)
            return dp[m][n];
        return dp[m][n] = uniquePathsUtil(m-1, n, dp) + uniquePathsUtil(m, n-1, dp);
    }

    private static int uniquePaths(int m, int n) {
        int dp[][] = new int[m+1][n+1];
        return uniquePathsUtil(m, n, dp);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (N * M), ບ່ອນທີ່ N, M ຖືກ ນຳ ໃຊ້ເພື່ອເປັນຕົວແທນ ຈຳ ນວນແຖວ, ແລະຖັນໃນຕາຂ່າຍໄຟຟ້າ. ເນື່ອງຈາກວ່າມີທັງ ໝົດ ລັດ N * M, ຄວາມສັບສົນເວລາກໍ່ແມ່ນ O (N * M).

ຄວາມສັບສົນໃນອະວະກາດ

O (N * M), ພື້ນທີ່ທີ່ຕ້ອງການແມ່ນ ສຳ ລັບການສ້າງຕາຕະລາງ 2D DP. ຄວາມສັບສົນໃນອະວະກາດແມ່ນຫຼາຍຮູບແບບ ສຳ ລັບວິທີການ DP.