第288场周赛
按奇偶性交换后的最大数字
向表达式添加括号后的最小结果
思路
暴力模拟
- 先找加号位置
- 用双指针代替括号的位置，分割字符串
- 写一个计算子串的函数，方便后面使用
- 全部转成int计算
- 存哈希表
- 求value最小的key
代码
class Solution {
public:
int get_value(string e) {
int res = 0, t;
for (int i = 0; i < e.size(); i++) {
res = res * 10 + (e[i] - '0');
if (e[i + 1] == '+') t = res, res = 0, i++;
}
return res + t;
}
static bool cmp_value(const pair<string, int> left, const pair<string,int> right)
{
return left.second < right.second;
}
string minimizeResult(string expression) {
unordered_map<string, int> m;
int len = expression.size(), pos;
int minr = 0x3f3f3f3f;
for (int i = 0; i < len; i++) if (expression[i] == '+') pos = i;
for (int i = 0; i < pos; i ++) {
for (int j = len - 1; j >= pos + 1; j --) {
string a = expression.substr(i, j - i + 1);
string front = expression.substr(0, i);
string back = expression.substr(j + 1, len - j + 1);
int t = get_value(a);
int f = atoi(front.c_str());
int b = atoi(back.c_str());
int ans;
if(f == 0 && b == 0) ans = t;
else if (f == 0) ans = t * b;
else if (b == 0) ans = f * t;
else ans = f * t * b;
string tmp = front + "(" + a + ")" + back;
cout << tmp << endl;
m[tmp] = ans;
}
}
auto i = min_element(m.begin(), m.end(), cmp_value);
return i->first;
}
};
K 次增加后的最大乘积
思路
从样例可以找到规律，只要使得数组当中的每个数都接近相等这个值就是最大的，也就是贪心。可以使用优先队列来修改数。每次都修改那个最小的数，然后重新加入到优先队列里即可。
代码
class Solution {
public:
int maximumProduct(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < nums.size(); i++) {
heap.push(nums[i]);
}
for (int i = 0; i < k; i++) {
int t = heap.top() + 1;
heap.pop();
heap.push(t);
}
long long res = 1;
while (!heap.empty()) {
int t = heap.top();
heap.pop();
res = (res * t) % 1000000007;
}
return res;
}
};