面试经典150题

验证回文串

如果将全部大写字符转换为小写字符，并移除全部非字母数字后，正着读和反着读一样，就认为短语是一个回文串。

1. class Solution {
2. public:
3.     bool isPalindrome(string s) {
4.         int left = 0;
5.         int right = s.size()-1;
6.         while(left < right){
7.             while(left < right && !isalnum(s[left])){
8.                 left++;
9.             }
10.             while(left < right && !isalnum(s[right])){
11.                 right--;
12.             }
13.             if(left < right && tolower(s[left]) != tolower(s[right])){
14.                 return false;
15.             }
16.             left++;
17.             right--;
18.         }
19.         return true;
20.     }
21. };

复制代码

判断子序列

给定字符串s和t，判断s是否为t的子序列。
子序列是指原始字符串删除一些字符而不改变剩余字符相对位置形成的新字符串。
双指针
初始化两个指针i和j，分别指向s和t的初始位置。
每次贪婪匹配，匹配成功则i和j同时右移，匹配s的下一个位置，匹配失败则j右移，i稳定。
终极i移动到s的末尾，说明s是t的子序列。

1. class Solution {
2. public:
3.     bool isSubsequence(string s, string t) {
4.         int n = s.size();
5.         int m = t.size();
6.         int sIndex = 0, tIndex = 0;
7.         while(sIndex < n && tIndex < m){
8.             if(s[sIndex] == t[tIndex]){
9.                 sIndex++;
10.                 tIndex++;
11.             }else{
12.                 tIndex++;
13.             }
14.         }
15.         return sIndex == n;
16.     }
17. };

复制代码

两数之和

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& numbers, int target) {
4.         int left = 0;
5.         int right = numbers.size()-1;
6.         while(left < right){
7.             int num = numbers[left] + numbers[right];
8.             if(num == target){
9.                 return {left+1, right+1};
10.             }else if(num < target){
11.                 left++;
12.             }else{
13.                 right--;
14.             }
15.         }
16.         return {0,0};
17.     }
18. };

复制代码

赎金信

没有前后大小顺序关系，用双指针一般。

1. class Solution {
2. public:
3.     bool canConstruct(string ransomNote, string magazine) {
4.         sort(ransomNote.begin(), ransomNote.end());
5.         sort(magazine.begin(), magazine.end());
6.         int i = 0, j = 0, m = ransomNote.size(), n = magazine.size();
7.         while(i<m && j<n){
8.             if(ransomNote[i] == magazine[j]){
9.                 i++;
10.                 j++;
11.             }else{
12.                 j++;
13.             }
14.         }
15.         return i == m;
16.     }
17. };

复制代码

哈希表

1. class Solution {
2. public:
3.     bool canConstruct(string ransomNote, string magazine) {
4.         unordered_map<int, int> count;
5.         for(char c : magazine){
6.             count[c]++;
7.         }
8.         for(char c : ransomNote){
9.             if(count[c] == 0){
10.                 return false;
11.             }else{
12.                 count[c]--;
13.             }
14.         }
15.         return true;
16.     }
17. };

复制代码

数组

1. class Solution {
2. public:
3.     bool canConstruct(string ransomNote, string magazine) {
4.         int count[26] = {};
5.         for(char c : magazine){
6.             count[c-'a']++;
7.         }
8.         for(char c : ransomNote){
9.             if(count[c-'a'] == 0){
10.                 return false;
11.             }else{
12.                 count[c-'a']--;
13.             }
14.         }
15.         return true;
16.     }
17. };

复制代码

同构字符串

给两个字符串s和t，判断它们是否同构。

1. class Solution {
2. public:
3.     bool isIsomorphic(string s, string t) {
4.         unordered_map<char, char> s2t;
5.         unordered_map<char, char> t2s;
6.         
7.         for(int i=0; i<s.size(); i++){
8.             char x = s[i];
9.             char y = t[i];
10.             if((s2t.count(x) && s2t[x] != y) || (t2s.count(y) && t2s[y] != x)){
11.                 return false;
12.             }
13.             s2t[x] = y;
14.             t2s[y] = x;
15.         }
16.         return true;
17.     }
18. };

