LeetCode(68) -- 16, 17

P16. 3Sum Closest (Medium)

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

我的思路

Similar to 3 sum, each time, if the sum is closer to the target, update the diff and the result.

我的代码

public class P16_3SumClosest {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int diff = Integer.MAX_VALUE;
        int res = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int l = i + 1;
            int r = nums.length - 1;
            int sum = target - nums[i];
            while (l < r) {
                if (nums[l] + nums[r] == sum) {
                    return target;
                } else if (nums[l] + nums[r] < sum) {
                    if (Math.abs(sum - nums[l] - nums[r]) < diff) {
                        res = nums[i] + nums[l] + nums[r];
                        diff = Math.abs(sum - nums[l] - nums[r]);
                    }
                    l++;
                } else {
                    if (Math.abs(sum - nums[l] - nums[r]) < diff) {
                        res = nums[i] + nums[l] + nums[r];
                        diff = Math.abs(sum - nums[l] - nums[r]);
                    }
                    r--;
                }
            }
        }
        return res;
    }
}

95%

最优解

class Solution {
    public int threeSumClosest(int[] nums, int target) {

        if (nums.length == 3) {
            return nums[0] + nums[1] + nums[2];
        }

        Arrays.sort(nums);
        return findTarget(nums, target);
    }

    private int findTarget(int[] sorted, final int target) {
        int closest = sorted[0] + sorted[1] + sorted[2];
        int diff = Math.abs(closest - target);

        for (int lo = 0, end = sorted.length; lo < end - 2 && diff != 0; lo++) {
            // Upper bound
            if (sorted[lo] + sorted[end-1] + sorted[end-2] < target) {
                closest = sorted[lo] + sorted[end-1] + sorted[end-2];
                diff = Math.abs(closest - target);
                continue;
            }

            // Lower bound
            if (sorted[lo] + sorted[lo+1] + sorted[lo+2] > target) {
                int temp = sorted[lo] + sorted[lo+1] + sorted[lo+2];
                if (Math.abs(target - temp) <= diff) {
                    closest = temp;
                }
                break;
            }

            // Remaining values
            int mid = lo + 1;
            int hi = end - 1;
            while(hi > mid) {
                int temp = sorted[lo] + sorted[mid] + sorted[hi];
                if (temp == target) {
                    return target;
                }
                if(temp < target) {
                    mid++;
                }
                else {
                    hi--;
                }
                int tempDiff = Math.abs(target - temp);
                if (tempDiff <= diff) {
                    closest = temp;
                    diff = tempDiff;
                }
            }
        }

        return closest;
    }
}

P17. Letter Combinations of a Phone Number (Medium)

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

我的代码

public class P17_LetterCombinationsofaPhoneNumber {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        int digit = digits.charAt(0) - '0';
        int keySize = digit < 7 || digit == 8 ? 3 : 4;
        int offset;
        if (digit <= 7) {
            offset = (digit - 2) * 3;
        } else if (digit == 8) {
            offset = 19;
        } else {
            offset = 22;
        }
        for (int i = 0; i < keySize; i++) {
            ans.add(String.valueOf((char)('a' + offset + i)));
        }

        for (int i = 1; i < digits.length(); i++) {
            digit = digits.charAt(i) - '0';
            List<String> list = new ArrayList<>();
            for (int k = 0; k < ans.size(); k++) {
                String s = ans.get(k);
                keySize = digit < 7 || digit == 8 ? 3 : 4;
                if (digit <= 7) {
                    offset = (digit - 2) * 3;
                } else if (digit == 8) {
                    offset = 19;
                } else {
                    offset = 22;
                }
                for (int j = 0; j < keySize; j++) {
                    list.add(s + (char) ('a' + offset + j));
                }
            }
            ans = list;
        }
        return ans;
    }

    public static void main(String[] args) {
        List<String> strings = new P17_LetterCombinationsofaPhoneNumber().letterCombinations("7");
        System.out.println("strings = " + strings);
    }
}

100%

最优解

class Solution {
    HashMap<Character, String> map = new HashMap<>();
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return res;
        }
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        String[] str = new String[1];
        str[0] = "";
        getString(res, digits, str, 0);

        return res;
    }

    private void getString(List<String> res, String digits, String[] str, int index){
        if (index == digits.length()) {
            res.add(str[0]);
            return;
        }
        String s = getStr(digits.charAt(index));
        for(int i = 0; i < s.length(); i++) {
            str[0] += s.charAt(i);
            getString(res, digits, str, index + 1);
            str[0] = str[0].substring(0, index);
        }
    }

    private String getStr(Character ch) {
        return map.get(ch);
    }
}