LeetCode 13. 罗马数字转整数
题意输入罗马数字，输出对应的整数。具体规则间题面。
思路直接写。
由于两个字母结合的优先级高于一个字母的优先级，故我们可以把所有可能的情况存下来，然后遍历字符串时优先考虑两个字母的情况。时间复杂度$O(n)$。
代码123
...
LeetCode 12. 整数转罗马数字
发表于
|
更新于
|
分类于
LeetCode
题意输入整数，转化为罗马数字输出。具体转化规则见题面。
思路直接做。
可以把所有可选的数值列出来，然后从大到小选取数字。有点像给出固定面值的硬币，用贪心法凑固定数值所需要的最小个数的意思。时间复杂度：很低。
代码12345
...
LeetCode 11. 盛最多水的容器
发表于
|
更新于
|
分类于
LeetCode
题意给出$n$个垂直线段，相邻两线段之间的距离是$1$，选出一个区间，使得区间两端线段中较短的那根长度乘区间长度最大。
思路
想法1：枚举没对线段作为区间端点的情况。时间复杂度$O(n^2)$，太暴力。
想法2：双指针法
...
LeetCode 10. 正则表达式匹配
发表于
|
更新于
|
分类于
LeetCode
题意实现一个支持.和*的正则表达式匹配。其中.匹配任意单个字符，*匹配0或多个前面的那一个元素。
给出两个字符串s和p，前者只包含从a-z的小写字母，后者只包含从a-z的小写字母和两个匹配字符，问是否匹配。
思路
想法0：
...
LeetCode 9. 回文数
发表于
|
更新于
|
分类于
LeetCode
题意判断一个数是否为回文数。
思路
想法1：直接翻转数字，判断翻转后的数字和之前的是否相同。时间复杂度$O(log_{10}(n))$,要注意负数和爆int的问题。但这种做法只击败了37%的提交，考虑优化。
想法2：参考官
...
LeetCode 8. 字符串转换整数 (atoi)
发表于
|
更新于
|
分类于
LeetCode
题意实现一个atoi函数，具体功能如下：
丢弃开头无用的空格，直到找到第一个非空格的字符为止。
当寻找到的第一个非空字符为正负号时或数字时，将其与后面尽可能多的连续数字组合起来形成整数。剩余的部分忽略。
如果第一个字符非
...
LeetCode 7. 整数反转
发表于
|
更新于
|
分类于
LeetCode
题意给出一个 32 位的有符号整数，将这个整数中每位上的数字进行反转。
思路
想法：保留符号直接翻转，注意防止爆int。时间复杂度$O(log_{10}(n))$。
吐槽：官方给的结果是如果爆了int则返回0。（是我瞎了，
...
LeetCode 6. Z 字形变换
发表于
|
更新于
|
分类于
LeetCode
题意根据给定的行数，将字符串从上到下、从左到右进行Z字形排列，详见样例。
思路
想法1：直接模拟，时间复杂度$O(n)$。为什么运行时间只击败了21%的用户，内存消耗却击败了83%的用户？难道有什么空间换时间的方法？
想法
...
LeetCode 5. 最长回文子串
发表于
|
更新于
|
分类于
LeetCode
题意求给定子串的最长回文子串。
思路
想法1：枚举每个位置作为回文中心时的情况，往两边扩展看能扩展到什么位置，同时记录长度。时间复杂度$O(n^2)$。
想法2：以前当模板直接用的Manacher算法就是直接用来解决回文串
...
LeetCode 4. 寻找两个有序数组的中位数
发表于
|
更新于
|
分类于
LeetCode
题意给出两个有序数组，在时间复杂度$O(log(m + n))$内求出这两个数组的中位数。
思路
这个题目印象深刻，我在王道数据结构上做过，感觉是比每章给出的思维拓展题都要好的一道题目。与那道题不同的是，这道题两组数据给出
...