复制代码

分割字符串

1. vector<string> splitString(string& str){
2.         istringstream iss(str);
3.         vector<string> res;
4.         string word;
5.         while(iss >> word){
6.                 res.push_back(word);
7.         }
8.         return res;
9. }

复制代码

1. class Solution {
2. public:
3.     vector<string> splitString(string s){
4.         istringstream iss(s);
5.         vector<string> res;
6.         string word;
7.         while(iss >> word){
8.             res.push_back(word);
9.         }
10.         return res;
11.     }
12.     bool wordPattern(string pattern, string s) {
13.         unordered_map<char, string> char2s;
14.         unordered_map<string, char> s2char;
15.         
16.         vector<string> words = splitString(s);
17.         if(pattern.size() != words.size()){
18.             return false;
19.         }
20.         for(int i=0; i<pattern.size(); i++){
21.             char c = pattern[i];
22.             string word = words[i];
23.             if((char2s.count(c) && char2s[c] != word) || (s2char.count(word) && s2char[word] != c)){
24.                 return false;
25.             }
26.             char2s[c] = word;
27.             s2char[word] = c;
28.         }
29.         return true;
30.     }
31. };

复制代码

有用的括号

1. class Solution {
2. public:
3.     bool isValid(string s) {
4.         stack<char> stk;
5.         for(int i = 0; i<s.size(); i++){
6.             char ch = s[i];
7.             if(ch == '(' || ch == '[' || ch == '{'){
8.                 stk.push(ch);
9.             }else{
10.                 if(stk.empty()){
11.                     return false;
12.                 }
13.                 char topCh = stk.top();
14.                 if((topCh =='[' && ch == ']') || (topCh =='(' && ch == ')') || (topCh =='{' && ch == '}')){
15.                     stk.pop();
16.                 }else{
17.                     return false;
18.                 }
19.             }
20.         }
21.         return stk.empty();
22.     }
23. };

复制代码

1. class Solution {
2. public:
3.     bool isValid(string s) {
4.         int n = s.size();
5.         if(n % 2 == 1){
6.             return false;
7.         }
9.         unordered_map<char, char> pairs = {
10.             {']','['},
11.             {'}','{'},
12.             {')','('}
13.         };
15.         stack<char> stk;
16.         for(char ch:s){
17.             if(pairs.count(ch)){
18.                 if(stk.empty() || stk.top() != pairs[ch]){
19.                     return false;
20.                 }
21.                 stk.pop();
22.             }else{
23.                 stk.push(ch);
24.             }
25.         }
26.         return stk.empty();
27.     }
28. };

复制代码

简化路径

我们首先将给定的字符串path根据/分割成一个由多少字符串构成的列表，记为names。
names中包含的字符串只能为以下几种：

• 空字符串。例如当出现多个连续的/，就会分割出空字符串。
  
• 一个点.
  
• 两个点…
  
• 目次名。
  

对于空字符串以及一个点，无需处置惩罚。
对于两个点或者目次名，必要用一个栈来维护路径中的每一个目次名。当遇到两个点时，只要栈不为空，就切换到上一级（弹出栈顶目次），当遇到目次名时，就放入栈。

1. class Solution {
2. public:
3.     vector<string> splitString(string &path){
4.         vector<string> res;
5.         string temp;
6.         for(char c : path){
7.             if(c == '/'){
8.                 res.push_back(temp);
9.                 temp.clear();
10.             }else{
11.                 temp += c;
12.             }
13.         }
14.         res.push_back(temp);
15.         return res;
16.     }
18.     string simplifyPath(string path) {
19.         vector<string> names = splitString(path);
20.         vector<string> stk;
21.         for(int i=0; i<names.size(); i++){
22.             if(names[i] == ".."){
23.                 if(!stk.empty()){
24.                     stk.pop_back();
25.                 }
26.             }else if(!names[i].empty() && names[i] != "."){
27.                 stk.push_back(names[i]);
28.             }
29.         }
31.         string res;
32.         if(stk.empty()){
33.             res = "/";
34.         }else{
35.             for(int i=0; i<stk.size(); i++){
36.                 res += "/" + stk[i];
37.             }
38.         }
39.         return res;
40.     }
41. };

