牛杂网这类网站怎么做的,数商云网络科技有限公司,网站广告牌制作教程,上海网站建设seo推广绪论
上周因为有事没有参加周赛#xff0c;这周没有错过。这次周赛拿到了人生第一个AK#xff0c;参加大大小小的比赛这么多次#xff0c;从来没有AK过#xff0c;泪目了。 感觉这次比赛的思维难度对我来讲稍高一些#xff0c;前三道题就花了一个小时#xff0c;而以往…绪论
上周因为有事没有参加周赛这周没有错过。这次周赛拿到了人生第一个AK参加大大小小的比赛这么多次从来没有AK过泪目了。 感觉这次比赛的思维难度对我来讲稍高一些前三道题就花了一个小时而以往只需要半个小时。 看了一下排名前面的大牛们还是十分钟就AK了深觉自己还马达马达大内。
题目分析
比赛链接https://leetcode-cn.com/contest/weekly-contest-286/
题目难度上第二题和第三题都有一些思维量不像以前直接模拟。第四题我直接记忆化搜索在最后一分钟过了当时学习动态规划的时候接触到记忆化搜索对其嗤之以鼻觉得就是弱者想不出来状态转移方程用这种近似暴力的方式来处理。然后现在发现弱者竟是我自己记忆化搜索真香。
A找出两数组的不同
签到题数据量很小也没有仔细想直接两个哈希集合去重并判断每个元素是否在另一个集合出现过没有出现过就添加到结果数组中。
class Solution {
public:vectorvectorint findDifference(vectorint nums1, vectorint nums2) {unordered_setint s1, s2;for (auto x : nums1) s1.insert(x);for (auto x : nums2) s2.insert(x);vectorvectorint ret(2);for (auto x : s1) {if (s2.count(x) 0) ret[0].push_back(x);}for (auto x : s2) {if (s1.count(x) 0) ret[1].push_back(x);}return ret;}
};B美化数组的最少删除数
题目的意思就是偶数位置的元素要和下一个位置的元素不相等。因为只向后看 所以当时想到了一个构造答案的方法首先统计每个数字连续出现的次数x。对于偶数位置ansx-1对于奇数位置ansx-2。最后如果要填充奇数位置则ans因为最后一个位置必须要保证数组的长度为偶数。
class Solution {
public:int minDeletion(vectorint nums) {vectorpairint, int cnt;int n nums.size();for (int i 0; i n; ) {int j i 1;while (j n nums[j] nums[i]) j;cnt.emplace_back(nums[i], j - i);i j;}n cnt.size();int ans 0, x;bool is_even true;for (int i 0; i n; i) {x cnt[i].second;if (is_even) {ans x - 1;is_even false;} else {if (x 1) {is_even true;} else {ans x - 2;}}}if (!is_even) ans;return ans;}
};这样做的正确性在于对于偶数位置他如果连续出现了多次最多只能保留1个。对于奇数位置如果连续出现了多次最多只能保留2个。这里我们每次都选择的是尽可能保留以满足题目中的最短长度。最后我们处理了一下让整个数组的长度为偶数如果下一次要填充的是奇数位置的数字那么说明前面的位置是偶数位置需要将其删除。
接下来我们简单讨论一下为什么尽可能保留数字是最优的。假如某个位置我们可以保留某个数字但是我们将其删光了后面的数字会移动到前面同样需要删除并不能让解更好。详细的证明需要分类讨论之类的这里我们就不求甚解了。
C找到指定长度的回文数
是一个对我来讲有点思维量的模拟我们需要能够构造任意长度第任意大小的回文串。为了能够构造第x大的回文串我们需要使用类似进制转换的思想。 对于相同长度的回文串其值和相对大小是由前面一半的数字支配的后面一半的数字都不用进行考虑。 第一个数字只能是1-9后面的数字每一位都可以是0-9。对于一个回文串长度为intLength他的所有可能结果是maxn9∗10intLength−12maxn 9*10^{\frac{intLength -1}{2}}maxn9∗102intLength−1。如果x大于maxn则直接返回-1。 接下来我们来从前往后确定每一位数字的大小。第一位数字确定后后面的数字有maxn/9种可能。即第1——maxn个回文串的第一位是1第maxn1——2maxn个回文串的第一位是2。为了确定第一位的数字我们可能想要让x/maxn来确定。但是整除需要我们特别处理一下。 因为算数运算默认是从0开始的0——maxn-1 /x都是0。为了寻求这种统一我们不妨给x减一从而可以直接套用算术运算。 对于后面的位数也是同样的道理。总结一下就是为了能够让x对固定步长上面的maxn进行分组我们让x-1从而将原本1——maxn变成了0——manx-1变成了在数值意义上的同一组。 后面取余仍然会从0开始所以我们只用减一一次。
class Solution {using ll long long;ll n_, maxn_, len_;ll work(ll x) {--x;vectorint arr;ll n n_;arr.push_back(x / n 1);x % n;ll len len_;len - 2;while (len 0) {n / 10;arr.push_back(x / n);x % n;len - 2;}ll ret 0;for (auto x : arr) ret ret * 10 x;if (len_ 1) arr.pop_back();int nn arr.size();for (int i nn - 1; i 0; --i) ret ret * 10 arr[i];return ret;}public:vectorlong long kthPalindrome(vectorint queries, int intLength) {len_ intLength;int n (intLength - 1) 1;n_ 1;for (int i 0; i n; i) {n_ * 10;}maxn_ n_ * 9;vectorll ret;for (auto x : queries) {if (x maxn_) ret.push_back(-1);else {ret.push_back(work(x));}}return ret;}};
仔细研究了一下大牛的解法发现我这里处理复杂的原因是没有想到每位填充的也是十进制数字那么x-1maxn就是前一半数字。x-1是第一位从0开始的第x个数字加上maxn就是第一位从1开始的。
D从栈中取出 K 个硬币的最大面值和
我们很容易就可以计算出从一个栈中取m个硬币的面值和那么问题就是我们可以从n个栈中取硬币每个栈可以取0个或多个最终取k个的最大和。想了一下也没有什么状态转移的就直接记忆化搜索了。
class Solution {int n_;vectorvectorint sum;vectorint cnt;vectorvectorint memo;int dfs(int x, int k) {if (x n_) {return sum[x][k];} else {if (memo[x][k] ! -1) return memo[x][k];int kk std::min(k, (int)sum[x].size() - 1);for (int i std::max(0, k - cnt[x]); i kk; i) {memo[x][k] max(memo[x][k], sum[x][i] dfs(x 1, k - i));}}return memo[x][k] -1 ? INT_MIN : memo[x][k];}
public:int maxValueOfCoins(vectorvectorint piles, int k) {int n piles.size();memo.resize(n, vectorint(k 1, -1));n_ n - 1;sum.resize(n);cnt.resize(n);for (int i 0; i n; i) {auto arr piles[i];auto s sum[i];s.push_back(0);for (auto x : arr) {s.push_back(s.back() x);}}int t 0;for (int i n - 1; i 0; --i) {cnt[i] t;t piles[i].size();}return dfs(0, k);}
};
当时最后几分钟写完后一直运行错误我心态有点崩觉得果然又要到此为止了吗。但是还是耐下性子去看代码到底哪里有问题。当时报的是堆上的错误我就觉得是不是哪里数组越界了。认真一看sum、cnt不可能越界那是不是备忘录memo越界了呢仔细一想memo的第二个维度是可以取到k的而我第二个维度的大小只有k于是将第二个维度的大小改成k1就过了。 以前写记忆化搜索都是自己特化一个对pair的哈希然后用unordered_map做这次因为时间不够用的二维数组而之前都没有写过用二维数组进行备忘录所以就没注意过这个问题。
虽然时间紧迫但是我对自己这个记忆化搜索还是挺满意的有备忘录有必要的剪枝代码也很紧凑。 首先初始化了一下memo和sum数组sum[x][k]表示的是第x个栈取k个硬币的面值和memo[x][k]表示的是对于从x到n-1的栈总共取k个硬币的最大面值和最终的答案就是memo[0][k]初始化为-1表示没有进行更新如果memo[x][k]不可能存在则赋值为无穷小。因为我们求的是最大值所以不会用到这个状态。
cnt数组是为了剪枝维护的状态cnt[x]表示从x1到n-1总共有多少个硬币std::max(0,k-cnt[x])就表示第x个栈至少要取多少枚硬币才能够保证从x到n-1能够取到k个硬币std::min(k, (int)sum[x].size()-1)表示第x个栈至多能够取到多少个硬币。
总共最多有O(x)*O(k)2e6个状态每个状态至多求解一次每个状态的求解至多是O(k)因此最坏的时间复杂度是2e9。本来心里有些打鼓但是提交后发现通过了非常开心。
仔细阅读了一下大牛的解法发现是一个01背包问题。感觉自己对背包问题的理解还是不够深刻应该专门再整理一下背包问题的思路。
