「 复 古 未 来 」S y n t h w a v e 合 成 器 浪 潮

BACK TO THE FUTURE : 重回 80s 霓虹情结与赛博幻象

“我所见过的事物,你们人类绝对无法置信。我目睹太空飞船在猎户星座的端沿被击中,燃起熊熊火光。我看着C 射线在唐怀瑟之门附近的幽暗中闪耀。然而这些时刻终将湮没在时间里,就像泪水消失在雨中。” –《银翼杀手》

上世纪 60 年代,NASA 的两位科学家曼弗雷德・克林斯和内森・克兰取了 “控制论”(cy­ber­net­ics)与 “有机体”(or­gan­ism)两词的词首造出 “赛博格”(Cy­borg)一词,用来描述通过医学、生物学、仿生学等技术对有机体进行控制的人和人造物组成的统一功能体。

Read more

LeetCode[146] LRU缓存机制

“设计”: https://leetcode.com/tag/design/ Similar Questions: “LFU 缓存”: https://leetcode.com/problems/lfu-cache/ “设计内存文件系统”: https://leetcode.com/problems/design-in-memory-file-system/ “迭代压缩字符串”: https://leetcode.com/problems/design-compressed-string-iterator/

Problem:

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制

实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 1
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 3000
  • 0 <= value <= 104
  • 最多调用 3 * 104getput
Read more

LeetCode[3] 无重复字符的最长子串

“哈希表”: https://leetcode.com/tag/hash-table/
“双指针”: https://leetcode.com/tag/two-pointers/
“字符串”: https://leetcode.com/tag/string/
“Sliding Window”: https://leetcode.com/tag/sliding-window/
Similar Questions:
“至多包含两个不同字符的最长子串”: https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
“至多包含 K 个不同字符的最长子串”: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
“K 个不同整数的子数组”: https://leetcode.com/problems/subarrays-with-k-different-integers/

Problem:

给定一个字符串,请你找出其中不含有重复字符的 最长子串的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

示例 4:

1
2
输入: s = ""
输出: 0

提示:

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成
Read more

LeetCode[215] 数组中的第K个最大元素

方法一:基于快速排序的选择方法

我们可以改进快速排序算法来解决这个问题:在分解的过程当中,我们会对子数组进行划分,如果划分得到的q 正好就是我们需要的下标,就直接返回a[q];否则,如果 q 比目标下标小,就递归右子区间,否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间,提高了时间效率。这就是「快速选择」算法。

我们知道快速排序的性能和「划分」出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n−1,每次递归的时候又向 n−1 的集合中递归,这种情况是最坏的,时间代价是 O(n 2)。我们可以引入随机化来加速这个过程,它的时间代价的期望是 O(n),证明过程可以参考「《算法导论》9.2:期望为线性的选择算法」。

方法二:基于堆排序的选择方法

思路和算法

我们也可以使用堆排序来解决这个问题——建立一个大根堆,做 k−1 次删除操作后堆顶元素就是我们要找的答案。在很多语言中,都有优先队列或者堆的的容器可以直接使用,但是在面试中,面试官更倾向于让更面试者自己实现一个堆。所以建议读者掌握这里大根堆的实现方法,在这道题中尤其要搞懂「建堆」、「调整」和「删除」的过程。

Read more

LeetCode[206] 反转链表

方法一:迭代

在遍历链表时,将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

复杂度分析

时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。空间复杂度:O(1)。

方法二:递归

递归版本稍微复杂一些,其关键在于反向工作。假设链表的其余部分已经被反转,现在应该如何反转它前面的部分?

Read more