第286场Leetcode周赛题解
上周的周赛因个人原因未进行更新，实属抱歉，废话不说，直接切入主题吧。
1、找出两数组的不同
https://leetcode-cn.com/problems/find-the-difference-of-two-arrays/
涉及到的知识点：cpp中对set等容器的运用（因为这道题目较为简单，因此不同方法涉及到的知识点将会不同。因为本人主写cpp，所以有时候写的非算法知识点会更偏向于cpp）
解题思路：模拟
class Solution {public:vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> results;set<int> s1 = set<int>(nums1.begin(), nums1.end());set<int> s2 = set<int>(nums2.begin(), nums2.end());vector<int> re1, re2;set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(re1, re1.begin()));set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(), inserter(re2, re2.begin()));return {re1, re2};}};
另外讲一下，熟悉cpp的同学都知道有个插入迭代器inserter，可以不断的插入到指定的容器中。代码中的第8行和第9行中的第四个参数就使用了一个inserter，来将结果不断插入到新的容器中。
2、美化数组的最少删除数
https://leetcode-cn.com/problems/minimum-deletions-to-make-array-beautiful/
涉及知识点：双指针的运用
解题思路：声明两个变量分别用来保存被删除后的数组的最后一个元素以及一个从前往后不断遍历的索引。
class Solution {public:int minDeletion(vector<int>& nums) {int result = 0;if (nums.size() == 1) {return 1;}int left = 0;int right = 1;while (right < nums.size()) {// 如果是奇数if (left % 2 == 1) {left++;nums[left] = nums[right];right++;} else {if (nums[left] == nums[right]) {result++;right++;} else {left++;nums[left] = nums[right];right++;}}}// 因为美丽数组的长度必须为偶数，注意下标是从0开始if ((left % 2) == 0) {result++;}return result;}};
3、找到指定长度的回文数
https://leetcode-cn.com/problems/find-palindrome-with-fixed-length/
这道题目是一道技巧题，可以认为是一题规律题。
解题思路：模拟、找规律
举个例子：当intLength=5
10001(100)
10101(101)
10201(102)
...
99099(99)
上面是当intLength=5时，所有的回文数。仔细看括号里面的数字是呈一个递增的，然后再将前两个数字进行反转。解这道题的时候一定要抓住回文数对称的特点。
这样我们只需要算出在特定intLength情况下，括号内的最小值和最大值即可。
min_value = pow(10, (intLength - 1) / 2)
max_value = pow(10, (intLength + 1) / 2) - 1
num = 9 * pow(10, (intLength - 1) / 2)
其中num为回文数的个数。如果queries中的数字超过了num，则不存在这样的回文数，返回-1。在算queries中的第queries[i]个回文数时，只需要求出min_value + queries[i] - 1即可，然后再进行反转。
class Solution {public:vector<long long> kthPalindrome(vector<int>& queries, int intLength) {vector<long long> answer(queries.size());long long min = (long long)pow(10, (intLength - 1) / 2);long long max = (long long)pow(10, (intLength + 1) / 2) - 1;long long num = 9 * (long long)pow(10, (intLength - 1) / 2);for (int i = 0; i < queries.size(); ++i) {if (queries[i] > num) {answer[i] = -1;continue;}int tmp = min + queries[i] - 1;string s = to_string(tmp);if (intLength % 2 == 0) {string new_s = s;reverse(new_s.begin(), new_s.end());s += new_s;} else {string new_s = s.substr(0, s.size() - 1);reverse(new_s.begin(), new_s.end());s += new_s;}istringstream is(s);is >> answer[i];}return answer;}};
本题需要注意的点：
1、注意溢出问题
2、在进行反转的时候，上面的代码中借用了string来进行反转。这里依旧又个数值溢出问题。通常来说，string转换成整型，一般使用stoi方法，该方法只能将string转换成int。显然，在本题中会产生溢出，因此在本代码中使用了字符串流（不懂得请移步c++ primer），从而避免了溢出问题。
4、从栈中取出k个硬币的最大面值和
https://leetcode-cn.com/problems/maximum-value-of-k-coins-from-piles/
涉及到的知识点：背包问题
解题思路：可以将该问题转换为分组的01背包问题。
分别求得每个栈的前缀和，得到若干个pile[i]。问题转换为：在一个体积大小为k的背包中放入若干个体积为i的pile[i]，求价值最高的一种方案。
状态转移方程：
dp[j] = max(dp[j], dp[j - w]+piles[w])
其中dp[j]表示取出次数为j的最大硬币面值。
class Solution {public:int min(int a, int b) {return a < b ? a : b;}int maxValueOfCoins(vector<vector<int>>& piles, int k) {vector<int> dp(k + 1);int sumN = 0;for (auto pile: piles) {for (int i = 1; i < pile.size(); ++i) {pile[i] += pile[i - 1];}sumN = min(sumN + pile.size(), k);for (int j = sumN; j > 0; --j) {for (int w = 0; w < min(j,pile.size()); ++w) {dp[j] = max(dp[j], dp[j - (w + 1)] + pile[w]);}}}return dp[k];}};
注意：第16行中的状态转移方程为什么是（w + 1),因为我们在求前缀和的时候，pile[0]表示的是第一个物品的面值。因此w等于0的时候，相当于取出一次，因此要+1。
本周的周赛题解就到此为止了，需要好好消化。