【leetcode】第二部分

1-Longest Substring Without Repeating Characters

问题描述

给定一个字符串，找到没有重复字符的最长字串。

注意：返回结果必须是一个字串， 是一个子序列而不是字串。

解决思路

最开始的时候想的是最简单粗暴的方法暴力解决：两个循环，第一层循环，索引从 开始，找不重复的子字符串，每次递增 ，第二层遍历判断是否有重复，通过借助一个 的结构，可以将其算法复杂度限制在 上。提交不成功，原因：某个例子超时。

于是考虑：得找到一个 的方法来解决，也就是只遍历一遍。考虑到：定义两个指针 , ,从前往后，假设 中没有重复的字符，那么只需要判断 与前面是否有重复字符。如果没有，那么第二个指针继续向前 ；否则的话，找到与哪个字符重复，第一个指针移到下一位，即： ，其中 中存储的是字符的存储位置。这样能保证时间复杂度限制在 ，提交成功，耗时 。

代码

2-Median of Two Sorted Arrays

问题描述

有两个长度分别为 和 、并且已经排好序的数组：nums1和nums2。找到这两个数组的中位数，总体运行时间复杂度控制在 。

解题思路

找两个有序数组之间的中位数，思考一下，计算一个数列的中位数，如果该数列为单数，那么中位数为: ，否则的话为： 。那么，其实很明显，主要把问题转化为：找到两个有序数组的第 和 个数就行。

那么怎么获取第 小的数呢？很简单，使用两个指针，分别指向两个数组的开头，然后进行比较和遍历即可。

代码

3-Longest Palindromic Substring

问题描述

给定一个字符串 ，找到 中最长的回文子字符串。可以假定字符串的最长长度为 。

解决思路

拿到这个问题的时候丝毫摸不着头脑，于是偷偷查找了下网上的资料。偷懒找到了一个解法~主要思想是：动态规划，附一个动态规划的博客。动态规划的核心思想是：使用数学表达式来描述状态，以及如何进行状态之间的转移。在这里，我们先用数学形式来描述和求解这个问题：使用一个变量$a[i][j]$表示子字符串$s[i:j]$是否为回文字符串(取值为 和 )。定义状态之间的转移：

$$a[i][j]=\begin a[i+1][j-1] & \text\False & \text \end$$

初始化：很明显，当$i=j$时，$a[i][j]=True$。此外，我们通过看公式不难发现：$a[i][j]$的状态变化依赖于$a[i+1][j-1]$，因此考虑将$i$从后向前遍历，然后将$j$从$i$向后面遍历，另外的考虑到如果相邻两个字符相同，那么该值也应该为 ，此时$i-1 >= j + 1$。

代码

4-ZigZag Conversion

问题描述

在给定指定行数之后，使用一个 字型的模式描写 是按照下面的形式描述：

然后按照行进行读取，生成的字符串为：

需要完成一个函数将字符串基于行数完成这个转化：

解释：

解决思路

拿到这个问题的时候，第一个想法是：找到一个规律，计算出每一行下一个的标识是多少。例如，假设有 行，那么第一行第二列的下标值为 ，依次类推，每次都增加 ；而到了第 行，每列之间的间隔顺序分别是 ， ，找到这个规律后，只要不断叠加，直到下标超过字符串的长度为止。需要特别注意的是：第一行和第二行中每次间隔都是一样的，不用特殊处理。

图例： 每列之间的下标间隔示例（ ）

第二种方案：考虑使用一个字符串数组来存储每一行的字符，从前往后遍历整个字符串，判断应该将当前的字符应该添加到哪个字符串中，最后再遍历字符串数组。

代码

方案1

方案2

5-Reverse Integer

问题描述

给定一个32-位有符号的整数，将其位进行翻转。

注意：假设我们只能存储范围在$[−2^, 2^ − 1]$之间的32位有符号整型。当翻转的整数溢出时，该函数返回0。

