barretlee / daily-algorithms Goto Github PK

本题难度：★★

给定 N 个非负整数 a₁, a₂, ..., a_n, 每个数对应坐标上的一个点 (i, a_i)，在坐标轴上将所有的 (i ,0) 和 (i, a_i) 使用直线链接起来。

任何两条 相邻的 线 （包含 Y 轴） ，这两条线与 X 轴构成一个容器，找出容量最大的容器对应的线。

注意：不能够倾斜容器，并且 n 不小于 2。

本题难度：★

将一个 32-bit 无符号整数的所有数字倒序，输出一个新的整数，如

eg1. x = 123, return 321
eg2. x = -123, return -321

提示：

1. 考虑末尾为零的情况，如 10, 100
2. 考虑溢出情况，如将 1000000003 倒序排列

溢出则输出 0.

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/2.md

本题难度：★

给定一个罗马数字（1~3999），将其转换为整数。

例如罗马数字 MCDXXXVII 对应数字为：1437。

相关资料：#9

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/10.md

本题难度：★★

给一个整数（1~3999），将其转换为罗马数字。

例如整数 1437 对应罗马数字为：MCDXXXVII。

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/9.md

本题难度：★★

两个非空链表，分别代表两个非负整数，链表的每个节点储存着整数的一位，并且是倒序储存的，将这两个数字相加返回新的链表，如：

输入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
返回: 7 -> 0 -> 8

提示，这道题需要考虑溢出问题。

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/3.md

花点时间实践算法，每日练习。

• ★ 表示 easy，★★ 表示 medium，★★★ 表示 hard；
• 题目主要来自 leetcode，可能会适当变换题设，改变难度；
• 对于 ★ 和 ★★ 难度的题目，每天的量会随机出现 1~5 个，尤其是 ★ 的题目，比较简单。

白天出题，尽量晚上给出参考答案。

仓库结构

讨论列表：https://github.com/barretlee/daily-algorithms/issues，每天的题目 & 参考答案，会记录在本仓库。

• /questions，算法题，主要来自 leetcode；
• /answers，questions 对应的答案，文件名包含 empty 表示未给出答案，不过可以去 issue 中查看讨论；
• /ref，一些算法技巧，以及数据结构的实现。

本题难度：★★

给定一个整数数组 S，找到所有的三元元组 (a, b, c)，使得 a + b + c = 0，注意，

• (a, b, c) 中 a ≤ b ≤ c
• 不要输出重复的元组

比如：

给定 S = [-1, 0, 1, 2, -1, -4]，输出 [[-1, 0, 1], [-1, -1, 2]]

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/12.md

本题难度：★★

给定一个纯数字的字符串，根据下面九宫格表返回所有可能的字母组合：

比如给定 "23"，那么所有可能的输出为：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

注意：上面给出的是按照辞典顺序输出的，可以不考虑顺序。

本题难度：★

不使用额外储存空间，判断一个整数是否为回文数字。例如：

-22 -> false
1221 -> true
1221221 -> true
1234321 -> true
234 -> false

需要注意的是：

• 考虑负数
• 不允许使用额外储存空间，比如将数字转换成字符串
• 反转数字需要考虑溢出问题

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/7.md

本题难度：★★

找出一个字符串中最长的连续子串，输出这个子串的长度，要求：这个子串中没有重复的字符。

比如：

给定 abcabcbb，最长的子串为 abc，那么输出结果为 3;
给定 bbbbb，最长的子串是 b，输出结果为 1;
给定 pwwkew，最长的子串为 wke，输出 3.

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/4.md

本题难度：★

给定一个整数数组，其中有两项之和为一个特定的数字，假设每次 input 只有一个唯一解，不允许两次使用同一个元素，返回这两个数的索引。

比如：

给定 nums = [2, 7, 11, 15]，target = 9

由于 nums[0] + nums[1] = 9
所以返回 [0, 1]

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/1.md

本题难度：★★

给定一个长度为 n 的整数数组 S，找出所有的非重复四元组 (a, b, c, d) 使得 a + b + c + d = target，如：

给定数组 S = [1, 0, -1, 0, -2, 2], target = 0，
那么输出结果为：

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

要求：

1. 输出的四元组按照顺序排列，即 a ≤ b ≤ c ≤ d;
2. 最后的输出结果不存在重复元组.

本题难度：★★★

实现一个正则表达式引擎，让其支持匹配 . 和 *，其中：

• . 匹配任何单字符
• * 匹配 0 个或者多个前字符

需要匹配全部输入而非部分输入，函数格式如下：

bool isMatch(const char *s, const char *p)

如：

isMatch('aa', 'a') // false
isMatch('aa', 'aa') // true
isMatch('aaa', 'aa') // false
isMatch('aa', 'a*') // true
isMatch('aa', '.*') // true
isMatch('ab', '.*') // true
isMatch('aab', 'c*a*b') // true

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/6.md

本题难度：★

写一个函数，找出一个字符串数组的最长共同前缀。例如：

给定 ['hi, barret', 'hi, skylar', 'hi, john']，输出 'hi, '

本题难度：★★

给定一个长度为 n 整数数组 S，找出三个整数，使得三数之和最接近给定的一个目标数 target，返回这三数之和。

假定给定的 S 只有一个解，例如：

给定 S = [-1, 2, 1, -4], target = 1，与 target 最接近的三数和为 (-1 + 2 + 1 = 2)，输出 2.

本题难度：★★

找到字符串 s 中最长的连续回文串，假定 s 的最大长度为 1000，如

输入 "babad"，输出 "bab"，"aba" 也是正确答案
输入 "cbbd"，输出 "bb"

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/5.md