Python：在指定目录下查找满足条件的文件
2015-09-26更新：
现在发现要实现如下的功能，完全有现成的命令可以使用：
如递归查找名字含关键字的文件，使用find . -name "*keyword*"
如递归查找内容含关键字的文件，使用grep -Ir keyword .
之前写的程序就当做练手好了 ：）
Read on →JNI编程—— Linux下编写一个最简单的JNI程序
LeetCode: Restore IP Address
题目
https://oj.leetcode.com/problems/restore-ip-addresses/
分析
这道题和八皇后类似，采用回溯法来解决，也就是 剪枝过的DFS。
代码
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
题目
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
题目
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
题目
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