每日算法题：Day 27（机器学习）
作者：TeddyZhang，公众号：算法工程师之路
Day 27, 机器学习知识点走起~
1
编程题
【剑指Offer】字符流中第一个不重复的数
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
输出描述: 如果当前字符流没有存在出现一次的字符，返回#字符。
思路： 首先我们建立一个长度为256的数组，由于字符串中每个字符的范围是0~255，因此索引号相当于key, 而次数相当于value，再使用一个string类型记录整个字符串，当遍历完后，我们再次遍历整个字符串，寻找值为1的元素，返回其索引值就行！
char虽然是一个字符，其实质为一个8bit的空间，因此可以储存数字为0-255.
class Solution
{
private:
string str;
int ss[] = {};
public:
//Insert> void Insert(char ch)
{
str += ch;
ss[ch]++;
}
//return the first appearence> char FirstAppearingOnce()
{
int len = str.length();
for(int i = ; i < len;i++){
if(ss[str[i]] == ){
return str[i];
}
}
return '#';
}
};
【剑指Offer】链表的入环节点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路： 第一种思路最好想，也最容易入手，使用一个hash_set，保存访问过的节点地址，再遍历的同时进行搜索，如果搜到了，直接退出循环，返回这个节点即为入环节点，如果没有环，则遍历到nullptr退出，返回nullptr即可！
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead == nullptr || pHead->next == nullptr || pHead->next->next == nullptr){
return nullptr; // 三个节点以下不可能成环
}
unordered_set<ListNode*> set;
ListNode* cur = pHead;
while(cur != nullptr){
if(set.find(cur) == set.end()){
set.insert(cur);
}else{
break;
}
cur = cur->next;
}
return cur;
}
};
另外一个思路是快慢指针，可以做到空间复杂度为O(1)，其具体的数学论证过程就不细讲了，我也没有推导过，具体做法是：设置快慢指针，快指针指向慢指针的next，然后快指针一次走两步，慢指针一次走一步，如果有环结构，那么两个指针会一定重合，此时将一个指针指向头部，两个指针同时走，一次走一步，最终会在环的入口处再次相遇！返回当前节点即可
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead == nullptr || pHead->next == nullptr || pHead->next->next == nullptr){
return nullptr; // 三个节点以下不可能成环
}
ListNode* n1 = pHead->next;
ListNode* n2 = pHead->next->next;
while(n1 != n2){
if(n2->next == nullptr || n2->next->next == nullptr){
return nullptr;
}
n2 = n2->next->next;
n1 = n1->next;
}
n2 = pHead;
while(n1 != n2){
n1 = n1->next;
n2 = n2->next;
}
return n1;
}
}
2
概念题
【机器学习】简述一下K-means算法以及写出其伪代码？
K-means是一种经典的聚类算法，其基本思想是对于一组数据，首先随机找出K个簇中心，然后计算数据集中每个样本与这k个簇中心的距离（欧氏距离或者余弦距离等），然后将距离最小的簇中心分当前的样本，然后通过计算每个簇均值得到新的簇中心，然后一直迭代下去，直到簇中心不再变化或者到达最大迭代次数！
【机器学习】K-means的优缺点？
K-means算法试图通过最小距离准则找到最小的簇，当潜在的簇形状是凸面的，且簇与簇之间区别比较明显以及大小相近，则聚类效果比较明显！因此对于大数据来说，该算法效率很高效，且伸缩性好！
缺点：
- K值的选取不确定，通常做法是多做几次实验，画出对应的损失函数折线图，取最优的K值
- 对初始聚类中心敏感，经常由于初始值的选取原因使得聚类优化到局部最优解，而不是全局最优解，并且对于孤立点和噪声敏感
- 对于特殊分布的数据集不能够给出合理的聚类结果
【机器学习】针对上面K-means算法的缺点如何进行解决呢？
- 针对K取多少，取决于数据的分布，多尝试几个K值，看分成几类更加好解释结果和分析目的。
- 初始K值的选取，通常我们也需要多试几次，但一般初值的选取，尽量使得初始值的距离更加远一些，避免优化到局部最优
- 每个样本到簇中心的距离准则，可以使用不同的度量方式，比如余弦距离，曼哈顿距离，欧氏距离等，以期望达到全局最优
- 由于使用了欧式距离，因此一般需要对数据进行标准化，即将数据按比例缩放到一个区间，这样可以方式离散点的干扰。常用的标准化方法有：min-max标准化，z-score标准化（转换为标准正态分布）
【机器学习】簇中心如何确定，以及质心的迭代会不会一直进行，无法终止？
新的簇中心的计算为：各个维度的平均值所组成的新向量，注意这个新向量不一定为实际的数据点
由于K-means算法利用了误差平方和（SSE）的性质，即每个样本点到所属簇中心的距离的平方和，在优化过程中，由于是一个平方和函数，因此必定可以收敛，因此迭代一定会停下来，但为了防止过度优化，我们会设置一个最大的迭代次数，如果达到这个次数就会自动停止！