Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Unique Paths
- //Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths.
- //Memory Usage: 32.8 MB, less than 5.10% of Java online submissions for Unique Paths.
- class Solution {
- public int uniquePaths(int m, int n) {
- int[][] matrix = new int[n][m];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- if (i == 0 || j == 0) matrix[i][j] = 1;
- else {
- matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
- }
- }
- }
- return matrix[n - 1][m - 1];
- }
- }
- // Unique Paths II
- //Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths II.
- //Memory Usage: 38 MB, less than 100.00% of Java online submissions for Unique Paths II.
- class Solution {
- public int uniquePathsWithObstacles(int[][] obstacleGrid) {
- int n = obstacleGrid.length;
- int m = obstacleGrid[0].length;
- int[][] matrix = new int[n][m];
- for (int i = 0; i < n; i++) {
- if (obstacleGrid[i][0] == 1) {
- matrix[i][0] = 0;
- break;
- }
- matrix[i][0] = 1;
- }
- for (int j = 0; j < m; j++) {
- if (obstacleGrid[0][j] == 1) {
- matrix[0][j] = 0;
- break;
- }
- matrix[0][j] = 1;
- }
- for (int i = 1; i < n; i++) {
- for (int j = 1; j < m; j++) {
- matrix[i][j] = obstacleGrid[i][j] == 1 ? 0 : matrix[i - 1][j] + matrix[i][j - 1];
- }
- }
- return matrix[n - 1][m - 1];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement