题目参见https://www.acwing.com/activity/content/punch_the_clock/5/，感谢举行这样免费的活动。。
AcWing 13. 找出数组中重复的数字
这道题可以用另开数组的方式来保存次数，自然就很简单，但如果不开数组的情况下，就不太好做,这道题还是没好好理解。。。
截一下大佬的题解：
算法的主要思想是把每个数放到对应的位置上，即让 nums[i] = i，不对的话，就交换顺序。
比如 样例 [2, 3, 5, 4, 3, 2, 6, 7]
我们来模拟一下
5 3 2 4 3 2 6 7 2和5交换,bums[nums[0]]和nums[0]进行交换
2 3 2 4 4 5 6 7 5和2交换
然后发现2所处的位置不对，但目标位置上已经有个2了，表示重复了，就找到重复的数了。
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n=nums.size();
int ans=-1;
for(int i=0;i<n;i++)
{
if(nums[i]<0||nums[i]>=n)
return -1;
}
for(int i=0;i<n;i++)
{
while(nums[nums[i]]!=nums[i])
{
swap(nums[nums[i]],nums[i]);
}
if(nums[i]!=i&&nums[nums[i]]==nums[i])
{
return nums[i];
}
}
return -1;
}
};
AcWing 14. 不修改数组找出重复的数字
14
这道题的要求不用额外空间，就让这道题变得有难度了。
n+1个数放在n个位置，可以使用抽屉原理和分冶来做，题解是用二分来判断每个局部的范围的数是否大于局部的长度，如果大于长度，必然在重复，复杂度O(nlogn)
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n=nums.size();
int l=1;
int r=n-1;
while(l<r)
{
int ans=0;
int mid=(l+r)>>1;
for(int i=0;i<n;i++)
{
if(nums[i]>=l&&nums[i]<=mid)
{
ans++;
}
}
if(ans>mid-l+1)
r=mid;
else
l=mid+1;
}
return l;
}
};
还有个O(n)复杂度的，思维很巧妙，把数组中有重复数字，等价于链表中有环，元素的值代表next指针。。
https://www.acwing.com/solution/acwing/content/1220/
我们可以将数组视为一个（或多个链表），每个元素都是一个节点，元素的下标代表节点地址，元素的值代表next指针，因此，重复的元素意味着两个节点的next指针一样，即指向同一个节点，因此存在环，且环的起点即重复的元素。
链表有环：快慢指针，然后快指针置0，再相同速度一起跑
AcWing 15. 二维数组中的查找
这道题从左下角开始遍历，具有单调性。
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
int n=array.size();
if(n==0)
return 0;
int m=array[0].size();
int tx=n-1;
int ty=0;
while(tx>=0&&ty<m)
{
if(array[tx][ty]<target)
ty++;
else if(array[tx][ty]>target)
tx--;
else
return true;
}
return 0;
}
};
AcWing 16. 替换空格
能用额外的字符串，很裸的题，要求原地代替的话,用的牛客上的例子
class Solution {
public:
void replaceSpace(char *str,int length) {
int count=0;
for(int i=0;i<length;i++)
{
if(str[i]==' ')
count++;
}
for(int i=length-1;i>=0;i--)
{
if(str[i]!=' ')
str[i+2*count]=str[i];
else
{
str[i+2*count]='0';
str[i+2*count-1]='2';
str[i+2*count-2]='%';
count--;
}
}
}
};
AcWing 17. 从尾到头打印链表
反转链表，链表专题写过了
AcWing 18. 重建二叉树
根据先序遍历和中序遍历重建二叉树
这个比较不懂，要记录一下。
/**
* 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:
unordered_map<int,int> pos;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n=preorder.size();
for(int i=0;i<n;i++)
pos[inorder[i]]=i;
return dfs(preorder,0,n-1,0,n-1);
}
TreeNode* dfs(vector<int>&pre, int pl, int pr, int il, int ir)
{
if(pl>pr) return NULL;
int k=pos[pre[pl]]-il;//根节点在中序遍历中的顺序
TreeNode* root= new TreeNode(pre[pl]); //根节点
root->left=dfs(pre,pl+1,pl+k ,il,il+k-1); //前序遍历中后面K个为左，其余为右,中序遍历，根节点左边k个为左，右边为右
root->right=dfs(pre,pl+k+1,pr ,il+k+1,ir);
return root;
}
};
AcWing 19. 二叉树的下一个节点
二叉树题还是不会做，看题解。。中序遍历的下一个节点，当有右孩子的时候，找右子树的最左的节点，当没有右孩子的时候，继续找父亲节点，当节点是父亲节点的左儿子的时候，返回父亲节点。
https://www.acwing.com/solution/acwing/content/714/
代码：
/**
* 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;
}
else
{
while(p->father&&p==p->father->right) p=p->father;
return p->father;
}
}
};
AcWing 20. 用两个栈实现队列
代码如下
https://www.acwing.com/activity/content/code/content/43145/
AcWing21 .斐波那契数列
不用开辟额外数组进行求解
https://www.acwing.com/activity/content/code/content/43118/
acwing:22. 旋转数组的最小数字
O(N)遍历就行
https://www.acwing.com/activity/content/code/content/43148/
题解中有一种可以略快的方法，除了最后一部分，其余可以用二分做，大佬的题解
https://www.acwing.com/solution/AcWing/content/727/
https://www.acwing.com/activity/content/code/content/43118/
acwing: 23. 矩阵中的路径
class Solution {
public:
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
bool hasPath(vector<vector<char>>& matrix, string str) {
int n=matrix.size();
if(n==0)
return 0;
int m=matrix[0].size();
int len=str.size();
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(dfs(matrix,str,i,j,0,len))
return 1;
}
return 0;
}
bool dfs(vector<vector<char>>&matrix,string str,int x,int y,int index,int len)
{
if(matrix[x][y]!=str[index])
return 0;
if(index==len-1)
{
return 1;
}
char mm=matrix[x][y];
matrix[x][y]='!';
for(int i=0;i<4;i++)
{
int tx=dx[i]+x;
int ty=dy[i]+y;
if(tx>=0&&tx<matrix.size()&&ty>=0&&ty<matrix[0].size())
{
if(dfs(matrix,str,tx,ty,index+1,len))
return 1;
}
}
matrix[x][y]=mm;
return 0;
}
};
这道是一道典型的回溯题，回溯题的难点是处理返回值和边界
if(A) return 1和return A的写法要注意，经常写错，
最后的return 0不要忘了。。
做下来，收货还是不小的，继续刷题，进入第二周
网友评论