生活中我们很多情况下会设置多级路由，如一级路由器的无线信号太弱、一级路由器不能发射无线信号等原因。这种这种情况下就需要设置多级路由了。相比于仅仅设置一级路由来说，设置二级路由则麻烦了许多，一不小心，不光会自己上不了网，还可能会把别人也搞得上不了网。
设置二级路由器的方法有两种，下面分别对其进行介绍。
我们约定如下： 与Modem或者入户宽带相连的路由器称为A路由器，而与A路由器相连的路由器称为B路由器。局域网中其它计算机均可任意连接到其中的一台路由器的LAN口上，但同时也必须得遵守所连路由器的规则，即IP地址分配范围。
Read on →最近在亚马逊云主机上安装MySql，想远程访问，结果无论如何都访问不了。在踩了若干坑之后，终于访问成功了，在此做一下记录：EC2云主机上安装了MySql后如何开启远程访问。
Read on →2015-09-26更新：
现在发现要实现如下的功能，完全有现成的命令可以使用：
如递归查找名字含关键字的文件，使用find . -name "*keyword*"
如递归查找内容含关键字的文件，使用grep -Ir keyword .
之前写的程序就当做练手好了 ：）
Read on →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_;
};
简单的方法是直接在每层递归中记录一个ip_segment，这样能够省好多的代码。
因此在调用stoi()之前要先检查一下参数。
http://blog.csdn.net/u011095253/article/details/9158449
本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40989329
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_;
};
在写代码的过程中，犯了很多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
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;
}
};
一开始先删除头节点然后再连接两个链表，导致结果出问题了，原因在于删除头节点可能导致一个指针失效。
正确的做法应该是先连接链表再删除头节点。
http://www.cnblogs.com/springfor/p/3862392.html
本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40925997
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
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
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
https://oj.leetcode.com/problems/unique-paths-ii/
这道题是Unique Paths的变形，只是稍微复杂了一点。
1.
在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
现在如果第一行某个元素是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
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
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
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++基类派生类构造函数和析构函数的调用顺序存在疑惑，因此写了个小程序验证一下。
#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
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
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