原题：
找出数组中重复的数字
给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
代码：
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
for(int i=0;i<nums.size();i++)
{
if(nums[i]<0||nums[i]>=nums.size())
return -1;
}
for(int i=0;i<nums.size();i++)
{
while(nums[i]!=i&&nums[i]!=nums[nums[i]])
{
int temp=nums[i];
nums[i]=nums[temp];
nums[temp]=temp;
}
if(nums[i]!=i&&nums[i]==nums[nums[i]])
return nums[i];
}
return -1;
}
};
思路就是 先看一下有没有不在范围内的元素，如果有 就返回-1
然后我们在看其中的每一个元素 如果他的值不等于他的下标
思路比较简单不多讲了，时间复杂度是 O(n)，额外的空间复杂度是 O(1)。
不修改数组找出重复的数字
给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？
思路
如果不考虑思考题的条件下，只要新建一个unordered_map 然后在依次存放的过程中看是否已经有过改元素并退出即可。但如果考虑该情况下，我们可以使用二分法来解答此题。
二分算法模板
已知数组长度为n+1 切所有的数字均在1~n的范围内 按照抽屉原理，必然有一个数字重复 按照这个思路，我们可以对 1~n的区间进行二分查找
我们把L的值定位1，R的值定位N，然后将所有数据的值按照 [L,mid]和[mid+1，R]两个区间尽心分类，并统计每个区间内数字的个数 应为必然存在某个数字出现了两次，则 这两个区间中必然有一个其中数字的个数大于区间，然后将原区间缩减到该区间，继续执行二分直到找到某个区间长度为1，则数字便为重复出现的数字
具体代码如下：
int duplicateInArray(vector<int>& nums) {
int l=1,r=nums.size()-1;
while(l<r)
{
int mid=(l+r)/2,count=0;
for(int i=0;i< nums.size();i++)
if(nums[i]>=l&&nums[i]<=mid)
count++;
if(count<=mid-l+1)
l=mid+1;
else
r=mid;
}
return l;
}
二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
样例
输入数组：
[
[1,2,8,9]，
[2,4,9,12]，
[4,7,10,13]，
[6,8,11,15]
]
如果输入查找数值为7，则返回true，
如果输入查找数值为5，则返回false。
思路：此题我们可以从右上角往左下角查询，如果改值大于要查找的值，则把行号-1，否则把列号+1
代码如下
bool searchArray(vector<vector<int>> array, int target)
{
if(array.empty()||array[0].empty())
return false;
int i=0,j=array.size()-1;
while(i<array[0].size()&&j>=0)
{
if(array[i][j]==target)
return true;
if(array[i][j]>target)
j--;
else
i++;
}
return false;
}
题目：
请实现一个函数，把字符串中的每个空格替换成"%20"。
你可以假定输入字符串的长度最大是1000。
注意输出字符串的长度可能大于1000。
样例
输入："We are happy."
输出："We%20are%20happy."
string replaceSpaces(string &str) {
string str1="";
string::const_iterator it=str.begin();
while(it!=str.end())
{
if(*it!=' ')
str1+=*it;
else
str1+="%20";
it++;
}
return str1;
}
这个没啥讲的。。
输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。
返回的结果用数组存储。
样例
输入：[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:
vector<int> v;
void AddToList(ListNode* l)
{
if(l==NULL)
{
return;
}
else
AddToList(l->next);
v.push_back(l->val);
}
vector<int> printListReversingly(ListNode* head) {
AddToList(head);
return v;
}
};
类函数
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
vector<int> result;
while(head!=NULL)
{
result.push_back(head->val);
head=head->next;
}
return vector<int>(result.rbegin(),result.rend());
}
};
vector.rbegin 和rend 相当于begin 和End 的翻转
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
注意:
二叉树中每个节点的值都互不相同；
输入的前序遍历和中序遍历一定合法；
样例
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]
返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
题解：
首先我们来看一下先序遍历和中序遍历的遍历规则
先序遍历：
1：根节点->左子树->右子树
2：先序遍历的结果，第0个元素是根节点
3：根节点->所有左子树->所有右子树，子数内所有的值是连续的
例如 实例中的先序遍历结果
[3(根节点) ,9(左子树), 20,15,7(右子树)]
中序遍历:
1：左子树->根节点->右子树
2：根节点的左边必然都是左子树，根节点的右边必然都是右子树
然后通过以上这些原理，结合递归的思想
这是开始时的状况
按照上面的性质，前序遍历的首个元素 为根节点 也就是3 记为r0
r如图，我们可以得出3 是根节点，那么在中序遍历中找到3（因为题目规定数字不会重复出现）所以3左侧的所有成员就是此节点下所有左子树的元素，右边的成员是3所有右子树的元素
此时 我们把左子树单独拿出来看 其中只有元素9，说明9下面没有其他节点，此次结束。 将9记记为l0,并且返回此节点
同理，单独拿出右子树来看：
20位根节点 基座r0 15 和7 分别是左右子树的所有元素，切都没有子节点 所以分别将15 7记为r0l1,r0r1 此时所有均已便利完毕，将r0l1和r0r1设为r1的左右节点
再将l0 r0设为左右节点
推导过程完毕，下面上具体代码
/*
* 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:
vector<int> preOrder,inOrder;
map<int,int> hash_map;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
preOrder = preorder;
inOrder = inorder;
for(int i=0;i<inOrder.size();i++)
hash_map[inOrder[i]]=i;
return dfs(0,preOrder.size()-1,0,inOrder.size()-1);
}
TreeNode* dfs(int preL,int preR,int inL,int inR)
{
if(preL>preR) return nullptr;
int rootPos=hash_map[preOrder[preL]];
TreeNode* root = new TreeNode(preOrder[preL]);
TreeNode* left=dfs(preL+1,preL+rootPos-inL,inL,rootPos-1);
TreeNode* right=dfs(preL+rootPos-inL+1,preR,rootPos+1,inR);
root->left=left;
root->right=right;
return root;
}
};
具体流程位
1：首先看当前集合vec的元素数量是否为0，如果是，则返回nullptr 说明
2：取到当前树的根节点（前序遍历集合中的首个元素）并找到该元素在中序遍历中的下标，rootPos，则 下标在区间[0，rootPos-1]为左子树，[rootPos+1,vec.size()-1]为右子树
3：讲第二部获得的左子树和右子树继续进行上述两部操作
4：用递归的思想先从左右子树开始创建，最后添加到根节点
重点在在于函数dfs
在dfs的四个参数分别代表着 当前进行操作树 前序遍历的起始位置，结束为止 中序遍历的起始位置，结束位置
难点是这两行 里面的参数计算的实际意义
TreeNode* left=dfs(preL+1,preL+rootPos-inL,inL,rootPos-1) TreeNode* right=dfs(preL+rootPos-inL+1,preR,rootPos+1,inR);
这里我们使用具体例子来讲解，求的是被红色圈中的子树这一步的dfs
按照图中左子树的结果，preL 5 preR 5 inL 4 inR 4 rootPos 4
可得出下一次 left： preL 6 preR 5 preL<preR 说明无任何子树返回 nullptr
同理right 也为nullPtr 所以有 if(preL>preR) return nullptr
这道题到此结束，刷题路上第一道碰到的第一道话费时间这么久的题 如果大家有什么问题建议自己跑一遍逻辑推演一下
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。
注意：
如果给定的节点是中序遍历序列的最后一个，则返回空节点;
二叉树一定不为空，且给定的节点一定不是空节点；
样例
假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。
则应返回值等于3的节点。
解释：该二叉树的结构如下，2的后继节点是3。
2
/ \
1 3
这里我们先了解一下中序遍历的性质
如上图的二叉树，中序遍历结果相当于各个元素X周坐标不变，Y周坐标统一之后的排序，如图
我们可以从中发现两个性质
1：如果当前节点有右孩子，那么当前节点的下一个节点为该节点的右孩子 的最左节点（递归查找是否有左孩子）如F 的下一个节点为H
2：如果没有，那么就往上找，找到 p=p->father知道没有父节点或者p->father->left==p
例如D 的下一个节点为F G的没有下一个节点最后查找结果p=F，F没有父节点father为null
上代码
/**
* 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->father->right==p)
p=p->father;
return p->father;
}
};
这道题，，简单粗暴直接上代码就好
class MyQueue {
public:
stack<int> sta,cache;
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
sta.push(x);
}
void copy(stack<int> &a,stack<int> &b)
{
while(a.size())
{
b.push(a.top());
a.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
copy(sta,cache);
int num=cache.top();
cache.pop();
copy(cache,sta);
return num;
}
/** Get the front element. */
int peek() {
copy(sta,cache);
int num=cache.top();
copy(cache,sta);
return num;
}
/** Returns whether the queue is empty. */
bool empty() {
return sta.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();
*/
21. 斐波那契数列
输入一个整数 n ，求斐波那契数列的第 n 项。
假定从0开始，第0项为0。(n<=39)
样例
输入整数 n=5
返回 5
int Fibonacci(int n) {
if(n==0)
return 0;
else if(n==1)
return 1;
else
return Fibonacci(n-1)+Fibonacci(n-2);
}
很经典的一道递归题 代码比较简单但是。。。这只是性能最差的一种，如果是面试的话并不会出彩
具体分析：
在计算 f(n-1) 和f(n-2)的过程中会有大量已经经过计算的结果再次计算，所以将已经计算过得结果填表
下面的是手写伪代码 可能通不过主要看思路
map<int,int>hash_map;
int Fibonacci(int n) {
if(n==0)
return 0;
else if(n==1)
return 1;
if(hash_map[n])
return hash_map[n];
hash_map[n] = Fibonacci(n-1)+Fibonacci(n-2);
return hash_map[n];
}
但后来看大佬讲解发现大佬还有一种方法。。相对简洁
还是伪代码，大概看思路
时间复杂度和上面的一样是O(n)但没有开辟额外空间而且使用非递归算法不用担心爆栈的问题
int f(int n)
{
int a=0,b=1;
while(n--)
{
int c=a+b;
a=b;
b=c;
}
return a;
}
然后放下大佬的扩展阅读
求解斐波那契数列的若干方法
斐波那契数列虽然比较简单，但在此基础上能扩展出很多变形和相关
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为0，请返回-1。
样例
输入：nums=[2,2,2,0,1]
输出：0
先上自己最傻的遍历算法。。。从头到尾
int findMin(vector<int>& nums) {
int res=-1;
for(int i=0;i<nums.size();i++)
if(nums[i]<res||res==-1)
res=nums[i];
return res;
}
时间复杂度是O(n)的算法
然后我们继续分析一下这道题目 先不考虑题目中的连续问题
题目中在旋转之前，数组a0是单调递增的，旋转之后，我们可以把它看做两个新的数组min和max
也就是旋转后 数组变成了 [max,min] 那么寻找最小元素就相当于是寻找min[0]元素
而我们再看max和min的性质
由于原数组是单调递增的，所以如果在没有重复元素的情况下，max中的任意元素必然大于min中的任意元素
如果考虑到存在重复元素的情况下，就会有
如果max[0]==min[size()-1]那么我们从后往前去掉min中所有与max[0]相等的元素，那么就会有和上面相同的结论: max中的任意元素必然大于min中的任意元素
这时候我们就可以用二分来进行考虑
先上代码
int findMin(vector<int>& nums) {
int n=nums.size()-1;
if(n<0)
return -1;
while(nums[n]==nums[0]&&n>0)
n--;
if(nums[n]>=nums[0])
return nums[0];
int l=0,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(nums[mid] < nums[0])
r = mid;
else
l = mid + 1;
}
return nums[r];
}
首先 排除没有元素的情况
其次，max[0]==min[size()-1] 执行这一步操作
然后一步是对特殊情况 如果[max,min]的min元素数量为0，那么就是整个就是单调递增的，直接返回nums[0]
这种情况下，虽然时间负责度还是O(n)但是可以保证，可以保证除去最坏情况其他状况都要比上面的时间负责度更低
矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
注意：
输入的路径不为空；
所有出现的字符均为大写英文字母；
样例
matrix=
[
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]str="BCCE" , return "true"
str="ASAE" , return "false"
这道题目相相对简单，直接暴力搜索所有的路径，代码也相对比较简单，直接递归搜索所有就OK注意的是要把已经搜索过的路径用一个里面没有出现过的符号代替防止搜索时再次重复搜索 失败是将路径擦除
上代码
class Solution {
public:
bool hasPath(vector<vector<char>>& matrix, string str) {
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[i].size();j++)
if(dfs(matrix,str,0,i,j))
return true;
return false;
}
bool dfs(vector<vector<char>> mat,string str,int u,int x,int y)
{
char c=mat[x][y];
if(c!=str[u]) return false;
if(u==str.size()-1) return true;
mat[x][y]='*';
int dx[4]={0,1,0,-1};int dy[4]={1,0,-1,0};
for(int i=0;i<4;i++)
{
int a=dx[i]+x,b=dy[i]+y;
if(a>=0&&a<mat.size()&&b>=0&&b<mat[x].size())
if(dfs(mat,str,u+1,a,b))
return true;
}
mat[x][y]=c;
return false;
}
};
到此为止剑指offer第一周的题目就刷完了，11到题花了大概三天时间吧，难度也不是很大，和群里的大佬们差距还是太大。希望有朝一日能够红黑树快速幂各种数据结构算法谈笑风生
也是自己第一次开始认真刷题，希望能坚持下去。毕业工作一年深深感受到自己基础太差，加油吧。
2019/2/28
