LeetCode最受欢迎的100题汇总解答(1)

× 文章目录
  1. 1. 1.Two Sum [34.5%] [Easy]
  2. 2. 2.Add Two Numbers [27.7%] [Medium]
  3. 3. 3.Longest Substring Without Repeating Characters [24.3%] [Medium]
  4. 4. 4.Median of Two Sorted Arrays [21.7%] [Hard]
  5. 5. 5.Longest Palindromic Substring [25.2%] [Medium]
  6. 6. 10.Regular Expression Matching [24.1%] [Hard]
  7. 7. 11.Container With Most Water [36.6%] [Medium]
  8. 8. 15.3Sum [21.6%] [Medium]
  9. 9. 17.Letter Combinations of a Phone Number [34.4%] [Medium]
  10. 10. 19.Remove Nth Node From End of List [33.5%] [Medium]
  • 1.Two Sum ：从数组中找到 两个数 相加 和 为目标值 hasmap
  • 2.Add Two Numbers ：将两个链表表示的数相加 链表
  • 3.Longest Substring Without Repeating Characters ：没有重复元素的最长子字符串 hasmap
  • 4.Median of Two Sorted Arrays ：找到两个有序数组的中位数 二分
  • 5.Longest Palindromic Substring ：最长回文子字符串 以每个字符为中心扩散
  • 10.Regular Expression Matching ：判断表达式是否匹配，含有正则 . 和 * 。 DP
  • 11.Container With Most Water ：数组中任意两个点与x坐标组成的水桶，求最多能装多少水 两个指针
  • 15.3Sum ：数组中三个数能否相加后为0。求出所有组合，相同元素只算一次。 对所有不同元素求2sum
  • 17.Letter Combinations of a Phone Number ：递归、回溯经典题 回溯
  • 19.Remove Nth Node From End of List ：删除列表中从后往前数第n个结点 快慢指针

1.Two Sum [34.5%] [Easy]

  • 题意 ：给定一个整数数组，返回两个数字的索引，使它们相加到一个特定的目标。假定只有一个解，不能使用相同元素两次。

  • 例子

    • 对于数组nums = [2, 7, 11, 15]，目标值target为9，

    • 因为nums[0] + nums[1] = 2 + 7 = 9，所以返回[0, 1]。

  • 解题思路 ：使用Hashmap，key为数字，value为索引，遍历这个数组nums，如果target - nums[i]在map中，则找到了这两个数。

  • AC代码 ：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public class n1TwoSum{
      public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
          if (map.containsKey(target - numbers[i])) {
            result[1] = i + 1;
            result[0] = map.get(target - numbers[i]);
            return result;
          }
          map.put(numbers[i], i + 1);
        }
        return result;
      }
    }

2.Add Two Numbers [27.7%] [Medium]

  • 题意 ：给定两个非空的链表，表示两个非负整数， 低位在前，高位在后 。将两个数字相加并作为链表返回。假定两个数字不包含任何前导零，除了数字0本身。

  • 例子

    • 输入 (2 -> 4 -> 3) + (5 -> 6 -> 4)
    • 输出 7 -> 0 -> 8

  • 解题思路 ：按链表依次相加即可，注意进位

  • AC代码 ：

    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 n2AddTwoNumbers {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
          int carry = 0;
          ListNode newHead = new ListNode(0);
          ListNode p1 = l1, p2 = l2, p3 = newHead;
          while(p1 != null || p2 != null) {
            if (p1 != null) {
              carry += p1.val;
              p1 = p1.next;
            }
            if (p2 != null) {
              carry += p2.val;
              p2 = p2.next;
            }
            p3.next = new ListNode(carry % 10);
            p3= p3.next;
            carry = carry / 10;
          }
          if (carry == 1) {//不要忘记最后还有可能进位。
            p3.next = new ListNode(1);
          }
          return newHead.next;
        }
    }

3.Longest Substring Without Repeating Characters [24.3%] [Medium]

  • 题意 ：求无重复字符的最长子字符串

  • 例子

    • 给定“abcabcbb”，答案是“abc”，长度为3。
    • 给定“bbbbb”，答案是“b”，长度为1。
    • 给定“pwwkew”，答案是“wke”，长度为3。请注意，答案必须是子字符串，“pwke”是子序列而不是子字符串。

  • 解题思路 将字符串存储在key为字符、value为位置的hashmap，保留两个定义最大子字符串的指针。 移动右侧指针i扫描字符串，同时更新hashmap。 如果字符已经在hashmap中，则将左侧指针j移动到最后找到的同一个字符的右侧。注意，两个指针只能向前移动。

  • AC代码 ：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public class n3LongestSubstringWithoutRepeatingCharacters {
        public int lengthOfLongestSubstring(String s) {
          if (s.lenght() == 0) return 0;
          HashpMap<Character, Integer> map = new HashMap<>();
          int max = 0;
          for (int i = 0, j = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
              j = Math.max(j, map.get(s.charAt(i)) + 1); //移动到同一字符的右侧
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - j + 1);
          }
          return max;
        }
    }

