Leetcode笔记

索引
[隐藏]

最近开始刷leetcode,在这里记录一下做题的过程,不定期更新。

GitHub:https://github.com/nyanim/leetcode

Top 100 Liked Questions

Two Sum(Easy)

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

思路1 – 暴力搜索

题目本身很简单,使用两个for循环遍历即可。需要注意的是同一元素不能使用两次,因此在遍历时,内层循环需要直接从外层循环+1处开始,而不是从头开始。

Solution:https://github.com/nyanim/leetcode/blob/master/TwoSum.py

思路2 – 哈希表

新建一个哈希表(Python中使用字典即可),遍历数组,以数组中的值为哈希表的键,以数组中的键为哈希表的值,将数组中的内容存入哈希表。

在遍历的同时检查(target-当前遍历到的值)是否存在哈希表的键中,如果存在则返回哈希表中的值和当前遍历到的键。这样复杂度由O(n^2)降低至O(n)。

Solution:https://github.com/nyanim/leetcode/blob/master/TwoSum(Hashmap).py

Add Two Numbers(Medium)

https://leetcode.com/problems/add-two-numbers/

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思路

这个题目很有意思,输入为两个使用链表形式给出的倒序数字,要求将这两个数字相加,并将两者之和同样以倒序的链表形式输出。

我最初的思路是遍历链表,将两个数字读取为字符串,并转换成整数求和,然后再组装成链表,但是这样很没意思。

观察题目可以发现,我们可以使用加法竖式的方法来求解。以题目中给出的example为例,同时遍历两个链表:

  1. 2+5 = 7,没有进位。
  2. 4+6 = 10,取0,有进位。
  3. 3+4 = 7,加上进位=8。
  4. 得到结果7->0->8

需要注意在两个数组都遍历完成后,需要检查进位标记是否为真,如果为真则需要在开头补上一个1。

Solution:https://github.com/nyanim/leetcode/blob/master/AddTwoNumbers.py

Valid Parentheses(Easy)

https://leetcode.com/problems/valid-parentheses

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

思路

很经典的一道题。题目给出一个包含各种括号的字符串,要求检验这些括号是否恰当地闭合。

我的方法是使用一个栈,遍历字符串。当遇到左括号时,将符号入栈;当遇到右括号时,检查栈顶元素是否为相应的左括号。如果是,将栈顶元素出栈;如果不是则直接返回false。

这个题目有几个坑需要注意:

  1. 在检查栈顶元素之前先判断栈是否为空,否则遇到空栈时会报运行时错误。
  2. 全部元素遍历完成后,检查栈是否为空,防止存在没有闭合的左括号。

Solution: https://github.com/nyanim/leetcode/blob/master/ValidParentheses.py

Merge Two Sorted Lists(Easy)

https://leetcode.com/problems/merge-two-sorted-lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

思路

这个题目我本来想像Add Two Numbers一样同时遍历两个链表,然后将较小的那一个优先加入结果链表中。但是这种方法无法处理类似于1->5->6, 1->3->4的输入。所以我使用了比较弱智的方法,将两个链表分别遍历,将内容存入一个数组,排序后组装成链表输出。

需要注意的是OJ会给出几个输入为None的极端的用例,需要注意处理这种情况。

Solution:https://github.com/nyanim/leetcode/blob/master/MergeTwoSortedLists.py

Container With Most Water(Medium)

https://leetcode.com/problems/container-with-most-water/

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

思路

最简单的方式是暴力搜索,如下代码实现的暴力搜索时间复杂度为O(n^2)。它仅能通过一些简单的用例,在一些超长(长达一屏半)的用例上则会TLE,所以需要想办法优化。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = 0
        max=0
        for left in range(0,len(height)):
            for right in range(left+1, len(height)):
                area = (right - left) * min(height[left], height[right])
                if area > max:
                    max = area
        return max

我考虑过从数组中值最大的位置开始,从大到小搜索,但是这种办法似乎没有办法降低复杂度,而且显然无法处理一些极端用例,比如一个递增或递减的序列。

我最后参考答案中的解法,设置分别位于数组左右两端的两个指针,计算两个指针所指向的位置的面积。然后将两个指针当中所对应的值较小的一个向数组中央移动。

Solution:https://github.com/nyanim/leetcode/blob/master/ContainerWithMostWater.py

3Sum(Medium)

https://leetcode.com/problems/3sum

Given an array nums of n integers, are there elements abc in nums such that ab + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路(WA)

我只设置了两层循环,用于迭代三元组中的前两个,然后用0减去前两元素之和,检查差是否存在在数组中。如果存在,则检查下标是否和前两个元素相同,以避免同一元素被重复使用。无误后将结果加入结果数组中。

但是这样仍然不能避免结果中有两个甚至更多数组重复的问题(包括内容相同但元素的顺序不同的)。因此需要重新遍历结果数组,去除重复的元素。我使用set(a) - set(b) == set() 将数组转换为集合来检查两者包含的元素是否相同。如果相同,上述表达式会返回True ,这样的结果需要被丢弃。

但是集合去重法存在一个问题:无法处理元素中包含0的情况,如图:

在这种情况下,set(a) - set(b) 表达式直接返回了{0},这导致结果中本应被保留的[0,0,0] 被错误地丢弃,所以一直无法通过相关的用例。

Solution: https://github.com/nyanim/leetcode/blob/master/3Sum.py

Letter Combination of a Phone Number(Medium)

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

思路

首先我们构造一个字典,将数字和字母的映射存入,并初始化一个数组作为存放结果的队列。遍历输入的字符串。

在第一轮迭代时,将第一个数字所对应的三个(或四个)字母推入队列。其后的每一轮迭代,都从队列中取出第一个字符串,依次追加当前数字所对应的三个(或四个)字母后,推入队尾。迭代完成后即可得到结果。如果不想使用队列的话,可以在每次迭代中将结果数组复制为一个临时数组来代替。

Solution: https://github.com/nyanim/leetcode/blob/master/LetterCombinationOfAPhoneNumber.py

PalindromeNumber(Easy)

https://leetcode.com/problems/palindrome-number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

思路

很经典的回文数题目。最简单的方法是将字符串转换成数组,遍历数组的同时将这个数字的前半部分进栈,然后比较栈顶数字和当前数字是否相同。需要注意区分奇数位数或偶数位数的情况。

我正在思考不将数字转换成字符串的实现方法。

Solution: https://github.com/nyanim/leetcode/blob/master/PalindromeNumber.py

…待续…

Show CommentsClose Comments

Leave a comment