网站建设 app开发网站,德阳住房和城乡建设局网站,小程序如何开发,长沙制作网站文章目录找出数组中重复的数字不修改数组找出重复的数字二维数组中的查找替换空格从尾到头打印链表重建二叉树二叉树的下一个节点用两个栈实现队列斐波那契数列旋转数组的最小数字矩阵中的路径找出数组中重复的数字
https://www.acwing.com/problem/content/description/14/
…
文章目录找出数组中重复的数字不修改数组找出重复的数字二维数组中的查找替换空格从尾到头打印链表重建二叉树二叉树的下一个节点用两个栈实现队列斐波那契数列旋转数组的最小数字矩阵中的路径找出数组中重复的数字
https://www.acwing.com/problem/content/description/14/
给定一个长度为 n 的整数数组 nums数组中所有的数字都在 0∼n−1 的范围内。数组中某些数字是重复的但不知道有几个数字重复了也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。注意如果某些数字不在 0∼n−1 的范围内或数组中不包含重复数字则返回 -1数据范围
0≤n≤1000
样例
给定 nums [2, 3, 5, 4, 3, 2, 6, 7]。返回 2 或 3。解法一非最优有空间复杂度开销
时间O(n)
空间: O(n)
class Solution {
public:int duplicateInArray(vectorint nums) {unordered_mapint,int cnt;for(auto t : nums){if(t 0 || t nums.size()-1 )return -1;}for(auto t : nums){cnt[t] ;if(cnt[t] 1){return t;}}return -1;}
};解法2无空间复杂度开销
时间O(n)
空间: O(1)
class Solution {
public:int duplicateInArray(vectorint nums) {int n nums.size();for(auto t :nums){if(t 0 ||t n) return -1;}for(int i 0 ;i n;i){if(nums[i] ! i nums[nums[i]] ! nums[i]) // 索引i与nums[i]均不符合,可以是if。因为输入为从前向后钱买你的已经排列好{swap(nums[i],nums[nums[i]]);}if(nums[i] ! i nums[nums[i]] nums[i]) // nums[i]与位置不符合但目标位置符合表示有重复return nums[i];}return -1;}
};不修改数组找出重复的数字
https://www.acwing.com/problem/content/15/
给定一个长度为 n1 的数组nums数组中所有的数均在 1∼n 的范围内其中 n≥1。
请找出数组中任意一个重复的数但不能修改输入的数组。
数据范围
1≤n≤1000
样例
给定 nums [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
思考题如果只能使用 O(1) 的额外空间该怎么做呢思路
二分存在一边的数目大于n/2;
时间复杂度nlogn
class Solution {
public:int duplicateInArray(vectorint nums) {int n nums.size();int l 1, r n - 1; //数字的范围为1 ~ n所以左边为1while(l r){int mid l r 1;int s 0;for(auto t : nums){if(t l t mid)s ;}if(s mid - l 1) r mid;else l mid 1;}return l; }
};二维数组中的查找
https://www.acwing.com/problem/content/16/
在一个二维数组中每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。
请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。
数据范围
二维数组中元素个数范围 [0,1000]
样例
输入数组
[[1,2,8,9][2,4,9,12][4,7,10,13][6,8,11,15]
]
如果输入查找数值为7则返回true
如果输入查找数值为5则返回false。解法1:
时间复杂度: n2
class Solution {
public:bool searchArray(vectorvectorint array, int target) {int raw array.size();if(!raw) return false;int col array[0].size();for(int i 0;i raw;i)for(int j 0;j col;j)if(target array[i][j])return true;return false;}
};解法二
class Solution {
public:bool searchArray(vectorvectorint array, int target) {if(array.empty()) return false;int raw array.size(),col array[0].size();int i 0,j col - 1;while(i raw-1 j 0){if(array[i][j] target) return true;if(array[i][j] target){j--;}else i;}return false;}
};替换空格
https://www.acwing.com/problem/content/17/
请实现一个函数把字符串中的每个空格替换成%20。
数据范围
0≤ 输入字符串的长度 ≤1000。
注意输出字符串的长度可能大于 1000。
样例
输入We are happy.
输出We%20are%20happy.语法题
解法1
定义一个新的变量比在原变量处理更加简单
class Solution {
public:string replaceSpaces(string str) {string res;for(auto x : str){if(x ){res %20;}elseres x;}return res;}
};解法2
在原字符串上进行处理,不需要开辟额外空间
class Solution {
public:string replaceSpaces(string str) {for(int i 0;i str.size();i){if(str[i] ){str.erase(str.begin()i);str.insert(i,%20);}}return str;}
};注意
string erase(int pos, int n npos); //删除从Pos开始的n个字符string insert(int pos, int n, char c); //在指定位置插入n个字符cstring insert(int pos, const string str); //插入字符串
解法3
class Solution {
public:string replaceSpaces(string str) {int index str.find( );while(index ! -1){str.replace(index,1,%);str.insert(index1,20);index str.find( );}return str;}
};int find(const string str, int pos 0) const; //查找str第一次出现位置,从pos开始查找
从尾到头打印链表
https://www.acwing.com/problem/content/18/
输入一个链表的头结点按照 从尾到头 的顺序返回节点的值。
返回的结果用数组存储。
数据范围
0≤ 链表长度 ≤1000。
样例
输入[2, 3, 5]
返回[5, 3, 2]/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vectorint printListReversingly(ListNode* head) {vectorint res;while(head){res.push_back(head-val);head head-next;}// reverse(res.begin(),res.end());return vectorint(res.rbegin(),res.rend());}
};vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素拷贝给本身。reverse(f.begin(), f.end())两个参数需要用首地址和尾地址来指定反转的区域
解法2递归
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vectorint printListReversingly(ListNode* head) {if(!head) return{};auto s printListReversingly(head-next);s.push_back(head-val);return s;}
};重建二叉树
https://www.acwing.com/problem/content/23/
输入一棵二叉树前序遍历和中序遍历的结果请重建该二叉树。
注意:
二叉树中每个节点的值都互不相同
输入的前序遍历和中序遍历一定合法
数据范围
树中节点数量范围 [0,100]。
样例
给定
前序遍历是[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二叉树的下一个节点
https://www.acwing.com/activity/content/problem/content/213/
给定一棵二叉树的其中一个节点请找出中序遍历序列的下一个节点。注意如果给定的节点是中序遍历序列的最后一个则返回空节点;
二叉树一定不为空且给定的节点一定不是空节点
数据范围
树中节点数量 [0,100]。样例
假定二叉树是[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-right){p p-right;while(p-left){p p-left;}return p;}while(p-father p p-father-right ) p p-father;return p-father; }
};用两个栈实现队列
https://www.acwing.com/problem/content/36/
请用栈实现一个队列支持如下四种操作
push(x) – 将元素x插到队尾
pop() – 将队首的元素弹出并返回该元素
peek() – 返回队首元素
empty() – 返回队列是否为空
注意
你只能使用栈的标准操作push to toppeek/pop from top, size 和 is empty
如果你选择的编程语言没有栈的标准库你可以使用list或者deque等模拟栈的操作
输入数据保证合法例如在队列为空时不会进行pop或者peek等操作
数据范围
每组数据操作命令数量 [0,100]。
样例
MyQueue queue new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns falseclass MyQueue {
public:stackint stk,cache;/** Initialize your data structure here. */MyQueue() {}void copy(stackint a,stackint b){while(a.size()){b.push(a.top());a.pop();}}/** Push element x to the back of queue. */void push(int x) {stk.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {copy(stk,cache);int res cache.top();cache.pop();copy(cache,stk);return res;}/** Get the front element. */int peek() {copy(stk,cache);int res cache.top();copy(cache,stk);return res;}/** Returns whether the queue is empty. */bool empty() {return stk.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj MyQueue();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.peek();* bool param_4 obj.empty();*/斐波那契数列
输入一个整数 n 求斐波那契数列的第 n 项。
假定从 0 开始第 0 项为 0。
数据范围
0≤n≤39
样例
输入整数 n5
返回 5class Solution {
public:int Fibonacci(int n) {int a 0,b 1;while(n--){int c a b;a b,b c;}return a;}
};旋转数组的最小数字
https://www.acwing.com/problem/content/20/
把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。
输入一个升序的数组的一个旋转输出旋转数组的最小元素。
例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转该数组的最小值为 1。
数组可能包含重复项。
注意数组内所含元素非负若数组大小为 0请返回 −1。
数据范围
数组长度 [0,90]。
样例
输入nums [2, 2, 2, 0, 1]
输出0解法1
class Solution {
public:int findMin(vectorint nums){int l 0,r nums.size()-1;if(r 0) return -1;while(r 0 nums[r] nums[0]) r--;if(nums[r] nums[0]) return nums[0];while(l r){int mid lr 1;if(nums[mid] nums[0]) r mid;else l mid 1;}return nums[r];// sort(nums.begin(),nums.end());// return nums[0];}
};解法2
class Solution {
public:int findMin(vectorint nums){return nums.empty() ? -1 : *min_element(nums.begin(),nums.end());}
};min_element 和 max_element 头文件: #include algorithm 作用返回容器中最小值和最大值的指针。 *min_element(nums.begin(),nums.end())返回最小值
矩阵中的路径
https://www.acwing.com/problem/content/21/
请设计一个函数用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始每一步可以在矩阵中向左向右向上向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子则之后不能再次进入这个格子。
注意
输入的路径不为空
所有出现的字符均为大写英文字母
数据范围
矩阵中元素的总个数 [0,900]。
路径字符串的总长度 [0,900]。
样例
matrix
[[A,B,C,E],[S,F,C,S],[A,D,E,E]
]
strBCCE , return true
strASAE , return falseclass Solution {
public:bool hasPath(vectorvectorchar matrix, string str) {for(int i 0;i matrix.size();i)for(int j 0;j matrix[i].size();j)if(matrix[i][j] str[0]){if(dfs(matrix,str,0,i,j)) return true;}return false;}bool dfs(vectorvectorchar matrix,string str,int u,int x,int y){if(u str.size()-1 ) return true;char t matrix[x][y];matrix[x][y] *;int dx[4] {-1,0,1,0},dy[4] {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 matrix.size() b 0 b matrix[a].size() str[u1] matrix[a][b])if(dfs(matrix,str,u1,a,b)) return true; }matrix[x][y] t;return false;}
};
