C++实现简单KNN算法

基本思路(引用自机器学习实战p19)

  1. 计算已知类别数据集中的点与当前点之间的距离;
  2. 按照距离递增次序排序;
  3. 选取与当前点距离最小的k个点;
  4. 确定前k个点所在类别的出现频率;
  5. 返回前k个点出现频率最高的类别作为当前点的预测分类。

继续阅读C++实现简单KNN算法

LeetCode 222 Count Complete Tree Nodes 非递归和递归解法

https://leetcode.com/problems/count-complete-tree-nodes/ 题目描述:求完全树的所有节点个数。

非递归方法,116ms. 比较左右节点的树高,如果左树高,则结果加上右树的节点,指针进入左孩子; 如果左右树高相同,则结果加上左树的节点,指针进入由孩子。

继续阅读LeetCode 222 Count Complete Tree Nodes 非递归和递归解法

Why C++ pow(10, 5) = 9999 ? (double type, FPU, SSE)

The question is coming from Why pow(10,5) = 9,999 in C++ in StackOverflow.

Environment

  • OS: Win8.1, 64bit
  • IDE: Code::Blocks 13.12

Code:

const int num = 10;

    for(int i = 0; i < 5; ++i){
        int res = pow(num, i);
    cout << res << endl;
    }

Wrong result:

1
10
99
1000
9999

Why?

继续阅读Why C++ pow(10, 5) = 9999 ? (double type, FPU, SSE)

百度数据挖掘实习工程师一、二现场面试(深圳)

一面

项目

详细介绍项目。

现场手写代码

  • 字符串反转
  • 快排

Python

  • 如何提高Python的运行效率
  • 写一个简单的正则匹配表达式(将文本中的123.4匹配出来)

机器学习

  • KNN(分类与回归)
  • CART(回归树用平方误差最小化准则,分类树用基尼指数最小化准则)
  • Logistics(推导)
  • GBDT(利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值,拟合一个回归树)
  • 随机森林(Bagging+CART)
  • SVM与随机森林比较
  • 改变随机森林的训练样本数据量,是否会影响到随机森林学习到的模型的复杂度
  • Logistics与随机森林比较
  • GBDT与随机森林比较
  • 自己实现过什么机器学习算法
  • 推荐算法(基于用户的协同过滤,基于内容的协同过滤)
  • 如何做一个新闻推荐

继续阅读百度数据挖掘实习工程师一、二现场面试(深圳)

LeetCode 155 Min Stack 使用一个单链表解法

大家的解法都是使用两个栈,一个正常栈,一个最小栈,当有新的最小值时则同时压入最小栈,当弹出的值等于最小值时则同时弹出最小栈栈顶。时间复杂度为O(1),空间复杂度为O(n+k)(k为最小栈的长度)。

我用单链表A了这道题,单链表表头存放最小值,push时从表头插入,模拟入栈,并比较最小值,随时更新表头的最小值;pop时,弹出第二个节点,若popped的值为最小值,则遍历整个链表,更新新的最小值;通过访问链表第二个节点得到栈顶元素,访问表头得到最小值。push,top,getMin的时间复杂度均为O(1),但pop的时间复杂度为O(n),空间复杂度为O(n),此解法对于内存限制的情况有用。

继续阅读LeetCode 155 Min Stack 使用一个单链表解法