//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size(); i ++ ){
            if(res < 2 || nums[i] != nums[res - 2]) nums[res ++ ] = nums[i];
        }
        return res;
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0 || board[0].size() == 0) return false;
        for(int i = 0; i < board.size(); i ++ )
            for(int j = 0; j < board[0].size(); j ++ )
                if(dfs(i, j, 0, board, word)) return true;
        return false;
    }

    bool dfs(int x, int y, int cur, vector<vector<char>>& board, string& word){
        if(board[x][y] != word[cur]) return false;
        if(cur == word.size() - 1) return true;
        auto t = board[x][y];
        board[x][y] = '.';
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        for(int i = 0; i < 4; i ++ ){
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.') continue;
            if(dfs(a, b, cur + 1, board, word)) return true; 
        }
        board[x][y] = t;
        return false;
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        for(int i = 0; i < (1 << n); i ++ ){
            int t = i;
            vector<int> path;
            for(int j = 0; j < n; j ++ ){
                if(t >> j & 1) path.push_back(nums[j]);
            }
            res.push_back(path);
        }
        return res;
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> combine(int n, int k) {
        dfs(1, k, n);
        return ans;
    }

    void dfs(int cur, int k, int n){
        if(k == 0){
            ans.push_back(path);
            return;
        }
        for(int i = cur; i <= n; i ++ ){
            path.push_back(i);
            dfs(i + 1, k - 1, n);
            path.pop_back();
        }
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hs, ht;
        for(auto& c : t) ht[c] ++ ;
        int cnt = 0;
        string res;
        for(int i = 0, j = 0; i < s.size(); i ++ ){
            if(hs[s[i]] ++  < ht[s[i]]) cnt ++ ;
            while(hs[s[j]] > ht[s[j]]){
                hs[s[j]] --;
                j ++ ;
            }
            if(cnt == t.size() && (res == "" || res.size() > i - j + 1)){
                res = s.substr(j, i - j + 1);
            }
        }
        return res;
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        if(!n) return;
        for(int i = 0, j = 0, k = n - 1; i <= k; ){
            if(nums[i] == 0) swap(nums[i ++ ], nums[j ++ ]);
            else if(nums[i] == 1) i ++ ;
            else swap(nums[i], nums[k -- ]);
        }
        return;
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(!matrix.size() || ! matrix[0].size()) return false;
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n * m;
        while(l < r){
            int mid = l + r >> 1;
            if(matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }
        if(r == n * m || matrix[r / m][r % m] != target) return false;
        return true;
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(!matrix.size() || !matrix[0].size()) return;
        int n = matrix.size(), m = matrix[0].size();
        vector<bool> row(n), col(m);
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < m; j ++ )
                if(matrix[i][j] == 0) row[i] = col[j] = true;
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < m; j ++ )
                if(row[i] || col[j]) matrix[i][j] = 0;
        return;
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    int minDistance(string word1, string word2) {
        word1 = ' ' + word1, word2 = ' ' + word2;
        vector<vector<int>> f(word1.size(), vector<int>(word2.size()));

        for(int i = 0; i < word1.size(); i ++ ) f[i][0] = i;
        for(int i = 0; i < word2.size(); i ++ ) f[0][i] = i;

        for(int i = 1; i < word1.size(); i ++ )
            for(int j = 1; j < word2.size(); j ++ ){
                f[i][j] = min(f[i][j - 1], f[i - 1][j]) + 1;
                int t = word1[i] != word2[j];
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + t);
            }
        return f[word1.size() - 1][word2.size() - 1];
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    string simplifyPath(string path) {
        if(path.back() != '/') path += '/';
        string res, name;
        for(auto& c : path){
            if(c != '/') name += c;
            else{
                if(name == ".."){
                    while(res.size() && res.back() != '/') res.pop_back();
                    if(res.size()) res.pop_back();
                }
                else if(name != "." && name != ""){
                    res += "/" + name;
                }
                name = "";
            }
        }
        if(!res.size()) res += '/';
        return res;
    }
};