LeetCode3

发表于 更新于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟

续LeetCode2

有了前面的做题经验，会发现接下来做的题有许多都是一个样板的翻版，都很类似，只要掌握了一些方法还是容易应对的。我写的一般都是新的题。

11.盛最多水的容器

题目地址

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例： >输入：[1,8,6,2,5,4,8,3,7]
>输出：49

begin

这个你会怎么去解呢？我的第一想法就是刚刚见识过的双指针，试试嘛。但是判断如何移动时慌了，不知道咋办了。之后看来题解恍然大悟，自己真傻，怎么移动？当时真是没脑筋，当然是低的向中间移动了，哎。

一种java题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxArea(int[] height) {
        int maxarea=0,l=0,h=height.length-1;
        while(l<h){
            maxarea=Math.max(maxarea,Math.min(height[l],height[h])*(h-l));
            if(height[l]<=height[h]){
                l++;
            }
            else{
                h--;
            }
        }
        return maxarea;
    }
}

详细题解

35.搜索插入位置

题目地址

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例1： >输入: [1,3,5,6], 5
>输出: 2

示例2： >输入: [1,3,5,6], 2
>输出: 1

示例3： >输入: [1,3,5,6], 7
>输出: 4

示例4： >输入: [1,3,5,6], 0
>输出: 0

begin

这是一个典型的二分法应用，迷惑的点在这个题叫“搜索插入位置”，关键是不存在时要找到插入为。想通这个就容易了，之后可以尝试这个69. x 的平方根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l=0,h=nums.length-1;
        while(l<=h){
            int mid=l+(h-l)/2;
            if(target==nums[mid]){
                return mid;
            }else if(target>nums[mid]){
                l=mid+1;
            }
            else{
                h=mid-1;
            }
        }
        return l;
    }
}

详细题解

141.环形链表

题目地址

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例1：

141-1

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

141-1

输入：head = [1,2], pos = 0 输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例3：

141-1

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [\(0\), \(10^4\)]
  • \({-10}^5\) <= Node.val <= \({10}^5\)
  • pos 为 \(-1\) 或者链表中的一个 有效索引 。

begin

官方给了两种方法。这个题是一定要放在这的原因就是因为第二种解法，我只能说能产生这种想法和思维的简直了。

方法一：哈希表

利用哈希表判断是否有重复元素进而得出结果。

官方方法一java

1
2
3
4
5
6
7
8
9
10
11
12
public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) {
        if (nodesSeen.contains(head)) {
            return true;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return false;
}

复杂度分析

  • 时间复杂度：O(\(n\))，对于含有 n 个元素的链表，我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(\(1\))的时间。
  • 空间复杂度：O(\(n\))，空间取决于添加到哈希表中的元素数目，最多可以添加 \(n\) 个元素。

方法二：快慢指针

想象跑步比赛，当无环时：快指针等于null，即到终点了，返回false。当有环时：快慢指针都会进入环赛道中，必定存在快指针超越慢指针，即的确有环，返回true。

官方方法二java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

复杂度分析

  • 时间复杂度：O(\(n\))，让我们将 \(n\) 设为链表中结点的总数。为了分析时间复杂度，我们分别考虑下面两种情况。

    • 链表中不存在环：
      快指针将会首先到达尾部，其时间取决于列表的长度，也就是 O(\(n\))。
    • 链表中存在环： 我们将慢指针的移动过程划分为两个阶段：非环部分与环形部分：
    1. 慢指针在走完非环部分阶段后将进入环形部分：此时，快指针已经进入环中 迭代次数 = 非环部分长度 = \(N\)
    2. 两个指针都在环形区域中：考虑两个在环形赛道上的运动员 - 快跑者每次移动两步而慢跑者每次只移动一步。其速度的差值为 1，因此需要经过 二者之间距离速度差值次循环后，快跑者可以追上慢跑者。这个距离几乎就是 "环形部分长度 \(K\)" 且速度差值为 \(1\)，我们得出这样的结论 迭代次数 = 近似于 "环形部分长度 K".

    因此，在最糟糕的情形下，时间复杂度为 O(\(N+K\))，也就是 O(\(n\))。

  • 空间复杂度：O(\(1\))，我们只使用了慢指针和快指针两个结点，所以空间复杂度为 O(\(1\))。

详细题解