当前位置：首页 > news >正文

408算法题leetcode--第11天

news 来源：原创 2024/9/22 4:38:01

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();}
};