Archive for the ‘Algorithm’ category

DFS通用解法

May 8th, 2015

最近在刷一些算法题,发现DFS在单链表,二叉树,图,集合的解题比较多,具有一定的通用规律,现在讲通用方法记录下。拿二叉树举例,比如我们需要从根走到叶子节点才能得到一个解,这种类型非常适合是用DFS,再以二维数组举例,我们可以将二维数组当成一个图,进行搜索,在搜索的同事满足一定的匹配等。

一般情况下Wide-FS只要求有一个解,而且需要将整个中间状态存储到内存中,而DFS只存储一条路径,非常时候解决一些问题。

在DFS中我们需要一个收敛条件,也就是合法解。这时我们就需要把这个中间状态保存到最后的结果中。为了加快深搜,我们可以剪枝,常用方式使用状态数组表示,提前return,可以大大加快递归速度。

通用dfs模板:

/**
* dfs 模板.
* @param[in] input 输入数据指针
* @param[out] path 当前路径,也是中间结果,可以是一维数组
* @param[out] result 存放最终结果,二维数组
* @param[inout] cur or gap 标记当前位置或距离目标的距离,或者可以
* 是start end等标记
* @return 路径长度,如果是求路径本身,则不需要返回长度
* 可以返回bool等,依照题目要求来实现。
*/
void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作,修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

这里我举一个例子:列举所有set可能的子集合,比如S=[1,2,3],那么结果是[[3],[2],[1],[1,2,3],[1,3],[2,3],[1,2],[]]
解决这个问题,需要首先按照上面的这种模板构建,首先是这个dfs的input 也就是这个S,中间路径path与S类型相同。结果应该是一个二维数组,也就是vector< vector > result,最后我们需要一个step作为收敛条件。

void dfs(const vector<int> &S, vector<int> &path, vector<vector<int> > &result,int step) {
     if (step == S.size()) {//到达S.size()收敛
           result.push_back(path);
           return;
     }
     //这里没有剪枝
     // 不选S[step]
     subsets(S, path, step + 1, result);
     // 选S[step]
     path.push_back(S[step]);
     subsets(S, path, step + 1, result);
     path.pop_back();
}
 void dfs(vector<int>& nums,vector<int> &path,vector<vector<int>> &result,
                     vector<int>::iterator start){
 
     result.push_back(path);
 
     for(auto i = start;i<nums.end();i++)
     {
          path.push_back(*i);
          dfs(nums,path,result,i+1);
          path.pop_back(); 
     }
 }

深度搜索比较难以理解,层层递归会让我迷失,不过进行断点认真跟踪是可行的。最后跟踪断点结果是:

[]
3
2
2,3
1,
1,3
1,2
1,2,3

还有很多场景,比如二维数组寻路,都会用到上下左右的移动,还要使用flag来标示,具体查看
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/word-search/

priority_queue与heap的使用

April 20th, 2015

1.priority_queue

priority_queue是一个优先队列,下面是他的声明,我们平时可以直接使用下面的方式声明一个优先队列。

priority_queue<int> pq

优先队列内部是一个heap的实现,也就是说默认push到priority_queue中的数据,当我们pop出来的时候,默认是优先级最高的,(数字大的优先级高,数字小的优先级低),这个数据结构默认使用vector作为容器,cmp函数默认使用less作为比较函数。

下面的是一个完整的priority_queue的声明

std::priority_queue
template <class T, class Container = vector<T>,
class Compare = less < typename Container::value_type> > class priority_queue;

 

priority_queue<Type, Container, Functional>
其中Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list。STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果把后面俩个参数缺省的话,优先队列就是大顶堆,队头元素最大。

我们使用的时候和平常queue的方式没有什么太大的却别,最大的区别在于这个cmp应该如何自定义。我们知道cmp是一个函数指针,所以我们可以有两种方式重载cmp函数。

 

struct cmp
{
    bool operator () (int &a, int &b)
    {
        return a > b ;              // 从小到大排序,值 小的 优先级别高
    }
}; 

priority_queue<int,vector<int>,cmp> q;

 

方式1:

struct Time {
    int h;
    int m;
    int s;
};

class CompareTime {
    public:
    bool operator()(Time& t1, Time& t2) // Returns true if t1 is earlier than t2
    {
       if (t1.h < t2.h) return true;
       if (t1.h == t2.h && t1.m < t2.m) return true;
       if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
       return false;
    }
}

