程序员进阶之算法练习(十六)

前言

正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 没有捷径,但手熟尔; 一步领先,步步领先。

正文

5. Longest Palindromic Substring 题目链接 题目大意: 输入一个回文串,输出长度最长的回文子串; 如果有多个答案,输出任意一个。

Example Input: "babad" Output: "bab" Note: "aba" is also a valid answer.

** 题目解析:** 模板题,有现成的解法。 求回文串有O(N)的算法,详见manacher解析。 ** 复杂度解析:** 空间、时间复杂度都是O(N), N是字符串的长度; ** 其他解法:** 暴力,从每个点开始枚举,判断最长的回文子串,O(N^2); kmp,回文串s和s的转置是一样的,那么可以把原串s和s'进行匹配,判断区间是否合法;(有可能存在匹配,但是区间不重叠的情况)

30. Substring with Concatenation of All Words 题目链接 ***题目大意: *** 给出一个字符串s,一个字符列表words,words内的单词都是同一长度,找到一个区间,要求: 1、区间内的字符串,可以切分成若干个连续的子串,每个子串都是words的单词; 2、每个单词只出现一次; 输出所有可能的区间的起点。

For example, given: s: "barfoothefoobarman" words: ["foo", "bar"] You should return the indices: [0,9].

题目解析: 题目提供了一个了一个不可忽视的限制,所有的words是同一长度,这样就避免了fool和foo的情况; 并且在判断s的子串是否出现时,可以直接截取长度为m的字符串。 这样流程就变成: 1、初始位置s,截取m个字符str,查询str是否在words中,如果在则判断下m个字符; 2、如果不在words中,则回溯到最初的位置s,从s+1开始判断。

但是, 这样的复杂度会很高,因为回溯之后又要从原来的位置的下一个开始匹配。 有一种优化方案:假设len为words字符串的统一长度; 从0,1,2...到len-1,分别匹配一次即可。 这样可以采取一种策略,当(l, r)的字符串最后len个字符匹配失败后,直接从r+1的位置匹配;因为(r-len,r)的字符不存在words中; 如果(r-len, r)在之前已经在k出现过,则可以把左边界移到k+1,直到遇到右边界; 可以在len次枚举后得到结果。

** 复杂度解析: ** 时间复杂度是O(N*len),len为words中单词的长度。 空间复杂度是O(M*len),hash的空间复杂度较高;

** 其他解法:** 有稍微慢一点,但是代码量很小的做法。 仅需20行。 详见这里

56. Merge Intervals 题目链接 ** 题目大意:** 给出n个数字区间,把有相交的区间合并起来。

example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

题目解析: 区间合并只需考虑最左和最右的边界。 先排序,把可能合并到区间集合在一起。 容易知道如果前面区间的right >= 当前区间的left 的时候,是可以合并的。 那么遍历一遍,判断边界是否相交即可。

** 复杂度解析:** 时间复杂度是O(NlogN),N是区间个数(时间都在排序上); 空间复杂度是O(N),有可能返回N个结果。

** 代码量:** 比较函数有简单写法。 sort(ins.begin(), ins.end(), [](Interval a, Interval b){return a.start < b.start;});

76. Minimum Window Substring 题目链接 ** 题目大意:** 给出两个字符串S和T,在S中寻找一个子串s,要求: 1、s包括T出现过的所有字符; 2、s的字符串长度最小;

For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".

如果没有,返回空串; 题目保证只有一个答案。

** 题目解析:** 题目要求s出现T中所有的字符,但是没有顺序要求,那么对于一段字符串: 字符串的位置是无意义的。 假设已经选择一段字符串str,再选新的一个字符c; 如果字符c没有出现过,那么c应该并入str中; 如果字符c已经出现过,那么新出现的c比原来的c更优; 在匹配过程中,当出现所有T的字符之后,一直保存最小的字符串长度。

这里可以用反证法来证明。

假设按照这一规则,选出包括所有T字符的子串s=(l, r),最右边的字符是c; 如果在(l, r)的位置k,k∈(l, r),存在字符c,并且(l, k)出现过所有T的字符; 那么按照之前的过程(l, k)会是最小值。

** 复杂度解析:** 时间复杂度是O(N),N是字符S的长度; 空间复杂度是O(M),M是T的长度;

**实现过程: ** 收获一枚WA,没想到题目还有这种数据:

