每日算法题：Day 13
作者：TeddyZhang，公众号：算法工程师之路
Day 13, 机器学习知识点走起~
1
编程题
【剑指Offer】复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路： 第一个思路十分简单，使用一个hash_map来储存这些节点，key与value都是每个节点的地址，这样方便我们在遍历时获取这些节点，但是注意value是新建的节点，虽然其label一样，但地址是不同的！
遍历原来的链表，对hash_map的value中的next和random进行修改，修改后，返回其头节点即可！
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
if(pHead == nullptr)
return nullptr;
unordered_map<RandomListNode*, RandomListNode*> hash_map;
RandomListNode* cur = pHead;
while(cur != nullptr){
RandomListNode* tmp = new RandomListNode(cur->label);
hash_map[cur] = tmp;
cur = cur->next;
}
cur = pHead;
while(cur != nullptr){
hash_map[cur]->next = hash_map[cur->next];
hash_map[cur]->random = hash_map[cur->random];
cur = cur->next;
}
return hash_map[pHead];
}
};
当然，上面的方法虽然好理解，但是使用了额外的辅助空间hash_map，那么有没有不适用额外的空间复杂度的方法去实现呢？
- 把复制的结点链接在原始链表的每一对应结点后面
- 修改那些复制节点的random指针，怎么去寻找呢？其random指向为被复制节点的random指向的节点的next节点！
- 将原链表与copy链表分离，主要就是修改next指针的指向，注意复制链表的最后一个结点的next指针不能跟原链表指向同一个空结点nullptr，next指针要重新赋值nullptr
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
if(pHead == nullptr)
return nullptr;
RandomListNode* cur = pHead;
RandomListNode* pNext = nullptr;
while(cur != nullptr){
pNext = cur->next;
cur->next = new RandomListNode(cur->label);
cur->next->next = pNext;
cur = pNext; // 将每个节点进行拷贝
}
cur = pHead;
// 设置拷贝节点的随机指针
RandomListNode* copyNode = nullptr;
while(cur != nullptr){
pNext = cur->next->next;
copyNode = cur->next; // cur->random->next 就是cur->random的拷贝节点
copyNode->random = ((cur->random != nullptr) ? cur->random->next : nullptr);
cur = pNext;
}
cur = pHead;
RandomListNode* res = pHead->next;
while(cur != nullptr){
pNext = cur->next->next;
copyNode = cur->next;
cur->next = pNext;
copyNode->next = (pNext != nullptr) ? pNext->next : nullptr;
cur = pNext;
}
return res;
}
};
【剑指Offer】二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路： 注意此题目是将一个二叉搜索树转换成排序的双向链表，如果没有其他要求，我们可以直接对这个二叉树进行中序遍历，就可以得到已经排序好的节点，然后组合成一个双向链表，但题目不允许转换成新的节点！
尽管如此，仍然可以使用中序遍历的思路，这时我们需要使用一个指针保存前驱节点pre，首先将pre指向当前节点的left，若pre不为空，则修改pre的right指向当前节点，接着让前驱节点向后移动，也就是指向当前节点cur。
当然后一个思路，将中序遍历改成非递归的版本，这个可以自己尝试~
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void process(TreeNode* cur, TreeNode*& pre){
if(cur == nullptr) return;
process(cur->left, pre);
cur->left = pre;
if(pre) pre->right = cur;
// 如果前驱节点不为空，则将前驱节点的右节点指向当前节点
pre = cur;
process(cur->right, pre);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == nullptr) return nullptr;
TreeNode* pre = nullptr; // 声明指针要进行初始化
process(pRootOfTree, pre);
TreeNode* res = pRootOfTree;
while(res->left){
res = res->left;
}
return res;
}
};2
概念题
【机器学习】模型训练中偏差和方差的功能和作用？
- 偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力（模型拟合能力）；
- 方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响（模型的稳定性）；
- 噪声则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度！
【机器学习】偏差和方差的权衡（过拟合与欠拟合）问题
如上图所示，在模型训练中，模型的拟合能力越来越强，因此bias越来越小，但是方差却越来越大！如下所说：
- 当训练不足时，模型的拟合能力不够（数据的扰动不足以使模型产生显著的变化），此时偏差主导模型的泛化误差；
- 随着训练的进行，模型的拟合能力增强（模型能够学习数据发生的扰动），此时方差逐渐主导模型的泛化误差；
- 当训练充足后，模型的拟合能力过强（数据的轻微扰动都会导致模型产生显著的变化），此时即发生过拟合（训练数据自身的、非全局的特征也被模型学习了）
因此，在模型训练中，我们要使用一些策略和手段来使得模型达到最优的状态（Optimal State）！
【机器学习】对于模型过拟合问题，有哪些措施可以解决呢？
- 数据增强，或者收集更多更具有代表性的数据
- 合适的模型，第一，可以根据数据量的多少选择小模型或者大模型，第二，早停，由于模型训练如果时间太长的话，会使得模型拟合能力过强，从而导致过拟合，因此应该在适当的时间将训练停止，第三，加上正则项即限制权重，使得权重W不会过大，也可以防止过拟合，第四，增加噪声干扰，可以在输入或者权重初始化时加入随机噪声！
- 集成方法，bagging，使用不同部分的数据集进行训练，然后进行投票选择，boosting，综合多个简单模型的结果得到一个靠谱的结果！dropout，实际上在不同阶段训练了不同的网络结构，然后将这些网络形成一个整体！