2020米哈游春招笔试题
返回两个数组中相同数字不相交的最大连线数
//给定两数组
int[] a = {2, 5, 1, 2, 5};
int[] b = {10, 5, 2, 1, 5, 2};
//输出：3
int[] a1 = {1, 2, 3};
int[] b1 = {1, 3, 2};
//输出：2
int[] a2 = {2, 5, 1, 2, 5, 1, 3};
int[] b2 = {10, 5, 2, 7, 5, 3, 3};
//输出：4答案：
/**
* 返回两个数组中相同数字不相交的最大连线数
*
* @param A int整型一维数组 整数集合A
* @param B int整型一维数组 整数集合B
* @return int整型
*/
//暴力
public int maxUncrossedLines(int[] A, int[] B) {
int max = 0;
for (int i = 0; i < A.length; i++) {
int ti = i;
int cnt = 0;
int j = 0;
while (ti < A.length && j < B.length) {
if (A[ti] == B[j]) {
cnt++;
ti++;
}
j++;
}
max = max > cnt ? max : cnt;
}
return max;
}
//dp[][]
public int maxUncrossedLines2(int[] A, int[] B) {
int alen = A.length;
int blen = B.length;
int max = 0;
//dpij 代表从0-i,0-j的相同数字不相交的最大连线数
int[][] dp = new int[alen + 1][blen + 1];
if (A[0] == B[0])
dp[0][0] = 1;
for (int i = 1; i < alen; i++) {
for (int j = 1; j < blen; j++) {
if (A[i] == B[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
for (int i = 0; i < alen; i++) {
for (int j = 0; j < blen; j++) {
System.out.printf(" " + dp[i][j]);
}
System.out.println();
}
return max;
}
//递归
public int maxUncrossedLines3(int[] A, int[] B) {
return helper(A, B, 0, 0);
}
public int helper(int[] a, int[] b, int i, int j) {
if (i >= a.length || j >= b.length) {
return 0;
}
if (a[i] == b[j])
return helper(a, b, i + 1, j + 1) + 1;
return Math.max(helper(a, b, i, j + 1), helper(a, b, i + 1, j));
}
回头改改主题把comment的CSS冲突改掉
更新：改好了
悄悄说一句，这题暴力模拟和NOIP难度差不多（