Algorithm: Leetcode Contest 402

3185. Count Pairs That Form a Complete Day II

Solution

class Solution {
    public long countCompleteDayPairs(int[] hours) {
        long res = 0;
        // build a map, key is the value mod 24, value is a list of index
        
        // then iterate on hours, find its remaining value in map, then accumulate res
        Map<Integer, List<Integer>> map = new HashMap<>();
        
        int temp = 0;
        for(int i = 0; i < hours.length; i++) {
            temp = hours[i] % 24;
            if (map.containsKey((24 - temp) % 24)) {
                res += map.get((24 - temp) % 24).size();
            }
            
            if (!map.containsKey(temp)) {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(temp, list);
            } else {
                List<Integer> list = map.get(temp);
                list.add(i);
            }
            
            
        }
        
        return res;
    }
}

Recap

1. remember use long or int
2. the var name, temp is not good for understanding

3186. Maximum Total Damage With Spell Casting

Solution 1

class Solution {
    public long maximumTotalDamage(int[] power) {
        // sort power
        Arrays.sort(power);

        // dp -> best result when casting ith spell
        long[] dp = new long[power.length];
        dp[0] = power[0];
        long preMax = 0, res = dp[0];
        for(int left = 0, right = 1; right < power.length; right++) {
            if (power[right] == power[right - 1]) {
                dp[right] = dp[right - 1] + power[right];
            } else {
                while(power[left] + 2 < power[right]) {
                    preMax = Math.max(preMax, dp[left++]);
                }

                dp[right] = preMax + power[right];
            }
            res = Math.max(res, dp[right]);
        }

        return res;
    }
}

Solution 2

class Solution {
    public long maximumTotalDamage(int[] power) {
        Arrays.sort(power);
        
        return dfs(0, 0, 0, 0, power);
    }
    
    private long dfs(long cur, long nextLegit, int lastUsed, int index, int[] power) {
        if (index == power.length) {
            return cur;
        }
        
        long take = 0;
        
        if(power[index] > nextLegit || power[index] == lastUsed) {
           take = dfs(cur + power[index], power[index] + 2, power[index], index + 1, power);
        }
        
        long skip = dfs(cur, nextLegit, lastUsed, index + 1, power);
        
        return Math.max(skip, take);
    }
}

Recap

1. how to build string String.format("%s", xxx)