Loading... ## 例题 #### 例题1： 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？  网格中的障碍物和空位置分别用 1 和 0 来表示。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-paths-ii 题解： ```java class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int x_length = obstacleGrid.length; int y_length = obstacleGrid[0].length; if(x_length<=0||y_length<=0){ return 0; } if(obstacleGrid[0][0]==1){ // 如果一开始就是障碍物 return 0; } int[][] f = new int[x_length][y_length]; f[0][0]=1; for(int i=0;i<x_length;i++){ for(int j=0;j<y_length;j++){ if(obstacleGrid[i][j]==1){ // 如果有障碍物 f[i][j]=0; }else{ if(i==0&&j==0){ // 如果是起点 f[i][j]=1; }else{ f[i][j]=0; if(i-1>=0){ // 如果是从左边来 f[i][j]+=f[i-1][j]; } if(j-1>=0){ // 如果是右边来 f[i][j]+=f[i][j-1]; } } } } } return f[x_length-1][y_length-1]; } } ``` #### 例题2： 这里有`n`个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得**相邻的房屋颜色不同**，并且费用最小，返回最小的费用。 费用通过一个`n`x`3` 的矩阵给出，比如`cost[0][0]`表示房屋`0`染红色的费用，`cost[1][2]`表示房屋`1`染绿色的费用。 来源：LintCode 链接：https://www.lintcode.com/problem/paint-house/description 题解： ```java public class Solution { /** * @param costs: n x 3 cost matrix * @return: An integer, the minimum cost to paint all houses */ public int minCost(int[][] costs) { // write your code here int[][] f = new int[costs.length+1][3]; //初始化 0 栋房子 0 元 f[0][0] = f[0][1] = f[0][2] =0; for(int i=1;i<costs.length+1;i++){ // i 栋房子的三种颜色 for(int j=0;j<3;j++){ // 初始化为最大 f[i][j]=Integer.MAX_VALUE; // i-1 栋房子的三种颜色 for(int k=0;k<3;k++){ if(j==k){ // 撞色 continue; } /* f[i-1][k] 前 i-1 栋房子k颜色的花费 */ /* costs[i-1][j] 第 i-1 栋房子j颜色的花费 */ /* f[i][j] 前 i 栋房子k颜色的花费 */ if(f[i-1][k]+costs[i-1][j]<f[i][j]){ f[i][j]=f[i-1][k]+costs[i-1][j]; } } } } // 结果取三种颜色最小值 int res = Math.min(f[costs.length][0],f[costs.length][1]); return Math.min(res,f[costs.length][2]); } } ``` #### 例题3： 有一个消息包含`A-Z`通过以下规则编码 ``` 'A' -> 1 'B' -> 2 ... 'Z' -> 26 ``` 现在给你一个加密过后的消息，问有几种解码的方式 我们不能解码空串，因此若消息为空，你应该返回0。 消息的长度 n ≤ 100 来源：LintCode 链接：https://www.lintcode.com/problem/decode-ways/description 题解： ```java public class Solution { /** * @param s: a string, encoded message * @return: an integer, the number of ways decoding */ public int numDecodings(String s) { // write your code here char[] ss = s.toCharArray(); int length = ss.length; if(length<=0){ return 0; } int[] f = new int[length+1]; f[0]=1; for(int i=1;i<=length;i++){ f[i]=0; // 一个数字的情况 int t = ss[i-1]-'0';//把它转化为数字 if(t>=1&&t<=9){ // 不能包含 0 f[i]+=f[i-1]; } // 判断两个数字的情况 if(i>=2){ t = (ss[i-2]-'0')*10+(ss[i-1]-'0'); if(t>=10&&t<=26){ f[i]+=f[i-2]; } } } return f[length]; } } ``` ## 题目 #### 题目1： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。 注意：你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock 题解： ```java class Solution { public int maxProfit(int[] prices) { // // 第 i 天卖出，在第 i-x>0 天买入 // // 子问题 // // f[i] = min(f[i-1]...f[1]) f[i]>min(f[i-1]...f[1]) // int length = prices.length; // if(length<=1){ // return 0; // } // int[] f = new int[length]; // int res = 0; // f[0]=0; // for(int i=1;i<length;i++){ // f[i]=0; // //找出股票价格最小 // for(int j=0;j<=i;j++){ // if(f[i]<prices[i]-prices[i-j]){ // f[i]=prices[i]-prices[i-j]; // res = Math.max(res,f[i]); // } // } // } // return res; // v2 // 维护一个最大利润，维护一个最低股票价格 int min = Integer.MAX_VALUE; int max = 0; for(int i=0;i<prices.length;i++){ min = Math.min(prices[i],min); max = Math.max(prices[i]-min,max); } return max; } } ``` #### 题目2： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-subarray 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ```java class Solution { public int maxSubArray(int[] nums) { int length = nums.length; if(length<=0){ return 0; } // int[] f = new int[lngth+1]; // f[0]=0; // for(int) int res=nums[0]; for(int i=1;i<length;i++){ // if(nums[i]+nums[i-1]>nums[i]){ // nums[i]+=nums[i-1]; // } nums[i]=Math.max(nums[i]+nums[i-1],nums[i]); res = Math.max(res,nums[i]); } return res; } } ``` #### 题目3： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/climbing-stairs 题解： ```java class Solution { public int climbStairs(int n) { // // 最后一步 有两种方法 1 or 2 // int[] f = new int[n+1]; // f[0]=1; // for(int i=1;i<=n;i++){ // f[i]=1; // if(i-1>0){ // f[i]+=f[i-1]; // } // if(i-2>0){ // f[i]+=f[i-2]-1; // 这里多加了 1 // } // } // return f[n]; // 滚动数组 空间复杂度优化 int p=0, q=0, r=1; for(int i=0;i<n;i++){ p=q; q=r; r=p+q; } return r; } } ``` Last modification：December 11th, 2020 at 12:31 pm © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