解决思路

感觉这一题需要关注点在于：如何解决溢出的问题。考虑到整数的范围： 。一个有点作弊的想法是：使用语法自带的异常来处理，从而返回默认值 （o(╯□╰)o，这个想法好像没办法实现，因为溢出并不会报错）。

如果是负数，则先转化为正数，最后返回的时候将其转为负数即可。下面只考虑正数的情况：一般的做法，每次取整数的最后一位，然后每次乘以 ，累加起来，核心思路是：

接下来就看怎么判断溢出了，分析一下，当$ret >= INTMAX/10$的时候再乘以 ，则可能会溢出，分两种情况：

$ret > INTMAX/10$：肯定会溢出

$ret == INTMAX/10$：需要判断 的值是否大于$INTMAX\%10$，如果大于则会溢出。

另外，需要特别注意的是：负数的值比整数多一，因此需要对边界进行个调整。时间复杂度方面，一个 循环，$O(\log(x))$，$log(x)$表示 的位数。

另外，每台机器的$MAXINT$值不一样，在题干给定的条件下，我这里直接使用了 计算。

代码

6-String to Integer (atoi)

问题描述

实现一个函数 将字符串转化为一个整数。该函数先忽略必要的空白字符，直到第一个非空白的字符。然后，从这个字符开始,第一个是可选的加号或减号，后面是一些数字.将其编译为一个数字。

字符串可能会在构成整数的字符后面包含其它的字符，可以将这些字符忽视，并且不会影响该函数的行为。

如果非空白字符的第一个序列不是一个有效的整数，或者如果该字符串要么是空字符串.要么只包含空白字符，不用执行任何转化。

如果没有有效的转化.返回 。

注意：

只有空白字符 被看做是空白字符

假设我们在只能存储32位有符号整数的范围$[-2^,2^-1]$的环境中运行。如果整数值超过可表示值的范围，返回 （$2^-1$）或者 (${-2}^$)

解题思路

分析下，我们需要处理的字符包含 / / / ，其中，如果是空白字符，那么可以忽略，直到第一个数字字符或符号字符表明匹配正式开始，然后直到最后或者是其它字符为止。

另外，考虑到溢出的问题，可以参考上一题整数翻转的考虑来进行处理，在加之前判断是否溢出：

$ret > INTMAX/10$：肯定会溢出

$ret == INTMAX/10$：需要判断 的值是否大于$INTMAX\%10$，如果大于则会溢出。

写好代码之后，第一次提交报错了，输入为 时，应该不做转换，我这边进行了处理，还是没看清楚题目，空格符号只针对前面还没正式开始的情况，开始了之后遇到空格也应该要停止。

代码

7-Palindrome Number

问题描述

判断一个整数是否是一个回文数字。当数组向前读取和向后读取都相同时，整数是一个回文数字。

进一步：是否可以在不将其转变为字符串的情况下解决这个问题？

解题思路

看到这个题目的时候，第一想法是用两个指针分别表示，可是题干里面明确说了不建议使用字符串的方式进行比较...于是乎，想到：可不可以每次获得首尾两个数字进行比较呢？判断首尾是否相同，不相同直接返回，相同则继续进行比较，直到中间没有数字或者数字小于10为止。

提交之后，发现当中间有0的时候，这种方法就失败了，因为在计算中间值的时候会把0给去掉...

于是，换个思路：其实题干给了个很好的提示：将数字翻转过来，判断与原始数字是否相等就可以解决这个问题啦。（不过需要特别注意：溢出的问题~~~，虽然好像如果溢出的话，肯定就不是回文了，但是建议还是做个判断。）

此外，可以进一步进行简化，不一定需要全部翻转才能判断，例如我只翻转一半，将其与前一部分进行比较，如果后面的和前面的一样的话，也能证明该数字是一个回文数字。只不过需要考虑到位数为单数和双数的情况。

代码

方案一