题目
- 今天看到个题是长这样子滴↓
暴力解法
刚开始看到这道题刚开始还以为挺简单的，就用暴力解法去字符串匹配就搞定（其实我也只想到了字符串匹配的方法）
- 自认为的这道题考点有两个：
- 字符串匹配。
- 数组截取的所有情况覆盖。
- 所以我最开始写出来的暴力解法代码如下：（期间也让同事试了下这道题他做出来也是这种字符串匹配的思路）
public int findLength(int[] A, int[] B) {
List<String> AList = new ArrayList<>(A.length);
for (int i : A) {
AList.add(String.format("%03d", i));
}
List<String> BList = new ArrayList<>(B.length);
for (int i : B) {
BList.add(String.format("%03d", i));
}
String splitTag = "-";
String targetStr = String.join(splitTag, BList);
int result = 0;
int size = A.length;
int len = size;
while (len > 0) {
int index = 0;
while (index + len <= size) {
List<String> tmpList = AList.subList(index, index + len);
String tmpStr = String.join(splitTag, tmpList);
if (targetStr.contains(tmpStr)) {
result = len;
break;
}
index++;
}
if (result != 0) {
break;
}
len--;
}
return result;
}
然后在leecode上找到了这道题然后把自己代码丢进去后发现有种情况的用例不能通过。当AB两个数组没有任何一个匹配的子数组时我的代码居然返回1，用例如下：
- A: [32,4,78,5,9]
- B: [23,65,12,76,70]
发现当单个数组的情况，A数组中的5和B数组中的65匹配上了... 也确实如此因为我用的contains。当同事觉得我字符串匹配肯定行不通时我居然“鸡贼”的找到个解决方法，既然题目限定0 <= A[i], B[i] < 100，我就在最开始int数组转换字符串的时候加上补全三位数AList.add(String.format("%03d", i))，果然就跑通了这种用例。
最优解法
正当我以为问题解决了信心满满提交代码又发现。。。。超时了，一看测试用例，两个1000个元素的数组，运行超时。放在本地跑了试下，居然要9s，也难怪毕竟两个for循环，复杂度至少O(n^2)。最后实在忍不住了，去看答案。
原来这道题考的是动态规划，十行代码搞定，1000数组的用例才跑60ms。。。
后来通过一哥们写的这篇文章好好学习了下动态规划，然后发现：这不就是大学在线性代数课上老师讲过的知识么？我上大学那会线代自认为还学得挺好的，期末还考了90多分。学过就忘，一看又想起来，真的要学以致用啊。
最后结合解决代码和这篇文章的解释就能深刻记忆一下动态规划的运用
public int findLength(int[] A, int[] B) {
int n = A.length, m = B.length;
int[][] dp = new int[n + 1][m + 1];
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
ans = Math.max(ans, dp[i][j]);
}
}
return ans;
}
还是题刷得太少了啊~