云淡峰清

# 算法训练营

# 第一题：两数之和（twoSum）

LeetCode 第1题

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

  • 示例：
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1
2
3
4
5
答案解析 
var twoSum = function(nums, target) {
	let res = {}
	for (let i = 0; i < nums.length; i++) {
		let num = nums[i]
		if (num in res) {
			return [res[num], i]
		} else {
			res[target - num] = i
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

# 第二题： 斐波那契数列

LeetCode 第509题

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

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
1
2

给定 N，计算 F(N)

  • 示例 1：
  输入：2
  输出：1
  解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
1
2
3
  • 示例 2：
  输入：3
  输出：2
  解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
1
2
3
  • 示例 3：
  输入：4
  输出：3
  解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
1
2
3

提示：

  • 0 ≤ N ≤ 30
答案解析 
var fib = function(N) {
	// 方法一：递归
	if (N === 0 || N === 1) {
		return N
	}
	return fib(N - 1) + fib(N - 2)

	// 方法二：递推
	let cache = []
	for (let i = 0; i <= N; i++) {
		if (i === 0 || i === 1) {
			cache[i] = i
		} else {
			cache[i] = cache[i - 1] + cache[i - 2]
		}
	}
	return cache[N]

	// 方法三：通项公式
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 第三题： 有效的括号

LeetCode 第20题

给定一个只包括'('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

  • 1、左括号必须用相同类型的右括号闭合。
  • 2、左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

  • 示例 1:
输入: '()'
输出: true
1
2
  • 示例 2:
输入: '()[]{}'
输出: true
1
2
  • 示例 3:
输入: '(]'
输出: false
1
2
  • 示例 4:
输入: '([)]'
输出: false
1
2
  • 示例 5:
输入: '{[]}'
输出: true
1
2
答案解析 
var isValid = function(s) {
	const map = {
		'(': ')',
		'[': ']',
		'{': '}',
	}
	let stack = []
	for (let i = 0; i < s.length; i++) {
		if (stack.length > s.length / 2) return false

		if (s[i] in map) {
			stack.push(s[i])
		} else if (s[i] !== map[stack.pop()]) {
			return false
		}
	}
	return !stack.length
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 第四个题： 简化路径

LeetCode 第71题

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

  • 示例 1：

输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
1
2
3
4

示例 2：

输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
1
2
3

示例 3：

输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
1
2
3

示例 4：

输入："/a/./b/../../c/"
输出："/c"
1
2

示例 5：

输入："/a/../../b/../c//.//"
输出："/c"
1
2

示例 6：

输入："/a//b////c/d//././/.."
输出："/a/b/c"
1
2
答案解析 
var simplifyPath = function(path) {
	const pathArr = path.split('/').filter(p => p !== '')
	const stack = []
	for (let i = 0; i < pathArr.length; i++) {
		let p = pathArr[i]
		if (p === '..') {
			stack.pop()
		} else if (p !== '.') {
			stack.push(p)
		}
	}
	return '/' + stack.join('/')
}
1
2
3
4
5
6
7
8
9
10
11
12
13

← 前端安全漏洞与防御 →