Leetcode刷题-(41~45)-Java

算法是码农的基本功，也是各个大厂必考察的重点，让我们一起坚持写题吧。

遇事不决，可问春风，春风不语，即是本心。

我们在我们能力范围内，做好我们该做的事，然后相信一切都事最好的安排就可以啦，慢慢来，会很快，向前走，别回头。

目录

1.缺失的第一个正数

2.接雨水

3.字符串相乘

4.通配符匹配

5.跳跃游戏II

---

1.缺失的第一个正数

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/first-missing-positive/description/

思路1：如果不考虑空间复杂度的情况下，用哈希表存入元素，然后从1开始枚举判断元素是否在哈希表中即可，时间复杂度和空间复杂度都是O(n) 。

思路2：通过修改数组本身模拟：先将小于0的数字都变换成n+1，接下来将小于等于n的元素索引替换成负数，然后🏪找出第一个大于0的数字即是结果。

Java版：

哈希表法：

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length ;Map<Integer, Integer> map = new HashMap<>() ;for(int i=0; i<n; i++){map.put(nums[i], i) ;}int j = 1 ;for(j=1;j<=n; j++){if(!map.keySet().contains(j)){return j ;}}return j ;}
}

方法2:模拟：先将小于等于0的都变为n+1，然后将小于等于n的都变为负数，最后找出第一个大于0的元素所对应的索引，若未找到则返回n+1。

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length ;for(int i=0; i<n; i++){if(nums[i] <= 0){nums[i] = n + 1 ;}}for(int i=0; i<n; i++){int num = Math.abs(nums[i]) ;if(num <= n){nums[num-1] = - Math.abs(nums[num-1]) ;}}for(int i=0; i<n; i++){if(nums[i] > 0){return i + 1 ;}}return n + 1 ;}
}

2.接雨水

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/trapping-rain-water/solutions/

思路：利用双指针模拟，计算可以接到的雨水，维护左右指针以及左右侧柱子高度的最值，由两侧向中间遍历，每次更新左侧或者右侧柱子高度的最值，并计算可以接水的情况。

时间复杂度O(n)、空间复杂度O(1)

Java版：

class Solution {public int trap(int[] height) {int left = 0, right = height.length - 1 ;int leftMax = 0, rightMax = 0 ;int ans = 0 ;while(left < right){leftMax = Math.max(leftMax, height[left]) ;rightMax = Math.max(rightMax, height[right]) ;if(height[left] < height[right]){ans += leftMax - height[left] ;left ++ ;}else{ans += rightMax - height[right] ;right -- ;}}return ans ;}
}

3.字符串相乘

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/multiply-strings/

思路1：直接用BigInteger进行大数的相乘，最后将乘积转换成字符串。

Java版：

import java.math.* ;
class Solution {public String multiply(String num1, String num2) {BigInteger b1 = new BigInteger(num1) ;BigInteger b2 = new BigInteger(num2) ;return b1.multiply(b2).toString() ;}
}

4.通配符匹配

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/wildcard-matching/description/

思路：动态规划的思想，dp[n][m]表示长度为n的字符串s与长度为m的字符串p是否能匹配成功，

需要初始化dp[0][j]，然后根据递推式更新dp[i][j].

Java版：

class Solution {public boolean isMatch(String s, String p) {// dp[n][m]: 字符串s的前n字符与字符串p的前m个字符是否匹配int n = s.length(), m = p.length() ;boolean [][] dp = new boolean[n+1][m+1] ;// 初始化s为空与p是否能够匹配，空的s只能与p的*匹配dp[0][0] = true ;for(int j=1; j<=m; j++){if(p.charAt(j-1) == '*'){dp[0][j] = true ;}else{break;}}// 遍历更新dp数组for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(p.charAt(j-1) == '*'){// 匹配任意字符或者空字符dp[i][j] = dp[i-1][j] || dp[i][j-1] ;}else if(p.charAt(j-1) == '?' || s.charAt(i-1) == p.charAt(j-1)){// 匹配一个字符dp[i][j] = dp[i-1][j-1] ;}}}return dp[n][m] ;}
}

5.跳跃游戏II

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/jump-game-ii/description/

思路：动态规划思想，dp[n]表示走到第n个位置所需要的最小步数。判断从第j位置是否可以走到i位置，如果可以则更新dp[i]的最小值。

Java版：

class Solution {public int jump(int[] nums) {int n = nums.length ;int [] dp = new int [n] ;dp[0] = 0 ;for(int i=1; i<n; i++){dp[i] = Integer.MAX_VALUE ;for(int j=0; j<i; j++){if(nums[j] >= i-j){dp[i] = Math.min(dp[j]+1, dp[i]) ;}}}return dp[n-1] ;}
}