这篇文章记录了leetcode上20.有效的括号、21.合并两个有序链表、26.删除排序数组中的重复项、27.移除元素 、28.实现strStr()五道题目的答案和解析。
20、有效的括号
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。有效字符串需满足:1、左括号必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
python代码:
1 |
|
well,well,well,这个题目重点应该不再算法上,而是在编程实现上,思路很明确,就是左括号不能出现在对应右括号的右边,括号必须成对出现。
1 |
|
这个函数将字符转换为了数字,以便于判断是否配对问题,这个我感觉应该是最直观的方法吧,左括号为一个正数,右括号为负数,对应的相加刚好为0。
1 |
|
这里我考虑了三种特殊情况,1、长度不是偶数的话,那肯定至少有一组没有配对。2、根据题目要求。3、如果第一个括号为右括号的话,也是直接返回错误,因为违法了顺序规则。
1 |
|
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 |
|
python程序:
1 |
|
这道题属于链表操作,最多需要遍历最长链表的长度。属于常规题目,但是链表的操作有一套定式,开始先声明头部,然而头部用两个变量来表示,因为链表的特性,你只能依次的回溯,不能直接跳到你想要的位置,所以用两个 变量,一个只是在最后返回的时候用,一次则参与主要运算。
1 |
|
第一个循环,是算法的第一部分,因为两个链表的长度不一定相同,则这个循环会在短链表结束时停止,说明合并工作已经完成大部分了,接下来只需要将长链表的剩余部分接在合并的链表后面就行了,思路就是谁的值小我就加进合并的链表。
1 |
|
这里就是上面所说的将长链表剩余的添加进合并链表里面,因为从上面我们并不能得知哪个链表长,所以两个都要检查。
26、删除排序数组中的重复项
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
python程序:
1 |
|
思路很常规,使用快慢指针,遍历一遍就可以。
1 |
|
特殊情况处理,当给的字符串长度为0时,返回0。
1 |
|
这一块是快慢指针的使用,i代表慢指针,j是快指针,快指针按照正常顺序遍历列表,慢指针指示不重复的元素的位置,快指针每次循环都会增加,慢指针只有在遇到不重复元素时才增加。
27、移除元素
给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
python代码:
1 |
|
这道题目仍是考察编程能力,思路很简单很直观。
1 |
|
老样子,先把特殊情况搞定。
1 |
|
继续运用快慢指针,这类题目让你就地进行操作的,感觉快慢指针是首选的方法。
28、实现strStr()
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
- 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
python代码:
1 |
|
这道题比较常规,虽然是一次通过,但是花费时间有点长,主要是数组越界问题总是要想好一会,到底是总长还是总长-1。
1 |
|
老规矩,既然题目中提示了,那就把needle
长度为0的情况单独考虑。
1 |
|
我们把needle
想象成图像处理里面模板匹配算法的模板,我们主体依旧是遍历haystack
,每个元素都与needle[0]
进行比较,只有相同了,才有继续往下谈的必要。假如haystack[i]
与needle[0]
相同了,那我们就进入循环,从i开始两个字符串依次进行比对,只要有不一样的,就结束,继续判断haystack[i+1]
与needle[0]
是否相同。其中没当进行新的迭代时,都要判断一下haystack
剩余部分的长度是否小于needle
的长度,若小于,直接结束,不可能匹配到,大于等于才继续。