4.Median of Two Sorted Arrays [21.7%] [Hard]

  • 题意 ：找到两个排序数组的中位数。整体运行时间复杂度要求为O（log（m + n））。

  • 例子

    • nums1 = [1, 3]，nums2 = [2]

    • The median is 2.0

    • nums1 = [1, 2]，nums2 = [3, 4]

    • The median is (2 + 3)/2 = 2.5

  • 解题思路 ：思想与二分查找思想一样，每次可以去掉k/2的值， k = (m + n) / 2。该方法的核心是将原问题转换为一个寻找第k小数的问题，这样中位数实际上是第（m + n）/2小的数。因此本质问题是 求解第k小数 的问题。

  • AC代码 ：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public class n4MedianOfTwoSortedArrays {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
          int m = nums1.length, n = nums2.length;
          int l = (m + n + 1) / 2, r = (m + n + 2) / 2;//考虑偶数时中位数有两个，需要去平均值
          return (getKth(nums1, 0, nums2, 0, l) + getKth(nums1, 0, nums2, 0, r)) / 2;  
        }
        public double getKth(int[] A, int aStart, int[] B, int bStart, int k) {
          if (aStart > A.length - 1) return B[bStart + k - 1];//A为空，直接取B的中位数
          if (bStart > B.length - 1) return A[aStart + k - 1];
          if (k == 1) return Math.min(A[aStart], B[bStart]); // k为1，表示找到中位数
          int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
          if (aStart + k / 2 - 1 < A.length) aMid = A[aStart + k / 2 - 1];
          if (bStart + k / 2 - 1 < B.length) bMid = B[bStart + k / 2 - 1];
          if (aMid < bMid)
            return getKth(A, aStart + k / 2, B, bStart, k - k / 2); // aMid小于bMid，表明中位数在aMid右部分、bMid左部分
          else
            return getKth(A, aStart, B, bStart + k / 2, k - k / 2);// 中位数在aMid左部分、bMid右部分
        }
    }

5.Longest Palindromic Substring [25.2%] [Medium]

  • 题意 ：给定一个字符串s，找到s中最长的 回文子字符串 。假定s的最大长度为1000。

  • 例子

    • Input: “babad”
    • Output: “bab”

    • Note: “aba” is also a valid answer

    • Input: “cbbd”

    • Output: “bb”

  • 解题思路 ：以每个字符作为回文子字符串中心向左右扩散，如果左右相等则增加距离，返回左右指针。要注意的是，如果是 偶回文子字符串，则中心为两个字符而不是一个字符 。

    • Manacher’s Algorithm可以做到O(n)，但有些复杂就不写了。

  • AC代码 ：

    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 n5LongestPalindromicSubstring {
        public String longestPalindrome(String s) {
          int start = 0, end = 0;
          for(int i = 0, i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
              start = i - (len - 1) / 2;
              end = i + len / 2;
            }
          }
          return s.substring(start, end + 1);
        }
        private int expandAroundCenter(String s, int left, int right) {
            while (left >= 0 && right < s.length && s.charAt(left) == s.charAt(right)) {
              left--;
              right++;
            }
            return right - left - 1;
        }
    }

10.Regular Expression Matching [24.1%] [Hard]

  • 题意 ：判断表达式是否匹配，含有正则 . 和 * 。 . 匹配任何单个字符， * 匹配0个或多个前面的字符

  • 例子

    • isMatch(“aa”,”a”) ? false
    • isMatch(“aa”,”aa”) ? true
    • isMatch(“aaa”,”aa”) ? false
    • isMatch(“aa”, “a*“) ? true
    • isMatch(“aa”, “.*“) ? true
    • isMatch(“ab”, “.*“) ? true
    • isMatch(“aab”, “c*a*b”) ? true

  • 解题思路 ： 用动态规划做， dp[i][j] 表示s的前i位字符与p的前j位字符匹配。则有以下情况

    • 如果 p.charAt(j) == s.charAt(i) ，则 dp[i][j] = dp[i-1][j-1] 。
    • 如果 p.charAt(j) == '.' ， 则 dp[i][j] = dp[i-1][j-1] ;
    • 如果 p.charAt(j) == '*' ，则
      • 如果 p.charAt(j-1) != s.charAt(i) ， dp[i][j] = dp[i][j-2] （将a*当作空）
      • 如果 p.charAt(j-1) == s.charAt(i) 或 p.charAt(i-1) == '.' ，则： dp[i][j] = dp[i-1][j] (将a当作多个a) 或 dp[i][j] = dp[i][j-1] (将a当作单个a) 或 dp[i][j] = dp[i][j-2] (将a*当作空)

  • AC代码 ：

    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
    public class n10RegularExpressionMatching {
        public boolean isMatch(String s, String p) {
          if (s.length == null || p.length == null) return false;
          boolean[][] dp = new boolean[s.length + 1][p.length + 1];
          dp[0][0] = true;
          for (int i = 0; i < p.length; i++) {
            if (p.charAt(i) == '*' && dp[0][i - 1])
              dp[0][i] = true;
          }
          for (int i = 0; i < s.length; i++) {
            for (int j = 0; j < p.length; j++) {
              if (p.charAt(j) == s.charAt(i))
                dp[i + 1][j + 1] = dp[i][j];
              if (p.charAt(j) == '.')
                dp[i + 1][j + 1] = dp[i][j];
              if (p.charAt(j) == '*') {
                if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.')
                  dp[i + 1][j + 1] = dp[i + 1][j - 1];
                else
                  dp[i + 1][j + 1] = (dp[i][j + 1] || dp[i + 1][j] || dp[i + 1][j - 1]);
              }
            }
          }
        }
    }

