侧边栏壁纸
博主头像
GabrielxD

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

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

目 录CONTENT

文章目录

【贪心算法, 哈希表】子字符串的最优划分【力扣第 310 场周赛】

GabrielxD
2022-09-12 / 0 评论 / 0 点赞 / 84 阅读 / 677 字 / 正在检测是否收录...

题目

6177. 子字符串的最优划分


给你一个字符串 s ,请你将该字符串划分成一个或多个 子字符串 ,并满足每个子字符串中的字符都是 唯一 的。也就是说,在单个子字符串中,字母的出现次数都不超过 一次

满足题目要求的情况下,返回 最少 需要划分多少个子字符串*。*

注意,划分后,原字符串中的每个字符都应该恰好属于一个子字符串。

示例 1:

输入:s = "abacaba"
输出:4
解释:
两种可行的划分方法分别是 ("a","ba","cab","a") 和 ("ab","a","ca","ba") 。
可以证明最少需要划分 4 个子字符串。

示例 2:

输入:s = "ssssss"
输出:6
解释:
只存在一种可行的划分方法 ("s","s","s","s","s","s") 。

提示:

  • 1 <= s.length <= 10^5
  • s 仅由小写英文字母组成

解题

方法一:贪心 哈希表

思路

维护一个哈希表(set)表示一个分组中的字符。

遍历字符串,如果哈希表中已经存在当前的字符,那它们就不能分在同一组,遂把分组计数加一,把哈希表清空。然后把当前字符加入哈希表表示放入该分组。

代码

class Solution {
    public int partitionString(String s) {
        Set<Character> set = new HashSet<>();
        int cnt = 1;
        for (char ch : s.toCharArray()) {
            if (set.contains(ch)) {
                ++cnt;
                set.clear();
            }
            set.add(ch);
        }
        return cnt;
    }
}
class Solution {
public:
    int partitionString(string s) {
        unordered_set<char> st;
        int cnt = 1;
        for (char ch : s) {
            if (st.find(ch) != st.end()) {
                ++cnt;
                st.clear();
            }
            st.insert(ch);
        }
        return cnt;
    }
};

因为只会出现小写字母(只有 26 种情况),所以可以拿一个长度 26 的布尔数组代替哈希表记录字符是否出现。

class Solution {
    public int partitionString(String s) {
        boolean[] has = new boolean[26];
        int cnt = 1;
        for (char ch : s.toCharArray()) {
            int curr = ch - 'a';
            if (has[curr]) {
                ++cnt;
                Arrays.fill(has, false);
            }
            has[curr] = true;
        }
        return cnt;
    }
}
class Solution {
public:
    int partitionString(string s) {
        vector<bool> has(26);
        int cnt = 1;
        for (char ch : s) {
            int curr = ch - 'a';
            if (has[curr]) {
                ++cnt;
                has.clear();
                has.resize(26);
            }
            has[curr] = true;
        }
        return cnt;
    }
};

使用位运算优化:

class Solution {
    public int partitionString(String s) {
        int has = 0, cnt = 1;
        for (char ch : s.toCharArray()) {
            int curr = ch - 'a';
            if ((has & (1 << curr)) > 0) {
                ++cnt;
                has = 0;
            }
            has |= (1 << curr);
        }
        return cnt;
    }
}
class Solution {
public:
    int partitionString(string s) {
        int has = 0, cnt = 1;
        for (char ch : s) {
            int curr = ch - 'a';
            if (has & (1 << curr)) {
                ++cnt;
                has = 0;
            }
            has |= (1 << curr);
        }
        return cnt;
    }
};
0

评论区