avatar

Leetcode-202010

LCP 19. 秋叶收藏集 - 20201001

小扣出去秋游,途中收集了一些红叶和黄叶,他利用这些叶子初步整理了一份秋叶收藏集 leaves, 字符串 leaves 仅包含小写字符 r 和 y, 其中字符 r 表示一片红叶,字符 y 表示一片黄叶。
出于美观整齐的考虑,小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等,但均需大于等于 1。每次调整操作,小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕

正值双节,力扣来了个开幕雷击,这种题还是有难度,从题解来分析吧。

动态规划

题解中有提到一个词 - 示性函数,其实就是一个结果为二元的函数,或者说布尔函数,这个问题不大,主要是对状态的分析,题解使用了f[i][j]来存储状态,最后取f[n-1][2]来作为return。

其中j可以为0、1、2,分别表示头部的红、中间的黄、和尾部的红,然后对每个j进行分析

  • j == 0,这个是最简单的,只需要把第i片叶子变成红色,题解的说明可能不太明了,其实这时候的意思是,f[i][j]是如果第i片叶子应该是头部红的话至此应该操作的次数。然后f[i][0] = f[i-1][0] + isYellow(i),因为第i片叶子需要是头部红,所以前面的叶子也应该是头部红,加上的就是f[i-1][0]
  • j == 1,第i - 1片叶子既可以是头部红又可以是中间黄,取其中最小的就可以,直接写f[i][1] = f[i-1][0] + isRed(i)
  • j == 2,稍微复杂一些,第i - 1片叶子既可以是中间黄又可以是尾部红,但是不能是头部黄(即不能跳过中间黄的状态,题目要求3种状态各个至少为1),f[i][2] = min(f[i-1][1], f[i-1][2]) + isYellow(i)
class Solution {
public:
int minimumOperations(string leaves) {
int n = leaves.size();
vector<vector<int>> f(n, vector<int>(3));
f[0][0] = (leaves[0] == 'y');
f[0][1] = f[0][2] = f[1][2] = INT_MAX; // 使用一个上限
int isRed, isYellow;
for (int i = 1; i < n; i++) {
isRed = (leaves[i] == 'r');
isYellow = (leaves[i] == 'y');
f[i][0] = f[i-1][0] + isYellow;
f[i][1] = min(f[i-1][0], f[i-1][1]) + isRed;
if (i >= 2) f[i][2] = min(f[i-1][1], f[i-1][2]) + isYellow; // 保证i是在第3片叶子开始才判断有无尾部红
}

return f[n-1][2];
}
};

image-20201001225313743

但是空间复杂度为O(n),可以简化状态存储,仔细查看上面的代码,所谓f[i-1]不过是上一次的f,并无必要开一个双重数组,使用一个vector<int>f(3)即可,使用以下代码。

class Solution {
public:
int minimumOperations(string leaves) {
int n = leaves.size();
vector<int> f(3);
f[0] = (leaves[0] == 'y');
f[1] = f[2] = INT_MAX;
int isRed, isYellow;
for (int i = 1; i < n; i++) {
isRed = (leaves[i] == 'r');
isYellow = (leaves[i] == 'y');
if(i >= 2) f[2] = min(f[1], f[2]) + isYellow;
f[1] = min(f[0], f[1]) + isRed;
f[0] += isYellow;
}
return f[2];
}
};

image-20201001225849353

771. 宝石与石头 - 20201002

给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此”a”和”A”是不同类型的石头。

示例 1:

输入: J = “aA”, S = “aAAbbbb”
输出: 3

示例 2:

输入: J = “z”, S = “ZZ”
输出: 0

注意:

S 和 J 最多含有50个字母。
J 中的字符不重复。

水题,但是可以学习一下bitset,C++中的bitset类似封装过的bitmap,内存小,可以作为bool数组使用,(原来8位的bool现在只需要1位)。bitset不仅可以像一个int一样进行位运算,还有一些实例函数可以使用。

初始化方法: bitset<size> name(to_int_size)

size是指bitset长度,to_int_size是作为int的大小,

c.size()      // 返回大小(位数)
c.count() // 返回1的个数
c.any() // 返回是否有1
c.none() // 返回是否没有1
c.set() // 全都变成1
c.set(p) // 将第p + 1位变成1
c.set(p, x) // 将第p + 1位变成x
c.reset() // 全都变成0
c.reset(p) // 将第p + 1位变成0
c.flip() // 全都取反
c.flip(p) // 将第p + 1位取反
c.to_ulong() // 返回它转换为unsigned long的结果,如果超出范围则报错
c.to_ullong() // 返回它转换为unsigned long long的结果,如果超出范围则报错
c.to_string() // 返回它转换为string的结果
// 来源: https://blog.csdn.net/Q1410136042/article/details/82119599
class Solution {
public:
int numJewelsInStones(string J, string S) {
bitset<128> arr(0);
for (char i : J)
arr[(int)i] = 1;
int ret = 0;
for (char i : S)
if (arr[(int) i]) ret++;
return ret;
}
};
文章作者: X Mεl0n
文章链接: http://www.zrzz.site/2020/10/01/Leetcode-202010/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 X Mεl0n | 随手记

评论