2019-04-01-LeetCodeTop100高频题目解答

LeetCode Top 100 高频题目

已完成 LeetCode Top 100 中所有编程题。

1. 两数之和

思路：直接用 HashMap 存储差值，之后遍历找到这个差值即可返回。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numToIndex = new HashMap<>();
    int len = nums.length;
    int[] result = new int[2];
    for (int i = 0; i < len; i++) {
        if (numToIndex.containsKey(nums[i])) {
            result[0] = numToIndex.get(nums[i]);
            result[1] = i;
            return result;
        } else {
            numToIndex.put(target - nums[i], i);
        }
    }
    return new int[2];
}

2. 两数相加

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode next = head;
    int sum = 0;
    while (l1 != null || l2 != null) {
        sum /= 10;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        next.next = new ListNode(sum % 10);
        next = next.next;
    }
    if (sum / 10 == 1) next.next = new ListNode(1);
    return head.next;
}

3. 无重复字符的最长子串

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0 || s.length() == 1) return s.length();
    HashMap<Character, Integer> hashMap = new HashMap<>();
    int head = 0, max = 0;
    for (int i = 0; i < s.length(); i++) {
        if (hashMap.containsKey(s.charAt(i))) {
            head = Math.max(hashMap.get(s.charAt(i)) + 1, head);
        }
        max = Math.max(i - head + 1, max);
        hashMap.put(s.charAt(i), i);
    }
    return max;
}

4. 寻找两个有序数组的中位数

5. 最长回文子串 — 动态规划

public String longestPalindrome(String s) {
    if (s.length() == 0 || s.length() == 1) return s;
    int left = 0, right = 1, maxLength = 0;
    int len = s.length();
    boolean[][] check = new boolean[len][len];
    for (int i = 0; i < len; i++) {
        check[i][i] = true;
        for (int j = 0; j < i; j++) {
            check[j][i] = s.charAt(i) == s.charAt(j) && (i - j < 2 || check[j + 1][i - 1]);
            if (check[j][i] && i - j + 1 > maxLength) {
                maxLength = i - j + 1;
                left = j;
                right = i + 1;
            }
        }
    }
    return s.substring(left, right);
}

11. 盛最多水的容器 — 双指针

15. 三数之和 — 排序+双指针

17. 电话号码的字母组合 — 排列组合