LeetCode简单类型02(20-21-26-27-28)

发表于 | 分类于 | 阅读次数

这篇文章记录了leetcode上20.有效的括号、21.合并两个有序链表、26.删除排序数组中的重复项、27.移除元素 、28.实现strStr()五道题目的答案和解析。

20、有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：1、左括号必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

python代码：

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
39
40
41
42
43
44
class Solution(object):
    def trans(self,t):
        if t=='(':
            return 1
        elif t==')':
            return -1
        elif t=='[':
            return 2
        elif t==']':
            return -2
        elif t=='{':
            return 3
        elif t=='}':
            return -3
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        len_s = len(s)
        if len_s%2!=0:
            return False
        if s=='':
            return True
        if self.trans(s[0])<0:
            return False
        left_s=''
        for i in xrange(len_s):
            if self.trans(s[i])>0:
                left_s+=s[i]
            elif self.trans(s[i])<0 and len(left_s)>=1:
                if self.trans(s[i])+self.trans(left_s[-1])==0:
                    if len(left_s)==1:
                        left_s=''
                    else:
                        left_s=left_s[:-1]
                else:
                    return False
            else:
                return False
        if left_s=='':
            return True
        else:
            return False

well，well，well，这个题目重点应该不再算法上，而是在编程实现上，思路很明确，就是左括号不能出现在对应右括号的右边，括号必须成对出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
def trans(self,t):
    if t=='(':
        return 1
    elif t==')':
        return -1
    elif t=='[':
        return 2
    elif t==']':
        return -2
    elif t=='{':
        return 3
    elif t=='}':
        return -3

这个函数将字符转换为了数字，以便于判断是否配对问题，这个我感觉应该是最直观的方法吧，左括号为一个正数，右括号为负数，对应的相加刚好为0。

1
2
3
4
5
6
7
len_s = len(s)
if len_s%2!=0:
    return False
if s=='':
    return True
if self.trans(s[0])<0:
    return False

这里我考虑了三种特殊情况，1、长度不是偶数的话，那肯定至少有一组没有配对。2、根据题目要求。3、如果第一个括号为右括号的话，也是直接返回错误，因为违法了顺序规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
for i in xrange(len_s):
    if self.trans(s[i])>0:
        left_s+=s[i]
    elif self.trans(s[i])<0 and len(left_s)>=1:
        if self.trans(s[i])+self.trans(left_s[-1])==0:
            if len(left_s)==1:
                left_s=''
            else:
                left_s=left_s[:-1]
        else:
            return False
    else:
        return False

ps：第一次提交这次题目时候写了一个有bug的程序，但是通过了，已经反馈到他们网站，这里是修正后的程序。

  • 这段程序是算法的精髓，首先我们至少要把字符串遍历一遍，我们使用了一个新的字符串left_s用来保存左括号，意思就是我从头开始遍历s，遇到左括号就放进left_s，遇到右括号我先判断是不是和left_s最后面的是对应的，如果是那么就抵消，继续往后遍历，如果不对应，则结束。
  • 这里还有点要注意的，之前的错误就是在if self.trans(s[i])+self.trans(left_s[-1])==0:时，没有提前判断left_s的长度，如果刚好在此时之前都成功配对，那么left_s='',也就是你在根据索引取值就要报错，但是网站没有此类测试数据。

21、合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

python程序：

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        _rootNode=ListNode(0)
        rNode = _rootNode
        while l1 and l2:
            if l1.val<=l2.val:
                rNode.next = ListNode(l1.val)
                rNode = rNode.next
                l1 = l1.next
            else:
                rNode.next = ListNode(l2.val)
                rNode = rNode.next
                l2 = l2.next
        while l1:
            rNode.next = ListNode(l1.val)
            rNode = rNode.next
            l1 = l1.next
        while l2:
            rNode.next = ListNode(l2.val)
            rNode = rNode.next
            l2 = l2.next

        return _rootNode.next

这道题属于链表操作，最多需要遍历最长链表的长度。属于常规题目，但是链表的操作有一套定式，开始先声明头部，然而头部用两个变量来表示，因为链表的特性，你只能依次的回溯，不能直接跳到你想要的位置，所以用两个 变量，一个只是在最后返回的时候用，一次则参与主要运算。

