LeetCode 6-10题

6.ZigZag Conversion

题目

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

代码

我的解法:

思路分析

使用数组完成,大体思路是把创造一个Array,里面每一个位置存放s的元素对应的index。那么在循环遍历的时候就可以逐次加s的元素,把它完成。所以一开始要求这个数组一共有多少列,然后轮询,根据数学推导出来的公式分别赋值,赋值结束后就得到结果,这个做法的问题在于需要数学推导很久,其实并不是最优解法。比较好的思路如下:

这里首先创造了一个二维的矩阵,每一行是一个string,它以index遍历s的每一个元素,以step控制前进的方向,如果第0行,是向下走,那么step累加,否则向上走,step递减。每次的元素加到对应行的string中,最后把L的所有行加在一起即可,这个编程简单,思路清晰,厉害的一笔。

注意点

  1. L = [''] * numRows创造多维数组
  2. numpy库的用法
  3. ''.join(L)指令的用法如下:

    string.join(seq)是以string作为分隔符,将seq所有的元素(的字符串表示)合并为一个新的字符串


7. Reverse Integer

题目

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Example 2:

Example 3:

Note:
Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

代码

我的解法:

思路分析

我的方法是把x转变成字符型,然后字符逆序,生成新的字符串,把它转化为int型后看他是否越界,越界返回0。

注意点

  1. Python的指数运算不用^,而是使用**

8. String to Integer (atoi)

题目

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

代码

我的解法:

思路分析

这里要注意几种情况,首先是数字前面和后面的空格,所以用str.strip()函数把空格消掉,然后要判断正负号,判断完后把正负号丢掉,轮询取出里面的数字,并且存到ret里面去,最后返回值要注意int类型的范围。

注意点

  1. str.strip()可以去掉str前面和后面的空格
  2. list()可以把str里的每个元素取出来
  3. str.isdigit()可以判断字符串是否只由数字组成,是的话返回True,否则返回False
  4. ord(char)返回char的Ascii位置对应的十进制整数

9. Palindrome Number

题目

Determine whether an integer is a palindrome. Do this without extra space

代码

我的解法:

思路分析

这里要注意几点,首先我想到的方法是化成string类型然后比较,但是这样不符合题目Do this without extra space.的条件,所以可以直接把数字回文,然后比较二者是否相等,但是在回文数的练习中我们知道可能会有溢出的情况,那么我们可以考虑数字的一半是不是相等,所以思路应该这样。

首先,我们应该关心一些边缘情况。所有负数不是回文,例如:-123不是回文,所以我们可以为所有负数返回false。

现在让我们考虑如何恢复数字的后半部分。对于1221号码,如果我们做1221%10,我们得到最后一位数字1,为了得到第二位数字,我们需要从1221中删除最后一位数字,我们可以将它除以10,1221 / 10 = 122.然后我们可以通过做一个10,122%10 = 2的模数再次得到最后一个数字,如果我们把最后一个数字乘以10并加上第二个数字1 * 10 + 2 = 12,我们想要的还原号码。继续这个过程会给我们更多的数字还原的数字。

现在的问题是,我们怎么知道我们已经达到了一半呢?

由于我们将数字除以10,并将倒数乘以10,当原数小于倒数时,意味着我们已经处理了一半的数字。

注意点

  1. 任何末尾为0的数字不是回文
  2. 15和16行的语序要注意,不能乱换,不然会出问题,因为x已经被处理了

10. Regular Expression Matching

题目

Implement regular expression matching with support for '.' and '*'.

代码

我的解法:

思路分析

如果没有'*',问题会更容易,我们只需从左到右检查文本的每个字符是否匹配模式。

'*'出现时,我们可能需要检查文本的许多不同的后缀,看它们是否与模式的其余部分相匹配。

递归解决方案是一种直接的方式来表示这种关系。

如果模式中存在星号,它将位于第二个位置p的第二个位置。那么,我们可能会忽略这部分(0个),或者删除文本中的匹配字符(多个,删除一个继续匹配后面的)。如果我们在这些操作之后剩余的字符串匹配,则匹配初始输入。

但是这样的解法时间复杂度和空间复杂度都比较高,LeetCode官网上还有另一种DP的解法,但是我看不懂……

注意点

  1. 递归函数的书写方式
  2. 判断是否有效可以用bool或者lenth来算

发表评论