Monday, December 21, 2015

Boost学习（1）： 时间和日期


开篇算是一个小巧玲珑的boost::timer， design类似QTimer,但其实不是很好用，因为里面用的是busy spin, sleep的时候measure会有问题。 而且精度靠的POSIX的平台依赖的精度，所以不觉得有多好用。。。

两个API：
void restart() : 计时开始
double elpased(): 经过时间

还有其他的， 比如progresss_timer, display_timer之类的，也不算是有用。 有一个用的比较多，data_timer库，这个在新工作里面看见他们用来转换database时间，和写log用。但是看了下，反倒好长。。。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <boost/timer.hpp>
#include <iostream>
#include <boost/thread.hpp>
using namespace std;

/*
 * boost/timer testing block
 */

int main()
{
 boost::timer t;
 cout<<"Maximum time:"<<t.elapsed_max()<<endl;
 cout<<"Max resolution:"<<t.elapsed_min()<<endl;
 t.restart();
 boost::this_thread::sleep(boost::posix_time::seconds(5));
 cout<<"timer: "<<t.elapsed()<<endl;
 return 0;
}


date_time:
放一个简单的例子：





 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
  #include "boost/date_time/gregorian/gregorian.hpp"
  #include <iostream>
  #include <string>

  int
  main()
  {

    using namespace boost::gregorian;
    date t1;
    date t2 = from_undelimited_string("20151221");
    date t3 = from_string("2015-12-21");
    date t4(max_date_time);
    std::cout<<t1<<std::endl;
    std::cout<<t2<<std::endl;
    std::cout<<t3<<std::endl;
    std::cout<<t4<<std::endl;

    std::cout<<"Year: "<<t2.year()<<" Month:"<<t2.month().as_enum()<<" Day:"<<t2.day()<<std::endl;
    std::cout<<"The day of the week: "<<t2.day_of_week().as_long_string()<<std::endl;
    std::cout<<"Format output:"<<to_simple_string(t2)<<std::endl;
    std::cout<<"Format output:"<<to_iso_string(t2)<<std::endl;
    std::cout<<"Format output:"<<to_iso_extended_string(t2)<<std::endl;
    if (t1.is_not_a_date())
     std::cout<<t1<<std::endl;
    if (t4.is_special())
     std::cout<<t4<<std::endl;
    return 0;
  }

输出为：
not-a-date-time
2015-Dec-21
2015-Dec-21
9999-Dec-31
Year: 2015 Month:12 Day:21
The day of the week: Monday
Format output:2015-Dec-21
Format output:20151221
Format output:2015-12-21
not-a-date-time

综合一下：
date 可以由工厂函数from_simple_string, from_string, from_undelimited_string,或者直接由constructor构造。
一些比较有用的API 为判断是否特殊，给出日月年，某月某日第几天等等。
输出可以直接由operator<<或者由工厂函数，to_simple_string, to_iso_string, to_iso_extended_string来输出。

此外还有一些数学运算等等。

下面这个例子来表示运算符以及一些其他的固定用法。









 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include "boost/date_time/gregorian/gregorian.hpp"
#include <iostream>
#include <string>

using namespace boost::gregorian;

class CreditCard{
public:
 CreditCard(const std::string& bankName, int recordDay)
   :bankName_(bankName),
    recordDay_(recordDay)
 {
 };
 int calc_free_days(date consume_day = day_clock::local_day()) const
 {
  date billDay(consume_day.year(),consume_day.month(), recordDay_);
  if (consume_day > billDay)
   billDay += months(1);
  return (billDay - consume_day).days() + 20;
 };

 friend bool operator<(const CreditCard& left, const CreditCard& right)
 {
  return left.calc_free_days()<right.calc_free_days();
 }
 std::string bankName_;
 int recordDay_;
};


int main() {
 CreditCard cardA("BOA", 5);
 CreditCard cardB("CapitalOne", 12);
 CreditCard toUse = std::max(cardA,cardB);
 std::cout<< cardA.bankName_ <<std::endl;
}

这个例子是计算信用卡免息日期，免息日期公式为还款日减去消费日期加20. 有两张卡，比较哪张可以用。 用到date_duration.days() 和 += operator等等。

