【LeetCode解析】LeetCode逐题解析(1 ~ 5题)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode解析】LeetCode逐题解析(1 ~ 5题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 两数之和

题目分析

数据范围：2 ~ 10⁴：使用o(n)级别算法。

算法思路：问题等价于找两个数在集合中的下标，返回集合中元素的下标通常考虑时间复杂度为o(1)的hash查找，或者是使用数组映射(对空间复杂度要求较高)，由于本题集合中元素的大小范围为：-10⁹ ~ 10⁹，因此我们选取hash查找来解决此问题

时间复杂度：o(n)

java代码

class Solution {
     static HashMap <Integer, Integer> map; // hash表
     static int n; // 集合中元素个数
     static int[] res; // 最后的结果
     public int[] twoSum(int[] nums, int target) {
          map = new HashMap<>();
          n = nums.length;
          res = new int[2];
          for (int i = 0; i < n; i ++) map.put(nums[i], i); // 初始化map，将对应集合中的元素值和元素下标相互映射

          for (int i = 0; i < n; i ++) {
               int t = target - nums[i];
               if (map.containsKey(t) && i != map.get(t)) { // 判断集合中是否包含元素以及确保同一个元素不被重复使用
                    res[0] = i;
                    res[1] = map.get(t);
                    break;
               }
          }

          return res;
     }
}

2. 两数相加

题目分析

本题直接模拟加法即可，具体步骤如下：
循环遍历两个链表的每一位数字，将两个数字相加，记录下余数(当前位的结果)以及进位，将余数加入待返回的结果中，注意：循环仅当两个数都遍历完成以及不存在进位时结束(当然也可以单独判断最后一位是否有进位)。

java代码

class Solution {
     static ListNode dummy; // 虚拟节点，用来处理结果
     static ListNode res; // 最后返回的结果
     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
          dummy = new ListNode();
          res = dummy;

          int t = 0;
          while (l1 != null || l2 != null || t != 0) { // 仅当两个链表都遍历结束以及不存在进位时结束
               int num1 = 0, num2 = 0; // 记录两个链表的的每一位上的值
               if (l1 != null) num1 = l1.val;
               if (l2 != null) num2 = l2.val;
               int v = (num1 + num2 + t) % 10; // 记录两个链表每一位相加的余数
               t = (num1 + num2 + t) / 10; // 记录两个链表每一位相加产生的进位
               dummy.next = new ListNode(v);
               dummy = dummy.next;
               if (l1 != null) l1 = l1.next; // 遍历链表的下一位
               if (l2 != null) l2 = l2.next;
          }

          return res.next;
     }
}

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

题目分析

数据范围：0 ～ 5 * 10⁴，使用o(n²)以下的算法

算法思路：使用滑动窗口(相当于于队列或双指针)解决，定义两个指针 l = 0， r = 0；r 表示滑动窗口的右端点，l 表示滑动窗口的左端点，指针 r 从前往后遍历，并且将元素加入滑动窗口中，在添加到滑动窗口的过程中判断当前窗口中是否包含待添加的元素，若有，则向左移动 l 指针并删除窗口中的元素，直到窗口中不包含待添加的元素，最后将 r 所指元素添加到滑动窗口中，并且更新最大值。

时间复杂度：o(n)

tips：由于是滑动窗口，所以 l < r(可类比队列)，窗口中的元素一定不重复

java代码

class Solution {
     static HashSet<Character> set; // 使用set存储窗口中的元素，方便判重
     static int n;
     static int maxValue; // 最后返回的最大值
     public int lengthOfLongestSubstring(String s) {
          set = new HashSet<>();
          n = s.length();
          maxValue = 0; // 初始化最大值

          for (int r = 0, l = 0; r < n; r ++) {
               while (l < r && set.contains(s.charAt(r))) { // 当窗口中包含待加入的元素时，直到窗口中不包含待加入元素
                    set.remove(s.charAt(l ++));
               }
               maxValue = Math.max(maxValue, r - l + 1); // 记录滑动窗口的最大大小
               set.add(s.charAt(r)); // 把待加入元素加入到窗口中
          }

          return maxValue;
     }
}

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

题目分析

数据范围：题目要求使用log(n + m)算法，所以传统排序算法就不试用

