LeetCode 实践练习71-75

LeetCode—71(简化路径)

方法：规律，若遇到".“的情况直接去掉，若遇到”…"的情况，删掉紧挨着的上一个路径。还有若为空，则返回/，如果有多个/只保留一个。C++中有专门处理字符串的机制，我们可以使用stringstream来分割字符串，然后对每一段处理。
C++代码：

class Solution {
public:
    string simplifyPath(string path) {
        string res,temp;
        stringstream ss(path);
        vector<string> v;
        while(getline(ss,temp,'/')){
            if(temp == "" || temp == ".") continue;
            if(temp == ".." && !v.empty()) v.pop_back();//遇见..退到上一个目录
            else if (temp != "..") v.push_back(temp);//字母就加入v;
        }
        for (string s : v) res += "/" + s;
        return res.empty() ? "/" : res;
    }
};

LeetCode—72(编辑距离)

LeetCode—73(矩阵置零)

方法：
$O(mn)$O(mn)空间的解法，就是直接新建一个和maxtrix的矩阵，直接一行一行的扫，有0，将新建矩阵对应行为0.在进行列操作。
$O(m+n)$O(m+n)空间的解法，就是直接用一个m大小的行数组，记录哪行存在0，再用一个n大小的列数组，记录哪列存在0，直接更新原矩阵。
$O(1)$O(1)空间的解法，意味着不可以新建数组，待解。

LeetCode—74(搜索二维矩阵)

方法：
第一个方法，可以在最后一列上使用一次二分法，在该行使用一次二分法。即使用两次二分法。
第二个方法，只是用一次二分法，将二维数组看成一个一个一维数组，0,m*n-1.
C++代码：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        if(target < matrix[0][0] || target > matrix.back().back()) return false;//小于第一个或者大于最后一个
        int m = matrix.size(),n = matrix[0].size();
        int left = 0,right = m*n-1;
        while(left <= right){
            int mid = left + (right - left)/2;//记住这里，防止溢出，而且指针，迭代器不支持相加操作，所以不用(right-left)>>1
            if(matrix[mid/n][mid%n] == target) return true;
            else if(matrix[mid/n][mid%n] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};

LeetCode—75(颜色分类)

方法：（不太懂）

C++代码：

class Solution {
public:
    void sortColors(int A[], int n) {int red = 0, blue = n - 1;
        for (int i = 0; i <= blue; ++i) {
            if (A[i] == 0) {
                swap(A[i], A[red++]);
            } else if (A[i] == 2) {
                swap(A[i--], A[blue--]);
            } 
        }
    }
};