Python：在指定目录下查找满足条件的文件

class Solution
{
public:
    vector<string> restoreIpAddresses(string s)
    {
        s_ = s;
        helper("", 1, 0);

        return res_;
    }

    void helper(string ip, int segment_num, int index)
    {
        if (segment_num == 4)
        {
            string ip_segment = s_.substr(index, s_.size() - index);
            if (!ip_segment.empty() && ip_segment.length() <= 3 
                    && isValid(ip_segment))
            {
                ip += ip_segment;
                res_.push_back(ip);
            }
        }
        else
        {
            for (int i = 1; i <= 3 && i <= s_.size() - index; i++)
            {
                string ip_segment = s_.substr(index, i);
                if (isValid(ip_segment))
                    helper(ip + ip_segment + '.', segment_num + 1, index + i);
            }
        }
    }

    bool isValid(string ip_segment)
    {
        if (ip_segment[0] == '0')
            return (ip_segment == "0");
        if (stoi(ip_segment) <= 255)
            return true;
        else
            return false;
    }

private:
    string s_;
    vector<string> res_;
};

Note

一开始做的采用一种非常麻烦的方法，每一层的solution记录每个点的位置，这样一来 isValid以及最后生成IP的时候就会特别的繁琐。

简单的方法是直接在每层递归中记录一个ip_segment，这样能够省好多的代码。

stoi()的参数不能为“”，也不能超出int的表示范围，否则程序会崩溃。

因此在调用stoi()之前要先检查一下参数。

像stoi()这种函数如果崩溃了，可以采用 break + display 的方法在gdb 中找出崩溃的原因。

参考

http://blog.csdn.net/u011095253/article/details/9158449

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40989329

LeetCode: LRU Cache

2014/11/9

题目
分析
代码
Note
参考

题目

https://oj.leetcode.com/problems/lru-cache/

分析

这道题主要考察的是数据结构的设计能力。

首先考虑用hash_map来存储数据，这样get()可以达到O(1)；不过hash_map没有淘汰LRU Cache的高效办法：一种方法是每个node存放一个最近使用的时间，每次set()时遍历时找出LRU node，这样set()是O(n)的时间复杂度，而且这样设计的话每次还要计算出哪个节点和现在的时间差值最大，实现起来特别麻烦。

之前面试的时候面试官提示可以用list实现：每次把最近用到的节点放到list最前面。但是当时觉得这种方法不太好，因为get()和set()的时间复杂度都是O(n)，效率实在太低。

现在来看，应该是把hash_map和链表结合起来来用，使得get()和set()都能够达到O(1)的时间复杂度：每次用到的数据添加到list最前面，每次需要淘汰数据时，淘汰list的最后面的元素。同时用hash_map记录每个key在list中的位置，这样每次要根据key查询数据时，便到hash_map中查找数据。

代码

class LRUCache
{
public:
    LRUCache(int capacity)
    {
        capacity_ = capacity;
    }

    int get(int key)
    {
        if (cache_map_.find(key) == cache_map_.end())
            return -1;
        else
        {
            //delete old node and push a new node in front of list
            int temp = cache_map_[key]->second;
            cache_.erase(cache_map_[key]);
            cache_.push_front(pair<int, int>(key, temp));
            cache_map_[key] = cache_.begin();
            return temp;
        }
    }

    void set(int key, int value)
    {
        if (cache_map_.find(key) == cache_map_.end())
        {
            if (cache_.size() >= capacity_)
            {
                //delete the last node of list
                cache_map_.erase(cache_.back().first);
                cache_.pop_back();
            }
            //push new node in front of list
            cache_.push_front(pair<int, int>(key, value));
            cache_map_[key] = cache_.begin();
        }
        else
        {
            //delete old node and push a new node in front of  list
            cache_.erase(cache_map_[key]);
            cache_.push_front(pair<int, int>(key, value));
            cache_map_[key] = cache_.begin();
        }
    }

private:
    int capacity_;
    list<pair<int, int>> cache_;
    unordered_map<int, list<pair<int, int>>::iterator> cache_map_;
};

Note

在写代码的过程中，犯了很多2B的错误，导致花了很久才找出错误。

在更新list中的node时，忘记了同时更新map中的数据。
错误的把list.end()当做了list最后一个节点。 list.back()才是list最后一个节点。

