每日5题Day9 - LeetCode 41 - 45

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：41. 缺失的第一个正数 - 力扣（LeetCode）

今天这道题没有ac，写不动了，下次再通过吧，先给个半成品下次回来改掉

class Solution {public int firstMissingPositive(int[] nums) {//使用掩码来做吧，通过$与|来记录一下各个数是否有出现int mask = 0;int n = nums.length;// 将正整数放置到对应的位置for (int num : nums) {if (num > 0 && num <= n) {mask |= (1 << (num - 1));}}// 找到第一个缺失的正整数for (int i = 0; i < n; i++) {if ((mask & (1 << i)) == 0) {return i + 1;}}// 如果数组中包含了1到n之间的所有正整数，则缺失的是n+1return n + 1;}
}

---

第二题：42. 接雨水 - 力扣（LeetCode）

class Solution {public int trap(int[] height) {//单调站的传统题Deque<Integer> deque = new ArrayDeque<>();int res = 0;for(int i = 0; i < height.length; i++){while(!deque.isEmpty() && height[i] > height[deque.peekLast()]){int tmp = deque.pollLast();if(!deque.isEmpty()){//注意宽和高是如何得到的int h = Math.min(height[deque.peekLast()], height[i]) - height[tmp];int w = i - deque.peekLast() - 1;res += h * w;}}deque.offerLast(i);}return res;}
}

---

第三题：43. 字符串相乘 - 力扣（LeetCode）

class Solution {public String multiply(String num1, String num2) {//直接模拟就好int m = num1.length();int n = num2.length();int[] result = new int[m + n]; // 保存每一位的乘积结果// 逐位相乘，注意从个位加至高位for (int i = m - 1; i >= 0; i--) {for (int j = n - 1; j >= 0; j--) {int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); // 乘积int sum = mul + result[i + j + 1]; // 加上当前位的值result[i + j] += sum / 10; // 进位result[i + j + 1] = sum % 10; // 当前位的结果}}// 将结果数组转换为字符串StringBuilder sb = new StringBuilder();for (int digit : result) {if (!(sb.length() == 0 && digit == 0)) { // 忽略结果数组的前导零sb.append(digit);}}return sb.length() == 0 ? "0" : sb.toString();}
}

---

第四题：44. 通配符匹配 - 力扣（LeetCode）

本题借用：【宫水三叶】的思路来解决的

class Solution {public boolean isMatch(String ss, String pp) {int n = ss.length(), m = pp.length();// 技巧：往原字符头部插入空格，这样得到 char 数组是从 1 开始，而且可以使得 f[0][0] = true，可以将 true 这个结果滚动下去ss = " " + ss;pp = " " + pp;char[] s = ss.toCharArray();char[] p = pp.toCharArray();// f(i,j) 代表考虑 s 中的 1~i 字符和 p 中的 1~j 字符 是否匹配boolean[][] f = new boolean[n + 1][m + 1];f[0][0] = true;for (int i = 0; i <= n; i++) {for (int j = 1; j <= m; j++) {if (p[j] == '*') {//注意这个地方逻辑的判断：//条件一：不加'*'时的情况：f[i][j - 1]//条件二：(i - 1 >= 0 && f[i - 1][j])//满足其一即可为truef[i][j] = f[i][j - 1] || (i - 1 >= 0 && f[i - 1][j]);} else {//当字符为'?'时的判断逻辑，肯定要前面也满足truef[i][j] = i - 1 >= 0 && f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?');}}}return f[n][m];}
}

---

 第五题：45. 跳跃游戏 II - 力扣（LeetCode）

class Solution {public int jump(int[] nums) {//不dp了，可以直接贪心策略实现，少用点空间if(nums.length == 0 || nums.length == 1){return 0;}int cnt = 0, curlen = 0, maxlen = 0;for(int i = 0; i < nums.length; i++){maxlen = Math.max(maxlen, i + nums[i]);if(maxlen >= nums.length - 1){cnt++;break;}if(i == curlen){curlen = maxlen;cnt++;}}return cnt;}
}

---