这里我们必须保证重载的()函数返回值是bool,上面的重载函数核心就是当t1<t2时候,返回tree,所以得到的也就是从大到小的排列,也是这个数据结构默认的,如果我们想重新实现这个数据结构,改为从小到大排列,那么可以使用下面的方式

方式2:

class CompareTime {
public:
    bool operator()(Time& t1, Time& t2) // t2 has highest prio than t1 if t2 is earlier than t1
    {
       if (t1.h > t2.h) return true;
       if (t2.h == t1.h && t2.m < t1.m) return true;
       if (t2.h == t1.h && t2.m == t1.m && t2.s < t1.s) return true;
       return false;
    }
};

保证第一个大于第二个返回true即可。
上面我们看到在一个class类里面重载()函数,我们也可以在要使用的类里面,使用struct{}方式。

class Solution {
public:
.....
private:
struct cmp {
        bool operator()(ListNode* node1, ListNode* node2) {
            return node1->val > node2->val;
        }
    };
};

在C/C++中,我们可以等同class与struct相似。

2.heap

heap 主要分为push_heappop_heapsort_heapreverse四个函数,我们使用这四个函数使得vector中数据按照heap来排列。

make_heap的两种形式:

template <class RandomAccessIterator>
  void make_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
  void make_heap (RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp );

同样有一个comp函数可以指定以排列顺序,所以priority_queue是基于heap的方式来实现的。

示例代码:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class priority_queue
{
    private:
        vector<int> data;
    public:
        void push( int t ){
            data.push_back(t);
            push_heap( data.begin(), data.end());
        }
        void pop(){
            pop_heap( data.begin(), data.end() );
            data.pop_back();
        }
        int top() { return data.front(); }
        int size() { return data.size(); }
        bool empty() { return data.empty(); }
}; 

int main()
{
    priority_queue test;
    test.push( 3 );
    test.push( 5 );
    test.push( 2 );
    test.push( 4 );

    while( !test.empty() ){
        cout << test.top() << endl;
        test.pop(); }
    return 0;
}

 

参考:

[1] http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html

[2] http://www.cplusplus.com/reference/queue/priority_queue/

[3] http://stackoverflow.com/questions/23529815/how-to-use-stdmake-heap

[4] http://www.cppblog.com/mzty/archive/2005/12/15/1770.html

Recursing with STL

March 31st, 2015

最近使用装有节点值的vector容器的前序遍历与中序遍历去构造一颗Binary Tree。

我们都知道先序遍历的顺序是 :中-左-右,中序遍历的顺序是:左-中-右,后续遍历是左-右-中。

举例:

//         1
//        / \
//       2   5
//      / \   \
//     3   4   6

这棵树的先序遍历:1 2 3 4 5 6 中序遍历: 3 2 4 1 5 6 后续:3 4 2 6 5 1 。

众所周知,已知一个树的先序和中序,或者是中序和后续,便可以构造出一棵树,构造的思路是先序的第一个节点就是根,然后查找这个根在中序中的位置,中序遍历中根的位置的左边就是左子树,后面是右子树。然后递归进入到下一层:先序 2 3 4 中序 3 2 4 ,可以看出先序中2是根,然后查找中序2的位置,就得到 3 是 2 的左子树,4是2的右子树,依次recurse。

下面使用STL的方式构造这棵树:已知vector &preorder, vector &inorder是装有先序和中序的vector容器,使用递归就是设置出一个中间状态,对他进行分析,并且函数的参数必须是每次都可以用减小范围的。

STL中,我们都知道有vector::iterator方式来遍历vector元素值,获取这种iterator有两种方式:1)preorder.begin()获取vector中第一个元素的指针。2)begin(preorder),返回的也是vector第一个指针。他们都可以使用*得到值。

end()比较特殊,它返回的是最后元素的下一个元素,也就是一个越界的元素,直接引用会导致数组越界。

auto pos = find(preorder.begin(),preorder.end(),val) 查找当前val的的节点,返回当前val的指针。
distance(preorder.begin(),pos) 直接返回中开始到pos的距离,不包括pos。

