AcWing 13. 找出数组中重复的数字
题目
给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；
- 朴素算法是利用hash表，通过扫一遍数组，如果之前出现过重复数字，则判断完成。时间复杂度O(n)，空间复杂度O(n)。
利用本身数字的特性，由于数组长度为n，并且数字范围为0~n-1，因此可以利用数组的坑位当做hash表，每次碰到了数字和坑位不匹配，就把当前数换到对应的坑位上。如果坑位已经有相同元素，则判断完成。由于每个数只会交换一次，因此时间复杂度O(n)，空间复杂度O(1)。
代码
class Solution { public: int duplicateInArray(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; i ++) { if (nums[i] < 0 || nums[i] >= n) { return -1; } } int res = -1; for (int i = 0; i < n; i ++) { // nums[i] != i 判断当前坑位不匹配 // nums[i] != nums[nums[i]] 防止重复交换(死循环) while (nums[i] != i && nums[i] != nums[nums[i]]) { swap(nums[i], nums[nums[i]]); } // 如果第i个元素和当前位置不匹配，并且也无法交换 // 则找到一个重复元素 if (res == -1 && nums[nums[i]] == nums[i] && i != nums[i]) { res = nums[i]; } } return res; } };AcWing 14. 不修改数组找出重复的数字
题目
给定一个长度为n+1 的数组
nums，数组中所有的数均在 1∼n 的范围内，其中n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。 返回 2 或 3。解法
由题意可知，有n+1个数，但是只有n个坑位，因此根据抽屉原理，则必然有重复的数字。
我们该题目可以利用分治的思想，解空间为[1~n]，我们把区间分成[1,2/n]和[2/n + 1, n]，统计区间内的数字个数，通过抽屉原理，可以剔除一半的解空间。该步骤的时间复杂度O(logn)。
统计区间内的数字个数，该步骤的时间复杂度为O(n)，最终算法的时间复杂度为O(nlogn)。代码
class Solution { public: int duplicateInArray(vector<int>& nums) { int n = nums.size(); int left = 1, right = n; while(left < right) { int mid = (left + right) >> 1; int cnt = 0; for (auto c: nums) { if (c >= left && c <= mid) { cnt ++; } } if (cnt > mid - left + 1) { right = mid; } else { left = mid + 1; } } return right; } };AcWing 15. 二维数组中的查找
题目
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。样例
输入数组： [ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ] 如果输入查找数值为7，则返回true， 如果输入查找数值为5，则返回false。解法
- 朴素解法是遍历整个矩阵，时间复杂度是O(n^2)。
- 该矩阵其实是有单调性的，我们可以从右上角开始搜索，如果搜索成功，刚刚好，如果搜索不成功，我们可以根据大小关系剔除一行或者一列。因此最终的时间复杂度为O(n + m)，n为矩阵的行，m为矩阵的列。
代码
class Solution { public: bool searchArray(vector<vector<int>> array, int target) { if (array.empty() || array[0].empty()) { return false; } int n = array.size(), m = array[0].size(); int x = 0, y = m - 1; while(x < n && y >= 0) { if (target == array[x][y]) { return true; } else if (target > array[x][y]) { x ++; } else { y --; } } return false; } };AcWing 17. 从尾到头打印链表
题目
输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。
返回的结果用数组存储。
- 利用递归，时间复杂度O(n)
-
代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: vector<int> ans; void dfs(ListNode* head) { if (!head) { return; } dfs(head->next); ans.push_back(head->val); } vector<int> printListReversingly(ListNode* head) { dfs(head); return ans; } };AcWing 18. 重建二叉树
题目
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
注意:
- 二叉树中每个节点的值都互不相同；
- 输入的前序遍历和中序遍历一定合法；
样例
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]
返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
3
/ \
9 20
/ \
15 7
解法
每次我们都想办法构建某个子树的根节点，根据前序遍历和中序遍历的特点可以知道，前序遍历的遍历顺序为根节点、左子树、右子树，而中序遍历的遍历顺序为左子树、根节点、右子树。
因此我们可以利用当前前序遍历的第一个点，然后构建根节点，然后该节点把中序遍历分成两个部分，再递归创建左子树和右子树。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildsubTree(vector<int>& preorder, vector<int>& inorder, int &pre_idx, int in_left, int in_right) {
TreeNode* root = new TreeNode(preorder[pre_idx]);
int in_idx;
for (in_idx = in_left; in_idx <= in_right; in_idx ++) {
if (preorder[pre_idx] == inorder[in_idx]) {
break;
}
}
pre_idx ++;
if (in_idx > in_left) {
root->left = buildsubTree(preorder, inorder, pre_idx, in_left, in_idx - 1);
}
if (in_right > in_idx) {
root->right = buildsubTree(preorder, inorder, pre_idx, in_idx + 1, in_right);
}
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) {
return NULL;
}
int pre_idx = 0;
return buildsubTree(preorder, inorder, pre_idx, 0, inorder.size() - 1);
}
};
AcWing 19. 二叉树的下一个节点
题目
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。
注意：
- 如果给定的节点是中序遍历序列的最后一个，则返回空节点;
- 二叉树一定不为空，且给定的节点一定不是空节点；
样例
假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。
则应返回值等于3的节点。
解释：该二叉树的结构如下，2的后继节点是3。
2
/ \
1 3
解法
首先要熟悉中序遍历的顺序。左子树、根节点、右子树。
因此，当遍历到一个节点时，该节点的左子树已经遍历完了，因此如果该节点有右儿子节点，我们需要找到右子树中第一个需要遍历的点（即右儿子的左儿子的左儿子….）；如果该节点的右儿子为空，那我们需要回溯到该节点的父节点，如果回溯前节点时父节点的左儿子，则返回该父节点，如果回溯前节点时父节点的右儿子，则继续回溯到无法回溯为止。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode *father;
* TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p) {
if (!p) {
return NULL;
}
// 如果右子树存在，找到右子树中第一个需要遍历的节点
if (p->right) {
p = p->right;
while(p->left) {
p = p->left;
}
return p;
}
// 回溯
while(p->father) {
// 如果回溯前的点是父节点的左子树，返回父节点
if (p->father->left == p) {
return p->father;
} else { // 否则继续回溯
p = p->father;
}
}
return NULL;
}
};
AcWing 20. 用两个栈实现队列
题目
请用栈实现一个队列，支持如下四种操作：
- push(x) – 将元素x插到队尾；
- pop() – 将队首的元素弹出，并返回该元素；
- peek() – 返回队首元素；
- empty() – 返回队列是否为空；
注意：
- 你只能使用栈的标准操作：
push to top，peek/pop from top,size和is empty； - 如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；
- 输入数据保证合法，例如，在队列为空时，不会进行
pop或者peek等操作；
样例
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
解法
首先队列要保证先入先出，因此我们需要把先入栈的元素放到栈顶，一个栈无法实现该要求。
因此，我们把一个栈作为数据栈，另一个栈作为过渡栈，每次添加元素的时候，都先把数据栈中的元素压到过渡栈中，然后把新的数据放到数据栈底部，再把过渡栈的数据一次放回数据栈。
代码
class MyQueue {
public:
stack<int> intermedia, data;
/** Initialize your data structure here. */
MyQueue() {}
/** Push element x to the back of queue. */
void push(int x) {
while(data.size()) {
intermedia.push(data.top());
data.pop();
}
data.push(x);
while(intermedia.size()) {
data.push(intermedia.top());
intermedia.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int t = data.top();
data.pop();
return t;
}
/** Get the front element. */
int peek() {
return data.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return data.empty();
}
};
AcWing 22. 旋转数组的最小数字
题目
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为0，请返回-1。
样例
输入：nums=[2,2,2,0,1]
输出：0
解法
该题目可以用二分来做。由下图所示，旋转后的数组可以根据num[0]来进行划分，前半部分>=num[0]，后半部分<=num[0]，但是这里有一个问题，如果二分过程中，num[mid] == num[0]，我们无法区分应该选择左区间还是右区间，因此我们在二分之前，先把后面的等于num[0]的数去掉，再进行二分即可。
另外值得注意的是边界问题，如果数组没有旋转，最小值为num[0]。如果数组均为一个值，因此消除数字会把所有的数字消除，这样最小值也为num[0]。
代码
class Solution {
public:
int findMin(vector<int>& nums) {
if (nums.size() == 0) {
return -1;
}
int n = nums.size();
int left = 0, right = n - 1;
while(nums[left] == nums[right]) {
right --;
}
if (left > right || nums[right] > nums[left]) {
return nums[left];
}
while(left < right) {
int mid = (left + right) >> 1;
if (nums[mid] < nums[0]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[right];
}
};
AcWing 23. 矩阵中的路径
题目
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
注意：
- 输入的路径不为空；
- 所有出现的字符均为大写英文字母；
样例
matrix=
[
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
str="BCCE" , return "true"
str="ASAE" , return "false"
解法
代码
class Solution {
public:
int n, m;
vector<vector<bool>> st;
bool dfs(vector<vector<char>>& matrix, int x, int y, string &str, int idx) {
if (matrix[x][y] != str[idx]) {
return false;
}
// note: can not use "idx == str.size()"
// last move maybe not success
if (idx == str.size() - 1) {
return true;
}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
for (int i = 0; i < 4; i ++) {
int a = x + dx[i];
int b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b]) {
st[a][b] = true;
if(dfs(matrix, a, b, str, idx + 1)) {
return true;
}
st[a][b] = false;
}
}
return false;
}
bool hasPath(vector<vector<char>>& matrix, string &str) {
if (matrix.empty() || matrix[0].empty()) {
return false;
}
n = matrix.size(), m = matrix[0].size();
st = vector<vector<bool>>(n, vector<bool>(m, false));
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
st[i][j] = true;
if (dfs(matrix, i, j, str, 0)) {
return true;
}
st[i][j] = false;
}
}
return false;
}
};
若有收获，就点个赞吧
0 人点赞