参考

http://fisherlei.blogspot.com/2013/11/leetcode-lru-cache-solution.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40954059

LeetCode: Partition List

2014/11/8

题目
分析
代码
Note
参考

题目

https://oj.leetcode.com/problems/partition-list/

分析

新建两个链表，第一个链表存放小于x的数，另一个存放大于等于x的数

从前往后遍历给定链表的每一个元素，并根据大小添加到上面创建的两个链表中。

最后把两个链表连接起来。

代码

class Solution
{
public:
    ListNode *partition(ListNode *head, int x)
    {
        struct ListNode *less = new struct ListNode(0);
        struct ListNode *equal_or_greater = new struct ListNode(0);
        struct ListNode *ph, *pl, *pe;

        ph = head;
        pl = less;
        pe = equal_or_greater;
        //partition list into the two lists
        while (ph != NULL)
        {
            if (ph->val < x)
            {
                pl->next = ph;
                pl = pl->next;
                ph = ph->next;
            }
            else
            {
                pe->next = ph;
                pe = pe->next;
                ph = ph->next;
            }
        }

        //link the two lists
        pl->next = equal_or_greater->next;
        pe->next = NULL;

        //delete first node of the two lists
        struct ListNode *temp;
        temp = less;
        less = less->next;
        delete temp;
        delete equal_or_greater;

        return less;
    }
};

Note

一开始先删除头节点然后再连接两个链表，导致结果出问题了，原因在于删除头节点可能导致一个指针失效。

正确的做法应该是先连接链表再删除头节点。

参考

http://www.cnblogs.com/springfor/p/3862392.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40925997

LeetCode: Search a 2D Matrix

2014/11/8

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/search-a-2d-matrix/

分析

用二分查找来解决这道题：

第一次二分查找在第一列中找到那个数所在的那一行，第二次二分查找在那一行中找出那个数。

时间复杂度是O(log(m)) + O(log(n))

一开始想不出第一次二分查找应该怎么写，即找出第一个比target小的那个数，

后来看了参考中的解法才明白，二分查找退出的那一时刻，如果arr[mid] != target，那么arr[l] 是第一个比target大的数，arr[r]是第一个比target小的数。

代码

class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int h = matrix.size();
        int w = matrix[0].size();


        int l = 0;
        int r = h - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (matrix[mid][0] < target)
                l = mid + 1;
            else if (matrix[mid][0] > target)
                r = mid - 1;
            else
                return true;
        }

        int row = r;
        if (row < 0)
            return false;

        l = 0;
        r = w - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (matrix[row][mid] < target)
                l = mid + 1;
            else if (matrix[row][mid] > target)
                r = mid - 1;
            else
                return true;
        }
        return false;
    }
};

参考

http://blog.csdn.net/linhuanmars/article/details/24216235

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40920131

LeetCode: Edit Distance

2014/11/7

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/edit-distance/

分析

一开始没有思路，看了一些大神的解法以后才明白如何用动态规划的思路来解决这道题。

数据结构

创建一个二维数组res[][]，其中res[i][j]用来代表word1[0 : i-1]和word2[0 : j-1]的EditDistance。

递归关系

考虑word1[i] == word2[j]的情况，直接匹配即可，res[i][j] = res[i-1][j-1];

考虑word1[i] == word2[j]的情况，这种情况下分为以下多种情况来处理，然后取其中的最小值即可

A. 用replace来处理，res[i][j] = res[i-1][j-1] + 1。这个应该很好理解，比如"abc1"和"abc2"两个字符串，res["abc1"]["abc2"] = res["abc"]["abc"] + 1。

B. 用insert来处理，res[i][j] = res[i][j-1] + 1; 举个例子，还是"abc1"和"abc2"两个字符串，res["abc1"]["abc2"] = res["abc1"]["abc"] + 1;

C. 用delete来处理，res[i][j] = res[i-1][j] + 1; 举个例子，还是"abc1"和"abc2"两个字符串，res["abc1"]["abc2"] = res["abc"]["abc2"] + 1;

数据结构的初始化

因为在递归关系中用到了res[i-1][j-1]，所以数据结构中的数据必然要先初始化才行，

res[i][0] = i; 代表 ""和"abc2"的EditDistance为4

res[0][i] = i; 代表 "abc1"和""的EditDistance为4

