字符串问题-LeetCode 227、387（处理字符串）
字符串问题-LeetCode 227、387（处理字符串）
作者：TeddyZhang，公众号：算法工程师之路
栈问题：LeetCode #227 #387
1
编程题
【LeetCode #227】基本计算器II
实现一个基本的计算器来计算一个简单的字符串表达式的值。 字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。整数除法仅保留整数部分。
示例 1:
输入: "3+2*2" 输出: 7 示例 2: 输入: " 3/2 " 输出: 1
解题思路：
总体思路来说，我们遍历字符串的每个字符，注意：加减乘除以及空格的ASCII码 < '0'。如果这个字符为数字字符，需要将两个非数字字符之间的不包含空格的字符串变换成数值！ 表达式：num = num * 10 - '0' + s[i];
对于非数字字符来说，有三种情况：
- '+': 将这个字符后面的数压入堆栈nums中
- '-': 将这个字符后面的数取反后压入堆栈nums中
- '*' 或 '/': nums.top()为这个符号前面的数，而num为这个符号后面的数，根据符号计算这两个数的值后，再压入堆栈
这样一来，表达式的结果就是最后堆栈内所有数值的和，有一个问题：表达式的第一个值是怎么获取的呢？因为程序中总是将非数字符号后面的值压入堆栈中，但第一个值的前面有符号么？当然有，因为sign的初始化为'+'.
class Solution {
public:
int calculate(string s) {
int res = , num = ;
char sign = '+';
stack<int> nums;
for(int i = ; i < s.size(); i++){
if(s[i] >= '0'){
num = num * - '0' + s[i]; //要先做减法，否则int型会溢出
}
if((s[i] < '0' && s[i] != ' ') || i == s.size() -1){
if(sign == '+'){
nums.push(num);
}
else if(sign == '-'){
nums.push(-num);
}
else if(sign == '*' || sign == '/'){
int tmp = sign == '*' ? nums.top() * num : nums.top() / num;
nums.pop();
nums.push(tmp);
}
sign = s[i];
num = ;
}
}
while(!nums.empty()){
res += nums.top();
nums.pop();
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/basic-calculator-ii
【LeetCode #387】字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = "leetcode" 返回 0. s = "loveleetcode", 返回 2.
注意事项：您可以假定该字符串只包含小写字母。
解题思路：
首先建立一个26大小的数组，使用s[i]-'0'作为索引，一次遍历后，使用数组储存每个字符出现的次数。接着再对字符串进行一次遍历，然后根据字符去数组中查找相应的次数，如果第一次出现次数为1，则返回，否则返回-1.
class Solution {
public:
int firstUniqChar(string s) {
int len = s.size();
if(len == ) return -1;
vector<int> table(, );
for(int i = ; i < len; i++){
table[s[i] - 'a'] ++;
}
for(int i = ; i < len; i++){
if(table[s[i] - 'a'] == ){
return i;
}
}
return -1;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string