每日算法题：Day 19
Day 19, 深度学习知识点走起~
1
编程题
【剑指Offer】数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
思路： 首先要清楚这种看似简单的题目，使用直接遍历是可以，但一般不得分，由于题目给出了排序数组，对于排序数组来说，常用的搜索查找方式为二分查找（binary search）。这里有个巧妙的方法，我们并不是去搜索k这个数，而是去搜索k-0.5和k+0.5这两个小数，进而返回待插入的位置！
比如：1 2 2 2 3 4 且k = 2 则，k+0.5会返回3的索引即4，而k-0.5会返回第一个2的索引即1，两者相减得3，即为最后的结果！二分代码如下，只返回begin位置！
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
return biSearch(data, k+0.5) - biSearch(data, k-0.5);
}
private:
int biSearch(vector<int>& data, double num){
int begin = , end = data.size() - ;
while(begin <= end){
int mid = begin + (end - begin) / ;
if(data[mid] < num)
begin = mid + ;
else if(data[mid] > num)
end = mid - ;
}
return begin;
}
};
另外一个思路直接使用STL中的库函数equal_range来获取与某一个值相等的上下边界，十分好用的！
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
auto res = equal_range(data.begin(), data.end(), k);
return res.second - res.first;
}
};
【剑指Offer】二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路： 递归解法：一般和深度有关的我们都可以使用dfs算法，然后使用一个res用于记录深度，每次递归到叶节点，将res和max进行比较，将最大的值存入max变量中，结束递归！这样我们就可以找到每一条路径深度最大的哪一个路径了！
（完整复杂版）
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot == nullptr) return ;
int res = ;
int max = INT_MIN;
dfs(pRoot, res, max);
return max;
}
private:
void dfs(TreeNode* pRoot, int res, int& max){
if(pRoot->left == nullptr && pRoot->left == nullptr){
if(res > max)
max = res;
}
if(pRoot->left != nullptr){
dfs(pRoot->left, res+, max);
}
if(pRoot->right != nullptr){
dfs(pRoot->right, res+, max);
}
}
};
（简化版本）减少了参数变量，并进行了整合，只需要一句话！
class Solution {
public:
int TreeDepth(TreeNode* pRoot){
return pRoot ? max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+ :;
}
};
第二种使用非递归的思路，我们都知道层次遍历，每次都是遍历完上一层才会去下一层遍历。因此，我们可以对层次遍历加以修改！设置一个depth变量，如果遍历完一层，则让depth++。层次遍历需要队列的辅助！
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot == nullptr) return ;
queue<TreeNode*> que;
que.push(pRoot);
int depth = ;
while(!que.empty()){
int size = que.size();
depth++;
while(size--){
TreeNode* tmp = que.front();
que.pop();
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
}
}
return depth;
}
};2
概念题
【深度学习】为什么要引入非线性激励函数
知乎:什么ReLU要好过tanh和sigmoid function
- 使用激活函数的目的是为了向网络中加入非线性因素；加强网络的表示能力，解决线性模型无法解决的问题
- 神经网络的万能近似定理认为主要神经网络具有至少一个非线性隐层，这样只要给定足够数量的神经元，那么就可以以任意精度来近似任何一个从一个有限空间到另一个有限维空间的函数了！
- 如果没有非线性函数，那么不管多少层，整个网络任然是线性的，这也会失去万物近似的性质
【深度学习】ReLU函数的几种变形整理
标准ReLU及其扩展都基于公式：g(z;α)=max(0,z)+α min(0,z)
- 当α=0时，为标准线性整流单元
- 当α=-1时，为绝对值整流单元，g(z)=|z|
- Leaky ReLU，固定α=0.01，即一个很小的值，但不为零
- pReLU，将α作为一个可学习的参数
- maxout单元： 与一般的激活函数h = g(x)，Maxout激活函数相当于加入了一层的激活函数层，包含参数为K个，原来的激活函数一般只有一个α，然后综合起来输出激活值最大的值！如下图所示：
Maxout的优缺点：
- Maxout拟合能力特别强，可以拟合任意的凸函数，并具有ReLU的所有优点，线性和非饱和性！
- 缺点很明显，激活函数参数量大大增加，导致整体参数量剧增！
【深度学习】ReLU和Sigmoid区别和优势对比
- 避免梯度消失 sigmoid函数在输入取绝对值非常大的正值或负值时会出现饱和现象，在图像上表现为变得很平，此时函数会对输入的微小变化不敏感，从而造成梯度消失； ReLU 的导数始终是一个常数，负半区为 0，正半区为1，所以不会发生梯度消失现象
- 减缓过拟合 ReLU 在负半区的输出为 0。一旦神经元的激活值进入负半区，那么该激活值就不会产生梯度/不会被训练，造成了网络的稀疏性，从而导致稀疏激活！ 这有助于减少参数的相互依赖，缓解过拟合问题的发生
- 加速计算 ReLU 的求导不涉及浮点运算，所以速度更快
腾讯云开发者