其他

在2. 递归关系中，还少考虑了一种情况，只不过为了理解起见一开始没有说，

当res[i] == res[j]时， res[i][j] 有时不能直接等于res[i-1][j-1]，因为有可能用insert/delete处理的EditDistance比直接匹配的EditDistance更小，

所以res[i][j] = min(直接匹配，insert处理， delete处理)，即 res[i][j] = min(res[i-1][j-1], res[i-1][j] + 1, res[i][j-1] + 1);

代码

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> res(m + 1, vector<int>(n + 1));

        for (int i = 0; i <= m; i++)
            res[i][0] = i;
        for (int i = 0; i <= n; i++)
            res[0][i] = i;

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
            {
                res[i][j] = min(res[i-1][j] + 1, res[i][j-1] + 1);
                if (word1[i-1] == word2[j-1])
                    res[i][j] = min(res[i][j], res[i-1][j-1]);
                else
                    res[i][j] = min(res[i-1][j-1] + 1, res[i][j]);
        }

        return res[m][n];
    }
};

参考

http://yucoding.blogspot.com/2013/09/leetcode-question-29-edit-distance.html

http://fisherlei.blogspot.com/2012/12/leetcode-edit-distance.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40894107

LeetCode: Minimum Path Sum

2014/11/6

题目
分析
代码

题目

https://oj.leetcode.com/problems/minimum-path-sum/

分析

动态规划题，

某一点的MinimumPathSum = min(左侧点的MinimumPathSum, 上侧点的MinimumPathSum) + 该点的数值

不过第一行和第一列的MinimumPathSum有些特殊，需要单独处理一下。

代码

class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> res(grid);

        //First row and first col 's Minimum Path Sum
        for (int i = 1; i < m; i++)
            res[i][0] += res[i-1][0];
        for (int i = 1; i < n; i++)
            res[0][i] += res[0][i-1];

        //Other points's Minimum Path Sum
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                res[i][j] += min(res[i-1][j], res[i][j-1]);

        return res[m-1][n-1];
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40868907

LeetCode: Unique Paths II

2014/11/6

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/unique-paths-ii/

分析

这道题是Unique Paths的变形，只是稍微复杂了一点。

在Unique Paths中， paths[i][j] = paths[i-1][j] + paths[i][j-1];

在Unique Paths II中，在这句之前要加一个判断语句来判断obstacleGrid[i][j]的值是否为1，如果是1则将paths[i][j]直接赋值为0

仅仅做完第一步还不行，原本第一行都为1，

现在如果第一行某个元素是obstacle，那么这一行该元素及其之后的元素路径数都为0，为什么呢？

因为要想如Unique Paths中所说路径长度达到最小，那么第一行obstacle之后的元素必然不能走。

第一列也是同样的道理。

代码

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> paths(m, vector<int>(n, 1));

        int firstRowFirstObstacle = -1;
        int firstColFirstObstacle = -1;
        //get first obstacle position in first col and first row 
        for (int i = 0; i < m; i++)
            if (obstacleGrid[i][0] == 1)
            {
                firstColFirstObstacle = i;
                break;
            }
        for (int i = 0; i < n; i++)
            if (obstacleGrid[0][i] == 1)
            {
                firstRowFirstObstacle = i;
                break;
            }

        //assign 0 where firstObstacle and after that in first row and col
        if (firstColFirstObstacle != -1)
            for (int i = firstColFirstObstacle; i < m; i++)
                paths[i][0] = 0;
        if (firstRowFirstObstacle != -1)
            for (int i = firstRowFirstObstacle; i < n; i++)
                paths[0][i] = 0;

        //calculate paths
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (obstacleGrid[i][j] == 1)
                {
                    paths[i][j] = 0;
                    continue;
                }
                paths[i][j] = paths[i-1][j] + paths[i][j-1];
            }
        }

        return paths[m-1][n-1];
    }
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40865761

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40866417

LeetCode: Unique Paths

2014/11/6

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/unique-paths/

分析

一开始没弄懂题意，存在一些问题：能不能走重复的路径？路径长度是否要求为最短的？

后来看了一些答案才明白，题目的隐含要求是，在走最短的路径的前提下，求不同路径数目。

这样一来题目就简单了，某一点的不同路径数 = 左侧点的不同路径数 + 上侧点的不同路径数