对于精确到小时分钟秒毫秒的对象用time_duration,这个定义在posix_time里。






 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include "boost/date_time/gregorian/gregorian.hpp"
#include <iostream>
#include <string>
#include <boost/date_time/posix_time/posix_time.hpp>

int main() {
 using namespace boost::posix_time;
 boost::posix_time::time_duration dur(1,2,3,4);
 std::cout<<dur<<std::endl;
 std::cout<<"Hour:"<<dur.hours()<<" Min:"<<dur.minutes()
   <<" Second"<<dur.seconds()<<std::endl;
 hours hr(2);
 minutes m(3);
 seconds s(4);
 millisec ms(5);
 time_duration dur2 = hr+m+s+ms;
 std::cout<<dur2<<std::endl;
 std::cout<<dur2 - minutes(4)<<std::endl;
 
 return 0;
}

那么date和time_duration合起来就算是一个完整的时间点了。。。






 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include "boost/date_time/gregorian/gregorian.hpp"
#include <iostream>
#include <string>
#include <boost/date_time/posix_time/posix_time.hpp>

int main() {
 using namespace boost::gregorian;
 boost::posix_time::ptime p = boost::posix_time::time_from_string("2015-12-21 02:33:25.1341");
 std::cout<<p<<std::endl;
 std::cout<<p.date()<<std::endl;
 std::cout<<p.time_of_day()<<std::endl;
 std::cout<<p+years(2)+boost::posix_time::minutes(25)<<std::endl;
 boost::posix_time::ptime p2 = boost::posix_time::microsec_clock::universal_time();
 std::cout<<p2<<std::endl;
 std::cout<<p2-p<<std::endl;
 return 0;
}
Posted by at No comments:

Boost 学习 （开篇）

新工作要用到太多的boost了，以前习惯拿QT里面的库来用，觉得也将就。 什么QHashTable --> boost::unordered_map, QVariant --> boost::any, QThread -->boost::thread这些都差不多的。 其实都是为了跨平台和封装。 新工作里面用到了大量的boost， 比如用boost的binidng和functor来模拟反射，所以很恶心，但是还是蛮实用。 以前自己工作中用到过boost.python这个模块，觉得很好用。后面我会挑自己喜欢的一些内容，做一下笔记。
Posted by at No comments:

Saturday, August 22, 2015

LintCode(16) Permutations II

Given a list of numbers with duplicate number in it. Find all unique permutations.
Have you met this question in a real interview? 
Yes
Example
For numbers [1,2,2] the unique permutations are:
[
    [1,2,2],
    [2,1,2],
    [2,2,1]
]

Challenge
Do it without recursion.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int> > permuteUnique(vector<int> &nums) {
        // write your code here
        vector<vector<int>> result;
        vector<int> solution;
        if (nums.empty())
            return result;
        vector<bool> visited(nums.size(),false);
        sort(nums.begin(),nums.end());
        dfs(nums,result,solution, visited);
        return result;
    }
    
    void dfs(vector<int>& nums, vector<vector<int>>&result, vector<int>& solution, vector<bool>& visited){
        if (solution.size()==nums.size()){
            result.push_back(solution);
            return;
        }
        for (int i=0; i<nums.size(); i++){
            if (visited[i])
                continue;
            visited[i]=true;
            solution.push_back(nums[i]);
            dfs(nums,result, solution, visited);
            solution.pop_back();
            visited[i]=false;
            while(nums[i]==nums[i+1])
                i++;
        }
    }
};
Posted by at No comments:
Labels:

LintCode(15) Permutations

Given a list of numbers, return all possible permutations.
Have you met this question in a real interview? 
Yes
Example
For nums = [1,2,3], the permutations are:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Challenge
Do it without recursion.


