408算法题leetcode--第11天

3. 无重复字符的最长子串

• 3. 无重复字符的最长子串
• 思路：滑动窗口
• 时间：O(n)；空间：O(字符种类数)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 滑动窗口：如果没有出现相同的字符，那么右指针一直向右
        int ret = 0, size = s.size();
        unordered_map<char, int>mp;
        for(int i = 0, j = 0; j < size; j++){
            if(mp.find(s[j]) != mp.end()){
                while(mp.find(s[j]) != mp.end()){
                    mp.erase(s[i]);
                    i++;
                }
            }
            mp[s[j]] = 1;
            ret = max(ret, j - i + 1);
        }
        return ret;
    }
};

48. 旋转图像

• 48. 旋转图像
• 思路：观察法
• 时间：O($n^2$)；空间：O(1)

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // 观察法：先行对称上下互换，再转置矩阵
        int n = matrix.size();
        for(int i = 0; i < n / 2; i++){
            for(int j = 0; j < n; j++){
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

54. 螺旋矩阵

• 54. 螺旋矩阵
• 思路：模拟
• 时间：O($n^2$)；空间：O(1)

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int>ret;
        int left = 0, right = matrix[0].size() - 1, top = 0, bottom = matrix.size() - 1;
        while(left <= right && top <= bottom){
            for(int i = left; i <= right; i++){
                ret.push_back(matrix[top][i]);
            }
            if(++top > bottom){
                break;
            }
            for(int i = top; i <= bottom; i++){
                ret.push_back(matrix[i][right]);
            }
            if(--right < left){
                break;
            }
            for(int i = right; i >= left; i--){
                ret.push_back(matrix[bottom][i]);
            }
            if(--bottom < top){
                break;
            }
            for(int i = bottom; i >= top; i--){
                ret.push_back(matrix[i][left]);
            }
            if(++left > right){
                break;
            }
        }
        return ret;
    }
};

20. 有效的括号

• 20. 有效的括号
• 思路：左括号入栈，遇到对应的右括号出栈
• 时间：O(n)；空间：O(n)

class Solution {
public:
    bool isValid(string s) {
        stack<int>stk;
        for(auto c : s){
            if(c == '(' || c == '{' || c == '['){
                stk.push(c);
            } else if(c == ')' && stk.size() && stk.top() == '('){
                stk.pop();
            } else if(c == ']' && stk.size() && stk.top() == '['){
                stk.pop();
            }else if(c == '}' && stk.size() && stk.top() == '{'){
                stk.pop();
            } else {
                return false;
            }
        }
        if(stk.size()){
            return false;
        }
        return true;
    }
};

150. 逆波兰表达式求值

• 150. 逆波兰表达式求值
• 思路：栈
• 时间：时间：O(n)；空间：O(n)

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 遇到数字就入栈
        // 遇到符号就弹出两个数计算，然后将数重新入栈
        stack<long long>stk;
        for(auto c : tokens){
            if(c == "+" || c == "*" || c == "-" || c == "/"){
                auto t1 = stk.top();
                stk.pop();
                auto t2 = stk.top();
                stk.pop();
                long long temp = 0;
                if(c == "+") temp = t1 + t2;
                else if(c == "-") temp = t2 - t1;
                else if(c == "*") temp = t1 * t2;
                else temp = t2 / t1;
                stk.push(temp);
            } else {
                stk.push(stoll(c));
            }
        }
        return stk.top();
    }
};