【稀土掘金AI刷题】简单四则运算 两个数列

简单四则运算

问题描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。注意事项如下：

• 输入是一个字符串表达式（可以假设所给定的表达式都是有效的）

• 字符串表达式可以包含的运算符号为：左括号 (, 右括号 ), 加号 +, 减号 -

• 可以包含的数字为：非负整数（< 10）

• 字符串中不包含空格

• 处理除法 case 的时候，可以直接省略小数部分结果，只保留整数部分参与后续运算

• 请不要使用内置的库函数 eval

输入格式

如：3+4*5/(3+2)

数据约束

见题目描述

输出格式

计算之后的数字

输入样例：

• 1+1
• 3+4*5/(3+2)
• 4+2*5-2/1
• (1+(4+5+2)-3)+(6+8)

输出样例：

• 2
• 7
• 12
• 23

思路

这种有层级且相邻层级之间有关系的可以使用栈stack来解决，我们定义一个nums栈用来存数字，ops栈来存加减乘除等操作。我们使用for循环来遍历输入的字符串表达式，如果这个字符是数字就压栈到nums中，如果是操作就压栈到ops中，这是我们最初的想法，但在表达式中有（）和乘除与加减之间的优先级的操作，那么该如何解决呢？对于（）和乘除与加减之间的运算级的优先问题，我们可以通过提前运算来解决。那么在压栈时，我们就要把运算符区分开来，遇见（我们就压进去，当遇见）时我们就要把括号之间的数都算赶紧再继续操作，遇见普通的加减乘除的运算符就要和栈顶比较运算级，如果栈顶的运算优先级大，我们就先处理已经入栈的表达式直到栈顶运算级较小为止。

代码实现（C++)

#include <iostream>
#include <string>
#include <stack>using namespace std;// 函数说明：判断字符c是否为数字
bool isDigit(char c) { return c >= '0' && c <= '9'; }// 函数说明：将字符c由char转换为int
int char2int(char c) { return c - '0'; }// 函数说明：由操作符operate决定a，b之间的运算并返回结果
double calculate(double a, double b, char operate)
{switch(operate){case '+': return a + b;case '-': return a - b;case '*': return a * b;case '/': return a / b;}return -1;  // if error
}// 函数说明：由运算符返回运算符等级
int precedence(char c)
{if (c == '*' || c == '/'){return 1;}else return 0;
}// 函数说明：由输入的字符串表达式运算返回double类型的结果（主要算法函数）
double solution(const std::string expression)
{// 定义栈stack<double> nums;	// 存数的stack<char> ops;	// 存运算等级的// 遍历表达式的每个字符for (int i = 0; i < expression.size(); ++i){char c = expression[i];if (isDigit(c)){int num = char2int(c);nums.push(num);}else if (c == '('){ops.push(c);}else if (c == ')'){while (ops.top() != '('){double b = nums.top();nums.pop();double a = nums.top();nums.pop();nums.push(calculate(a, b, ops.top()));ops.pop();}ops.pop();}else{while (!ops.empty() && ops.top() != '(' && precedence(c) <= precedence(ops.top())) {double b = nums.top();nums.pop();double a = nums.top();nums.pop();nums.push(calculate(a, b, ops.top()));ops.pop();}ops.push(c);}}// 运算剩余栈内表达式while (!ops.empty()){double b = nums.top();nums.pop();double a = nums.top();nums.pop();nums.push(calculate(a, b, ops.top()));ops.pop();}return nums.top();
}int main()
{// You can add more test cases herecout << (solution("1+1") == 2) << endl;cout << (solution("3+4*5/(3+2)") == 7) << endl;cout << (solution("4+2*5-2/1") == 12) << endl;cout << (solution("(1+(4+5+2)-3)+(6+8)") == 23) << endl;return 0;
}

两个数列

问题描述

给定长度分别为 n 和 m 的两个数列a[n]、b[m]，和一个整数k。求|(a[i] - b[j])^2 - k^2|的最小值。

输入格式

第一行有 2 个整数 n、m、k，分别表示数列 a、b 的长度，以及公式中的整数 k。

第二行有 n 个整数，表示数列 a 的各个元素。

第三行有 m 个整数，表示数列 b 的各个元素。

输出格式

求上述公式的最小值。

数据范围

其中 20%的数据：1 <= n,m <= 3000，-10^9 <= a[i], b[j], k <= 10^9，for all i, j

其中 30%的数据：1 <= n,m <= 50000，k = 0，-10^9 <= a[i], b[j] <= 10^9，for all i, j

其中 50%的数据：1 <= n,m <= 50000，-10^9 <= a[i], b[j], k <= 10^9，for all i, j

输入样例

5 5 1
5 3 4 1 2
0 6 7 9 8

5 5 0
5 3 4 1 2
0 6 7 9 8

输出样例

0
1

思路

这个问题可以使用暴力枚举的方法解决。首先，我们可以将所有可能的 (i, j) 组合存储在一个列表中。然后，对于列表中的每个 (i, j)，我们可以计算值，并将其与当前的最小值进行比较。如果计算出的值小于当前的最小值，那么我们就更新最小值。

在实际代码中，我们可以使用两个嵌套循环来枚举所有可能的 (i, j) 组合，并使用一个变量来存储当前的最小值。在每次计算出 (i, j)的值后，我们可以使用 abs() 函数来计算差的绝对值，然后将其与当前的最小值进行比较。如果计算出的值小于当前的最小值，那么我们就更新最小值。

源码（C++）

#include <iostream>
#include <vector>
#include <algorithm>int min(int a, int b) {return a > b ? b : a;
}int solution(std::vector<std::vector<int>> cases) {int n = cases[0][0], m = cases[0][1], k = cases[0][2];std::vector<int> a(n), b(m);for (int i = 1; i <= n; ++i) {a[i - 1] = cases[1][i - 1];}for (int i = 1; i <= m; ++i) {b[i - 1] = cases[2][i - 1];}int min_val = INT_MAX;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {int diff = a[i] - b[j];int sq_diff = diff * diff;int abs_diff = abs(sq_diff - k * k);min_val = min(min_val, abs_diff);}}return min_val;
}int main() {std::vector<std::vector<int>> case1 = {{5, 5, 1}, {5, 3, 4, 1, 2}, {0, 6, 7, 9, 8}};std::vector<std::vector<int>> case2 = {{5, 5, 0}, {5, 3, 4, 1, 2}, {0, 6, 7, 9, 8}};std::cout << (solution(case1) == 0) << std::endl;std::cout << (solution(case2) == 1) << std::endl;return 0;
}