@TOC
简化路径
解题思路，看到题目要求，很容易的就想到了利用栈来解决问题，使用栈存储地址路径，然后通过遍历路径获得每一层地址的字符串，然后根据地址字符串判断操作，如果是..，则当栈不为空的情况出栈，如果是.或者空则不操作，否则入栈。
AC代码:
class Solution {
public:
string simplifyPath(string path) {
if(path.size() == 0) return "/";
if(path[path.size() -1] != '/') path = path.append("/");
stack<string> name;
auto l = path.begin();
for(auto r = path.begin(); r != path.end(); ++r) {
if((*l == '/' && *r != '/') || (l == r)) continue;
else {
string tmp(l, r);
cout << l - path.begin() << " " << r - path.begin() << " ";
cout << tmp << endl;
if(tmp == "/..") {
if(!name.empty()) name.pop();
} else if(!(tmp == "/" || tmp == "/.")) {
name.push(tmp);
}
l = r;
}
}
string res;
while(!name.empty()) {
res = name.top() + res;
name.pop();
}
return res.size() == 0? "/" : res;
}
};
编辑距离
看到这道题的时候脑子一片空白，然后想到的是先求出最长公共字符串，可惜可惜啊，都想到最长公共字符串了，都和动态规划沾上关系了，我这竟然还没有想到就直接用动态规划解决，毕竟三种操作都放在那里，告诉你如何状态转移了，默哀三秒。
步入正题，这道题确实是有点意思的，对于动态规划来说，说不明显但是在用完之后怎么看怎么明显。首先明确状态为何?
定义状态数组dp[i][j]表示word1的第i个字符和word2的第j个字符的编辑距离。
初始化:当word1为0的时候，编辑距离就是word2的长度；同理当word2为0的时候，编辑距离就是word1的长度。
状态转移:dp[i][j]有三种方式可以到达，分别为word1插入，word1删除，word1替换。这里会有奇怪的地方，word1删除，岂不是不能做到，毕竟在走到dp[i][j]的时候是不知道dp[i+1][j]的值。但是word1删除等价于word2插入。所以三种操作代表三种转移方案。
状态转移方程:dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。不过还是有需要注意的地方，就是替换的时候，如果两个字符串的第i-1个字符和第j-1个字符是相等的，那么我是不需要进行操作的。所以word1替换的操作需要根据字符是否相等来决定是否+1操作。
AC代码:
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
if(n * m == 0) return n + m;
int dp[n+1][m+1];
//default
memset(dp, 0, sizeof(dp));
for(int i = 0; i < m+1; ++i) dp[0][i] = i;
for(int i = 0; i < n+1; ++i) dp[i][0] = i;
//State transition
for(int i = 1; i < n+1; ++i) {
for(int j = 1; j < m+1; ++j) {
int inert = dp[i-1][j] + 1;
int delet = dp[i][j-1] + 1;
int replace = dp[i-1][j-1];
if(word1[i-1] != word2[j-1]) replace += 1;
dp[i][j] = min(inert, min(delet, replace));
}
}
return dp[n][m];
}
};
矩阵置零
第一反应就是利用两个set分别保存将要被置为0的行和列，然后看到题目要求:
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
不错，第一反应就是一个简单的改进方案，囧。
然后苦苦思索常数空间，想到的一个方案就是在找到0之后先不置为0，用一个别的数字先代替，当然第一反应是-1，但是在写代码的时候又考虑到没说数组中不存在-1的数字，随推翻。然后再次思索，随失败。不甘心的参考了解题，神奇。
最后是通过以第一行第一列作为标记，然后单独考虑第一行第一列，最后虽然额外空间是常数空间，但是怎么都觉得这个代码比较臃肿。
AC代码:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
bool fr = false, fc = false;
int m = matrix.size();
int n = (*matrix.begin()).size();
//判断第一行是否存在0
for(int i = 0; i < n; ++i) {
if(matrix[0][i] == 0) {
fr = true;
break;
}
}
//判断第一列是否存在0
for(int j = 0; j < m; ++j) {
if(matrix[j][0] == 0) {
fc = true;
break;
}
}
//除了第一行第一列，遍历数组，如果存在0，则将此位置对应的首个行和列置为0
for(int i = 1; i < m; ++i) {
for(int j = 1; j < n; ++j) {
if(matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
//判断该位置的首个行和列是否为0，是则修改此位置为0
for(int i = 1; i < m; ++i) {
for(int j = 1; j < n; ++j) {
if(matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
//单独考虑的第一行第一列
if(fr) {
for(int i = 0; i < n; ++i) {
matrix[0][i] = 0;
}
}
if(fc) {
for(int j = 0; j < m; ++j) {
matrix[j][0] = 0;
}
}
}
};
搜索二维矩阵
看到排序数组，而且查找值，提高效率。不用思考就是二分查找，矩阵又如何，两次二分查找就可以解决了，先找行，再找列，找到返回true，否则返回false。
AC代码:
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
if(m == 0) return false;
int n = (*matrix.begin()).size() - 1;
if(n == -1) return false;
int targetm = 0, targetn = 0;
while(targetm < m) {
int midm = targetm + (m - targetm) / 2;
if(matrix[midm][0] == target) return true;
else if(matrix[midm][0] < target) {
targetm = midm + 1;
}else {
m = midm;
}
}
targetm = targetm == 0 ? 0 : targetm-1;
while(targetn <= n) {
int midn = targetn + (n - targetn) / 2;
if(matrix[targetm][midn] == target) return true;
else if(matrix[targetm][midn] < target) {
targetn = midn + 1;
}else {
n = midn - 1;
}
}
return false;
}
};
PS,二维数组其实也是一维数组，所以这道题二分查找可以更简洁，left = 0;right = m*n-1;mid = left + (right - left) / 2，对应的值是matrix[mid/n][mid%n]。
颜色分类
解题思路，这道题不就是排序吗，可以利用快速排序的思想，以1为基准，小于1的放左边，大于1的放右边。这样的话我们可以维护1的左右边界，遍历一次数组即可完成。
AC代码:
class Solution {
public:
void sortColors(vector<int>& nums) {
if(nums.size() < 2) return;
//left记录1的左边界，right记录1的右边界
int left = 0, right = nums.size() - 1;
for(int i = 0; i <= right; ++i) {
if(nums[i] == 0) {
swap(nums[left++], nums[i]);
}
if(nums[i] == 2) {
//i--保证从后面交换过来的数字再次判断是否为0
swap(nums[i--], nums[right--]);
}
}
}
};
