关于LeetCode446的几点疑问

作者: geekzl管理员 发布时间: 2021-08-12 08:08:26 9.38K 人阅读   百度未收录

关于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



版权声明

当前位置:极客学长 | 极客中心 » 关于LeetCode446的几点疑问

发表评论

Captcha Code

我还会在以下平台发布内容

知乎 CSDN