没啥好说的。。。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int> > permute(vector<int> nums) {
        // write your code here
        vector<vector<int>> result;
        vector<int> solution;
        if (nums.size()==0)
            return result;
        sort(nums.begin(), nums.end());
        vector<bool> visited(nums.size(), false);
        dfs(nums,result,solution, visited);
        return result;
    }
    
    void dfs(vector<int>& nums, vector<vector<int>>& result, vector<int>& solution, vector<bool>& visited){
        if (solution.size()==nums.size()){
            result.push_back(solution);
            return;
        }
        for (int i=0; i<nums.size(); i++){
            if (visited[i])
                continue;
            visited[i]=true;
            solution.push_back(nums[i]);
            dfs(nums,result, solution, visited);
            visited[i]=false;
            solution.pop_back();
        }
    }
};
Posted by at No comments:
Labels:

LintCode(18) Subsets II

Given a list of numbers that may has duplicate numbers, return all possible subsets
Have you met this question in a real interview? 
Yes
Example
If S = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Note
Each element in a subset must be in non-descending order.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.

画一画就知道了，每次遍历的时候只取出第一个有重复的数字就是了。。。所以加了个剪枝。。。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsetsWithDup(const vector<int> &S) {
        // write your code here
        vector<vector<int>> result;
        vector<int> solution;
        vector<int> input(S.begin(),S.end());
        sort(input.begin(),input.end());
        dfs(result, solution, input, 0);
        return result;
    }
    
    void dfs(vector<vector<int>>& result, vector<int>& solution, vector<int>& input, int ind){
        result.push_back(solution);
        if(solution.size()==input.size())
            return;
        for (int i= ind; i<input.size(); i++){
            if (i!=ind && input[i]==input[i-1])
                continue;
            solution.push_back(input[i]);
            dfs(result, solution, input, i+1);
            solution.pop_back();
        }
    }
};
Posted by at No comments:
Labels:

LintCode(17) Subsets

Given a set of distinct integers, return all possible subsets.
Have you met this question in a real interview? 
Yes
Example
If S = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Note
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

经典的回溯，没啥好说的，直接贴答案吧。。。看不懂自己画个图就知道了


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsets(vector<int> &nums) {
     // write your code here
     vector<vector<int>> result;
     vector<int> solution;
     sort(nums.begin(),nums.end());
     dfs(nums,result,solution, 0);
     return result;
    }
    
    void dfs(vector<int>& nums, vector<vector<int>>& result, vector<int>& solution,int ind){
        result.push_back(solution);
        if (solution.size()==nums.size())
            return;
        for (int i=ind; i<nums.size(); i++){
            solution.push_back(nums[i]);
            dfs(nums,result,solution,i+1);
            solution.pop_back();
        }
    }
};
Posted by at No comments:
Labels:

LintCode(34) N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
Have you met this question in a real interview? 
Yes

Example
For n=4, there are 2 distinct solutions.

承接上题，变了个花样。。。不过可以看出这种题目的规律。。。其实很羞愧的一直在想dp的事情，貌似dp是解不出的。。。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    /**
     * Calculate the total number of distinct N-Queen solutions.
     * @param n: The number of queens.
     * @return: The total number of distinct solutions.
     */
    int totalNQueens(int n) {
        // write your code here
        if (n==0)
            return 0;
        vector<int> solution;
        int res=0;
        dfs(solution, res, n);
    
        return res;
    }
    
    void dfs(vector<int>& solution, int& res, int n){
        if (solution.size()==n)
            res++;
        for (int i=0; i<n; i++){
            if (!isValid(solution, i))
                continue;
            solution.push_back(i);
            dfs(solution, res, n);
            solution.pop_back();
        }
    }
    
    bool isValid(vector<int>& solution, int ind){
        if (solution.empty())
            return true;
        int n=solution.size();
        for (int i=0; i<n; i++){
            if (solution[i]==ind)
                return false;
            if (solution[i]+i==ind+n)
                return false;
            if (i-solution[i] == n-ind)
                return false;
        }
        return true;
    }
    
};
Posted by at No comments:
Labels:

LintCode(33) N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
Have you met this question in a real interview? 
Yes
Example
There exist two distinct solutions to the 4-queens puzzle:
[
    [".Q..", // Solution 1
     "...Q",
     "Q...",
     "..Q."],
    ["..Q.", // Solution 2
     "Q...",
     "...Q",
     ".Q.."]
]

Challenge
Can you do it without recursion?

