day54_60

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

1.判断子序列

class Solution {public boolean isSubsequence(String s, String t) {if (s.length() == 0) return true;for (int i = 0, j = 0; j < t.length(); j++) {if (s.charAt(i) == t.charAt(j)) {// 若已经遍历完 s ，则提前返回 trueif (++i == s.length())return true;}}return false;}
}

2.不同的子序列

class Solution {public int numDistinct(String s, String t) {memo = new int[s.length()][t.length()];for (int[] row : memo) {Arrays.fill(row, -1);}return dp(s, 0, t, 0);}int[][] memo;// 定义：该函数返回 s[i..] 中的子序列 t[j..] 的数量int dp(String s, int i, String t, int j) {int m = s.length(), n = t.length();if (j == n) {// 子序列全部匹配完成return 1;}if (n - j > m - i) {// 待匹配子序列的长度不应该比字符串的长度还要短return 0;}if (memo[i][j] != -1) {// 已经计算过对应状态return memo[i][j];}int res = 0;// 状态转移方程if (s.charAt(i) == t.charAt(j)) {res += dp(s, i + 1, t, j + 1) + dp(s, i + 1, t, j);} else {res += dp(s, i + 1, t, j);}memo[i][j] = res;return res;}
}

3.两个字符串的删除操作(最长公共子序列变形)

class Solution {public int minDistance(String s1, String s2) {int m = s1.length(), n = s2.length();// 复用前文计算 lcs 长度的函数int lcs = longestCommonSubsequence(s1, s2);return m - lcs + n - lcs;}public int longestCommonSubsequence(String s1, String s2) {int m = s1.length(), n = s2.length();int[][] dp = new int[m + 1][n + 1];// 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]// 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]// base case: dp[0][..] = dp[..][0] = 0for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 现在 i 和 j 从 1 开始，所以要减一if (s1.charAt(i - 1) == s2.charAt(j - 1)) {// s1[i-1] 和 s2[j-1] 必然在 lcs 中dp[i][j] = 1 + dp[i - 1][j - 1];} else {// s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[m][n];}
}

4.编辑距离

int minDistance(String s1, String s2) {int m = s1.length(), n = s2.length();// 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i+1][j+1]int[][] dp = new int[m + 1][n + 1];// base case for (int i = 1; i <= m; i++)dp[i][0] = i;for (int j = 1; j <= n; j++)dp[0][j] = j;// 自底向上求解for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1.charAt(i-1) == s2.charAt(j-1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = min(dp[i - 1][j] + 1,dp[i][j - 1] + 1,dp[i - 1][j - 1] + 1);}}}// 储存着整个 s1 和 s2 的最小编辑距离return dp[m][n];
}int min(int a, int b, int c) {return Math.min(a, Math.min(b, c));
}

5.回文子串

class Solution {public int countSubstrings(String s) {// 动态规划法boolean[][] dp = new boolean[s.length()][s.length()];int ans = 0;for(int j = 0; j < s.length(); j++){for(int i = 0; i <= j; i++){if(s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i+1][j-1])){dp[i][j] = true;ans++;}}}return ans;}
}

6.最长回文子序列

class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();// dp 数组全部初始化为 0int[][] dp = new int[n][n];// base casefor (int i = 0; i < n; i++) {dp[i][i] = 1;}// 反着遍历保证正确的状态转移for (int i = n - 1; i >= 0; i--) {for (int j = i + 1; j < n; j++) {// 状态转移方程if (s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}// 整个 s 的最长回文子串长度return dp[0][n - 1];}
}

7.每日温度

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] res = new int[n];// 这里放元素索引，而不是元素Stack<Integer> s = new Stack<>(); /* 单调栈模板 */for (int i = n - 1; i >= 0; i--) {while (!s.isEmpty() && temperatures[s.peek()] <= temperatures[i]) {s.pop();}// 得到索引间距res[i] = s.isEmpty() ? 0 : (s.peek() - i); // 将索引入栈，而不是元素s.push(i); }return res;}
}

8.下一个更大元素1

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 1.单调栈，倒序输入相当于正序输出，// 2.抽象思想，将数值抽象成 “身高”，身高高的将身高矮的挡住// for循环从后向前扫描元素，while循环把两个 "个字高" 之间的元素排除// 算法时间复杂度为O(n)，每个元素都被push入栈，而最多会被pop一次，也就是O(n)// 记录nums2中每个元素的下一个更大元素int[] greater = nextGreaterElement1(nums2);//转化成映射，元素 x -> x的下一个更大元素HashMap<Integer, Integer> greaterMap = new HashMap<>();for(int i = 0; i < nums2.length; i++){
// 注意一个重点，nums1 & nums2 中的元素都是不重复的，才能使用这个方法greaterMap.put(nums2[i],greater[i]);}//nums1是nums2的子集， 所以根据greatMap可以得到结果int[] res = new int[nums1.length];for(int i = 0; i < nums1.length; i++){res[i] = greaterMap.get(nums1[i]);}return res;}int[] nextGreaterElement1(int[] nums){int n = nums.length;//存放答案的数组int[] res = new int[n];Stack<Integer> s = new Stack<>();//倒着往栈里放for(int i = n - 1; i >= 0; i--){//判定个字高矮while(!s.isEmpty() && s.peek() <= nums[i]){//矮个 小于 当前的值，那么下一个最大的值就不是它//pop() 之后继续循环，找有没有比当前值大的元素s.pop();}//nums[i]，在当前元素之后的元素都比当前元素小，那么返回-1res[i] = s.isEmpty() ? -1 : s.peek();s.push(nums[i]);}return res;}
}

9.下一个更大元素2

class Solution {public int[] nextGreaterElements(int[] nums) {int n = nums.length;int[] res = new int[n];Stack<Integer> s = new Stack<>();// 数组长度加倍模拟环形数组// n - 1 - 0 + 1 = n个元素， 改成 2n - 1 - 0 + 1 = 2n个元素// 其实这里改成 2n - 2也行，就少复制了一个数组尾部元素，不影响 n - 1之前索引元素的计算// n - 1 的索引计算 也只依靠 复制后的 0 ~ n-2索引的元素for (int i = 2 * n - 1; i >= 0; i--) {// 索引 i 要求模，其他的和模板一样while (!s.isEmpty() && s.peek() <= nums[i % n]) {s.pop();}res[i % n] = s.isEmpty() ? -1 : s.peek();s.push(nums[i % n]);}return res;}
}

10.接雨水

核心思想考虑单个列能接多少水，单个列接水数量取决于两边最高左柱子和最高右柱子

class Solution {int trap(int[] height) {if (height.length == 0) {return 0;}int n = height.length;int res = 0;// 数组充当备忘录int[] l_max = new int[n];int[] r_max = new int[n];// 初始化 base casel_max[0] = height[0];r_max[n - 1] = height[n - 1];// 从左向右计算 l_maxfor (int i = 1; i < n; i++)l_max[i] = Math.max(height[i], l_max[i - 1]);// 从右向左计算 r_maxfor (int i = n - 2; i >= 0; i--)r_max[i] = Math.max(height[i], r_max[i + 1]);// 计算答案for (int i = 1; i < n - 1; i++)res += Math.min(l_max[i], r_max[i]) - height[i];return res;}
}

11.柱状图中最大的矩形

class Solution {public int largestRectangleArea(int[] heights) {/*只做单调栈思路:参考"编程狂想曲"思路比较好理解1.核心思想:求每条柱子可以向左右延伸的长度->矩形最大宽度;矩形的高->柱子的高度计算以每一根柱子高度为高的矩形面积,维护面积最大值2.朴素的想法:遍历每一根柱子的高度然后向两边进行扩散找到最大宽度3.单调栈优化:因为最终的目的是寻找对应柱子height[i]右边首个严格小于height[i]的柱子height[r]左边同理找到首个严格小于height[i]的柱子height[l]维护一个单调递增栈(栈底->栈顶),那么每当遇到新加入的元素<栈顶便可以确定栈顶柱子右边界而栈顶柱子左边界就是栈顶柱子下面的柱子(<栈顶柱子)左右边界确定以后就可以进行面积计算与维护最大面积时间复杂度:O(N),空间复杂度:O(N)*/// 引入哨兵// 哨兵的作用是 将最后的元素出栈计算面积 以及 将开头的元素顺利入栈// len为引入哨兵后的数组长度int len = heights.length + 2;int[] newHeight = new int[len];newHeight[0] = newHeight[len - 1] = 0;// [1,2,3]->[0,1,2,3,0]for(int i = 1; i < len - 1; i++) {newHeight[i] = heights[i - 1];}// 单调递增栈:存储每个柱子的索引,使得这些索引对应的柱子高度单调递增Stack<Integer> stack = new Stack<>();// 最大矩形面积int res = 0;// 遍历哨兵数组for(int i = 0; i < len; i++) {// 栈不为空且当前柱子高度<栈顶索引对应的柱子高度// 说明栈顶元素的右边界已经确定,就是索引为i的柱子(不含)// 此时将栈顶元素出栈,栈顶矩形左边界为栈顶元素下面的索引(首个小于栈顶)while(!stack.empty() && newHeight[i] < newHeight[stack.peek()]) {// 栈顶索引出栈并记录int pop = stack.pop();// 计算出栈顶元素矩形的宽度如(0,1,2)->[1,2,1],两边都不包含// 因此右索引-左索引-1=矩形宽度int w = i - stack.peek() - 1;// 栈顶索引对应的柱子高度就是矩形的高度int h = newHeight[pop];// 计算矩形面积int area = w * h;// 维护矩形面积最大值res = Math.max(res, area);}// 每当弹出一个索引就计算一个矩形面积// 直到当前元素>=栈顶元素(或者栈为空)时,栈顶柱子的右边界还没确定// 因此当前元素索引入栈即可stack.push(i);}return res;}
}