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)

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 使用一个单链表解法

栈和堆的区别,C++ new创建对象

/*
 * 栈和堆的区别:http://blog.csdn.net/hairetz/article/details/4141043
 * C++用new来创建对象和非new来创建对象的区别:http://www.cnblogs.com/GODYCA/archive/2013/01/10/2854777.html
 */

#include <iostream>
using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
 };


int main()
{
    ListNode dummy(0);
    ListNode *tail = &dummy;
    for (int i = 0; i < 5; ++i){
        // 下面两行注释的代码是错误的,它只是在循环中每次定义一个局部变量,存放于栈中相同的位置,会出现node->next = &node的情况,造成自环,而且每一次循环后,这些存储单元会被系统自动释放。
        //ListNode node(i);
        //tail->next = &node;

        // 所以正确的方法是用new,在堆中分配了内存,而堆中内存的分配和释放必须由程序员手动释放。
        tail->next = new ListNode(i);
        tail = tail->next;
    }

    ListNode *p = dummy.next;
    while(p){
        cout << p->val << endl;
        p = p->next;
    }

    return 0;
}