今天的目标三道剑指offer，一道LeetCode。完成
1.二维数组查找某个数是否存在，数组是从左到右，从上到下依次增大的，可以从右上角和左下角开始查询。以右上角为例。
a:首先处理一下特殊情况，获取一下二维数组的行数，如果二维数组为空直接返回false.
b:再获取列数。从右上角开始查询的话则当前行为0，当前列为最后一列，循环条件就是行不大于最后一行，列不小于第一列。
c:查询过程。如果当前位置的值等于目标值，直接返回true，如果当前位置的值大于目标值，那么最后一列不可能存在目标值，所以可以列--，如果当前位置的值小于目标值，那么第一行不可能存在目标值，所以行++。最后得返回一个false，对应没有查询到目标值的情况。
bool Find(int target, vector<vector<int> > array) {
int n=array.size();
if(n<=0) return false;
int m=array[0].size();
int curr=0,curc=m-1;
while(curr<n&&curc>=0)
{
if(array[curr][curc]==target)
{
return true;
}
else if(array[curr][curc]>target)
{
curc--;
}
else
{
curr++;
}
}
return false;
}
2.替换空格。将字符串中的空格替换成%20.
a:首先两个参数的意义，str是个字符数组，length是此数组的最大的容量。
b.统计实际字符串的长度和空格的个数，替换之后新的字符串的长度等于原始长度+2*空格个数。
c:做两个特殊情况的判定，一个是如果字符串为空，或者字符数组的容量小于等于0，二是如果新字符串的长度大于数组的容量，都直接返回空。
d:准备两个指针，一个指向新字符串的最后一位，一个指向旧字符串的最后一位。如果旧字符串的位置不为空，则直接复制给新字符串当前位置，否则替换成%20.直到旧字符串减为0为止。
void replaceSpace(char *str,int length) {
if(str==nullptr||length<=0)
{
return;
}
int newlength=0;
int spacelength=0;
int strlength=0;
int i=0;
while(str[i]!='\0')
{
if(str[i]==' ')
{
spacelength++;
}
strlength++;
i++;
}
newlength=strlength+2*spacelength;
if(newlength>length)
{
return;
}
i=newlength;
int j=strlength;
while(j>=0&&i>j)
{
if(str[j]!=' ')
{
str[i--]=str[j];
}
else
{
str[i--]='0';
str[i--]='2';
str[i--]='%';
}
j--;
}
}
3.从尾到头打印链表。
第一种，申请栈。（空间复杂度为O(N)）
a:如果栈头为空直接返回一个空数组
b:把链表中的数依次压入栈中，再弹出压入数组里。
vector<int> printListFromTailToHead(ListNode* head) {
stack<int>s;
vector<int>res;
if(!head)
{
return res;
}
ListNode* node=head;
while(node)
{
s.push(node->val);
node=node->next;
}
while(!s.empty())
{
res.push_back(s.top());
s.pop();
}
return res;
}
如果面试不允许申请额外空间，需要先反转链表，再存入数组里，最后记得把链表再反转回去，最好不要改动原始数据。相当于做两道题。
LeetCode
求给定二叉树的最小深度。
第一种：递归。（DFS）
a:首先判断根节点是否为空，为空返回0；
b:进入递归，计算左子树的高度，再计算右子树的高度。
c:左右左右子树高度是否为0，是的话返回l+r+1，这对应二叉树只有一边子树的情况。
d:最后返回左右子树最小值+1.
int run(TreeNode *root) {
if(!root)
return 0;
int l = run(root->left);
int r = run(root->right);
if(l==0 || r==0)
return 1+l+r;
return 1+min(l,r);
}
第二种:非递归（BFS），层次遍历的原理。
a:首先判断根节点是否为空，为空返回0；
b:结果变量初始化为1。根不为空，压入一个队列中。如果队列不为空，计算此时队列的大小（每一层的所有节点数），判断每个节点的左右两个孩子是否为空，都为空直接返回结果。如果不是，那么将改节点压入队列。每一层循环完之后，结果加一。
c:最后队列为空后，返回结果值。
int run(TreeNode *root) {
if(!root)
{
return 0;
}
if(!root->left&&!root->right)
{
return 1;
}
queue<TreeNode *>que;
que.push(root);
int res=1;
while(!que.empty())
{
int size=que.size();
for(int i=0;i<size;i++)
{
TreeNode *node=que.front();
que.pop();
if(!node->left&&!node->right)
{
return res;
}
if(node->left)
{
que.push(node->left);
}
if(node->right)
{
que.push(node->right);
}
}
res+=1;
}
return res;
}转载：https://blog.csdn.net/H19950929/article/details/102485553