可以用递归来求解，但这样效率底下，需要动态规划的方法来解决。

代码

class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> paths(m, vector<int>(n, 1));

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                paths[i][j] = paths[i-1][j] + paths[i][j-1];

        return paths[m-1][n-1];
    }
};

参考

http://blog.csdn.net/kenden23/article/details/17303497

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40865761

LeetCode: N-Queens II

2014/11/2

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/n-queens-ii/

分析

跟N-Queens这道题解法一样，略作修改即可。

代码

class Solution
{
public:
    int totalNQueens(int n)
    {
        vector<int> solution(n);
        helper(solution, 0, n);

        return res;
    }
    void helper(vector<int> &solution, int row, int n)
    {
        if (row == n)
            res++;
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (isValid(solution, row, i))
                {
                    solution[row] = i;
                    helper(solution, row + 1, n);
                }
            }
        }
    }
    bool isValid(vector<int> &solution, int row, int col)
    {
        for (int i = 0; i < row; i ++)
            if (solution[i] == col || abs(i-row) == abs(solution[i]-col))
                return false;
        return true;
    }

private:
    int res = 0;
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40686105

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40711959

LeetCode: N-Queens

2014/11/2

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/n-queens/

分析

这道题采用的是回溯法，跟DFS非常类似，只不过是在DFS的递归前加一个判断。
关于如何表示结果。

可以采用一个N*N二维数组来存放结果，但是我们可以采用更好的办法：经过观察我们可以发现，每一行必然有一个皇后，因此我们可以用一个一维数组来表示结果，solution[0]=3 代表第0行的皇后放在第三列， solution[1]=5 代表第1行的皇后放在第5列，……以此类推。

关于如何判断一种结果是否合法。

题目要求任意两个皇后不能在同一行、同一列或者用一斜线上，在2中我们已经提过了用一维数组solution[n]来表示结果，任两个皇后肯定不在同一行，判断第i行和第j行的皇后是否同一列可以用 solution[i] == solution[j]来判断；如何判断第i行皇后和第j行皇后是否在同一斜线上呢？可以用 abs(i-j) == abs(solution[i] - solution[j]) 来判断。

代码

class Solution
{
public:
    vector<vector<string>> solveNQueens(int n)
    {
        vector<int> solution(n);
        helper(solution, 0, n);

        return res;
    }

    void helper(vector<int>& solution, int row, int n)
    {
        if (row == n)
        {
            vector<string> solution_2d(n, string(n, '.'));
            for (int i = 0; i < n; i++)
                solution_2d[i][solution[i]] = 'Q';

            res.push_back(solution_2d);
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (isValid(solution, row, i))
                {
                    solution[row] = i;
                    helper(solution, row + 1, n);
                }
            }
        }
    }

    bool isValid(vector<int>& solution, int row, int col)
    {
        for (int i = 0; i < row; i++)
            if (solution[i] == col || abs(i-row) == abs(solution[i]-col))
                return false;
        return true;
    }

private:
    vector<vector<string>> res;
};

参考

http://www.cnblogs.com/TenosDoIt/p/3801621.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40686105

关于C++构造析构顺序的总结

2014/11/1

起因
代码
输出
分析
结论

起因

之前对C++基类派生类构造函数和析构函数的调用顺序存在疑惑，因此写了个小程序验证一下。

代码

#include <iostream>
using namespace std;

class Base
{
public:
    Base()
    {
        cout << "Base::Base()" << endl;
    }

    ~Base()             //case3
//  virtual ~Base()     //case4
    {
        cout << "Base::~Base()" << endl;
    }
};

class Derived : public Base
{
public:
    Derived()
    {
        cout << "Derived::Derived()" << endl;
    }
    ~Derived()
    {
        cout << "Derived::~Derived()" << endl;
    }
};

int main()
{
    cout << "------case1: Base Object------------------------------" << endl;
    Base *p = new Base();
    delete p;

    cout << "\n\n";
    cout << "------case2: Derived Object---------------------------" << endl;
    Derived *p3 = new Derived();
    delete p3;

    cout << "\n\n";
    cout << "------case3/case4: Base pointer to Derived Object-----" << endl;
    cout << "------(not virtual function/virtual function)---------" << endl;
    Base *p2 = new Derived();
    delete p2;

    return 0;
}

