Posts Tagged ‘STL’

Combination Sum 思路

June 1st, 2015

最新刷leetcode的题目,发现了Combination Sum题目,这个题目分为I、II、III。难度层层递进,题目就是遍历vector容器,选择出符合target number的sum组合,这个题目的思路可以参考DFS通用解法。我们使用那个DFS模板,首先要构造dfs函数。

一般情况下,我们需要五个参数:结果,原始数据集,中间结果,当前指向的数据,满足target number的值:

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target)

然后我们根据candidates中的数据集,深搜这个数据集的各种可能性,将达成target的path中间结果加入result,按照通用模版

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
              }
}

第一步:收敛也就是target==0
第二步:使用for(),并在循环中剪枝 if(target-candidates[current]<0) return;
第三步:如果通过第二部,也就意味着这个current合格,可以将这个加入到path中,然后继续深度遍历。dfs(result,candidates,path,current,target-candidates[current]);这里的问题是candidates的数据是可重复的,可以多次使用。如果只使用一次的话,也就意味着我们需要sort(),然后需要将上个满足条件的值跳过,也就是II中的nums[i]==nums[i-1]比较Combination Sum II

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target){
		if(!path.empty()&&target==0){
			result.push_back(path);
			return;
		}
		if(current<candidates.size()){
			int tmp = -1;//start from 0 and 1
			for(;current<candidates.size();current++){
				if(candidates[current]==tmp)
					continue;
				if(target-candidates[current]<0)
					return;

				tmp = candidates[current];
				path.push_back(candidates[current]);
				dfs(result,candidates,path,current+1,target-candidates[current]);
				path.pop_back();
			}
		}
	}

 

 

题目:

 

https://leetcode.com/problems/combination-sum/

https://leetcode.com/problems/combination-sum-ii/

https://leetcode.com/problems/combination-sum-iii/

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/