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
LeetCode: Edit Distance
题目
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
题目
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