11.Container With Most Water [36.6%] [Medium]

  • 题意 ：给定一个非负整数数组，其中每个数表示坐标（i，ai）处的点。 绘制n条垂直线，使得线i的两个端点在（i，ai）和（i，0）处。 找到两条线，它们与x轴一起形成一个容器，使得容器含有最多的水。

  • 例子 无

  • 解题思路 ： 两个指针分别在0和n - 1位置，记下此时的面积，比较这两个位置的大小，如果右边大，则左指针向右遍历；如果左边大，则右指针向左遍历。然后计算新的面积。保存最大的面积

  • AC代码 ：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public class n11ContainerWithMostWater {
        public int maxArea(int[] height) {
          int left = 0, right = height - 1;
          int max = 0;
          while (left < right) {
            max = Math.max(max, Math.abs(height[left] - height[right]) * (right - left));
            if (height[left] > height[right])
              right--;
            else
              left++;
          }
        }
    }

15.3Sum [21.6%] [Medium]

  • 题意 ：给定n个整数的数组S，S中是否有元素a，b，c，使得c + b + c = 0？ 找到数组中所有这样的三个元素，相同结果只记一次

  • 例子 ：S = [-1, 0, 1, 2, -1, -4]，结果为[[-1, 0, 1], [-1, -1, 2]]

  • 解题思路 ：转换成twoSum问题。对于S中所有的不同元素，求它们的twoSum

  • AC代码 ：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public class n15ThreeSum {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);//排序，避免相同元素重复计算
            List<List<Integer>> res = new LinkedList<>();
            for (int i = 0; i < nums.length - 2; i++) {
              if (i == 0 || nums[i] != nums[i - 1]) {
                int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];
                while(lo < hi) {
                  if (nums[lo] + nums[hi] == sum) {
                    res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    while (lo < hi && nums[lo] == nums[lo + 1]) lo++;//避免重复计算
                    while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                  }
                  else if (nums[lo] + nums[hi] < sum) lo++;
                  else hi--;
                }
              }
            }
        }
    }

17.Letter Combinations of a Phone Number [34.4%] [Medium]

  • 题意 ：给定一个数字字符串，返回数字可能代表的所有可能的字母组合。映射关系是手机的九宫格。

  • 例子

    • Input:Digit string “23”
    • Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

  • 解题思路 ：回溯，没啥说的。

  • AC代码 ：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public class n17LetterCombinationsOfAPhoneNumber {
        public List<String> letterCombinations(String digits) {
          String table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
          List<String> list = new ArrayList<>();
          leeterCombination(list, digits, "", 0, table);
          return list;
        }
        private void leeterCombination(List<String> list, String digits, String curr, int index, String[] table){
          if (index == digits.length()){
            if (curr.length() != 0) list.add(curr);
            return;
          }
          String temp = table[digits.charAt(index) - '0'];
          for (int i = 0; i < temp.length(); i++) {
            String next = curr + temp.charAt(i);
            leeterCombination(list, digits, next, index + 1, table);
          }
        }
    }

19.Remove Nth Node From End of List [33.5%] [Medium]

  • 题意 ：给定一个链表，要求删除 从尾部数起 第n个节点，只允许遍历一次。

  • 例子

    • Given linked list: 1->2->3->4->5, and n = 2.
    • After removing the second node from the end, the linked list becomes 1->2->3->5.

  • 解题思路 ：快慢指针。快指针先走n + 1个结点，然后快慢指针一起遍历，当快指针到null时，慢指针就指向n前面的点

  • AC代码 ：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public class n19RemoveNthNodeFromEndOfList {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode start = new ListNode(0);
            ListNode slow = start, fast = start;
            slow.next = head;
            for (int i = 0; i < n + 1; i++) {
              fast = fast.next;
            }
            while (fast != null) {
              slow = slow.next;
              fast = fast.next;
            }
            slow.next = slow.next.next;
            return start.next;
        }
    }
赏

与你相遇，好幸运。

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

厌恶争执，不善言说<br><br>藏器于身，待时而动<br><br>祇畏神明，敬惟慎独