java solution Beat 100%, idea from Frog Jump


  • 0
    P

    The same idea with Frog Jump, what's different is the next step size k is the same with previous (not like Frog Jump problem, k-1, k and k+1). But what more complicated than Frog Jump is how to handle the duplicated elements.
    Let dp[i][j] denote the number of slices ending at nums[j] with the previous nums[i],

    [0, 1, ..., i, ..., j], [..., k]
                |       |         |
               pre     cur       next
    

    At j, we should check next = cur + (cur-pre) exits or not. If exists, we update

    dp[k][j] += dp[j][i] + 1, and
      result += dp[j][i] + 1; 
    
    public int numberOfArithmeticSlices(int[] A) {
            int n = A.length;
            Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
            for(int i=0; i<n; i++){
                List<Integer> list = map.get(A[i]);
                if(list==null) list = new ArrayList<Integer>();
                list.add(i);
                map.put(A[i], list);
            }
            int[][] dp = new int[n][n];
            int res = 0;
            for(int cur=1; cur<n; cur++){
                for(int pre=cur-1; pre>=0; pre--){
                    long nextValue = (long)A[cur]+((long)A[cur]-A[pre]);
                    if(nextValue<Integer.MIN_VALUE || nextValue>Integer.MAX_VALUE) continue;
                    int nextVal = (int)nextValue;
                    if(map.containsKey(nextVal)){ 
                        List<Integer> list = map.get(nextVal);
                        int pos = Collections.binarySearch(list, cur+1);
                        pos = pos<0?(-pos-1):pos;
                        while(pos<list.size()){ 
                            int next = list.get(pos++);
                            dp[next][cur] += dp[cur][pre]+1;
                            res += dp[cur][pre]+1;
                        }
                        
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.