LeetCode题目:
其他:
1143. 最长公共子序列
跳转: 1143. 最长公共子序列
学习: 代码随想录公开讲解
问题:
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
思路:
dp数组值的含义是到当前(text到i的子数组和text2到j的子数组)的最大公共子序列长度.
因为是公共子序列,不用连续,所以需要向后传递状态,只要前面出现过后面都可以继续更新.
于是比起公共子数组多了一步如果不相等从j或上一个的j+1继承状态,
因为需要基于当前更新,所以内层循环要顺序遍历,上一层的状态可以单独处理.
复杂度:
- 时间复杂度: O ( n m ) O(nm) O(nm)
- 空间复杂度: O ( n ) O(n) O(n)
代码:
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[] fn = new int[n+1];
int pre;
for (int i = 0; i < m; i++) {
pre = 0;
for (int j = 0; j <n; j++) {
int tmp = fn[j+1];
fn[j + 1] = text1.charAt(i) == text2.charAt(j) ? pre + 1 : Math.max(fn[j],fn[j+1]);
pre = tmp;
}
}
return fn[n];
}
}
1035. 不相交的线
跳转: 1035. 不相交的线
学习: 代码随想录公开讲解
问题:
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
nums1[i] == nums2[j]- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
思路:
不相交就是一旦连线之后双方都不在回头,就是顺序连线,相当于求最长公共子序列
复杂度:
- 时间复杂度: O ( n m ) O(nm) O(nm)
- 空间复杂度: O ( m ) O(m) O(m)
代码:
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int[] dp = new int[m+1];
int pre;
for(int i=0;i<n;i++){
pre = 0;
for(int j=0;j<m;j++){
int tmp = dp[j+1];
dp[j+1] = nums1[i]==nums2[j]?pre+1:Math.max(dp[j+1],dp[j]);
pre = tmp;
}
}
return dp[m];
}
}
53. 最大子数组和
跳转: 53. 最大子数组和
学习: 代码随想录公开讲解
问题:
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
思路:
上一步不为负数的情况基于上一步更新,可以理解为贪心,也可以理解为动态规划.
复杂度:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
代码:
class Solution {
public int maxSubArray(int[] nums) {
int f0 = nums[0];
int ans = f0;
for (int i = 1; i < nums.length; i++) {
f0 = Math.max(f0+nums[i],nums[i]);
ans = Math.max(ans,f0);
}
return ans;
}
}
392. 判断子序列
跳转: 392. 判断子序列
问题:
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
思路:
可以直接求最长公共子序列长度看看和s是否相等
也可以顺序匹配,遍历一遍t,匹配过一个不回头,继续匹配下一个
复杂度:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
代码:
class Solution {
public boolean isSubsequence(String s, String t) {
if(s.isEmpty()) return true;
int counter = 0;
for(char c:t.toCharArray())
if(s.charAt(counter)==c&&++counter==s.length()){
return true;
}
return false;
}
}
2094. 找出 3 位偶数(每日一题)
跳转: 2094. 找出 3 位偶数
学习: 灵茶山艾府题解
问题:
给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。
你需要找出 所有 满足下述条件且 互不相同 的整数：
- 该整数由
digits中的三个元素按 任意 顺序 依次连接 组成。 - 该整数不含 前导零
- 该整数是一个 偶数
例如，给定的 digits 是 [1, 2, 3] ，整数 132 和 312 满足上面列出的全部条件。
将找出的所有互不相同的整数按 递增顺序 排列，并以数组形式返回*。*
思路:
回溯暴搜符合条件的子序列.
不重,每层一样的数字只选一次,各层间不能选同一个索引
不漏,每次都从头开始选.
复杂度:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)
代码:
class Solution {
List<String> list = new ArrayList<>();
StringBuilder sb = new StringBuilder();
void dfs(int[] digits) {
if (sb.length() == 3) {
list.add(sb.toString());
return;
}
int[] visited = new int[10];
for (int i = 0; i < digits.length; i++) {
if (digits[i] == -1 || visited[digits[i]] > 0)
continue;
if (sb.length() == 0 && digits[i] == 0)
continue;
if (sb.length() == 2 && digits[i] % 2 > 0)
continue;
sb.append(digits[i]);
int tmp = digits[i];
digits[i] = -1;
dfs(digits);
sb.delete(sb.length() - 1, sb.length());
digits[i] = tmp;
visited[digits[i]] = 1;
}
}
public int[] findEvenNumbers(int[] digits) {
Arrays.sort(digits);
dfs(digits);
return list.stream().mapToInt(Integer::parseInt).toArray();
}
}
总结
练习了动规解决子序列问题