Tuesday, December 29, 2015

[LeetCode] Maximum Product of Word Lengths

Reference: https://leetcode.com/discuss/74589/32ms-java-ac-solution
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    public int maxProduct(String[] words) {
        if (words == null || words.length <= 1) return 0;
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String str1, String str2) {
                return str2.length() - str1.length();
            }
        });
        int[] wordHash = hashWords(words);
        int maximumProduct = 0;
        int left = 0, right = words.length - 1;
        while (left < right) {
            for (int i = left + 1; i <= right; i++) {
                if ((wordHash[left]&wordHash[i]) == 0) {
                    maximumProduct = Math.max(maximumProduct, words[left].length() * words[i].length());
                    right = i - 1;
                    break;
                }
            }
            left++;
        }
        return maximumProduct;
    }
     
    private int[] hashWords(String[] words) {
        int[] hash = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                hash[i] |= (1 << (word.charAt(j) - 'a'));
            }
        }
        return hash;
    }
}
Posted by at No comments:

Monday, December 28, 2015

[LeetCode] Burst Ballons

Reference: https://leetcode.com/discuss/72216/share-some-analysis-and-explanations
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] ballons = new int[nums.length+2];
        int index = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) ballons[index++] = nums[i];
        }
        ballons[0] = ballons[index] = 1;
        int[][] maximumPoints = new int[index+1][index+1];
        for (int stepLength = 2; stepLength <= index; stepLength++) {
            for (int left = 0; left <= index - stepLength; left++) {
                int right = left + stepLength;
                for (int i = left + 1; i < right; i++) {
                    maximumPoints[left][right] = Math.max(maximumPoints[left][right], maximumPoints[left][i] + maximumPoints[i][right] + ballons[left]*ballons[i]*ballons[right]);
                }
            }
        }
        return maximumPoints[0][index];
    }
}
Posted by at No comments:

Sunday, December 27, 2015

[LeetCode] Coin Change

Wrong one with greedy way,
Example: [130, 110, 1] 220

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return -1;
        Arrays.sort(coins);
        return numberOfCoins(coins, coins.length - 1, amount);
    }
    
    private int numberOfCoins(int[] coins, int coinIndex, int remainAmount) {
        if (remainAmount == 0) return 0;
        if (coinIndex < 0) return -1;
        int numberOfCurrentCoin = remainAmount / coins[coinIndex];
        while (numberOfCurrentCoin >= 0) {
            int numberOfRemainCoin = numberOfCoins(coins, coinIndex-1, remainAmount - numberOfCurrentCoin * coins[coinIndex]);
            if (numberOfRemainCoin >= 0) return numberOfRemainCoin + numberOfCurrentCoin;
            numberOfCurrentCoin--;
        }
        return -1;
    }
}
Iterative solution:
https://leetcode.com/discuss/76217/java-both-iterative-recursive-solutions-with-explanations
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return -1;
        if (amount <= 0) return 0;
        
        int[] minCoins = new int[amount + 1];
        minCoins[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            minCoins[i] = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i - coin >= 0 && minCoins[i - coin] != Integer.MAX_VALUE) {
                    minCoins[i] = Math.min(minCoins[i], minCoins[i - coin] + 1);
                }
            }
        }
        
        return minCoins[amount] == Integer.MAX_VALUE ? -1 : minCoins[amount];
    }
}
Recursive solution:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return -1;
        if (amount <= 0) return 0;
        HashMap<Integer, Integer> amountToCoinNumber = new HashMap<Integer, Integer>();
        return coinChangeHelper(coins, amount, amountToCoinNumber);
    }
     
    private int coinChangeHelper(int[] coins, int amount, HashMap<Integer, Integer> amountToCoinNumber){
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        if (amountToCoinNumber.containsKey(amount)) return amountToCoinNumber.get(amount);
        int minimumNumber = -1;
        for (int coin : coins) {
            int remainNumber = coinChangeHelper(coins, amount - coin, amountToCoinNumber);
            if (remainNumber >= 0) {
                minimumNumber = Math.min(minimumNumber == - 1 ? Integer.MAX_VALUE : minimumNumber , remainNumber + 1);
            }
        }
        amountToCoinNumber.put(amount, minimumNumber);
        return amountToCoinNumber.get(amount);
    }
}
Posted by at No comments:

Friday, December 25, 2015

[LeetCode] SuperUglyNumber

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int nthSuperUglyNumber(int n, int[] primeCollection) {
        if (primeCollection == null || primeCollection.length == 0) return 0;
         
        ArrayList<Integer> superUglyNumberCollection = new ArrayList<Integer>();
        superUglyNumberCollection.add(1);
        int[] lastNumberIndex = new int[primeCollection.length];
         
        for (int i = 2; i <= n; i++) {
            int possibleNumber = primeCollection[0] * superUglyNumberCollection.get(lastNumberIndex[0]);
            for (int j = 1; j < primeCollection.length; j++) {
                possibleNumber = Math.min(possibleNumber, primeCollection[j] * superUglyNumberCollection.get(lastNumberIndex[j]));
            }
            superUglyNumberCollection.add(possibleNumber);
            for (int j = 0; j < primeCollection.length; j++) {
                if (possibleNumber == primeCollection[j] * superUglyNumberCollection.get(lastNumberIndex[j])) {
                    lastNumberIndex[j]++;
                }
            }
        }
         
        return superUglyNumberCollection.get(n-1);
    }
}
Wrong one:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int nthSuperUglyNumber(int n, int[] primeCollection) {
        if (primeCollection == null || primeCollection.length == 0) return 0;
         
        ArrayList<Integer> superUglyNumberCollection = new ArrayList<Integer>();
        superUglyNumberCollection.add(1);
        int[] lastNumberIndex = new int[primeCollection.length];
         
        for (int i = 2; i <= n; i++) {
            int possibleNumber = primeCollection[0] * superUglyNumberCollection.get(lastNumberIndex[0]);
            for (int j = 1; j < primeCollection.length; j++) {
                possibleNumber = Math.min(possibleNumber, primeCollection[j] * superUglyNumberCollection.get(lastNumberIndex[j]));
            }
            superUglyNumberCollection.add(possibleNumber);
            for (int j = 0; j < primeCollection.length; j++) {
                if (possibleNumber == primeCollection[j] * superUglyNumberCollection.get(lastNumberIndex[j])) {
                    lastNumberIndex[j]++;
                    break; //This doesn't account for duplicates
                }
            }
        }
         
        return superUglyNumberCollection.get(n-1);
    }
}
Posted by at No comments:
Subscribe to: Posts (Atom)