算法思路：首先题目要求求中位数，其实可以更一般化，即求第k位数 (令k等于(m + n) / 2就是求中位数) ；由于两个数组都是有序的，所以，我们不难证明出前k位数一定是由数组 num1 的前 l1 个连续数和数组 num2 的前 l2 个连续数构成 (即满足 l1 + l2 == k) ；因此，我们可以每次删除掉 num1 的前 k1 个数（当num1[k1] < num2[k2]时）或者删除掉 num2 的前 k2 个数（当num1[k1] > num2[k2时），k1、k2 满足 k1 + k2 <= k；但为了使平均时间复杂度满足 log(m + n)，我们每次取 k1 = k / 2，k2 = k - k1^【1】；然后再递归的去删除掉剩余的数，直到 k == 1 或者其中有一个数组被全部删除^【2】。

时间复杂度：o(log(m + n))

tips【1】：可能大家会问为什么【1】这句话中为什么 k1 + k2 <= k，大家可以看看下面的图解：
【LeetCode解析】LeetCode逐题解析(1 ~ 5题),leetcode,算法,职场和发展
如上图所示，我们可以假设前 k 个数是由 0～m 以及 0 ～ n 这两段构成，所以由图中我们不难看出，如果 k1 + k2 > k，那么就存在如图中的这种可能：即 k1 > m && k2 > n，那么我们在递归删除区间时就可能将第k个数删除掉，因此我们必须保证 k1 + k2 <= k，即保证 k1 与 k2 至少有一个点在 m 或 n 的左侧。

tips【2】：这道题最恶心的地方还是边界问题的讨论，为了简洁，我将这道题的边界问题主要分为两大类：
一、递归返回条件的讨论(即问题/递归什么时候结束)：
情况1：如果 k1 == num1.length 时，这时候说明 num1 数组已经被全部删除，那么此时求两个数组的第 k 个数就变成了求 num2 数组中的第 k 个数，即结果就为 num2[k2 + k - 1]。
情况2：如果 k == 1 时，这时候相当于找 num1 和 num2 中的第一个数，因此我们只需要返回 min(num1[k1], num2[k2])。
二、num1.length + num2.length 奇偶性的讨论：
情况1：如果 num1.length + num2.length 为奇数，那么我们直接返回中位数即可。
情况2：如果 num1.length + num2.length 为偶数，那么返回中间两个数之和除以 2。

java代码

class Solution {
     static int find(int[] num1, int l1, int[] num2, int l2, int k) {
          if (num1.length - l1 > num2.length - l2) return find(num2, l2, num1, l1, k); // 默认 num1 的长度大于 num2

          if (l1 == num1.length) return num2[l2 + k - 1]; // 当 num1 被全部删除，直接返回 num2 的第 k 个数
          if (k == 1) return Math.min(num1[l1], num2[l2]); // 当 k == 1 时，返回 min(num1[l1], num2[l2])

          int t1 = Math.min(num1.length, l1 + k / 2), t2 = l2 + k - (t1 - l1); // 每次 num1 删除 min(num1.length - l1, k / 2) 个元素或num2 删除 k - min(num1.length - l1, k / 2) 个元素

          if (num1[t1 - 1] < num2[t2 - 1]) return find(num1, t1, num2, l2, k - (t1 - l1)); // 递归删除
          else return find(num1, l1, num2, t2, k - (t2 - l2));
     }

     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
          int n = nums1.length + nums2.length;
          if (n % 2 == 0) { // 判断 nums1 的长度加上 nums2 的长度是奇数还是偶数
               int l = find(nums1, 0, nums2, 0, n / 2);
               int r = find(nums1, 0, nums2, 0, n / 2 + 1);
               return (l + r) / 2.0;
          } else {
               return find(nums1, 0, nums2, 0, n / 2 + 1);
          }
     }
}

5. 最长回文子串

题目分析

数据范围：1～1000，所以可以使用 o(n²) 级别算法（暴力枚举）

算法思路：中心扩散法，枚举字符串的每一位（即枚举中心），然后在再中心扩散，注意有两种情况，情况一：字串长度为奇数，直接从中心点 i 向两边扩散即可；情况二：字串长度为偶数，从 i 和 i + 1 这两点同时向两侧扩散；这两种情况可以在遍历字符串时同时枚举。

时间复杂度：o(n²)文章来源地址https://www.toymoban.com/news/detail-827422.html

java代码

class Solution {
     static int n; // 表示字符串的长度
     static int maxL; // 表示当前最长的回文串长度
     static int LL; // 记录最终最长回文子串的左端点
     static int RR; // 记录最终最长回文子串的右️端点

     static void find(String s, int l, int r) {
          while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { // 枚举字符串中每个点然后从此点向两边扩散
               if (r - l + 1 > maxL) {
                    maxL = r - l + 1;
                    LL = l;
                    RR = r;
               }
               l --;
               r ++;
          }
     }

     public String longestPalindrome(String s) {
          n = s.length();
          maxL = 0;

          for (int i = 0; i < n; i ++) {
               find(s, i, i); // 情况一
               find(s, i, i + 1); // 情况二
          }

          return s.substring(LL, RR + 1);
     }
}