首页 > 其他分享 >LeetCode三则

LeetCode三则

时间:2024-04-19 23:56:10浏览次数:26  
标签:三则 obstacleGrid matrix int 路径 Solution LeetCode dp

63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。
机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。
那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。

说明:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //int数组的初值为0
        int[][] dp = new int[m][n];
        //起始行有障碍物,则后续均无法到达
        if (obstacleGrid[0][0] == 1||obstacleGrid[m-1][n-1] == 1)return 0;
        dp[0][0] = 1;
        //起始列有障碍物,则无法到达,直接返回0
        for(int i=1;i<m;i++){
            if(obstacleGrid[i][0] == 0)
                dp[i][0] = 1;
            else
                break;
        }
        //起始行有障碍物,则后续均无法到达
        for(int j=1;j<n;j++){
            if(obstacleGrid[0][j] == 0)
                dp[0][j] = 1;
            else
                break;
        }
        //因为dp的起始列行中无法达到的位置都为0
        //所以,若存在多个障碍无法到达终点,则终点也为0
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j] == 0)
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        return dp[m-1][n-1];
    }
}
Solution
120. 三角形最小路径和
给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。
class Solution {
    /**
     * @author XiSoil
     * @date 2024/04/19 09:48
     *执行分布用时3ms,击败的83.45%Java用户
     *消耗内存分布43.14MB,击败的45.60%Java用户
     **/
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0)
                    dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
                else if (j == i)
                    dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
                else
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
        }
        int min = 10001;
        for (int i = 0; i < n; i++) {
            min = Math.min(min, dp[n - 1][i]);
        }
        return min;
    }
}
Solution
931. 下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始,
并从每一行中选择一个元素。
在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。
具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
public class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int min = Integer.MAX_VALUE;
        int[][] dp = new int[m][n];
        for(int i= 0; i<m;i++){
            dp[0][i] = matrix[0][i];
        }
        for(int i=1;i<m;i++)
            for (int j=0;j<n;j++){
                if(j==0)
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j+1])+matrix[i][j];
                else if(j==n-1)
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])+matrix[i][j];
                else
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1]))+matrix[i][j];
                if (i == m-1)
                    min = Math.min(min,dp[m-1][j]);
            }
        return min;
    }
}
Solution

 

标签:三则,obstacleGrid,matrix,int,路径,Solution,LeetCode,dp
From: https://www.cnblogs.com/xxaxf/p/18147022

相关文章

  • leetcode回文数
    给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121是回文,而123不是。示例1:输入:x=121输出:true示例2:输入:x=-121输出:false解释:从左向右读,为-121。从右向左读,为121-。因此......
  • LeetCode三则
    三道动态规划62.不同路径一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?输入:m=3,n=7输出:28输入:m=3,n=2输出:3解释:......
  • LeetCode 面试经典150题---008
    ####151.反转字符串中的单词给你一个字符串s,请你反转字符串中单词的顺序。单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意:输入字符串s中可能会存在前导空格、尾随空格......
  • LeetCode- 19 删除链表的倒数第N个节点
    题目地址https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/参考实现/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){t......
  • LeetCode三则
    198.打家劫舍你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况......
  • LeetCode两则
    1137.第N个泰波那契数泰波那契序列Tn定义如下:T0=0,T1=1,T2=1,且在n>=0的条件下Tn+3=Tn+Tn+1+Tn+2给你整数n,请返回第n个泰波那契数Tn的值。示例1:输入:n=4输出:4解释:T_3=0+1+1=2T_4=1+1+2=4示例2:输入:n=25输出:1389537提示:0<=n......
  • LeetCode 面试经典150题---007
    ####13.罗马数字转整数罗马数字包含以下七种字符:I,V,X,L,C,D和M。字符数值I1V5X10L50C100D500M1000例如,罗马数字2写做II,即为两个并列的1。12写做X......
  • LeetCode 1315. Sum of Nodes with Even-Valued Grandparent
    原题链接在这里:https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/description/题目:Giventhe root ofabinarytree,return thesumofvaluesofnodeswithan even-valuedgrandparent.Iftherearenonodeswithan even-valuedgrandpar......
  • LeetCode三则
    53.最大子数组和给你一个整数数组nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。示例1:输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组[4,-1,2,1]的和最大,为6。示例2:输入:nums=[1]输出:1示例3:输......
  • leetcode插件问题
    1.使用一段时间后,提交答案一直返回undefind原因为插件缓存token有效期已过,需要重新登录2.重新登录......