序言

本系列博客笔记都是本人在刷leetcode题目时受到的一些启发和学习笔记，本人习惯使用Java进行练习，所以我的答题都是使用Java进行的，源码已经在GitHub开源，点击跳转GitHub欢迎在评论区进行讨论，但是本人的刷题速度较慢且现阶段只考虑刷算法题目，请见谅。

第一题：两数之和

原题

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

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

解答

解法一

分析

这道题目基本上的算法相当固定，简单的就是遍历，只要遍历全部的数组就一定能找到符合条件的或者是知道无解。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static class Solution {
       public int[] twoSum(int[] nums, int target) {
           int[] res = {0, 0};
           for (int i = 0; i < nums.length - 1; i++) {
               for (int j = i + 1; j < nums.length; j++) {
                   if (nums[i] + nums[j] == target) {
                       res[0] = i;
                       res[1] = j;
                   }
               }
           }
           return res;
       }
   }

解法二

分析

使用HashMap作为一个中间介质，对所有的数字先进行存储，然后再进行依次遍历，判断希望的数字是不是再map中出现，是一种比较简单的方法。但是遍历的过程是一个完整的循环，在解法三中可以进行优化。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static class Solution2 {
     public int[] twoSum(int[] nums, int target) {
         Map<Integer, Integer> map = new HashMap<>();
         for (int i = 0; i < nums.length; i++) {
             map.put(nums[i], i);
         }
         for (int i = 0; i < nums.length; i++) {
             int complement = target - nums[i];
             if (map.containsKey(complement) && map.get(complement) != i) {
                 return new int[] { i, map.get(complement) };
             }
         }
         throw new IllegalArgumentException("No two sum solution");
     }
 }

解法三

分析

答题思路与解法一相近，但是在添加到HashMap的过程中一边进行判断一边添加。是目前我看到的最优的解法。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
static class BestSolution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

第二题：两数相加

原题

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

解答

分析

这道题目比较简单，解法基本上固定，其他的高级的解法欢迎讨论。

我用了一个变量表示进位，然后进行依次的相加就可以得到答案了，唯一要注意的就是最高位有可能会多一位进位。直接上代码吧，没啥好说的。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode Head = new ListNode(0);
        ListNode firstNode = l1, secondNode = l2, curr = Head;
        int carry = 0;
        while (firstNode != null || secondNode != null) {
            int x = (firstNode != null) ? firstNode.val : 0;
            int y = (secondNode != null) ? secondNode.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (firstNode != null) firstNode = firstNode.next;
            if (secondNode != null) secondNode = secondNode.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return Head.next;
    }
}

第三题：无重复字符的最长子串

原题

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

解答

解法一

分析

最简单的方法一定是进行遍历，然后用循环进行寻找，复杂度较高直接放代码

代码
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
static class Solution {
    public boolean contains(String s, char ch) {
        for (int i = 0; i < s.length(); i++) {
            if (ch == s.charAt(i))
                return false;
        }
        return true;
    }

    public int lengthOfLongestSubstring(String s) {
        if(s.equals(""))
            return 0;
        int maxCount = 1;
        for (int i = 0; i < s.length(); i++) {
            int plus = 1;
            if ((i + plus) == s.length())
                break;
            while (contains(s.substring(i, i + plus), s.charAt(i + plus))) {
                plus += 1;
                if (plus > maxCount)
                    maxCount = plus;
                if (i + plus == s.length())
                    return maxCount;
            }
        }
        return maxCount;
    }
}

解法二

分析

使用移动窗口的办法，基本上比较好理解，使用HashSet进行解题。原理就是将后一个字符加入Set中时校验这个字符是不是已经存在，如果已经存在就将现在的set中的元素个数和最长长度进行比较，如果最长就记录。然后起点后移一个字符，再次检测，循环往复。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static class Answer {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> temp = new HashSet<>();
        int pt = 0, res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i != 0)
                temp.remove(s.charAt(i - 1));
            while (pt < s.length() && !temp.contains(s.charAt(pt))) {
                temp.add(s.charAt(pt));
                pt++;
            }
            res = Math.max(pt - i, res);
        }
        return res;
    }
}

第四题：寻找两个中序数组的中位数

原题

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例

示例 1:

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

则中位数是 2.0
示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

解答

分析

目前我就只会一种，也是看了题解才会的方法。这道题有点诡异，这种方法依靠了中位数的定义，希望分别找到一条分割线可以分割两个有序数组，这条分割线的位置的定义如下：

  • 第一个数组的分割线左边的值小于第二个数组的分割线右边的值
  • 第一个数组的分割线右边的值大于第二个数组的分割线左边的值
  • 两条分割线两边的数字数量相等或是分割线左边多一个

这里有特殊情况是可以被允许的，就是一个数组的所有的元素都在分割线单边，这是可以的。

当找到这条分割线的时候题目基本上就做完了。如果总共的元素是偶数，只要取两条分割线左边的较大值和右边的较小值进行相加就可以了。如果是奇数，只要拿到分割线左边的较大值就可以了。

代码

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
37
38
static class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;

        int totalLeft = m + (n - m + 1) / 2;

        int left = 0;
        int right = m;
        while (left < right) {
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;
            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                left = i;
            }
        }

        int i = left;
        int j = totalLeft - i;
        int nums1Left = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1Right = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2Left = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2Right = j == n ? Integer.MAX_VALUE : nums2[j];

        if ((m + n) % 2 == 1) {
            return Math.max(nums1Left, nums2Left);
        } else {
            return (double) ((Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right))) / 2;
        }
    }
}

参考链接

本文所有题目来源于LeetCode，仅作为学习用途。