输出

------case1: Base Object------------------------------
Base::Base()
Base::~Base()


------case2: Derived Object---------------------------
Base::Base()
Derived::Derived()
Derived::~Derived()
Base::~Base()


------case3: Base pointer to Derived Object-----
------(not virtual function)---------
Base::Base()
Derived::Derived()
Base::~Base()


------case4: Base pointer to Derived Object-----
------(virtual function)---------
Base::Base()
Derived::Derived()
Derived::~Derived()
Base::~Base()

分析

由case1可知，

基类对象在创建的时候会自动调用构造函数；

销毁时会自动调用析构函数。
由case2可知，

普通派生类对象在创建时会先自动调用基类构造函数，然后调用自身构造函数；

销毁时会先自动调用自身的析构函数，然后调用基类的析构函数。
由case3/case4可知，

基类指针指向的派生类对象在创建时先自动调用基类构造函数，然后调用自身构造函数；

销毁时先判断，

如果析构函数不是虚函数，则当做基类对象析构————自动调用基类析构函数，

如果析构函数是虚函数，则当做派生类对象————先自动调用派生类析构函数，然后调用基类构造函数。

结论

综上，派生类对象构造析构的过程是这样的：

创建对象时，调用的构造函数只跟创建的对象类型有关，

判断对象类型，

  如果是基类对象，自动调用自身构造函数

  如果是派生类对象，先自动调用基类构造函数，然后调用自身构造函数。



销毁对象时，调用的析构函数跟析构函数是否是虚函数、指向它的指针类型和析构的对象类型有关

判断构造函数是否是为虚函数

  如果构造函数不是虚函数，按照指针类型（静态类型）析构

      如果指针类型是基类类型

      如果指针类型是派生类类型

  如果构造函数是虚函数，按照对象类型（动态类型）析构

      如果析构对象是基类类型

      如果析构对象是派生类类型

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40682855

LeetCode: Multiply Strings

2014/10/30

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/multiply-strings/

分析

大数乘法，不能直接相乘，因为会溢出。

首先两个乘数的各位之间两两相乘，得到多个同一列结果相加，

然后对结果进行进位。

如 25 × 25 = 625

2 5

× 2 5

————————————————————

10 25

4 10

————————————————————

4 20 25

————————————————————

6 2 5

代码

class Solution
{
public:
    string multiply(string num1, string num2)
    {
        vector<int> temp_res(num1.size() + num2.size(), 0);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        for (int i = 0; i < num1.size(); i++)
            for (int j = 0; j < num2.size(); j++)
                temp_res[i + j] += (num1[i]-'0') * (num2[j]-'0');

        int carry = 0;
        for (int i = 0; i < temp_res.size(); i++)
        {
            int temp = temp_res[i] + carry;
            temp_res[i] = temp % 10;
            carry = temp / 10;
        }

        for (int i = temp_res.size() - 1; i >= 0; i--)
        {
            if (temp_res[i] != 0)
                break;
            temp_res.pop_back();
        } 
        reverse(temp_res.begin(), temp_res.end());
        string res;
        for (int i = 0; i < temp_res.size(); i++)
            res += temp_res[i] + '0';

        return res.size() != 0 ? res : string("0");
    }
};

参考

http://www.cnblogs.com/TenosDoIt/p/3735309.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40604889

LeetCode: Combination Sum II

2014/10/27

题目
分析
代码
参考

题目

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

分析

这道题是Combination Sum的变形，也是采用DFS的思路，但相比之下要注意两点：

因为不能重复，所以在进进行DFS递归时，要直接从当前位置的下一个位置开始进行“试探”。
若num中存在两个相同的元素，为了防止结果中重复出现，只有在第一个元素被选中的情况下，第二个元素才进行“试探”，否则不进行“试探”。

代码

class Solution
{
public:
    vector<vector<int>> combinationSum2(vector<int> &num, int target)
    {
        vector<int> solution;
        this->num = num;
        sort(this->num.begin(), this->num.end());

        DFS(solution, target, 0);

        return res;
    }