Input: "a" "aa" Output: "a" Expected: ""

改改即可,记录下每个字符的数量。

123. Best Time to Buy and Sell Stock III 题目链接 题目大意: 给出n个数字的数组a,a[i]表示第i天股票的价格; 现在要求进行最多两次买卖: 1、不考虑购买数量,利润就是价格差,要求买卖后利润最大; 2、手上不能同时持有两次股票; 3、买卖次数最多为两次,可以为1次。

举例: [1,2,3,4] 利润最大是2;(只有一个选择1买、2卖、3买、4卖) 不能买1、2,在3、4卖。

** 题目解析:** 题目要求交易两次,但是两次又不能重叠。 那么可以枚举k,[1, k]为第一次交易,[k+1, n]为第二次交易,即可解决两次交易问题。 问题简化成在[1, k]中交易一次,求出最值。 [1, k] 同样可以简化为[1, t]区间买,[t+1, k]区间卖。 但是,这样的时间复杂度是O(N^2),因为需要枚举两次区间分隔。 实际上,这里面有很多重复的操作,比如说枚举完k之后,在枚举k+1的时候,有[1, k]区间的运算是之前求过的。 那么,考虑预处理,把这些结果存下来。

leftMax[i] 表示从左边开始,前i个的交易的最优解; rightMax[i] 表示从右边开始,前i个的交易的最优解; 这样只需要枚举k即可。 时间、空间复杂度O(n);

其他解法: 动态规划。 因为状态数非常少,直接用4个状态来表示当前状态。 // 0: 1 buy, 1: one buy/sell, 2: 2 buys/1 sell, 3, 2 buys/sells

139. Word Break 题目链接 ** 题目大意:** 给出原串s,字符串数组dict,要求: 1、把s分成多个连续的子串; 2、每个子串都在dict里面; 问,是否有解。

s = "leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code".

题目解析: 把一个串分成2个串的可能性有n种可能,n是字符串长度。 那么对于串[l, r] 如果[l, k] 和 [k+1, r]是合法的,那么[l, r]也是合法的。 故而用动态规划: dp[i][j] 表示字符串[i, j]是否为合法的子串; 枚举k∈[i, j] 来判断分割字符串的位置; 转移转移是O(N),因为需要判断区间[i, k]和[k+1, j]是否合法(用字典数配合); 最后判断dp[1, n]是否合法。

复杂度解析: 时间复杂度是O(N^3), N^2的状态 * N的字典数判断。 空间复杂度是O(N2+M),N2是状态数量,M是字典数;

优化方案: 1、dp用1维表示;dp[i] 表示前i个是否合理,转移的时候dp[i]=dp[k] && substr(k+1, i); 2、判断substr是否存在时,可以用字典树。

总结

给自己定了一个小目标:按照ACrate排序,把第一页所有的题目刷完。 目前已完成20题,第一页共有50道题,任务艰巨。 按照每日一题的时间来算,大概还要一个月的时间才能做完。 刚好,是年后。

一步领先,步步领先? 都知道操作系统、编译原理、网络原理、数据结构重要,但是现在已经没有毅力再去重新学一遍。 忙着面对生活与工作,偶尔的休闲时间则贡献给娱乐。 这就是普通的生活。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏苦逼的码农

一些常用的算法技巧总结

数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些...

15230
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

8920
来自专栏java一日一条

面试中的 10 大排序算法总结

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只...

21430
来自专栏趣谈编程

希尔排序

21360
来自专栏程序员叨叨叨

6.1 关系操作符(Comparison Operators)

在上一章中,我们已经介绍了Cg语言的基础数据类型(7种)、内置数据类型,以及数组、结构、接口等类型,本章将在此基础上讨论Cg中的表达式,表达式由操作符(oper...

6320
来自专栏chenjx85的技术专栏

leetcode-605-Can Place Flowers

10730
来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

20780
来自专栏轮子工厂

八大排序算法稳定性分析,原来稳定性是这个意思...

2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

25860
来自专栏云霄雨霁

字符串排序----排序算法的选择

25100
来自专栏Crossin的编程教室

【Python 第73课】reduce 函数

上次说了 Python 中一个比较有意思的内置函数 map,今天再来介绍另一个类似的函数:reduce map 可以看作是把一个序列根据某种规则,映射到另一个序...

29160

扫码关注云+社区

领取腾讯云代金券