Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

62. Διαφορετικά μονοπάτια

• Ο κωδικός μου (αναφορά σφάλματος)
  Σημεία που αισθάνομαι πολύ μπερδεμένα κατά τη διαδικασία γραφής: ① Η αντιστοιχία μεταξύ του δισδιάστατου πίνακα και αυτής της ερώτησης δεν είναι ξεκάθαρη

class Solution {
    public int uniquePaths(int m, int n) {
        int[][]dp = new int[m+1][n+1];
        dp[0][0] = 0;
        dp[0][1] = 1;
        dp[1][0] = 1;
        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}

/*
自己解题的时候思考过程

n-1 : 往右走的次数
m-1 : 往下走的次数 

dp[i][j]到当前的位置，有几种方法
dp[0][0] 0
dp[0][1] 1
dp[1][0] 1
dp[1][1] 2
dp[i][j] 的前一个状态是，(1)他的左边dp[i-1][j]，或者(1)dp[i-1][j-1]
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];

 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Σφάλμα αρχικοποίησης Η προετοιμασία εδώ πρέπει να καλύπτει ολόκληρη την αριστερή στήλη και την οριζόντια γραμμή.

// 第0列，dp[i][0] 表示到当前的位置，有几种方法，这一列都是只有一种
 for (int i = 0; i < m; i++) {
  dp[i][0] = 1;
 }
 
// 第0行，dp[0][i] 表示到当前的位置，有几种方法，这一行都是只有一种
 for (int i = 0; i < n; i++) {
     dp[0][i] = 1;
 }
1
2
3
4
5
6
7
8
9

Διάγραμμα αποθήκευσης δισδιάστατων συστοιχιών JAVA:

• διαδικασία σκέψης
  (1) Προσδιορίστε τη σημασία του πίνακα dp και των δεικτών:到当前的位置[i][j]，有几种方法 dp[i][j]
  (2) Προσδιορίστε τον τύπο αναδρομήςdp[i][j] = dp[i-1][j] + dp[i][j-1];
  (3) Πώς να αρχικοποιήσετε τον πίνακα dp本题就栽在这一步了，其实是要for循环 初始化一列和一排的
  (4) Προσδιορίστε τη σειρά διέλευσης από μπροστά προς τα πίσω
  (5) Χρησιμοποιήστε ένα παράδειγμα για να εξαγάγετε τον πίνακα dp
  (6) Εκτύπωση πίνακα dp

• μετα Χριστον

class Solution {
    public int uniquePaths(int m, int n) {
        int[][]dp = new int[m][n];

        for(int i=0; i<m; i++) {
            dp[i][0] = 1;
        }
        
        for(int i=0; i<n; i++) {
            dp[0][i] = 1;
        }

        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Ιάβα

Βρείτε το μήκος ενός δισδιάστατου πίνακα

int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
1
2

63. Διαφορετικά μονοπάτια II

• Εξάγετε τον τύπο dp[i][j] = dp[i-1][j] + dp[i][j-1];
  Εάν ο [i][j] είχε ένα εμπόδιο, θα ήταν αδύνατο να περπατήσει.
  if(obs[i][j] == 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];

• αρχικοποίηση
  Εάν υπάρχει κάποιο εμπόδιο στην πρώτη γραμμή ή στήλη, τότε όλα τα επόμενα θα αρχικοποιηθούν στο 0.

• Λάθος

java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3
  at line 22, Solution.uniquePathsWithObstacles
  at line 56, __DriverSolution__.__helper__
  at line 86, __Driver__.main
1
2
3
4

Επειδή το dp ξεκίνησε από [1][1]

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][]dp = new int[m][n];
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        } 
        //初始化
        for(int i=0; i<m && obstacleGrid[i][0]!=1; i++) {
            dp[i][0] = 1;
            //中途如果有obstacleGrid[i][0]!=0，那就暂停循环，Java初始化都赋了0
        }

        //初始化
        for(int j=0; j<n && obstacleGrid[0][j]!=1; j++) {
            dp[0][j] = 1;
        }
        for(int i=1; i<m; i++) { //这里写了0是错误的
            for(int j=1; j<n; j++) {
                dp[i][j] = (obstacleGrid[i][j]==0?(dp[i][j-1]+dp[i-1][j]):0);
            }
        }
        return dp[m-1][n-1];
    }
}

//我的思考
// obstacleGrid[i][j] = 1 此处有障碍物，走不了
// obstacleGrid[i][j] = 0
// dp[i][j] = dp[i-1][j] + dp[i][j-1]
// 如果 obstacleGrid[i-1][j] = 1，前一种状态就不能是dp[i-1][j]，dp[i][j] = dp[i][j-1]
// 如果 obstacleGrid[i][j-1] = 1，前一种状态就不能是dp[i][j-1]，dp[i][j] = dp[i-1][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

343. Διαίρεση ακεραίων

Δεν έχω ιδέα

Επικεντρωθείτε σε ιδέες επίλυσης προβλημάτων
① Διαιρέστε το στους ίδιους αριθμούς όσο το δυνατόν περισσότερο, όταν όλοι οι διαχωρισμένοι αριθμοί είναι ίσοι, το γινόμενο θα είναι το μεγαλύτερο. ② Ο βέλτιστος αριθμός διαχωρισμού είναι 3.

• μαθηματική μέθοδος

class Solution {
    public int integerBreak(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        return (int)Math.pow(3, a) * 2;
    }
}
1
2
3
4
5
6
7
8
9

• Δυναμικός προγραμματισμός;
  Δεν καταλαβαίνω λίγο

96. Διαφορετικά δυαδικά δέντρα αναζήτησης