每日算法题：Day 26（深度学习）
Day 26, 深度学习知识点走起~
1
编程题
【剑指Offer】正则表达式匹配
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
思路： 首先我们先使用递归的方法，既然要写递归程序，首先考虑递归的退出条件，第一，如果str和pattern都遍历结束到了'\0'，返回true.第二，如果str没有遍历完，而pattern遍历结束了，则不匹配，返回false。第三，str遍历完了，但pattern没有完，可能存在'*'，需要进行处理，否则返回false.
假如第二个字符是'*'，那么分为两种情况：
- 如果第一个字符和pattern匹配成功（注意'.'的情况），那么下一步分成三个情况： 1.'x* '匹配到一个字符，因此str+1, pattern+2 2.'x* '匹配到多个字符，需要重复判断，因此str+1, pattern不变 3.'x* '匹配到0个字符，str不动，因此，str, pattern+2
- 如果第一个字符和pattern不匹配，直接跳过'x*', pattern+2即可！
其他情况，如果两个字符匹配，str和pattern均向后移动，str+1, pattern+1.
class Solution {
public:
bool match(char* str, char* pattern){
if(str == nullptr || pattern == nullptr){
return false;
}
return matchCore(str, pattern);
}
private:
bool matchCore(char* str, char* pattern){
if(*str == '\0' && *pattern == '\0'){
return true;
}
if(*str != '\0' && *pattern == '\0'){
return false;
}
if(*(pattern+) == '*'){ // 当前字符的下一个字符是'*'
if(*str == *pattern || (*pattern == '.' && *str != '\0')){
return matchCore(str+, pattern+) ||
matchCore(str+, pattern) ||
matchCore(str, pattern+);
}else{
return matchCore(str, pattern+);
}
}
if(*str == *pattern || (*pattern == '.' && *str != '\0')){
return matchCore(str+, pattern+);
}
return false;
}
};
【剑指Offer】表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路： 转自牛课首页答案，思路请看注释！主要是利用标记符号、小数点和是否出现过E这三个标志位来解决！
class Solution {
public:
bool isNumeric(char* str) {
// 标记符号、小数点、e是否出现过
bool sign = false, decimal = false, hasE = false;
for (int i = ; i < strlen(str); i++) {
if (str[i] == 'e' || str[i] == 'E') {
if (i == strlen(str)-1) return false; // e后面一定要接数字
if (hasE) return false; // 不能同时存在两个e
hasE = true;
} else if (str[i] == '+' || str[i] == '-') {
// 第二次出现+-符号，则必须紧接在e之后
if (sign && str[i-1] != 'e' && str[i-1] != 'E') return false;
// 第一次出现+-符号，且不是在字符串开头，则也必须紧接在e之后
if (!sign && i > && str[i-1] != 'e' && str[i-1] != 'E') return false;
sign = true;
} else if (str[i] == '.') {
// e后面不能接小数点，小数点不能出现两次
if (hasE || decimal) return false;
decimal = true;
} else if (str[i] < '0' || str[i] > '9') // 不合法字符
return false;
}
return true;
}
};2
概念题
【深度学习】池化层的作用和类别？
池化层作用： 本质上，是在精简feature map数据量的同时，最大化保留空间信息和特征信息 目的：（a）对feature map及参数进行压缩，起到降维作用； （b）减小过拟合的作用。包括Max pooling 和average pooling； （c）引入不变性，包括平移、旋转、尺度不变性。但CNN的不变性的能力，本质是由卷积性质创造的；
类别：（Pytorch）
- nn.Maxpool2d 最大池化层，通过设置kernel_size, stride, padding进行调整
- nn.Avgpool2d 平均池化层，通过设置kernel_size, stride, padding进行调整
- nn.AdaptiveMaxpool2d 自适应最大池化层，通过一个tuple类型的out_size进行调整，不必手工记录卷积核大小
- nn.AdaptiveAvgpool2d 同上，只不过为平均池化层
【深度学习】感受野的理解以及计算公式
在卷积神经网络CNN中，决定某一层输出结果中一个元素所对应的输入层的区域大小，被称作感受野（Receptive Field）。通俗来说就是卷积层输出的一个点映射到输入矩阵上的区域大小。
对于目标检测或者语义分割来说，感受野的设计是至关重要的，因为目标在图像中的大小不一，且由于深度网络的设计feature map是逐层降低的，因此不同层的感受野不一样，因此获得的特征也大不相同，因此实际中经常会建立金字塔模型用来融合多个卷积层的特征！
具体的计算方法：(自上到下的实现方式)
- RF[i-1] = (RF[i] - 1) * stride[i] - KernelSize （由featuremap计算公式反推而来的，忽略padding的存在）
- RF[i-1] = (RF[i] - 1) * stride[i] - dilation[i] * (KernelSize-1)[i] + 1 (带dilation操作) 其实质就是计算feature map大小的反过程，假设最后一层的fp为1x1，反推到输入层，即为最后一层的感受野！接下来用几个例子展示！
参数顺序依次为：kernel_size, stride, padding 三层网络：[[7, 4, 3], [3, 2, 1], [5, 2, 2]]，且初始感受野RF=1
第一层感受野：(1 - 1) * 2 + 7 = 7 , 即感受野为7 第二层感受野：(自上向下算) (1 - 1) * 2 + 3 = 3 (3 - 1) * 4 + 7 = 15 , 即感受野为15 第三层感受野： (1 - 1) * 2 + 5 = 5 (5 - 1) * 2 + 3 = 11 (11 - 1) * 4 + 7 = 47 , 即感受野为47
【深度学习】感受野计算代码实现！
net = {'net': [[, , , ], [, , , ], [, , , ]]}
def inFromOut(net, layernum): # layernum为计算第几层感受野
RF =
for layer in reversed(range(layernum)): # 从高层开始计算，需要反转
fsize, stride, pad, dilation = net[layer]
RF = ((RF - ) * stride) + dilation*(fsize-1) +
return RF