1. 数据流的中位数
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：
addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2
进阶:
如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
出处：
https://edu.csdn.net/practice/23818932
代码：
class MedianFinder(object): def __init__(self): """ initialize your data structure here. """ self.array = [] def addNum(self, num): """ :type num: int :rtype: None """ self.array.append(num) def findMedian(self): """ :rtype: float """ self.array.sort() n = len(self.array) if n % 2 == 1: return self.array[n // 2] else: return (self.array[n // 2] + self.array[n // 2 - 1]) / 2.0 # Your MedianFinder object will be instantiated and called as such: # obj = MedianFinder() # obj.addNum(num) # param_2 = obj.findMedian() # %% obj = MedianFinder() obj.addNum(1) obj.addNum(2) print(obj.findMedian()) obj.addNum(3) print(obj.findMedian())
输出：
1.5
2
2. 罗马数字转整数
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个罗马数字，将其转为整数。
示例 1:
输入: "III"
输出: num = 3
示例 2:
输入: "IV"
输出: num = 4
示例 3:
输入: "IX"
输出: num = 9
示例 4:
输入: "LVIII"
输出: num = 58
解释: L = 50, V = 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: num = 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示：
1 <= num <= 3999
出处：
https://edu.csdn.net/practice/23818933
代码：
class Solution: def romanToInt(self, s: str) -> int: units = [ ["M", 1000, 1], ["CM", 900, 2], ["D", 500, 1], ["CD", 400, 2], ["C", 100, 1], ["XC", 90, 2], ["L", 50, 1], ["XL", 40, 2], ["X", 10, 1], ["IX", 9, 2], ["V", 5, 1], ["IV", 4, 2], ["I", 1, 1] ] end = len(s) start = 0 i = 0 r = 0 while i < len(units): unit = units[i][0] value = units[i][1] step = units[i][2] if end-start >= step and s[start:start+step] == unit: r += value start += step else: i += 1 return r # %% s = Solution() print(s.romanToInt("III")) print(s.romanToInt("IV")) print(s.romanToInt("IX")) print(s.romanToInt("LVIII")) print(s.romanToInt("MCMXCIV"))
输出：
3
4
9
58
1994
代码2： dict 把原题中的units列表改为字典形式
class Solution: def romanToInt(self, s: str) -> int: units = { "M": 1000, "CM": 900, "D": 500, "CD": 400, "C": 100, "XC": 90, "L": 50, "XL": 40, "X": 10, "IX": 9, "V": 5, "IV": 4, "I": 1 } res, i, j = 0, 0, 0 roman = list(units) while i < len(units): unit = roman[i] step = len(unit) if j+step <= len(s) and s[j:j+step] == unit: res += units.get(unit) j += step else: i += 1 return res # %% s = Solution() print(s.romanToInt("III")) print(s.romanToInt("IV")) print(s.romanToInt("IX")) print(s.romanToInt("LVIII")) print(s.romanToInt("MCMXCIV"))
3. 插入区间
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
示例 3：
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
示例 4：
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
示例 5：
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]
提示：
0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 10^5
intervals 根据 intervals[i][0] 按 升序 排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 10^5
出处：
https://edu.csdn.net/practice/23818934
代码：
class Interval(object): def __init__(self, s=0, e=0): self.start = s self.end = e class Solution(object): def list2interval(self, list_interval): ret = [] for i in list_interval: interval = Interval(i[0], i[1]) ret.append(interval) return ret def interval2list(self, interval): ret = [] x = [0,0] for i in interval: x[0] = i.start x[1] = i.end ret.append(x) x = [0,0] return ret def insert(self, intervals, newInterval): """ :type intervals: List[Interval] :type newInterval: Interval :rtype: List[Interval] """ if intervals is None or len(intervals) == 0: return [newInterval] intervals = self.list2interval(intervals) newInterval = Interval(newInterval[0], newInterval[1]) intervals.sort(key=lambda x:x.start) pos = 0 while pos < len(intervals): if newInterval.end < intervals[pos].start: intervals.insert(pos, newInterval) intervals = self.interval2list(intervals) return intervals if self.check_overlap(intervals[pos], newInterval): temp = intervals.pop(pos) newInterval = self.merge_intervals(temp, newInterval) else: pos += 1 if len(intervals) == 0 or pos == len(intervals): intervals.append(newInterval) intervals = self.interval2list(intervals) return intervals def check_overlap(self, curr_int, new_int): if curr_int.start <= new_int.start: if curr_int.end > new_int.start: return True else: if curr_int.start <= new_int.end: return True return False def merge_intervals(self, int1, int2): temp_int = Interval() temp_int.start = min([int1.start, int2.start]) temp_int.end = max([int1.end, int2.end]) return temp_int # %% s = Solution() print(s.insert(intervals = [[1,3],[6,9]], newInterval = [2,5])) print(s.insert(intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8])) print(s.insert(intervals = [], newInterval = [5,7])) print(s.insert(intervals = [[1,5]], newInterval = [2,3])) print(s.insert(intervals = [[1,5]], newInterval = [2,7]))
输出：
[[1, 5], [6, 9]]
[[1, 2], [3, 10], [12, 16]]
[[5, 7]]
[[1, 5]]
[[1, 7]]