复制代码

最小栈

设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。
辅助栈

• 入栈时，元素先入普通栈，取当前辅助栈的栈顶与元素比较，再将最小值插入栈顶。
  
• 出栈时，两个一起弹出。
  

1. class MinStack {
2.     stack<int> stk;
3.     stack<int> min_stk;
4. public:
5.     MinStack() {
6.         min_stk.push(INT_MAX);   
7.     }
8.    
9.     void push(int val) {
10.         stk.push(val);
11.         min_stk.push(min(min_stk.top(), val));
12.     }
13.    
14.     void pop() {
15.         stk.pop();
16.         min_stk.pop();
17.     }
18.    
19.     int top() {
20.         return stk.top();
21.     }
22.    
23.     int getMin() {
24.         return min_stk.top();
25.     }
26. };
28. /**
29. * Your MinStack object will be instantiated and called as such:
30. * MinStack* obj = new MinStack();
31. * obj->push(val);
32. * obj->pop();
33. * int param_3 = obj->top();
34. * int param_4 = obj->getMin();
35. */

复制代码

逆波兰表达式求值

1. class Solution {
2. public:
3.     int evalRPN(vector<string>& tokens) {
4.         stack<int> stk;
5.         for(int i=0; i<tokens.size(); i++){
6.             if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
7.                 int num2 = stk.top();
8.                 stk.pop();
9.                 int num1 = stk.top();
10.                 stk.pop();
11.                 if(tokens[i] == "+"){
12.                     stk.push(num1 + num2);
13.                 }else if(tokens[i] == "-"){
14.                     stk.push(num1 - num2);
15.                 }else if(tokens[i] == "*"){
16.                     stk.push(num1 * num2);
17.                 }else{
18.                     stk.push(num1 / num2);
19.                 }
20.             }else{
21.                 stk.push(stoi(tokens[i]));
22.             }
23.         }
24.         return stk.top();
25.     }
26. };

复制代码

基本盘算器

给一个字符串表达式s，请实现一个基本盘算器来盘算并返回它的值。
括号展开+栈
由于字符串除了数字与括号外，只有加号和减号两种运算符。
因此，如果展开表达式中全部的括号，则得到的新表达式中，数字本身不会发生变化，只是每个数字前面的符号会变化。
必要维护一个栈ops，此中栈顶元素记录了当前位置所处的每个括号的符号。
1+2+(3-(4+5))：

• 扫描到1+2时，由于当前位置没有被任何括号所包含，则栈顶元素为初始值+1；
  
• 扫描到1+2+(3时，当前位置被一个括号包含，该括号前面的符号为+号，因此栈顶元素+1
  

1. class Solution {
2. public:
3.     int calculate(string s) {
4.         stack<int> ops;
5.         ops.push(1);
6.         int sign = 1;
8.         int ret = 0;
9.         int i = 0;
10.         int n = s.size();
11.         while(i < n){
12.             if(s[i] == ' '){
13.                 i++;
14.             }else if(s[i] == '+'){
15.                 sign = ops.top();
16.                 i++;
17.             }else if(s[i] == '-'){
18.                 sign = -ops.top();
19.                 i++;
20.             }else if(s[i] == '('){
21.                 ops.push(sign);
22.                 i++;
23.             }else if(s[i] == ')'){
24.                 ops.pop();
25.                 i++;
26.             }else{
27.                 long num = 0;
28.                 while(i < n && s[i] >= '0' && s[i] <= '9'){
29.                     num = num * 10 + s[i]-'0';
30.                     i++;
31.                 }
32.                 ret += sign * num;
33.             }
34.         }
35.         return ret;
36.     }
37. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。