【leetcode】第二部分

1-Longest Substring Without Repeating Characters

问题描述

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

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

解决思路

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

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

代码

2-Median of Two Sorted Arrays

问题描述

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

解题思路

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

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

代码

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给去掉...

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

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

代码

方案一

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180722G1A9AF00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励