2020米哈游春招笔试题 返回两个数组中相同数 - Assbbs
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}…
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 ; }