基本算是暴力搜索了，剪枝的部分在于判断是不是一个合适的解，知道形成一个完整解之后，build string然后push到容器里。 本质是DFS， 加一点判断对角线的下三滥trick， 所以很无聊


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    vector<vector<string> > solveNQueens(int n) {
        // write your code here
        vector<vector<string>> result;
        vector<int> solution;
        if (n==0)
            return result;
        helper(result, solution, n);
        return result;
    }
    
    void helper(vector<vector<string>>& result, vector<int>& solution, int n){
        if (solution.size()==n){
            build_result(result, solution);
            return;
        }
        for (int i = 0; i<n; i++){
            if (!isValidSolution(solution, i))
                continue;
            solution.push_back(i);
            helper(result, solution, n);
            solution.pop_back();
        }
    }
    
    void build_result(vector<vector<string>>& result,const vector<int>& solution){
        int n=solution.size();
        vector<string> res(n, string(n,'.'));
        for (int i=0; i<n; i++){
            res[i][solution[i]]='Q';
        }
        result.push_back(res);
    }
    
    bool isValidSolution(const vector<int>& solution, int ind){
        int n = solution.size();
        if (n==0)
            return true;
        for (int i=0; i<n; i++){
            if (solution[i]==ind)
                return false;
            if (i-solution[i]==n-ind)
                return false;
            if (i+solution[i] == n+ind)
                return false;
        }
        return true;
    }
    
};
Posted by at No comments:
Labels:

LintCode(127) Topological Sorting Show result

Given an directed graph, a topological order of the graph nodes is defined as follow:
  • For each directed edge A -> B in graph, A must before B in the order list.
  • The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.
Have you met this question in a real interview? 
Yes
Example
For graph as follow:
picture
The topological order can be:
[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...

Note
You can assume that there is at least one topological order in the graph.


有向图的排序，基本上还是考察概念
遍历所有给定node的neighbors， 来mark 每一个被遍历的node的边数，因为是neighbors,所以必然有至少一个与他相连， 而没有被遍历到的自然为第一个被排出的。 然后push到q上去，想象把这个node从图中拿掉，那么他所有的neighbor必然少一条边，这个时候再减少计数，如果归零，则push到q上去。。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    typedef DirectedGraphNode Node;
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        unordered_map<Node*, int> map;
        for (int i=0; i<graph.size(); i++){
            Node* node = graph[i];
            for (int j=0; j<node->neighbors.size(); j++){
                Node* neighbor = node->neighbors[j];
                if (map.find(neighbor) == map.end())
                    map[neighbor]=1;
                else
                    map[neighbor]++;
            }
        }
        vector<Node*> result;
        queue<Node*> fifo;
        for (int i=0; i<graph.size(); i++){
            if (map.find(graph[i]) == map.end()){
                fifo.push(graph[i]);
                result.push_back(graph[i]);
            }
        }
        
        while(!fifo.empty()){
            Node* node = fifo.front();
            fifo.pop();
            for (int i=0; i<node->neighbors.size(); i++){
                Node* neighbor = node->neighbors[i];
                if (--map[neighbor] == 0){
                    fifo.push(neighbor);
                    result.push_back(neighbor);
                    map.erase(neighbor);
                }
            }
        }
        return result;
    }
};
Posted by at No comments:
Labels: ,

LintCode(135) Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 
Have you met this question in a real interview? 
Yes
Example
given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

Note
  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

这基本算是回溯法的经典题目了，之前朋友面试碰到过类似的，就是给 1， 5， 10， 25的硬币，求有多少种组合可以组成一个给定的币值， 其实就是这个题目。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        // write your code here
        vector<vector<int>> result;
        vector<int> solution;
        sort(candidates.begin(), candidates.end());
        helper(result, solution, candidates, 0, target);
        return result;
    }
    
    void helper(vector<vector<int>>& result, vector<int>& solution, vector<int>& candidates, int ind, int target){
        if (target<0)
            return;
        if (target==0){
            result.push_back(solution);
            return;
        }
        for (int i=ind; i<candidates.size(); i++){
            solution.push_back(candidates[i]);
            helper(result,solution, candidates, i, target-candidates[i]);
            solution.pop_back();
        }
    }
};
Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)