关于LeetCode446的几点疑问
关于LeetCode446
本文阅读重点
<
关于Leetcode 446. 等差数列划分 II - 子序列, 目前知道主要有两种解法: dfs和动态规划。
在网上看到两段Java版的dfs代码,试了一下可以过,其他见过的dfs写法大多数都超时了。自己试着改成了C++版,就出现整型越界的问题了。
这两段Java代码是:
Java dfs1:
class Solution {
public int numberOfArithmeticSlices(int[] A) {
Map<Integer, List<Integer>> indexMap = new HashMap<>();
for (int i = 0; i < A.length; i++) {
if (!indexMap.containsKey(A[i])) {
indexMap.put(A[i], new ArrayList<>());
}
indexMap.get(A[i]).add(i);
}
int result = 0;
for (List<Integer> indexes : indexMap.values()) {
int size = indexes.size();
if (size >= 3) {
result += (1 << size) - 1 - size - size * (size - 1) / 2;
}
}
for (int i = 0; i < A.length - 2; i++) {
for (int j = i + 1; j < A.length; j++) {
long diff = (long)A[j] - A[i];
if (diff == 0 || diff < Integer.MIN_VALUE || diff > Integer.MAX_VALUE) {
continue;
}
result += dfs(A, j, diff, indexMap);
}
}
return result;
}
private int dfs(int[] A, int index, long delta, Map<Integer, List<Integer>> indexMap) {
long next = A[index] + delta;
if (next < Integer.MIN_VALUE || next > Integer.MAX_VALUE || !indexMap.containsKey((int)next)) {
return 0;
}
int result = 0;
for (int i : indexMap.get((int)next)) {
if (i <= index) continue;
result += 1 + dfs(A, i, delta, indexMap);
}
return result;
}
}
疑点1: 这个代码的主要思路是什么,可以概括一下嘛?
疑点2: 这个代码如果改成C++, 怎么避免整型溢出?
下面是我尝试改成的C++代码。
总共有101个test case,我改的这个代码 TLE,test case 过了67个。溢出的原因是什么?long long还不够吗?
class Solution {
typedef long long LL;
public:
int numberOfArithmeticSlices(vector<int>& A) {
if (A.size() <= 2)
return 0;
unordered_map<LL, vector<LL>> indexDict;
for (int i = 0; i < A.size(); i++) {
if (!indexDict.count(A[i])) {
indexDict[A[i]] = {};
}
indexDict[A[i]].push_back(i);
}
LL result = 0;
for (auto kvp : indexDict) {
int size = kvp.second.size();
if (size >= 3) {
result += (LL)(1 << size) - 1 - size - (LL)(size * (size - 1)) / 2;
}
}
for (int i = 0; i < A.size() - 2; i++) {
for (int j = i + 1; j < A.size(); j++) {
LL diff = (LL)A[j] - A[i];
if (diff == 0 || diff < INT_MIN || diff > INT_MAX) {
continue;
}
result += dfs(A, j, diff, indexDict);
}
}
return int(result);
}
LL dfs(vector<int>& A, long index, long delta, unordered_map<LL, vector<LL>> indexDict) {
long next = A[index] + delta;
if (next < INT_MIN || next > INT_MAX || !indexDict.count((int)next)) {
return 0;
}
LL result = 0;
for (int i : indexDict[(int)next]) {
if (i <= index) continue;
result += 1 + dfs(A, i, delta, indexDict);
}
return (int)result;
}
};
疑点3: Java中的Integer.MIN_VALUE对应C++中的 INT_MIN还是 std::numeric_limits<int>::min()
或其他?
Java dfs2:
class Solution {
int res = 0;
Map<Integer, List<Integer>> idxs = new HashMap<>();
public int numberOfArithmeticSlices(int[] A) {
buildIdxMap(A);
for (Map.Entry<Integer, List<Integer>> entry : idxs.entrySet()) {
int d = entry.getValue().size();
if ( d> 2)
res += (1 << d) - 1 - d - d * (d - 1) / 2;
}
for (int j = 0; j < A.length-2; j++) {
for (int i = j+1; i <A.length-1; i++) {
long delta = (long)A[i] - (long)A[j];
if (delta == 0)
continue;
dfs(i,A[i]+delta,delta, 0);
}
}
return res;
}
private void dfs(int i, long b, long delta, int c) {
if(c>0)
res++;
if (b < Integer.MIN_VALUE || b > Integer.MAX_VALUE )
return;
List<Integer> l = idxs.get((int)b);
if(l == null)
return;
int idx = Collections.binarySearch(l,i+1); // Collections.binarySearch 改成 C++的low_bound理论上可以,但两者的返回值和找不到时的处理方式好像不同,Java如果没找到会在正确的地方插入, 返回-newIndex - 1
if (idx < 0) idx = -idx - 1;
for (int j = idx; j < l.size(); j++) {
dfs(l.get(j),b+delta, delta, c+1);
}
}
private void buildIdxMap(int[] A) {
for (int i = 0; i < A.length; i++) {
int a = A[i];
List<Integer> l = idxs.get(a);
if (l == null)
idxs.put(a, l = new ArrayList<>());
l.add(i);
}
}
}
疑点1: 这个代码的主要思路是什么,可以概括一下嘛?
疑点2: 这个代码如果改成C++, 其中的Collections.binarySearch 应该改为什么?或怎么改这个语句后面附近的逻辑?
参考:
以上两段Java代码来源: https://github.com/strengthen/LeetCode/blob/master/Java/446.java
版权声明
- 本文作者:极客中心
- 本文地址:https://www.geekzl.com/leetcode446-dfs-solutions.html
- 郑重声明:本文为原创或经授权转载的文章,欢迎转载,但转载时必须在文章页面明显位置注明出处: www.geekzl.com