前接初级算法题（上）

链表

链表问题相对容易掌握。 不要忘记 “双指针解法” ，它不仅适用于数组问题，而且还适用于链表问题。

另一种大大简化链接列表问题的方法是 “Dummy node” 节点技巧 ，所谓 Dummy Node 其实就是带头节点的指针。

我们推荐以下题目：反转链表，合并两个有序链表和链接环。

更有额外的挑战，你可以尝试运用 递归 来解决这些问题：反转链表，回文链表和合并两个有序链表。

/*
* 链表部分习题，统一采用不带头结点的单链表结构
* 结构体定义如下
*/
//Definition for singly - linked list.
struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};
1
2
3
4
5
6
7
8
9
10
11
12

3.01 删除链表的结点

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

示例 1：

输入：head = [4, 5, 1, 9], node = 5
输出：[4, 1, 9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

输入：head = [4, 5, 1, 9], node = 1
输出：[4, 5, 9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

// 替换法，测试通过
void deleteNode(ListNode* node) {
	node->val = node->next->val;
	node->next = node->next->next;
}
1
2
3
4
5

3.02 删除链表的倒数第N个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1, 2, 3, 4, 5], n = 2
输出：[1, 2, 3, 5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1, 2], n = 1
输出：[1]

// 方法一快慢指针，测试通过
// 首先建立一个头结点，方便后序编程
ListNode* removeNthFromEnd(ListNode* head, int n) {
	ListNode* dummy = new ListNode(0, head);
	ListNode* slow = dummy;
	ListNode* fast = head;
	for (int i = 0; i < n; ++i)
	{
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	slow->next = slow->next->next;
	ListNode* ans = dummy->next;
	delete dummy;
	return ans;
}
// 方法二两次遍历法，测试通过
// 第一遍得到链表长度，第二遍删除结点
int getlength(ListNode* head)
{
	int count = 0;
	while (head)
	{
		++count;
		head = head->next;
	}
	return count;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
	ListNode* dummy = new ListNode(0, head);
	int length = getlength(head);
	ListNode* ptr = dummy;
	for (int i = 1; i < length - n + 1; ++i)
	{
		ptr = ptr->next;
	}
	ptr->next = ptr->next->next;
	ListNode* ans = dummy->next;
	delete dummy;
	return ans;
}
// 方法三堆栈法，测试通过
// 遍历链表，所有结点入栈，然后根据n值出栈
ListNode* removeNthFromEnd(ListNode* head, int n) {
	ListNode* dummy = new ListNode(0, head);
	stack<ListNode*> ms;
	ListNode* cur = dummy;
	while (cur)
	{
		ms.push(cur);
		cur = cur->next;
	}
	for (int i = 0; i < n; ++i)
	{
		ms.pop();
	}
	ListNode* prev = ms.top();
	prev->next = prev->next->next;
	ListNode* ans = dummy->next;
	delete dummy;
	return ans;
}
// 方法四快慢指针，测试通过
// 不建立头结点，使用了额外的一个指针指向待删除结点的前驱
ListNode* removeNthFromEnd(ListNode* head, int n) {
	ListNode* fast = head, * slow = head, * prev = head;
	for (int i = 0; i < n - 1; ++i)
	{
		if (fast->next != NULL)
		{
			fast = fast->next;
		}
	}
	while (fast->next != NULL)
	{
		prev = slow;
		slow = slow->next;
		fast = fast->next;
	}
	if (slow == head) head = slow->next;
	else prev->next = slow->next;
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

3.03 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]

示例 2：

输入：head = [1, 2]
输出：[2, 1]

示例 3：

输入：head = []
输出：[]

// 方法一迭代法，测试通过
// 这是没有使用头结点的方法，使用了三个指针完成
ListNode* reverseList(ListNode* head) {
	if (head == nullptr) return nullptr;
	ListNode* first = head;
	if (first->next == nullptr) return head;
	ListNode* second = first->next;
	ListNode* third;
	if (second->next != nullptr) third = second->next;
	first->next = nullptr;
	while (third != nullptr)
	{
		second->next = first;
		first = second;
		second = third;
		third = third->next;
	}
	second->next = first;
	first = second;
	return first;
}
// 方法二迭代法，测试通过
// 方法一的改进版本，使用了更少的指针，减少了代码量
ListNode* reverseList(ListNode* head) {
	if (head == nullptr || head->next == nullptr) return head;
	ListNode* p = head;
	head = nullptr;
	while (p != nullptr)
	{
		ListNode* s = p;
		p = p->next;
		s->next = head;
		head = s;
	}
	return head;
}
// 方法三迭代法，测试通过
// 首先构造了头结点，然后按照有头结点的单链表进行逆置
ListNode* reverseList(ListNode* head) {
	ListNode* truehead = new ListNode(-1, head);
	ListNode* p = truehead->next;
	truehead->next = nullptr;
	while (p != nullptr)
	{
		ListNode* s = p;
		p = p->next;
		s->next = truehead->next;
		truehead->next = s;
	}
	return truehead->next;
}
// 方法四递归法，测试通过
// 基本思路是递归进入最后一个结点，然后再回归的时候逆接所有结点。较难理解，不建议采用
ListNode* reverse(ListNode* pre, ListNode* p)
{
	ListNode* tail = nullptr;
	if (p != nullptr)
	{
		tail = reverse(p, p->next);
		p->next = pre;
	}
	else
	{
		tail = pre;
	}
	return tail;
}
ListNode* reverseList(ListNode* head) {
	if (head == nullptr || head->next == nullptr) return head;
	return reverse(nullptr, head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

3.04 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1, 2, 4], l2 = [1, 3, 4]
输出：[1, 1, 2, 3, 4, 4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

// 方法一迭代法，测试通过
// 没有使用额外结点，直接在原链表进行操作，缺点是使用指针较多，代码不简洁
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
	if (list1 == nullptr || list2 == nullptr)
	{
		if (list1 == nullptr) return list2;
		else return list1;
	}
	ListNode* p1 = list1;
	ListNode* p2 = list2;
	ListNode* list3 = p1->val < p2->val ? p1 : p2;
	ListNode* p3 = list3;
	if (list3 == p1) p1 = p1->next;
	else p2 = p2->next;
	while (p1 != nullptr && p2 != nullptr)
	{
		if (p1->val < p2->val)
		{
			p3->next = p1;
			p3 = p1;
			p1 = p1->next;
		}
		else
		{
			p3->next = p2;
			p3 = p2;
			p2 = p2->next;
		}
	}
	if (p1 == nullptr)
	{
		p3->next = p2;
	}
	else
	{
		p3->next = p1;
	}
	return list3;
}
// 方法二迭代法，测试通过
// 继方法一的优化版本，使用了一个额外结点作为开始头结点，然后思路同方法一
// 代码简洁同时易于理解，建议采用
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
	ListNode* mergelist = new ListNode(-1);
	ListNode* prev = mergelist;
	while (list1 != nullptr && list2 != nullptr)
	{
		if (list1->val < list2->val)
		{
			prev->next = list1;
			list1 = list1->next;
		}
		else
		{
			prev->next = list2;
			list2 = list2->next;
		}
		prev = prev->next;
	}
	prev->next = list1 == nullptr ? list2 : list1;
	return mergelist->next;
}
// 方法三递归法，测试通过
// 基本思想如下：
// list1[0] + merge(list1[1:], list2)--list1[0] < list2[0]
// list2[0] + merge(list1, list2[1:])--otherwise
// 也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
// 在此思想的基础上加入边界条件判断，及空结点的情况
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
	if (list1 == nullptr)
	{
		return list2;
	}
	else if (list2 == nullptr)
	{
		return list1;
	}
	else if (list1->val < list2->val)
	{
		list1->next = mergeTwoLists(list1->next, list2);
		return list1;
	}
	else
	{
		list2->next = mergeTwoLists(list1, list2->next);
		return list2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

3.05 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1, 2, 2, 1]
输出：true

示例 2：

输入：head = [1, 2]
输出：false

// 方法一部分反转法，测试通过
// 通过快慢指针找到链表的中点，然后将中点之后的链表反转，前半部分和后半部分进行比较看是否相等
// 注意：调用了之前反转链表的方法
bool isPalindrome(ListNode* head) {
	ListNode* fast = head;
	ListNode* slow = head;
	while (fast != nullptr && fast->next != nullptr)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	slow = reverseList(slow);// 调用 反转链表 方法
	while (slow != nullptr)
	{
		if (slow->val != head->val) return false;
		slow = slow->next;
		head = head->next;
	}
	return true;
}
// 方法二堆栈法，测试通过
// 使用栈后进先出的特性，首先将链表中的元素入栈，然后从链表头部开始依次和栈顶元素进行比较，
// 不需要将链表所有元素再比较一遍，只需要比较前一半元素即可
bool isPalindrome(ListNode* head) {
	stack<ListNode*> stk;
	ListNode* p = head;
	int len = 0;
	while (p != nullptr)
	{
		stk.push(p);
		p = p->next;
		len++;
	}
	len >>= 1;
	for (int i = 0; i < len; ++i)
	{
		if (head->val == stk.top()->val)
		{
			stk.pop();
			head = head->next;
		}
		else return false;
	}
	return true;
}
// 方法三递归法，测试通过
// 基本思路是使用两个指针，一个从前往后走，一个从后往前走，依次比较元素是否相等
// 由于单链表无法直接从后向前遍历，但是利用递归一定会进行回归的特性可以在逻辑上
// 做到从后向前的递归。同时注意，前向指针需要进行外部定义，不受到函数调用栈的影响
ListNode* frontnode;// 外部定义指针
bool recursive(ListNode* currentNode) {
	if (currentNode != nullptr)
	{
		if (!recursive(currentNode->next)) return false;
		if (frontnode->val != currentNode->val) return false;
		frontnode = frontnode->next;
	}
	return true;
}
bool isPalindrome(ListNode* head) {
	frontnode = head;
	return recursive(head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

3.06 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3, 2, 0, -4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1, 2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

// 方法一快慢指针，测试通过
// 理论是如果链表有环那么两个指针一定会相遇。该方法简单省时，建议采用
bool hasCycle(ListNode* head) {
	ListNode* slow = head;
	ListNode* fast = head;
	while (1)
	{
		if (fast == nullptr || fast->next == nullptr) return false;
		fast = fast->next->next;
		slow = slow->next;
		if (slow == fast) break;
	}
	return true;
}
// 方法二哈希表，测试通过
// 将链表结点地址存入哈希表，如果地址出现第二次那么存在环
bool hasCycle(ListNode* head) {
	unordered_map<ListNode*, int> hashmap;
	ListNode* p = head;
	while (p != nullptr)
	{
		++hashmap[p];
		if (hashmap[p] > 1) return true;
		p = p->next;
	}
	return false;
}
// 方法三哈希表，测试通过
// 同方法二，使用了不同的数据结构
bool hasCycle(ListNode* head) {
	unordered_set<ListNode*> hashmap;
	while (head != nullptr)
	{
		if (hashmap.count(head))
		{
			return true;
		}
		hashmap.insert(head);
		head = head->next;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

树

树比链表稍微复杂，因为链表是线性数据结构，而树不是。 树的问题可以由 广度优先搜索 或 深度优先搜索 解决。 在本章节中，我们提供了一个对于练习 广度优先遍历 很好的题目。

我们推荐以下题目：二叉树的最大深度，验证二叉搜索树，二叉树的层次遍历 和 将有序数组转换为二叉搜索树。

/*
* 树形结构习题，数据结构定义如下
*/
//Definition for a binary tree node.
struct TreeNode {
	int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
1
2
3
4
5
6
7
8
9
10
11
12

4.01 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明 : 叶子节点是指没有子节点的节点。

示例：
给定二叉树[3, 9, 20, null, null, 15, 7]，

	 3
	/ \
   9  20
  / \
 15  7
1
2
3
4
5

返回它的最大深度 3 。

// 方法一深度优先法，测试通过
int maxDepth(TreeNode* root) {
	return root == nullptr ? 0 : std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
// 方法二广度优先法，测试通过
// 使用队列结构完成
int maxDepth(TreeNode* root) {
	if (root == nullptr) return 0;
	queue<TreeNode*> qu;
	qu.push(root);
	int ans = 0;
	while (!qu.empty())
	{
		int sz = qu.size();
		while (sz != 0)
		{
			TreeNode* p = qu.front();
			qu.pop();
			if (p->left) qu.push(p->left);
			if (p->right) qu.push(p->right);
			sz -= 1;
		}
		ans += 1;
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4.02 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2, 1, 3]
输出：true

示例 2：

输入：root = [5, 1, 4, null, null, 3, 6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

// 方法一中序遍历法，测试通过
// 由于中序遍历下的二叉搜索树产生的序列是递增的，所以根据该性质，
// 使用数组保存中序遍历下的结果，然后判断数组是否是递增的即可
// 注意：使用了算法库函数is_sorted，并且自定义排序规则
vector<int> vec;
void inorder(TreeNode* root) {
	if (root != nullptr)
	{
		inorder(root->left);
		vec.push_back(root->val);
		inorder(root->right);
	}
}
bool isValidBST(TreeNode* root) {
	inorder(root);
	return std::is_sorted(vec.begin(), vec.end(), [](int a, int b)->bool { return a <= b; });
}
// 方法二中序遍历法，测试通过
// 思想和方法一一样，但是使用了非递归的中序遍历，然后直接在遍历的途中进行大小判断。
// 相较于方法一速度更快，建议采用
bool isValidBST(TreeNode* root) {
	stack<TreeNode*> stack;
	long long inorder = (long long)INT_MIN - 1;

	while (!stack.empty() || root != nullptr) {
		while (root != nullptr) {
			stack.push(root);
			root = root->left;
		}
		root = stack.top();
		stack.pop();
		// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
		if (root->val <= inorder) {
			return false;
		}
		inorder = root->val;
		root = root->right;
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

4.03 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1, 2, 2, 3, 4, 4, 3]
输出：true

示例 2：

输入：root = [1, 2, 2, null, 3, null, 3]
输出：false

// 方法一递归法，测试通过
// 从根结点开始，对称的遍历二叉树的左子树和右子树
bool check(TreeNode* p, TreeNode* q)
{
	if (!p && !q) return true;
	if (!p || !q) return false;
	return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
	return check(root, root);
}
// 方法二迭代法，测试通过
// 使用队列辅助，将对称的每一对结点存入并取出看是否相等
bool check(TreeNode* p, TreeNode* q)
{
	queue<TreeNode*> qu;
	qu.push(p);
	qu.push(q);
	while (!qu.empty())
	{
		p = qu.front();
		qu.pop();
		q = qu.front();
		qu.pop();

		if (!p && !q) continue;
		if ((!p || !q) || (p->val != q->val)) return false;

		qu.push(p->left);
		qu.push(q->right);

		qu.push(p->right);
		qu.push(q->left);
	}
	return true;
}
bool isSymmetric(TreeNode* root) {
	return check(root, root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

4.04 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3, 9, 20, null, null, 15, 7]
输出： [[3], [9, 20], [15, 7]]

示例 2：

输入：root = [1]
输出： [[1]]

示例 3：

输入：root = []
输出：[]

// 队列法，测试通过
// 使用辅助队列完成层序遍历，注意使用curlevelsize变量确定每一层结点数
// 保证二维数组的构建正确
vector<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> ans;
	if (!root) return ans;
	queue<TreeNode*> qu;
	qu.push(root);
	while (!qu.empty())
	{
		int curlevelsize = qu.size();
		ans.push_back(vector<int>());
		for (int i = 1; i <= curlevelsize; ++i)
		{
			TreeNode* p = qu.front();
			qu.pop();
			ans.back().push_back(p->val);
			if (p->left) qu.push(p->left);
			if (p->right) qu.push(p->right);
		}
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4.05 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10, -3, 0, 5, 9]
输出：[0, -3, 9, -10, null, 5]
解释：[0, -10, 5, null, -3, null, 9] 也将被视为正确答案：

示例 2：

输入：nums = [1, 3]
输出：[3, 1]
解释：[1, null, 3] 和[3, 1] 都是高度平衡二叉搜索树。

// 递归法，测试通过
// 升序序列，二分法划分序列，选择中间的结点作为根结点，左右子树进行同样的操作
// 这样可以进行递归完成，这种方法可以保证二叉搜索树是平衡的
TreeNode* helper(vector<int>& nums, int left, int right)
{
	if (left > right) return nullptr;
	int mid = (left + right) / 2;
	TreeNode* root = new TreeNode(nums[mid]);
	root->left = helper(nums, left, mid - 1);
	root->right = helper(nums, mid + 1, right);
	return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
	return helper(nums, 0, nums.size() - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

排序和搜索

本章涵盖了在有序结构中的排序和搜索问题。

我们推荐 第一个错误的版本 这道题，作为介绍一个重要的算法的起始点。

5.01 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
输出：[1, 2, 2, 3, 5, 6]
解释：需要合并[1, 2, 3] 和[2, 5, 6] 。
合并结果是[1, 2, 2, 3, 5, 6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并[1] 和[] 。
合并结果是[1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是[] 和[1] 。
合并结果是[1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

// 方法一直接合并后排序，测试通过
// 由题意可知nums1不可能为空数组，所以可以直接这样写
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
	for (int i = 0; i < n; ++i)
	{
		nums1[m + i] = nums2[i];
	}
	std::sort(nums1.begin(), nums1.end());
}
// 方法二双指针法，测试通过
// 注意最后要将结果再拷贝回nums1
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
	int p1 = 0, p2 = 0;
	int sorted[m + n];
	int cur;
	while (p1 < m || p2 < n) {
		if (p1 == m) {
			cur = nums2[p2++];
		}
		else if (p2 == n) {
			cur = nums1[p1++];
		}
		else if (nums1[p1] < nums2[p2]) {
			cur = nums1[p1++];
		}
		else {
			cur = nums2[p2++];
		}
		sorted[p1 + p2 - 1] = cur;
	}
	for (int i = 0; i != m + n; ++i) {
		nums1[i] = sorted[i];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

5.02 第一个错误版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本[1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

// 二分查找，测试通过
// attention：The API isBadVersion is defined for you.
// 如果当前版本时错误版本，缩减右区域，反之缩减左区域，缩减直至一个点，该点即为答案
bool isBadVersion(int version) { return false; }
int firstBadVersion(int n) {
	int left = 1, right = n;
	while (left < right)
	{
		int mid = (right - left) / 2 + left;
		if (isBadVersion(mid))
		{
			right = mid;
		}
		else
		{
			left = mid + 1;
		}
	}
	return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

动态规划

本章中是一些经典的动态规划面试问题。

我们推荐以下题目：爬楼梯，买卖股票最佳时机 和 最大子序和。

6.01 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

// 方法一递归法，超时
// 基本递归思路是爬第n阶楼梯的策略是爬第n-1和n-2阶楼梯策略之和
// 递归方案存在重复计算的问题，导致了时间复杂度过高
int climbStairs(int n) {
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	else return climbStairs(n - 1) + climbStairs(n - 2);
}
// 方法二非递归方法，测试通过
// 采用了标准的动态规划方案，时间复杂度On
int climbStairs(int n) {
	int* dp = new int[n + 1];
	dp[0] = 1;
	dp[1] = 2;
	for (int i = 2; i < n; ++i)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n - 1];
}
// 方法三非递归优化方法，测试通过
// 不使用数组而只使用两个变量计算答案，时间复杂度On
int climbStairs(int n) {
	int p = 0, q = 0, r = 1;
	for (int i = 1; i <= n; ++i)
	{
		p = q;
		q = r;
		r = p + q;
	}
	return r;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

6.02 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1, 2, 3, 1]
输出：4
解释：偷窃 1 号房屋(金额 = 1) ，然后偷窃 3 号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2, 7, 9, 3, 1]
输出：12
解释：偷窃 1 号房屋(金额 = 2), 偷窃 3 号房屋(金额 = 9)，接着偷窃 5 号房屋(金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

// 方法一动态规划，测试通过
// dp数组中的第n个元素记录n个住户所能偷的最大金额
// 偷第n家住户时，最大金额可能是偷n-1家住户时的金额，或者是偷n-2家住户加上第n家住户的金额之和
int rob(vector<int>& nums) {
	int length = nums.size();
	if (length == 1) return nums[0];
	int* dp = new int[length];
	dp[0] = nums[0];
	dp[1] = std::max(nums[0], nums[1]);
	for (int i = 2; i < length; ++i)
	{
		dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
	}
	return dp[length - 1];
}
// 方法二动态规划优化，测试通过
// 优化了空间复杂度，使用变量代替数组
int rob(vector<int>& nums) {
	int length = nums.size();
	if (length == 1) return nums[0];
	int* dp = new int[length];
	dp[0] = nums[0];
	dp[1] = std::max(nums[0], nums[1]);
	for (int i = 2; i < length; ++i)
	{
		dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
	}
	return dp[length - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

6.03 买卖股票的最佳时机I

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7, 1, 5, 3, 6, 4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6 - 1 = 5 。
注意利润不能是 7 - 1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7, 6, 4, 3, 1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

// 方法一动态规划，测试通过
// 思路请参考题目1.2
int maxProfit_I(vector<int>& prices) {
	int length = prices.size();
	if (length == 1) return 0;
	vector<vector<int> > dp(length, vector<int>(2));
	dp[0][0] = 0;
	dp[0][1] = -prices[0];
	for (int i = 1; i < length; ++i)
	{
		dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
		dp[i][1] = std::max(dp[i - 1][1], -prices[i]);
	}
	return dp[length - 1][0];
}
// 方法二动态规划优化，测试通过
int maxProfit_I(vector<int>& prices) {
	int length = prices.size();
	if (length == 1) return 0;
	int nohold = 0;
	int hold = -prices[0];
	for (int i = 1; i < length; ++i)
	{
		nohold = std::max(nohold, hold + prices[i]);
		hold = std::max(hold, -prices[i]);
	}
	return nohold;
}
// 方法三双指针法，测试通过
// 一个指针记录当前最小值，一个遍历数组，同时计算出最大利润
int maxProfit_I(vector<int>& prices) {
	int length = prices.size();
	if (length == 1) return 0;
	int m = prices[0];
	int maxpro = 0;
	for (int i = 1; i < length; ++i)
	{
		m = std::min(m, prices[i]);
		maxpro = std::max(prices[i] - m, maxpro);
	}
	return maxpro;
}
// 方法四栈，测试通过
// 方法三的另一种实现方式，使用栈来完成
int maxProfit_I(vector<int>& prices) {
	int length = prices.size();
	if (length == 1) return 0;
	stack<int> stk;
	stk.push(prices[0]);
	int maxpro = 0;
	for (int i = 1; i < length; ++i)
	{
		if (stk.top() > prices[i])
		{
			stk.pop();
			stk.push(prices[i]);
		}
		else
		{
			int tmp = prices[i] - stk.top();
			if (tmp > maxpro) maxpro = tmp;
		}
	}
	return maxpro;
}
// 方法五触类旁通法，测试通过
// 请参照题目“最大子序和”。那个题目需要计算最大和，我们这里要计算最大差值
// 所以将最大子序和代码中求和部分改为求差值，并且将dp[0]的初值改为0即可
int maxProfit_I(vector<int>& prices) {
	int length = prices.size();
	vector<int> dp(length);
	dp[0] = 0;
	for (int i = 1; i < length; ++i)
	{
		dp[i] = std::max(0, dp[i - 1]) + prices[i] - prices[i - 1];
	}
	return *max_element(dp.begin(), dp.end());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

6.04 最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5, 4, -1, 7, 8]
输出：23

// 方法一动态规划，测试通过
// 考虑长度为i的序列的最大子序和等于长度i-1的序列的最大子序和加上当前第i个元素
// 但是如果之前的子序和已经小于零，那么应该舍弃之前的和，只考虑当前元素
// 该方案需要On级别的时间复杂度，是可以接受的
int maxSubArray(vector<int>& nums) {
	int length = nums.size();
	vector<int> dp(length);
	dp[0] = nums[0];
	for (int i = 1; i < length; ++i)
	{
		dp[i] = std::max(0, dp[i - 1]) + nums[i];
	}
	return *max_element(dp.begin(), dp.end());
}
// 方法二分治法，测试通过
// 分割原数列，使其拆分为更小的子数列直至长度为1，这样每个子数列的最大子序和很容易求出
// 然后再将所有子序列进行合并，这是该方案的基本思想，可以看出使用递归较为方便
class Status
{
public:
	int lSum, rSum, mSum, iSum;
	Status(int l, int r, int m, int i) :lSum(l), rSum(r), mSum(m), iSum(i) {}
};
Status pushUp(Status l, Status r)
{
	int iSum = l.iSum + r.iSum;
	int lSum = std::max(l.lSum, l.iSum + r.lSum);
	int rSum = std::max(r.rSum, r.iSum + l.rSum);
	int mSum = std::max(std::max(l.mSum, r.mSum), l.rSum + r.lSum);
	return Status(lSum, rSum, mSum, iSum);
}
Status get(vector<int>& nums, int l, int r)
{
	if (l == r)
	{
		return Status(nums[l], nums[l], nums[l], nums[l]);
	}
	int m = (l + r) / 2;
	Status lSub = get(nums, l, m);
	Status rSub = get(nums, m + 1, r);
	return pushUp(lSub, rSub);
}
int maxSubArray(vector<int>& nums) {
	return get(nums, 0, nums.size() - 1).mSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

设计问题

这类问题通常要求你实现一个给定的类的接口，并可能涉及使用一种或多种数据结构。 这些问题对于提高数据结构是很好的练习。

我们推荐以下题目：打乱数组 和 最小栈。

7.01 打乱数组

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class :

Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果

示例 1：

输入
[“Solution”, “shuffle”, “reset”, “shuffle”]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * vector param_1 = obj->reset();
 * vector param_2 = obj->shuffle();
 */

// 方法一调用库函数，测试通过
// reset函数使用一个原数组的副本返回即可
// shuffle使用C++算法库中的random_shuffle函数直接完成
class Solution {
public:
    vector<int> _nums;
    vector<int> _nums_copy;
    Solution(vector<int>& nums)
    :_nums(nums.begin(),nums.end()), _nums_copy(nums.begin(),nums.end())
    {}
    
    vector<int> reset() {
        return _nums_copy;
    }
    
    vector<int> shuffle() {
        std::random_shuffle(_nums.begin(),_nums.end());
        return _nums;
    }
};
// 方法二一般解法，测试通过
// reset函数实现不变
// shuffle配合swap和rand完成，数组中第i个元素将会与前[0...i]随机元素交换次序
class Solution {
public:
	vector<int> _nums;
	vector<int> _nums_copy;
	Solution(vector<int>& nums)
		:_nums(nums.begin(), nums.end()), _nums_copy(nums.begin(), nums.end())
	{}

	vector<int> reset() {
		return _nums_copy;
	}

	vector<int> shuffle() {
		auto n = _nums.end() - _nums.begin();
		for (auto i = n - 1; i > 0; --i)
		{
			std::swap(_nums[i], _nums[std::rand() % (i + 1)]);
		}
		return _nums;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

7.02 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类 :

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
[“MinStack”, “push”, “push”, “push”, “getMin”, “pop”, “top”, “getMin”]
[[], [-2], [0], [-3], [], [], [], []]

输出：
[null, null, null, null, -3, null, 0, -2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); – > 返回 - 3.
minStack.pop();
minStack.top(); – > 返回 0.
minStack.getMin(); – > 返回 - 2.

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

// 方法一双栈法，测试通过
// 其中一个栈行使正常栈的功能，另一个栈的栈顶放置最小值
class MinStack {
public:
	stack<int> stk;
	stack<int> min_stk;
	MinStack() {
		min_stk.push(INT_MAX);
	}

	void push(int val) {
		stk.push(val);
		min_stk.push(std::min(min_stk.top(), val));
	}

	void pop() {
		stk.pop();
		min_stk.pop();
	}

	int top() {
		return stk.top();
	}

	int getMin() {
		return min_stk.top();
	}
};
// 方法二辅助类，测试通过
// 定义一个辅助链表，链表始终进行头插，然后始终对头结点进行操作
// 注意链表的头结点永远存储的是当前最小值
class mylist {
public:
	int _val;
	int _min;
	mylist* next;

	mylist(int val, int min, mylist* p)
		:_val(val), _min(min), next(p)
	{}
};
class MinStack {
public:
	mylist* head;
	MinStack() :head(nullptr)
	{}

	bool is_empty() {
		return head == nullptr;
	}

	void push(int val) {
		if (is_empty())
		{
			head = new mylist(val, val, nullptr);
		}
		else
		{
			mylist* p = new mylist(val, std::min(val, head->_min), head);
			head = p;
		}
	}

	void pop() {
		mylist* p = head;
		head = head->next;
		delete p;
	}

	int top() {
		return head->_val;
	}

	int getMin() {
		return head->_min;
	}
};
// 方法三单栈法，测试通过
// 当压栈的值小于栈中最小值时，先把最小值入栈，然后再把需要压栈的值入栈，最后再更新栈中最小值。
// 如果压栈的值大于栈中最小值的时候，直接压栈
// 出栈的时候如果出栈的值等于最小值，说明最小值已经出栈了，要更新最小值
class MinStack {
public:
	stack<int> stk;
	int min;
	MinStack() {
		min = INT_MAX;
	}

	void push(int val) {
		if (val <= min)
		{
			stk.push(min);
			min = val;
		}
		stk.push(val);
	}

	void pop() {
		if (stk.top() == min)
		{
			stk.pop();
			min = stk.top();
		}
		stk.pop();
	}

	int top() {
		return stk.top();
	}

	int getMin() {
		return min;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

数学

面试中提出的大部分数学问题都不需要超出初中阶段的数学知识。

我们推荐以下题目：计数质数 和 3 的幂 。

8.01 Fizz Buzz

给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：

answer[i] == “FizzBuzz” 如果 i 同时是 3 和 5 的倍数。
answer[i] == “Fizz” 如果 i 是 3 的倍数。
answer[i] == “Buzz” 如果 i 是 5 的倍数。
answer[i] == i （以字符串形式）如果上述条件全不满足。

示例 1：

输入：n = 3
输出：[“1”, “2”, “Fizz”]

示例 2：

输入：n = 5
输出：[“1”, “2”, “Fizz”, “4”, “Buzz”]

示例 3：

输入：n = 15
输出：[“1”, “2”, “Fizz”, “4”, “Buzz”, “Fizz”, “7”, “8”, “Fizz”, “Buzz”, “11”, “Fizz”, “13”, “14”, “FizzBuzz”]

// 暴力法，测试通过
// 直接根据问题条件编写代码即可
vector<string> fizzBuzz(int n) {
	vector<string> ans;
	bool F_flag = false;
	bool B_flag = false;
	for (int i = 1; i <= n; ++i)
	{
		if (i % 3 == 0) F_flag = true;
		if (i % 5 == 0) B_flag = true;
		if (F_flag && !B_flag) ans.push_back("Fizz");
		else if (!F_flag && B_flag) ans.push_back("Buzz");
		else if (F_flag && B_flag) ans.push_back("FizzBuzz");
		else ans.push_back(to_string(i));
		F_flag = false;
		B_flag = false;
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

8.02 计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

// 方法一枚举法，超时
// 遍历每一个小于n的数，然后判断其是否是质数，优化了查询范围
// 时间复杂度大，不建议采用
bool isPrime(int val)
{
	for (int i = 2; i * i <= val; ++i)
	{
		if (val % i == 0) return false;
	}
	return true;
}
int countPrimes(int n) {
	int count = 0;
	for (int i = 2; i < n; ++i)
	{
		count += isPrime(i);
	}
	return count;
}
// 方法二埃氏筛，测试通过
// 对于任意质数x，其倍数一定是合数。由此维护一个标记数组，每遇到一个质数，就将其所有倍数标记为合数
// 为了减少重复标记，遇到质数x时从x*x开始标记而不是2x开始，注意这种方式只是可以相对减少重复标记
// 对于较大数字，i*i有可能超过int值上限，所以需要将其转换为long long长整型保存
int countPrimes(int n) {
	vector<int> isPrime(n, 1);
	int count = 0;
	for (int i = 2; i < n; ++i)
	{
		if (isPrime[i])
		{
			count += 1;
			if ((long long)i * i < n)
			{
				for (int j = i * i; j < n; j += i)
				{
					isPrime[j] = 0;
				}
			}
		}
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

8.03 3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3 ^ x。

// 方法一正向法，测试通过
// 使用3不断相乘，如果相乘结果大于n说明false，如果相等说明true
// 使用长整型避免相乘后的结果越界，代码稍复杂，不建议采用
bool isPowerOfThree(int n) {
	if (n < 0) return false;
	long long sum = 1;
	while (1)
	{
		if (sum == n) return true;
		if (sum * 3 > n) break;
		sum *= 3;
	}
	return false;
}
// 方法二反向法，测试通过
// 如果n可以被3整除，那么除以3，当n不能被3整除退出循环，最后判断n是否为1
// 代码简洁易懂，建议采用
bool isPowerOfThree(int n) {
	if (n <= 0) return false;
	while (n % 3 == 0)
		n /= 3;
	return n == 1;
}
// 方法三取巧法，测试通过
// 根据题目，数字范围是2^31-1，可以算出符合3的幂此方的最大数字是3^19=1162261467,
// 那么直接判断给出的n是否是改数字的约数即可
bool isPowerOfThree(int n) {
	if (n <= 0)return false;
	return 1162261467 % n == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

8.04 罗马数字转整数

罗马数字包含以下七种字符: 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:

输入: s = “III”
输出 : 3

示例 2 :

输入 : s = “IV”
输出 : 4

示例 3 :

输入 : s = “IX”
输出 : 9

示例 4 :

输入 : s = “LVIII”
输出 : 58
解释 : L = 50, V = 5, III = 3.

示例 5 :

输入 : s = “MCMXCIV”
输出 : 1994
解释 : M = 1000, CM = 900, XC = 90, IV = 4.

// 方法一哈希表，测试通过
// 哈希表存储罗马字母与整数的对应关系，然后遍历数组时查表
// 针对特殊组合进行特殊处理即可，代码长度较长，但是思路是清晰的
int romanToInt(string s) {
	unordered_map<char, int> hashmap;
	string alpha = { "IVXLCDM" };
	int value[7] = { 1,5,10,50,100,500,1000 };
	for (int i = 0; i < 7; ++i)
		hashmap[alpha[i]] = value[i];
	int length = s.size();
	int sum = 0;
	for (int i = 0; i < length; ++i)
	{
		if ((s[i] == 'I' || s[i] == 'X' || s[i] == 'C') && i + 1 < length)
		{
			if (s[i] == 'I')
			{
				if (s[i + 1] == 'V')
				{
					++i;
					sum += 4;
					continue;
				}
				else if (s[i + 1] == 'X')
				{
					++i;
					sum += 9;
					continue;
				}
			}
			else if (s[i] == 'X')
			{
				if (s[i + 1] == 'L')
				{
					++i;
					sum += 40;
					continue;
				}
				else if (s[i + 1] == 'C')
				{
					++i;
					sum += 90;
					continue;
				}
			}
			else
			{
				if (s[i + 1] == 'D')
				{
					++i;
					sum += 400;
					continue;
				}
				else if (s[i + 1] == 'M')
				{
					++i;
					sum += 900;
					continue;
				}
			}
		}
		sum += hashmap[s[i]];
	}
	return sum;
}
// 方法二哈希表改，测试通过
// 仍然使用哈希表存储映射关系，判断i和i+1元素大小关系，决定是求和还是作差
// 代码简洁，建议采用
int romanToInt(string s) {
	unordered_map<char, int> hashmap;
	string alpha = { "IVXLCDM" };
	int value[7] = { 1,5,10,50,100,500,1000 };
	for (int i = 0; i < 7; ++i)
		hashmap[alpha[i]] = value[i];
	int length = s.size();
	int sum = 0;
	for (int i = 0; i < length; ++i)
	{
		if (i + 1 < length && hashmap[s[i]] < hashmap[s[i + 1]])
			sum -= hashmap[s[i]];
		else
			sum += hashmap[s[i]];
	}
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

其他

本列表中是一些其他类型的题目。

我们推荐以下题目：位 1 的个数 和 有效的括号。

9.01 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

// 方法一循环检测法，测试通过
// 最简单的方法是使用数字1从第1位一直检查到第32位，同时更新计数值
int hammingWeight(uint32_t n) {
	uint32_t testnum = 1;
	int count = 0;
	for (int i = 0; i < 32; ++i)
	{
		if (n & testnum) count += 1;
		testnum <<= 1;
	}
	return count;
}
// 方法二位运算法，测试通过
// 每次进行n & (n-1)的运算，这样的每一次计算都可以使原数字中的一位二进制数由1反转为0
// 效率高于方法一，建议采用
int hammingWeight(uint32_t n) {
	int count = 0;
	while (n)
	{
		count += 1;
		n &= (n - 1);
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

9.02 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

// 方法一位运算法，测试通过
// 首先两数进行异或，并对异或后的结果计算位1的个数即可
// 注意调用了9.01中的方法hammingWeight()
int hammingDistance(int x, int y) {
	if (x == y) return 0;
	int res = x ^ y;
	return hammingWeight(res);
}
// 方法二循环检测法，测试通过
// 每次循环取出两个数的同一位进行比对，如果不相同就计数值加一，由此计算出结果
int hammingDistance(int x, int y) {
	if (x == y)return 0;
	int count = 0;
	for (int i = 0; i < 32; ++i)
	{
		if ((x & (1 << i)) != (y & (1 << i))) count += 1;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

9.03 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192(00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：n = 11111111111111111111111111111101
输出：3221225471(10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

// 方法一循环替换法，测试通过
// 从左到右遍历每一位，然后从右到左插入，常规方案简洁明了
uint32_t reverseBits(uint32_t n) {
	uint32_t leftbit = 0x80000000;
	uint32_t rightbit = 0x00000001;
	uint32_t res = 0;
	for (int i = 0; i < 32; ++i)
	{
		if ((n & leftbit >> i) != 0) res |= (rightbit << i);
	}
	return res;
}
// 方法二分治法，测试通过
// 对原数字进行分割，先是16位16位分割交换，然后是8位8位分割交换，
// 直到1位1位分割交换，整个数字的二进制位数就进行了颠倒
// 不用进行遍历，分治的思想较为重要，建议采用
uint32_t reverseBits(uint32_t n) {
	n = (n >> 16) | (n << 16);
	n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
	n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
	n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
	n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
	return n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

9.04 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出 : [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

示例 2 :

输入 : numRows = 1
输出 : [[1]]

// 数学法，测试通过
// 构建二维数组，根据性质填入数字即可
vector<vector<int>> generate(int numRows) {
	vector<vector<int>> res;
	for (int i = 1; i <= numRows; ++i)
	{
		res.push_back(vector<int>(i));
	}
	res[0][0] = 1;
	for (int i = 1; i < res.size(); ++i)
	{
		res[i][0] = res[i][i] = 1;
		for (int j = 1; j < res[i].size() - 1; ++j)
		{
			res[i][j] = res[i - 1][j] + res[i - 1][j - 1];
		}
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

9.05 有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false
示例 4：

输入：s = “([)]”
输出：false
示例 5：

输入：s = “{[]}”
输出：true

// 栈，测试通过
// 遇到左括号，将对应的右括号入栈；遇到右括号，若栈不空，比对栈顶元素
// 如果相同则出栈，不同返回false，最后判断栈是否为空
bool isValid(string s) {
	stack<char> stk;
	for (auto c : s)
	{
		if (c == '(') stk.push(')');
		else if (c == '[') stk.push(']');
		else if (c == '{') stk.push('}');
		else if (!stk.empty() && stk.top() == c) stk.pop();
		else return false;
	}
	return stk.empty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

9.06 缺失数字

给定一个包含[0, n] 中 n 个数的数组 nums ，找出[0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3, 0, 1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围[0, 3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0, 1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围[0, 2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围[0, 9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围[0, 1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

// 方法一数学法，测试通过
// 首先对[0,n]范围内所有数字进行求和，然后减去数组中所有数字，那么剩下的数字就是缺失的数字
// 简单易懂，建议采用
int missingNumber(vector<int>& nums) {
	int length = nums.size();
	int sum = (1 + length) * length / 2;
	for (int x : nums)
	{
		sum -= x;
	}
	return sum;
}
// 方法二构造法，测试通过
// 首先将[0,n]的所有数字插入到数组中，这样问题从找没有出现的一个数转化成找仅出现一次的数
// 根据1.5中所述，可以找到那个仅出现一次的数，这样本题也得到了解决
int missingNumber(vector<int>& nums) {
	int length = nums.size();
	for (int i = 0; i <= length; ++i)
	{
		nums.push_back(i);
	}
	int reduce = 0;
	for (auto x : nums)
	{
		reduce ^= x;
	}
	return reduce;
}
// 方法三排序遍历法，测试通过
// 首先将数组排序，然后根据下标比对，如果元素与下标不一致那么这个下标就是缺失的数字
// 如果比对到第n-1个仍未有结果，那么说明缺失的数字是数字n
int missingNumber(vector<int>& nums) {
	int length = nums.size();
	sort(nums.begin(), nums.end());
	for (int i = 0; i < length; ++i)
	{
		if (nums[i] != i) return i;
	}
	return length;
}
// 方法四哈希表，测试通过
// 将数组中所有元素录入哈希表，在哈希表中查找[0,n]所有元素，查不到的那个数就是缺失的数字
int missingNumber(vector<int>& nums) {
	int length = nums.size();
	unordered_set<int> hashtable;
	for (auto x : nums)
	{
		hashtable.insert(x);
	}
	int missing = -1;
	for (int i = 0; i <= length; ++i)
	{
		if (!hashtable.count(i))
		{
			missing = i;
			break;
		}
	}
	return missing;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60