Leetcode 701-800
771. Jewels and Stones (Easy)¶
You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
即两个字符串J和S，统计S中在J出现过的字符个数Input: J = "aA", S = "aAAbbbb" Output: 3
思路
哈希表统计即可
int numJewelsInStones(string J, string S) {
vector<int> map(256, 0);
for (auto c : J) map[int(c)] ++;
int answer = 0;
for (auto c : S) if (map[int(c)] > 0) answer ++;
return answer;
}
772. Basic Calculator III (Hard)¶
算术式求值，数字为非负数，包含加减乘除和括号
"1 + 1" = 2 " 6-4 / 2 " = 4 "2*(5+5*2)/3+(6/2+8)" = 21 "(2+6* 3+5- (3*14/7+2)*5)+3"=-12
解法一 递归
不包含整数的例子为227
那么在遇到括号时，递归来求解没有括号的式子，然后继续计算即可，代码如下，相比227解法只添加了递归处理部分
找到括号部分，可以用左括号和右括号数目比较来确定
int calculate(string s) {
long long cur = 0, res = 0, num = 0;
char op = '+';
for (int i = 0; i < s.size(); i ++) {
char c = s[i];
if (c == '(') {
int cnt = 1, j = i;
while (cnt != 0) {
i ++;
if (s[i] == ')') cnt --;
else if (s[i] == '(') cnt ++;
}
num = calculate(s.substr(j + 1, i - j - 1));
}
if (c >= '0' && c <= '9') {
num *= 10;
num += (c - '0');
}
if (c == '+' || c == '-' || c == '*' || c == '/' || i == s.size() - 1) {
switch (op) {
case '+':
cur += num;
break;
case '-':
cur -= num;
break;
case '*':
cur *= num;
break;
case '/':
cur /= num;
break;
}
if (c == '+' || c == '-' || i == s.size() - 1) {
res += cur;
cur = 0;
}
op = c;
num = 0;
}
}
return res;
}
解法二 逆波兰式求值
先将式子转换为逆波兰式，然后求值即可
逆波兰表达式即将运算符号写在两个运算数后面
1 + 2 -> 1 2 +
“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”：先3减去4，再加上5
逆波兰表达式不需要括号，解释过程为：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值
逆波兰式求解之前遇到过150
这里说明如何将中缀表达式转换为逆波兰式
用vector<string> rpn来存储逆波兰式，当遇到数字时，直接加入rpn即可，重点在于遇到操作符和括号时如何处理
对于运算符来说，是否要加入rpn取决于当前运算符优先级是否大于之后出现的运算符，因此要先加入一个运算符栈中，当下一个运算符优先级更低/到达式子结尾时，才将这个运算符出栈
以1+2*3为例，当遇到第一个加号时，不知道是否要加入rpn中，如果是1+2+3，rpn应该为1 2 + 3 +，如果是1+2*3，应该是1 2 3 * +
对于括号来说，遇到左括号入栈即可，不需要进行其它操作，也不影响之后的运算符判断，不过在遇到右括号的时候，应该把上一个左括号到这个右括号之间的运算符都出栈，因为这些运算都当前括号里的运算，需要先执行
具体代码如下，smallerThan是运算符优先级判断
- 当目前运算符是
+或-时，除过栈顶元素是左括号外，一定小于栈顶元素，左括号表示括号内式子的开始，等同于空，只有右括号才负责弹出左括号 - 当前运算符是
*或/时，只有栈顶元素也是乘除时，才将栈顶元素出栈
class Solution {
private:
bool smallerThan(char a, char b) {
if ((a == '-' || a == '+') && (b != '(')) return true;
if ((a == '*' || a == '/') && (b == '*' || b == '/')) return true;
return false;
}
int evalRPN(vector<string>& tokens) {
stack<long long> s;
if (tokens.size() == 0) return 0;
for (string token : tokens) {
if (token == "*") {
long long n2 = s.top(); s.pop();
long long n1 = s.top(); s.pop();
s.push(n1 * n2);
} else if (token == "+") {
long long n2 = s.top(); s.pop();
long long n1 = s.top(); s.pop();
s.push(n1 + n2);
} else if (token == "-") {
long long n2 = s.top(); s.pop();
long long n1 = s.top(); s.pop();
s.push(n1 - n2);
} else if (token == "/") {
long long n2 = s.top(); s.pop();
long long n1 = s.top(); s.pop();
s.push(n1 / n2);
} else {
s.push(stoll(token));
}
}
return s.top();
}
public:
int calculate(string s) {
vector<string> rpn;
stack<char> temp;
int begin = 0;
string num = "";
for (int i = 0; i < s.size(); i ++) {
if (s[i] == ' ') continue;
else if (s[i] >= '0' && s[i] <= '9') num += s[i];
else {
if (num != "") {
rpn.push_back(num);
num = "";
}
if (s[i] == ')') {
while (temp.top() != '(') {
rpn.push_back(string(1, temp.top()));
temp.pop();
}
temp.pop();
} else {
while (!temp.empty()) {
if (smallerThan(s[i], temp.top())) {
rpn.push_back(string(1, temp.top()));
temp.pop();
}
else break;
}
temp.push(s[i]);
}
}
}
if (num != "") rpn.push_back(num);
while (!temp.empty()) {
rpn.push_back(string(1, temp.top()));
temp.pop();
}
return evalRPN(rpn);
}
};
776. Split BST (Medium)¶
给一棵BST及一个值，将小于等于这个值的节点摘除成一棵树，其余节点返回一棵树
Input: root = [4,2,6,1,3,5,7], V = 2 Output: [[2,1],[4,3,6,null,null,5,7]] Explanation: Note that root, output[0], and output[1] are TreeNode objects, not arrays. The given tree [4,2,6,1,3,5,7] is represented by the following diagram: 4 / \ 2 6 / \ / \ 1 3 5 7 while the diagrams for the outputs are: 4 / \ 3 6 and 2 / \ / 5 7 1
迭代1
递归来做，在找到一个值小于等于V的node后，其左半部分一定已经选定，这时需要在右半部分中找其余节点
这里为了调整剩下的树结构，直接将右半部分提上来，同时这里传入祖先节点，更新祖先节点的左孩子
对于root节点，造一个节点指向root节点
TreeNode* helper(TreeNode* parent, TreeNode* root, int V) {
if (root == nullptr) return nullptr;
if (root->val <= V) {
TreeNode* node = new TreeNode(root->val);
node->left = root->left;
parent->left = root->right;
node->right = helper(parent, root->right, V);
return node;
} else return helper(root, root->left, V);
}
vector<TreeNode*> splitBST(TreeNode* root, int V) {
TreeNode* head = new TreeNode(-1);
head->left = root;
return { helper(head, root, V), head->left };
}
迭代2
然后找到另一种更简洁的写法，直接递归来求两部分
这里有幅图有助于思考，其实可以把BST想象成数值从左到右递增的数组，所以这道题就是要求做这样一道分割线
vector<TreeNode*> splitBST(TreeNode* root, int V) {
vector<TreeNode*> res{ nullptr, nullptr };
if (!root) return res;
if (root->val <= V) {
res = splitBST(root->right, V);
root->right = res[0];
res[0] = root;
} else {
res = splitBST(root->left, V);
root->left = res[1];
res[1] = root;
}
return res;
}