1
2
3
4
5
6
7
8
9
while l1 and l2:
    if l1.val<=l2.val:
        rNode.next = ListNode(l1.val)
        rNode = rNode.next
        l1 = l1.next
    else:
        rNode.next = ListNode(l2.val)
        rNode = rNode.next
        l2 = l2.next

第一个循环，是算法的第一部分，因为两个链表的长度不一定相同，则这个循环会在短链表结束时停止，说明合并工作已经完成大部分了，接下来只需要将长链表的剩余部分接在合并的链表后面就行了，思路就是谁的值小我就加进合并的链表。

1
2
3
4
5
6
7
8
while l1:
    rNode.next = ListNode(l1.val)
    rNode = rNode.next
    l1 = l1.next
while l2:
    rNode.next = ListNode(l2.val)
    rNode = rNode.next
    l2 = l2.next

这里就是上面所说的将长链表剩余的添加进合并链表里面，因为从上面我们并不能得知哪个链表长，所以两个都要检查。

26、删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

python程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        len_nums = len(nums)
        if len_nums==0:
            return 0
        i=0
        for j in xrange(1,len_nums):
            if nums[i]==nums[j]:
                continue
            else:
                i+=1
                nums[i]=nums[j]
        return i+1

思路很常规，使用快慢指针，遍历一遍就可以。

1
2
3
1
2
3
len_nums = len(nums)
if len_nums==0:
    return 0

特殊情况处理，当给的字符串长度为0时，返回0。

1
2
3
4
5
6
7
i=0
for j in xrange(1,len_nums):
    if nums[i]==nums[j]:
        continue
    else:
        i+=1
        nums[i]=nums[j]

这一块是快慢指针的使用，i代表慢指针，j是快指针，快指针按照正常顺序遍历列表，慢指针指示不重复的元素的位置，快指针每次循环都会增加，慢指针只有在遇到不重复元素时才增加。

27、移除元素

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        len_nums = len(nums)
        if len_nums==0:
            return 0
        i=0
        for j in xrange(len_nums):
            if nums[j]==val:
                if j==len_nums-1:
                    return i
                continue
            else:
                nums[i]=nums[j]
                i+=1
        return i

这道题目仍是考察编程能力，思路很简单很直观。

1
2
3
1
2
3
len_nums = len(nums)
if len_nums==0:
    return 0

老样子，先把特殊情况搞定。

1
2
3
4
5
6
7
8
9
i=0
for j in xrange(len_nums):
    if nums[j]==val:
        if j==len_nums-1:
            return i
        continue
    else:
        nums[i]=nums[j]
        i+=1

继续运用快慢指针，这类题目让你就地进行操作的，感觉快慢指针是首选的方法。

28、实现strStr()

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

  • 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        len_hays = len(haystack)
        len_need = len(needle)
        if len_need==0:
            return 0
        for i in xrange(len_hays):
            if i+len_need>len_hays:
                return -1
            if haystack[i]==needle[0]:
                for k in xrange(len_need):
                    if haystack[i+k]!=needle[k]:
                        break
                    if k==len_need-1:
                        return i
        return -1

这道题比较常规，虽然是一次通过，但是花费时间有点长，主要是数组越界问题总是要想好一会，到底是总长还是总长-1。

1
2
3
4
len_hays = len(haystack)
len_need = len(needle)
if len_need==0:
    return 0

老规矩，既然题目中提示了，那就把needle长度为0的情况单独考虑。

1
2
3
4
5
6
7
8
9
10
for i in xrange(len_hays):
    if i+len_need>len_hays:
        return -1
    if haystack[i]==needle[0]:
        for k in xrange(len_need):
            if haystack[i+k]!=needle[k]:
                break
            if k==len_need-1:
                return i
return -1

我们把needle想象成图像处理里面模板匹配算法的模板，我们主体依旧是遍历haystack，每个元素都与needle[0]进行比较，只有相同了，才有继续往下谈的必要。假如haystack[i]与needle[0]相同了，那我们就进入循环，从i开始两个字符串依次进行比对，只要有不一样的，就结束，继续判断haystack[i+1]与needle[0]是否相同。其中没当进行新的迭代时，都要判断一下haystack剩余部分的长度是否小于needle的长度，若小于，直接结束，不可能匹配到，大于等于才继续。