每日算法题：Day 12

算法工程师之路

发布于 2019-08-13 15:45:46

3550

发布于 2019-08-13 15:45:46

文章被收录于专栏：算法工程师之路

作者：TeddyZhang，公众号：算法工程师之路

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

编程题

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

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

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

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

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空间恢复到原来状态，这一操作也叫做回溯法！！！

/*
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;
    }
};

概念题

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

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

numpy代码实现Dropout:

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正则化的区别？为什么可以防止过拟合