前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日算法题:Day 12

每日算法题:Day 12

作者头像
算法工程师之路
发布2019-08-13 15:45:46
3550
发布2019-08-13 15:45:46
举报
文章被收录于专栏:算法工程师之路
作者:TeddyZhang,公众号:算法工程师之路

Day 12, 深度学习知识点走起~

1

编程题

【剑指Offer】二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路: 注意题目给出的是二叉搜索树,那么它就有一个很重要的性质:左孩子值<=根的值<=右孩子的值!但题目中说明了任意两个数字都互不相同,说明没有重复数字。

由于给出的是后序遍历,我们就可以知道最后一个数为根节点,并且其左子树的值均小于根节点的值,右子树的值均大于根节点的值。因此我们可以从头遍历,直到找到第一个大于根节点的值,我们就可以得到左右子树划分的边界,其后面所有值都应该大于根节点的值,最后利用分治思想进行递归即可!

代码语言:javascript
复制
class Solution {
public:
    bool process(vector<int> seq, int start, int end){
        if(seq.size() == ) return false;
        int i;   // 左子树的索引
        if (start >= end){
            return true;
        }
        for(i = ;i < end; i++){
            if(seq[i] > seq[end]){
                break;
            }
        }
        for(int j = i;j < end; j++){ // j 为右子树的索引
            if(seq[j] < seq[end]){
                return false;
            }
        }

        return process(seq, start, i-1) && process(seq, i, end-1);
    }

    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size() == )  return false;
        if (sequence.size() == )  return true;
        return process(sequence, , sequence.size());
    }
};

【剑指Offer】二叉树中和为某一数值的路径

输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路: 如果我们用语言表述的话,从头节点开始,走向叶节点,每条路都走一遍,然后判断每个路径的和是不是expectNumber,这就是DFS的思想。由于我们需要记录住每条路径,因此我们必须在每次递归后将trace的状态恢复为原来的状态,这样才可以达到共享trace空间的作用!

递归结束后将trace空间恢复到原来状态,这一操作也叫做回溯法!!!

代码语言:javascript
复制
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:

    void dfs(vector<vector<int>> &res, TreeNode* root, int number, vector<int>& trace){
        trace.push_back(root->val); // 记录当前节点的值
        if(root->left == nullptr && root->right == nullptr){
            if(number == root->val){   // 叶节点且路径之和为expectNumber,结束递归
                res.push_back(trace);
            }
        }else{
            if(root->left){
                dfs(res, root->left, number-root->val, trace);
            }
            if(root->right){
                dfs(res, root->right, number-root->val, trace);
            }
        }
        trace.pop_back();
    }

    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> res;
        vector<int> trace;
        if(root != nullptr){
            dfs(res, root, expectNumber, trace);
            return res;
        }
        return res;
    }
};

2

概念题

【深度学习】解释Dropout的原理和作用,并从底层实现?

Dropout是一种类似于Bagging方法的一种集成方法,可以在提高模型的性能的同时降低过拟合风险,其具体做法是在全连接层每次输出对神经元进行随机丢弃,这样网络模型可以随机变换成很多种形式,但与Bagging方法不同,这里的模型之间不独立,且共享参数。

numpy代码实现Dropout:

代码语言:javascript
复制
import numpy as np

def dropout(X, keep_dim=0.5):
    if(keep_dim <  or keep_dim >= ):
        raise Exception("keep_dim is in [0, 1]")

    if keep_dim == :
        return np.zeros_like(X)
    mask = np.random.uniform(, , X.shape) < keep_dim
    return mask * X / keep_dim

X = np.arange().reshape(, )
print(X)   #[[ 0  1  2  3  4  5  6  7]
           # [ 8  9 10 11 12 13 14 15]]
X = dropout(X)
print(X)  # [[ 0.  0.  4.  0.  0.  0.  0. 14.]
          #  [ 0.  0. 20.  0. 24. 26.  0. 30.]]

注意dropout后由于X中某些值变成了零,因此会导致输出减小,因此我们会将那些不为零的X / keep_dim,以增加最后的输出值!

【深度学习】L1正则化和L2正则化的区别?为什么可以防止过拟合

  • L1正则化是指权重向量W各个元素的绝对值之和
  • L2正则化是指权重向量W中各个元素的平方和
  • L1 正则化可以产生更稀疏的权值矩阵,可以用于特征选择,同时一定程度上防止过拟合
  • L2 正则化主要用于防止模型过拟合

由于在先验知识下,我们都知道过拟合的模型的权重都是比较大的,因此我们在损失函数中加入这种先验知识,限制权重不宜过大,相当于权重惩罚,限制参数的规模!这样就会使得模型具有更强大的泛化能力!

【深度学习】为什么L1正则化会产生大量的稀疏权重矩阵,而L2不会呢?

我们将L1正则的公式绘制成图,在二维情况下就是上面的菱形,假设J为在范数约束下的目标函数,J与L1第一次交点即为最优解,我们可以看到W1权重是0,而W2不为零,在高维情况下就会出现很多顶点,而J与这些顶点相交概率非常大,因此会出现W某一维或者几维为零的情况!因此就成为了稀疏矩阵!

详细文章见:L1和L2正则化

而L2为一个圆形,高维则是超球面,因此第一个交点为[W1, W2],一般不会出现为零的情况,稀疏性的概率就会变得非常小!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-08-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法工程师之路 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 作者:TeddyZhang,公众号:算法工程师之路
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档