    void DFS(vector<int> &solution, int target, int start)
    {
        if (target == 0)
        {
            res.push_back(solution);
        }
        else
        {
            for (int i = start; i < num.size() && num[i] <= target; i++)
            {
                if (i > 0 && num[i] == num[i-1] && num[i-1] != solution.back())
                    continue;
                solution.push_back(num[i]);
                DFS(solution, target - num[i], i + 1);
                solution.pop_back();
            }
        }
    }

private:
    vector<int> num;
    vector<vector<int>> res;
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40479161

http://www.cnblogs.com/remlostime/archive/2012/10/29/2745125.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40509643

LeetCode: Combination Sum

2014/10/26

题目
分析
代码

题目

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

分析

DFS，之前总结过很多道同类型的题。

代码

class Solution
{
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        if (candidates.size() == 0)
            return res;
        this->candidates = candidates;
        sort(this->candidates.begin(), this->candidates.end());
        vector<int> solution;

        DFS(solution, 0, target);

        return res;
    }
    void DFS(vector<int> &solution, int start, int target)
    {
        if (target == 0)
            res.push_back(solution);
        else
        {
            for (int i = start; i < candidates.size() && candidates[i] <= target; i++)
            {
                solution.push_back(candidates[i]);
                DFS(solution, i, target-candidates[i]);
                solution.pop_back();
            }
        }
    }
private:
    vector<int> candidates;
    vector<vector<int>> res;
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40479161

配置GDB支持STL调试

2014/10/26

环境
步骤
使用效果
参考

原生GDB不能支持STL调试，要进行STL调试必须进行一些配置才行，但网上的一些配置说明已经过时了，因此重新总结一下。

环境

Ubuntu 14.04 32位

GDB 7.7

步骤

Check-out最新的调试工具到本地一个文件夹下，比如 ~/yourname/gdb_printers

svn co svn://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/python
将下列内容添加到 ~/.gdbinit 文件夹中，其中的路径名改成上一步Check-out的工具对应的路径名

python
import sys
sys.path.insert(0, '/home/yourname/gdb_printers/python')
sys.path.append("/home/yourname/gdb_printers/python/libstdcxx/v6")
from libstdcxx.v6.printers import register_libstdcxx_printers
end

使用效果

如果代码是这样的：

vector a = {2, 3, 6, 7};

调试效果是这样的：

(gdb) p a
$1 = std::vector of length 4, capacity 4 = {2, 3, 6, 7}

参考

http://sourceware.org/gdb/wiki/STLSupport

http://stackoverflow.com/questions/26205564/gdb-pretty-printing-importerror-no-module-named-printers

http://blog.csdn.net/fdl19881/article/details/8710636

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40478407

LeetCode: Search for a Range

2014/10/26

题目
分析
代码

题目

https://oj.leetcode.com/problems/search-for-a-range/

分析

时间复杂度O(log n)，多半便是二分查找的题目。

题目要求找出一个范围，无非就是找到一个起始点和一个终止点，通过两次二分查找找到起始点和终止点即可。

起始点的特点是，等于target，而且它左侧没有target了或者它是数组第一个数。

终止点的特点是，等于target，而且它右侧没有target了或者它是数组最后一个数。

P.S. 标准二分查找代码可以查看这里。

代码

class Solution
{
public:
    vector<int> searchRange(int A[], int n, int target)
    {
        vector<int> res;
        int l, r, m;

        l = 0;
        r = n - 1;
        while (l <= r)
        {
            m = (l + r) >> 1;
            if ((A[m]==target) && (m==0 || A[m-1]!=target))
            {
                res.push_back(m);
                break;
            }
            else if (A[m] > target || A[m-1] == target)
                r = m - 1;
            else
                l = m + 1;
        }
        if (res.size() == 0)
        {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }

        l = 0;
        r = n - 1;
        while (l <= r)
        {
            m = (l + r) >> 1;
            if ((A[m]==target) && (m==n-1 || A[m+1]!=target))
            {
                res.push_back(m);
                break;
            }
            else if (A[m] < target || A[m+1] == target)
                l = m + 1;
            else 
                r = m - 1;
        }
        return res;
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40477301

标准二分查找代码

2014/10/26

代码
参考

二分查找算法在各种场合下经常会用到，在此总结一下它的标准代码。

代码

int binary_search(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;

    while (left <= right)
    {
        int mid = (left + right) >> 1;

        if (array[mid] < value)
            left = mid + 1;
        else if (array[mid] > value)
            right = mid + 1;
        else
            return mid;
    }

    return -1;
}