[TOC]
Leetcode 每日一题
好题,题解传送门 。 【dp】+【滚动数组】+【前缀和优化】
【贪心】
分析:
贪心。小的变大,大的变小。故先排序,之后的关键是确定一个位置i
,把0~i-1
之间的都变大k
,i~n-1
之间的都减小k
。
变化后的数组的mx = max(nums[i - 1] + k, nums[n - 1] - k)
,mi = min(nums[0] + k, nums[i] - k)
。(这里有一个点,分段是0~i-1
和i~n-1
,而不是0~i
和i+1~n-1
好处是后续处理的时候,可以不同特判n=1
的情况)。
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int smallestRangeII (vector<int >& nums, int k) { int n = nums.size (); sort (nums.begin (), nums.end ()); int ans = nums[n - 1 ] - nums[0 ], mx, mi; for (int i = 1 ; i < n; ++i) { mx = max (nums[i - 1 ] + k, nums[n - 1 ] - k); mi = min (nums[0 ] + k, nums[i] - k); ans = min (ans, mx - mi); } return ans; } };
分析:
只要不是k>=n
,遍历一遍就有答案了。但是自己sb了妹反应过来
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution {public : int findWinningPlayer (vector<int >& skills, int k) { int n = skills.size (); if (k >= n) return max_element (skills.begin (), skills.end ()) - skills.begin (); int l = 0 , r = 1 , tmp, cnt = 0 ; while (r < n) { if (cnt == k) return l; if (skills[l] < skills[r]) { tmp = r; l = r; r = tmp + 1 ; cnt = 1 ; } else { ++cnt; ++r; } } return l; } };
很典型的一个dp优化。【dp】+【bitset】+【位运算】
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int maxTotalReward (vector<int >& rewardValues) { sort (rewardValues.begin (), rewardValues.end ()); rewardValues.erase (unique (rewardValues.begin (), rewardValues.end ()), rewardValues.end ()); const int maxn = 100010 ; bitset<maxn> dp (1 ) ; int shit; for (const int & x: rewardValues) { shit = maxn - x; dp |= dp << shit >> (shit - x); } for (int i = maxn - 1 ; ; --i) if (dp[i]) return i; } };
官方难度标的是[hard],实际应该是个简单dp。
dp[i][j]
:当前这块长为len的地毯的右界在i,且正好用了j块地毯的情况下,剩下的白色最少为多少。
转移方程:$dp[i][j] = min(dp[i-1][j], dp[i-len][j - 1] - (sum[i] - sum[i - len]))$,其中sum数组是前缀和数组。
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : int minimumWhiteTiles (string floor, int numCarpets, int carpetLen) { int n = floor.size (); int ans = 0 ; vector<int > sum (n + 5 , 0 ) ; floor = '$' + floor; for (int i = 1 ; i <= n; ++i) ans += (floor[i] == '1' ), sum[i] = ans; vector<vector<int > > dp (n + 5 , vector <int >(numCarpets + 5 , ans)); for (int i = 1 ; i <= carpetLen; ++i) { for (int j = 1 ; j <= numCarpets; ++j) dp[i][j] -= sum[i]; } for (int i = carpetLen + 1 ; i <= n; ++i) { for (int j = 1 ; j <= numCarpets; ++j) { dp[i][j] = min (dp[i - carpetLen][j - 1 ] - (sum[i] - sum[i - carpetLen]), dp[i - 1 ][j]); } } return dp[n][numCarpets]; } };
我真是个笨比。
分析:
法一:有序集合(set
)
思路很简单,就是两个unordered_map
,一个是food→{rating,cuisine}
,另一个是cuisine→set{rating,food}
。但是自己写的太蠢了,很多细节不到位,常熟也比较大,T
了。
法二:懒删除堆(priority_queue
)
就是第二个数据结构改成一个堆,但是只插入不删除,只有在查询的时候,获取堆顶元素的时候,判断当前元素是否已经被删除,所以叫懒删除堆,很形象。
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class FoodRatings {private : unordered_map<string, pair<int , string>> food_mp; unordered_map<string, set<pair<int , string>>> cuisine_mp; public : FoodRatings (vector<string>& foods, vector<string>& cuisines, vector<int >& ratings) { int n = foods.size (); for (int i = 0 ; i < n; ++i) { auto & food = foods[i]; auto & cuisine = cuisines[i]; int rating = ratings[i]; food_mp[food] = {rating, cuisine}; cuisine_mp[cuisine].emplace (-rating, food); } } void changeRating (string food, int newRating) { auto & [rating, cuisine] = food_mp[food]; auto & st = cuisine_mp[cuisine]; st.erase ({-rating, food}); st.emplace (-newRating, food); rating = newRating; } string highestRated (string cuisine) { return cuisine_mp[cuisine].begin ()->second; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class FoodRatings {private : using pis = pair<int , string>; unordered_map<string, pis> food_mp; unordered_map<string, priority_queue<pis, vector<pis>, greater<>>> cuisine_mp; public : FoodRatings (vector<string>& foods, vector<string>& cuisines, vector<int >& ratings) { int n = foods.size (); for (int i = 0 ; i < n; ++i) { auto & food = foods[i]; auto & cuisine = cuisines[i]; int rating = ratings[i]; food_mp[food] = {rating, cuisine}; cuisine_mp[cuisine].emplace (-rating, food); } } void changeRating (string food, int newRating) { auto & [rating, cuisine] = food_mp[food]; cuisine_mp[cuisine].emplace (-newRating, food); rating = newRating; } string highestRated (string cuisine) { auto & pq = cuisine_mp[cuisine]; while (-pq.top ().first != food_mp[pq.top ().second].first) pq.pop (); return pq.top ().second; } };
tips:
unordered_map
比map
快,unordered_map
比map
快,unordered_map
比map
快。
对于字符串、容器等比较巨大的数据结构,以后直接用引用吧auto&
。
emplace
是push_back
和insert
的上位替代。
对于那种,需要按第一关键字升序,第二关键字降序的那种,把另一关键字存成负的,这样对两个关键字的排序就统一了(方便set
, priority_queue
等容器)。
erase
有很多种用法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 std::set<int > st = {1 , 2 , 3 , 4 , 5 }; st.erase (3 ); std::set<int > st = {1 , 2 , 3 , 4 , 5 }; auto it = st.find (3 ); if (it != st.end ()) { st.erase (it); } std::set<int > st = {1 , 2 , 3 , 4 , 5 }; auto it1 = st.find (2 ); auto it2 = st.find (4 ); st.erase (it1, it2);
priority_queue
相关。
1 2 priority_queue<int > pq; priority_queue<int , vector<int >, greater<>> pq;
懒删除堆。很形象的名字,对于那些有删除需求,但又是弱删除的数据结构很有意义。
分析:
置换: 一个排列到另一个排列的双射。
定义一个置换$P(x)$,将$nums_1$转化为一个递增的排列,$nums_2$同样需要通过$P(x)$映射。
置换不是排序,是映射 (可以理解成重命名 ),原来的公共子序列在映射后,子序列元素的位置没变 ,只是数值变了,仍然是公共子序列。所以置换不会改变公共子序列的个数 。
此时,只需要枚举三元组中间 的元素$y$即可。而$nums_1$是递增的,所以问题转化为求$nums_2$中长度为3,中间元素为$y$的递增子序列的数量$num_y$。假设元素$y$位于位置$i$,左侧小于$y$的元素数量为$less_y$,而右侧大于$y$的元素数量为$more_y$。那么,$num_y = less_y * more_y$,而$more_y = n - 1 - y - (i - less_y)$。
求解$less_y$的过程利用值域树状数组 非常方便(类似于求逆序对)。需要注意的是,这是的排列是从0开始的,而树状数组下标是从1开始的,要加1。
思路来源 。
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 template <typename T>class FenwickTree { vector<T> tree; public : FenwickTree (int n) : tree (n + 1 ) {} void update (int i, T val) { for (; i < tree.size (); i += i & -i) { tree[i] += val; } } T pre (int i) const { T res = 0 ; for (; i > 0 ; i &= i - 1 ) { res += tree[i]; } return res; } }; class Solution {public : long long goodTriplets (vector<int >& nums1, vector<int >& nums2) { int n = nums1. size (); vector<int > p (n + 5 , 0 ) ; for (int i = 0 ; i < n; ++i) p[nums1[i]] = i + 1 ; long long ans = 0 ; FenwickTree<int > t (n) ; for (int i = 0 ; i < n - 1 ; i++) { int y = p[nums2[i]]; int less = t.pre (y - 1 ); ans += 1LL * less * (n - y - (i - less)); t.update (y, 1 ); } return ans; } };
分析:
子数组越长,越能满足题意。枚举子数组右端点r
,当子数组满足条件时,不停的将nums[l]
从子数组中移除,即++l
。
属于是「越长越合法」型滑动窗口 ,存在一个一般模板:
维护一个有条件的滑动窗口
右端点右移,导致窗口扩大,满足条件
左端点右移,缩小窗口,找到右端点固定情况下,左端点的最右值(窗口大小的最小值)。
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : int countCompleteSubarrays (vector<int >& nums) { unordered_set<int > st (nums.begin(), nums.end()) ; int n = st.size (); unordered_map<int , int > mp; int ans = 0 ; int l = 0 ; for (const auto & x : nums) { ++mp[x]; while (mp.size () == n) { int y = nums[l]; if (--mp[y] == 0 ) mp.erase (y); ++l; } ans += l; } return ans; } };
分析:
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : string pushDominoes (string dominoes) { int n = dominoes.size (); int pre = -1 ; char ch; for (int i = 0 ; i <= n; ++i) { ch = i < n ? dominoes[i] : 'R' ; if (ch == '.' ) continue ; if (ch == (pre < 0 ? 'L' : dominoes[pre])) fill (dominoes.begin () + pre + 1 , dominoes.begin () + i, ch); else if (ch == 'L' ) { fill (dominoes.begin () + pre + 1 , dominoes.begin () + (pre + i + 1 ) / 2 , 'R' ); fill (dominoes.begin () + (pre + i) / 2 + 1 , dominoes.begin () + i, 'L' ); } pre = i; } return dominoes; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution {public : string pushDominoes (string dominoes) { int n = dominoes.size (); queue<int > q; vector<int > time (n, -1 ) ; vector<string> force (n) ; for (int i = 0 ; i < n; ++i) { if (dominoes[i] != '.' ) { q.emplace (i); time[i] = 0 ; force[i].push_back (dominoes[i]); } } string res (n, '.' ) ; int id, nxt, t; char ch; while (!q.empty ()) { id = q.front (); q.pop (); if (force[id].size () == 1 ) { ch = force[id][0 ]; res[id] = ch; nxt = (ch == 'L' ) ? (id - 1 ) : (id + 1 ); if (nxt >= 0 && nxt < n) { t = time[id]; if (time[nxt] == -1 ) { q.emplace (nxt); time[nxt] = t + 1 ; force[nxt].push_back (ch); } else if (time[nxt] == t + 1 ) force[nxt].push_back (ch); } } } return res; } };
分析:
dp[i][j]
为前i-1
列铺满,i
列为状态j
的情况下,一共有多少种方法。图片来源
还可以用矩阵快速幂加速,初始时dp[0]
对应的列向量为$x = [0 \ 0 \ 0 \ 1]^T$,n
次转移后,dp[n]
对应的$A^nx$。由此需要确定$A$,根据转移方程易得:
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 const long long mod = 1e9 + 7 ;class Solution {public : int numTilings (int n) { vector<vector<long long >> dp (n + 5 , vector <long long >(4 , 0 )); dp[0 ][3 ] = 1 ; for (int i = 1 ; i <= n; ++i) { dp[i][0 ] = dp[i - 1 ][3 ]; dp[i][1 ] = (dp[i - 1 ][0 ] + dp[i - 1 ][2 ]) % mod; dp[i][2 ] = (dp[i - 1 ][0 ] + dp[i - 1 ][1 ]) % mod; dp[i][3 ] = (dp[i - 1 ][0 ] + dp[i - 1 ][1 ] + dp[i - 1 ][2 ] + dp[i - 1 ][3 ]) % mod; } return dp[n][3 ]; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 const long long mod = 1e9 + 7 ;class Solution {public : vector<vector<long long >> mulMatrix (const vector<vector<long long >> &a, const vector<vector<long long >> &b) { int m = a.size (), k = b.size (), n = b[0 ].size (); vector<vector<long long >> res (m, vector <long long >(n)); for (int i = 0 ; i < m; ++i) { for (int j = 0 ; j < n; ++j) { for (int kk = 0 ; kk < k; ++kk) { res[i][j] = (res[i][j] + a[i][kk] * b[kk][j]) % mod; } } } return res; } int numTilings (int n) { vector<vector<long long >> mat = { {0 , 0 , 0 , 1 }, {1 , 0 , 1 , 0 }, {1 , 1 , 0 , 0 }, {1 , 1 , 1 , 1 } }; vector<vector<long long >> matn = { {1 , 0 , 0 , 0 }, {0 , 1 , 0 , 0 }, {0 , 0 , 1 , 0 }, {0 , 0 , 0 , 1 } }; while (n) { if (n & 1 ) matn = mulMatrix (matn, mat); mat = mulMatrix (mat, mat); n >>= 1 ; } return matn[3 ][3 ]; } };