java算法题每日多道十四

本文主要是介绍java算法题每日多道十四，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

322. 零钱兑换

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

答案

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];int max = Integer.MAX_VALUE;for(int i=0;i<dp.length;i++){//增强for循环不能赋值dp[i] = max;}dp[0] = 0;for(int i=0;i<coins.length;i++){for(int j=coins[i];j<=amount;j++){if(dp[j-coins[i]]!=max){dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}}return dp[amount]==max ? -1 : dp[amount];}
}

300. 最长递增子序列

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

答案

class Solution {public int lengthOfLIS(int[] nums) {int len = nums.length;int[] dp = new int[len];for(int i=0;i<len;i++){dp[i] = 1;} int res = 1;for(int i=0;i<len;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j]){dp[i] = Math.max(dp[i],dp[j]+1);}}res = Math.max(res,dp[i]);}return res;}
}

120. 三角形最小路径和

题目

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：23 46 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

答案

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int len = triangle.size();int[][] dp = new int[len][len];dp[0][0] = triangle.get(0).get(0);for(int i=1;i<len;i++){dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);for(int j=1;j<i;j++){dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + triangle.get(i).get(j);}dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);}int res = dp[len-1][0];for(int num : dp[len-1]){res = Math.min(res,num);} return res;}
}

64. 最小路径和

题目

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

答案

class Solution {public int minPathSum(int[][] grid) {if(grid==null || grid.length==0 || grid[0].length==0){return 0;}int m = grid.length,n = grid[0].length;int[][] dp = new int[m][n];dp[0][0] = grid[0][0];for(int i=1;i<m;i++){dp[i][0] = dp[i-1][0] + grid[i][0];}for(int j=1;j<n;j++){dp[0][j] = dp[0][j-1] + grid[0][j];}for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];}}return dp[m-1][n-1];}
}

63. 不同路径 II

题目

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

答案

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length,n = obstacleGrid[0].length;int[][] dp = new int[m][n];for(int i=0;i<m && obstacleGrid[i][0]==0;i++){dp[i][0] = 1;} for(int j=0;j<n && obstacleGrid[0][j]==0;j++){dp[0][j] = 1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==0){dp[i][j] = dp[i][j-1] + dp[i-1][j];}else{dp[i][j] = 0;}}}return dp[m-1][n-1];}
}

5. 最长回文子串

题目

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

答案

class Solution {public String longestPalindrome(String s) {if(s==null && s.length()==0){return "";} int start = 0,end = 0;for(int i=0;i<s.length();i++){int len1 = deal(s,i,i);int len2 = deal(s,i,i+1);int len = Math.max(len1,len2);if(len>end-start){start = i - (len-1)/2;end = i + len/2;}}return s.substring(start,end+1);}int deal(String s,int left,int right){while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){left--;right++;}return right - left - 1;}
}

97. 交错字符串

题目

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空

子字符串

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

答案

class Solution {public boolean isInterleave(String s1, String s2, String s3) {int m = s1.length(),n = s2.length(),len = s3.length();if(len != m+n){return false;}boolean[][] dp = new boolean[m+1][n+1];dp[0][0] = true;for(int i=0;i<=m;i++){for(int j=0;j<=n;j++){int p = i + j -1;if(i>0){dp[i][j] = dp[i][j] || (dp[i-1][j] && s1.charAt(i-1)==s3.charAt(p));}if(j>0){dp[i][j] = dp[i][j] || (dp[i][j-1] && s2.charAt(j-1)==s3.charAt(p));}}}return dp[m][n];}
}