侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【字符串, 贪心】根据模式串构造最小数字

GabrielxD
2022-08-17 / 0 评论 / 0 点赞 / 51 阅读 / 851 字 / 正在检测是否收录...

题目

2375. 根据模式串构造最小数字
484. 寻找排列


给你下标从 0 开始、长度为 n 的字符串 pattern ,它包含两种字符,'I' 表示 上升 ,'D' 表示 下降 。

你需要构造一个下标从 0 开始长度为 n + 1 的字符串,且它要满足以下条件:

  • num 包含数字 '1' 到 '9' ,其中每个数字 至多 使用一次。
  • 如果 pattern[i] == 'I' ,那么 num[i] < num[i + 1] 。
  • 如果 pattern[i] == 'D' ,那么 num[i] > num[i + 1] 。

请你返回满足上述条件字典序 最小 的字符串 num

示例 1:

输入:pattern = "IIIDIDDD"
输出:"123549876"
解释:
下标 0 ,1 ,2 和 4 处,我们需要使 num[i] < num[i+1] 。
下标 3 ,5 ,6 和 7 处,我们需要使 num[i] > num[i+1] 。
一些可能的 num 的值为 "245639871" ,"135749862" 和 "123849765" 。
"123549876" 是满足条件最小的数字。
注意,"123414321" 不是可行解因为数字 '1' 使用次数超过 1 次。

示例 2:

输入:pattern = "DDD"
输出:"4321"
解释:
一些可能的 num 的值为 "9876" ,"7321" 和 "8742" 。
"4321" 是满足条件最小的数字。

提示:

  • 1 <= pattern.length <= 8
  • pattern 只包含字符 'I' 和 'D'

解题

方法一:贪心

思路

首先考虑一个极端情况:当 pattern 中全为 'I' 时,构造出来的字符串应该是 "1234……",而当 pattern 中出现一段 'D' 的时候,为了保证构造出的字符串字典序最小,需要从这一段中第一个 'D' 出现的位置到最后一个 'D' 出现的位置填充逆序的数字,举个例子:

如果 pattern = "IIIDDD",那么:

image-20220817204805864

按照这个思路可以想出很多种构造字符串的方法,我们这里选择逆序部分字符串:

看图可以发现规律,最终构造出的字符串 "1237654" 可以看作是把字符串 "1234567""4567" 部分逆序而成的。

那么就可以找到规律:对于长度为 npattern 可以先初始化一个 1~n+1 的字符串(ans)(长度为 n+1),然后遍历 pattern 找到每一段逆序部分的开始(start)和结束(end)索引,然后把 ansstartend+1 部分逆序即可。


参考:【力扣周赛 306】数位 DP 通用模板 | LeetCode 算法刷题 - 第三题 贪心 优雅做法

代码

class Solution {
    char[] ans;

    public String smallestNumber(String pattern) {
        int n = pattern.length();
        ans = new char[n + 1];
        for (int i = 0; i <= n; ++i) ans[i] = (char) (i + '1');
        for (int i = 0; i < n; ++i) {
            if (pattern.charAt(i) == 'D') {
                int start = i;
                while (i < n && pattern.charAt(i) == 'D') ++i;
                reversePart(start, i);
            }
        }
        return String.valueOf(ans);
    }

    void reversePart(int start, int end) {
        while (start < end) {
            char tmp = ans[start];
            ans[start] = ans[end];
            ans[end] = tmp;
            ++start;
            --end;
        }
    }
}
class Solution {
public:
    string smallestNumber(string pattern) {
        int n = pattern.length();
        string ans;
        ans.resize(n + 1);
        for (int i = 0; i <= n; ++i) ans[i] = i + '1';
        for (int i = 0; i < n; ++i) {
            if (pattern[i] == 'D') {
                int start = i;
                while (i < n && pattern[i] == 'D') ++i;
                reverse(ans.begin() + start, ans.begin() + i + 1);
            }
        }
        return ans;
    }
};
0

评论区