宣传中心网站建设,网站建设与管理维护的答案李建青,h5第三方收款平台,中天建设集团有限公司排名算法是码农的基本功#xff0c;也是各个大厂必考察的重点#xff0c;让我们一起坚持写题吧。
遇事不决#xff0c;可问春风#xff0c;春风不语#xff0c;即是本心。
我们在我们能力范围内#xff0c;做好我们该做的事#xff0c;然后相信一切都事最好的安排就可以啦…算法是码农的基本功也是各个大厂必考察的重点让我们一起坚持写题吧。
遇事不决可问春风春风不语即是本心。
我们在我们能力范围内做好我们该做的事然后相信一切都事最好的安排就可以啦慢慢来会很快向前走别回头。
目录
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的数字都变换成n1接下来将小于等于n的元素索引替换成负数然后找出第一个大于0的数字即是结果。
Java版
哈希表法
class Solution {public int firstMissingPositive(int[] nums) {int n nums.length ;MapInteger, Integer map new HashMap() ;for(int i0; in; i){map.put(nums[i], i) ;}int j 1 ;for(j1;jn; j){if(!map.keySet().contains(j)){return j ;}}return j ;}
}
方法2:模拟先将小于等于0的都变为n1然后将小于等于n的都变为负数最后找出第一个大于0的元素所对应的索引若未找到则返回n1。
class Solution {public int firstMissingPositive(int[] nums) {int n nums.length ;for(int i0; in; i){if(nums[i] 0){nums[i] n 1 ;}}for(int i0; in; i){int num Math.abs(nums[i]) ;if(num n){nums[num-1] - Math.abs(nums[num-1]) ;}}for(int i0; in; 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[n1][m1] ;// 初始化s为空与p是否能够匹配空的s只能与p的*匹配dp[0][0] true ;for(int j1; jm; j){if(p.charAt(j-1) *){dp[0][j] true ;}else{break;}}// 遍历更新dp数组for(int i1; in; i){for(int j1; jm; 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 i1; in; i){dp[i] Integer.MAX_VALUE ;for(int j0; ji; j){if(nums[j] i-j){dp[i] Math.min(dp[j]1, dp[i]) ;}}}return dp[n-1] ;}
}