//1 2 3 4 5 6
auto Pos = find(pre_order.begin(),pre_order.end(),4);
auto dis = distance(pre_order.begin(),Pos);
cout << dis << "\n";
cout << *next(pre_order.begin(),dis);

我们发现dis = 3,而next是从1开始的3个元素后的下一个元素,也就是val=4的指针。

我们在定义这种迭代器声明的时候,会发现函数参数非常长

TreeNode *buildTree(vector<int>::iterator inorder_first,vector<int>::iterator inorder_end,
		vector<int>::iterator postorder_first,vector<int>::iterator postorder_end)

我们可以使用模板编程极大地简化声明:

template<typename InputIterator>
TreeNode *buildTree(InputIterator inorder_first,InputIterator inorder_end,
		InputIterator postorder_first,InputIterator postorder_end)
{
	if(postorder_first==postorder_end)
		return NULL;
	if(inorder_first==inorder_end)
		return NULL;
	int val = *prev(postorder_end);
	TreeNode *root = new TreeNode(val);

	auto in_rootPos = find(inorder_first,inorder_end,val);
	auto left_size = distance(inorder_first,in_rootPos);

	root->left = buildTree(inorder_first,next(inorder_first,left_size),postorder_first,
		next(postorder_first,left_size));
	root->right = buildTree(next(inorder_first,left_size+1),inorder_end,next(postorder_first,left_size)
		,prev(postorder_end));

	return root;
}

上面的代码是后序遍历与中序遍历组合成一棵树,先序与中序也是类似的。

 

 

参考:
http://www.cplusplus.com/reference/iterator/begin/?kw=begin
http://www.cplusplus.com/reference/iterator/end/?kw=end
http://www.cplusplus.com/reference/iterator/InputIterator/

数据挖掘—–自己整理的笔记

July 11th, 2014

将近一个月没有更新博客,主要这期间有太多的考试,数据挖掘就是其中的一门比较难的课程,由于一直不敢怎么掉以轻心,总结了好长的笔记来复习。其实在读研期间也曾考虑学习Data Mining方向,虽说不是很擅长,但是通过这门课也算是data mining入了门。

本科时候也学过这门课,那时候主要以计算为主,其中的原理有很多是云里雾里的感觉。这次的学习,使得我从数据的预处理,到关联规则,分类,聚类的算法,有了清晰的了解,并可以通过分析各个算法的优缺点,改进现有某个算法的存在的问题。

比如:

支持向量机( SVM)是 一种具有高准确率的分类方法。但是SVM 处理大型数据元组集时,速度很慢试开发一种可伸缩的算法克服以上困难。
1,先使用层次聚类的CF-tree构造出微小的聚类簇
2. 找出聚类簇的质心代表该聚类,然后使用SVM进行训练,这样可以大大减少数据元组的数量。
3. 找出超平面来划分这些微型聚类簇。
4. 加入新的聚类簇来进行SVM训练
5. 直到没有新的聚类簇加入,分类完毕

又比如:

提升的基本思想:假设你是一位患者,有某某些症状.你选择咨询多位医生,假设你根据医生先前的诊断准确率,对每位医生的诊断赋予一个权重.然后这些加权诊断的组合最为最终的诊断,这就是提升的基本思想.

提高决策归纳准确性的原因:在提升方法中,权重赋予每个训练元组.迭代的学习K个分类器序列,学习得到分类器Mi之后,更新权重,使得其后的分类器Mi+1”更关注” Mi误分类的训练元组,最终提升的分类器M*组合每个个体分类器,其中每个分类器投票的权重是其准确率的函数。可以扩充提升算法,预测连续值。

这个就是分类与聚类的结合,通过这种方式,我们克服了SVM的缺点,为我们所用!

下面贴出我从数据预处理,OLAP,到数据各种分类算法的笔记:

» Read more: 数据挖掘—–自己整理的笔记

从头到尾彻底解析Hash 表算法

October 10th, 2013

十一、从头到尾彻底解析Hash 表算法
作者:July、wuliming、pkuoliver
出处:http://blog.csdn.net/v_JULY_v
说明:本文分为三部分内容,
第一部分为一道百度面试题Top K算法的详解;第二部分为关于Hash表算法的详细阐述;第三部分为打造一个最快的Hash表算法。 » Read more: 从头到尾彻底解析Hash 表算法