图像学-色温、白平衡与色彩恒常性

1. 色温

• 色温这个概念是从黑体辐射来的。
• 根据日常的经验我们可以知道，给一个铁块加热，随着温度升高，铁块开始是暗红色，逐渐变成亮红色，如果能达到炼钢炉里那样的高温，铁融化成铁水，发出耀眼的金黄色光芒。
• 而天文学家也告诉我们，宇宙中的恒星可以看做一个个黑体，随着恒星温度的升高，恒星的颜色也是从红色到黄色，非常高温度的恒星甚至发出偏蓝色的光。

直接渲染了不同温度下黑体辐射的颜色。下图就是渲染出的不同温度黑体的颜色。

​ （黑体辐射的颜色）

Leetcode-547-省份数量

题目描述

• 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

• 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

• 给你一个 n x n 的矩阵isConnected，其中isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而isConnected[i][j] = 0表示二者不直接相连。

• 返回矩阵中 省份 的数量。

示例一 ：

1
2

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

1
2

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

1
2
3
4
5
6
7
8

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

Leetcode-830-较大分组的位置

题目描述

• 在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。

• 例如，在字符串s = "abbxxxxzyy"中，就含有 “a”, “bb”, “xxxx”, “z” 和 “yy” 这样的一些分组。

• 分组可以用区间 [start, end]表示,其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。

• 我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

• 找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

示例 1：

输入：s = "abbxxxxzzy"
输出：[[3,6]]
解释："xxxx" 是一个起始于 3 且终止于 6 的较大分组。

示例 2：

输入：s = "abc"
输出：[]
解释："a","b" 和 "c" 均不是符合要求的较大分组。

示例 3：

输入：s = "abcdddeeeeaabbbcd"
输出：[[3,5],[6,9],[12,14]]
解释：较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

输入：s = "aba"
输出：[]

提示：

• 1 <= s.length <= 1000
• s 仅含小写英文字母

Leetcode-509-斐波那契数

题目描述

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你 n ，请计算 F(n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

Leetcode-205-同构字符串

题目描述

• 给定两个字符串 s 和 t，判断它们是否是同构的。
• 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
• 所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

示例 1:

输入: s = "egg", t = "add"
输出: true

示例 2:

输入: s = "foo", t = "bar"
输出: false

示例 3:

输入: s = "paper", t = "title"
输出: true


说明:
你可以假设 s 和 t 具有相同的长度。

单调栈-合集

以下列出了单调栈的问题，供大家参考。

Leetcode-290-单词规律

题目描述

• 给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

• 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

示例1:

输入: pattern = "abba", str = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", str = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false

示例 4:

输入: pattern = "abba", str = "dog dog dog dog"
输出: false
说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。

​

排序-04-基数排序

Leetcode-376-摆动序列

题目描述

• 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

• 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反,[1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

• 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

示例 1:

输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。

示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

示例 3:

输入: [1,2,3,4,5,6,7,8,9]
输出: 2

进阶:
你能否用 O(n) 时间复杂度完成此题?

Leetcode-649-Dota2 参议院

题目描述

Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

• 禁止一名参议员的权利：

• 参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。

宣布胜利：

如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2游戏中决定改变。输出应该是 Radiant 或 Dire。

1
2
3
4
5

示例 1：

输入："RD"
输出："Radiant"
解释：第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，因此第二个参议员将被跳过因为他没有任何权利。然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人

1
2
3
4
5
6
7
8
9

示例 2：

输入："RDD"
输出："Dire"
解释：
第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利
第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止
第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

提示：

• 给定字符串的长度在 [1, 10,000] 之间.