专栏首页机器学习入门763. Partition Labels

763. Partition Labels

LWC 67: 763. Partition Labels

Problem:

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = “ababcbacadefegdehijhklij” Output: [9,7,8] Explanation: The partition is “ababcbaca”, “defegde”, “hijhklij”. This is a partition so that each letter appears in at most one part. A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.

Note:

  • S will have length in range [1, 500].
  • S will consist of lowercase letters (‘a’ to ‘z’) only.

思路: 很暴力,直接找可以Partition的位置,如果不能Partition,继续向后搜索直到找到第一个可以Partition的位置为止,这样剩余问题就是原问题的子问题了。

初始版本如下:

    public List<Integer> partitionLabels(String S) {
        List<Integer> ans = new ArrayList<>();
        if (S.length() == 0) return ans;

        char[] cs = S.toCharArray();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        for (; i < cs.length; ++i) {
            sb.append(cs[i]);
            if (part(sb, i, S)) {
                ans.add(sb.length());
                break;
            }
        }

        List<Integer> sub = partitionLabels(S.substring(i + 1));
        for (int hello : sub) ans.add(hello);
        return ans;
    }

    public boolean part(StringBuilder sb, int i, String S) {
        if (sb.toString().isEmpty()) return false;
        for (int j = i + 1; j < S.length(); ++j) {
            String letter = S.substring(j, j + 1);
            if (sb.toString().contains(letter)) return false;
        }
        return true;
    }

再精简一点,因为调用原函数,可以在for循环中完成,所以有:

    public List<Integer> partitionLabels(String S) {
        List<Integer> ans = new ArrayList<>();
        char[] cs = S.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cs.length; ++i) {
            sb.append(cs[i]);
            if (part(sb, i, S)) {
                ans.add(sb.length());
                sb = new StringBuilder();
            }
        }
        return ans;
    }

    public boolean part(StringBuilder sb, int i, String S) {
        if (sb.toString().isEmpty()) return false;
        for (int j = i + 1; j < S.length(); ++j) {
            String letter = S.substring(j, j + 1);
            if (sb.toString().contains(letter)) return false;
        }
        return true;
    }

万幸此答案没有超时,实际上我们还可以采用贪心的做法,降低时间复杂度。上个版本中,还需要计算StringBuilder的字符串中的每个字符是否在后续字符中出现过,实际上没有必要,我们只要记录StringBuilder中的每个字符出现的最后一个位置在哪,这样就避免每次都判断一遍,而是利用字符的最后位置直接判断。其次很重要的一点,字符串的partition的依据是:字符串中每个字符最后出现位置的整体最大值。

Java版本:

    public List<Integer> partitionLabels(String S) {
        List<Integer> ans = new ArrayList<>();
        char[] cs  = S.toCharArray();
        int n = cs.length;
        int[] last = new int[32];
        for (int i = 0; i < n; ++i) {
            last[cs[i] - 'a'] = i;
        }
        int pre = -1;
        int max = 0;
        for (int i = 0; i < n; ++i) {
            if (last[cs[i] - 'a'] > max) max = last[cs[i] - 'a'];
            if (max == i) {
                ans.add(max - pre);
                pre = max;
                max = max + 1;
            }
        }
        return ans;
    }

Python版本:

class Solution(object):
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        lst = {}
        n = len(S)
        for i, c in enumerate(S):
            lst[c] = i
        ans = []
        max = 0
        pre = -1
        for i in range(n):
            if lst[S[i]] > max: max = lst[S[i]]
            if max == i:
                ans.append(max - pre)
                pre = max
                max = max + 1
        return ans

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 4.6平面上的分治法(2)

    指出一点:新的点一定由这些坐标的横纵坐标生成,所以求出投影即能满足条件①,条件②在求解①的过程中自然满足。

    用户1147447
  • LeetCode Weekly Contest 29解题思路

    代码很简单,简单说明下思路就出来了。按照题意,不管怎么二分,整个数组都会被划分成两部分和,这两部分和必然一大一小。如nums = [1,4,3,2],划分如下[...

    用户1147447
  • 3259. Wormholes

    重新回顾了下Bellman-Ford算法,核心思路如下:从单个源点出发,如果经过N轮还在更新时,说明存在负环。证明:假设不存在负环,那么最短路径必然不会经过一个...

    用户1147447
  • POJ1041

    欧拉路问题 本次比赛的水题 对于这题的无向图,要每一个点的度数都为偶数,才存在欧拉回路。 #include<iostream> #include<cstdi...

    triplebee
  • 贪心算法举例分析

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • LeetCode 914. 卡牌分组(最大公约数)

    每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。

    Michael阿明
  • LeetCode Single Number题目分析代码

    Given an array of integers, every element appears twice except for one. Find tha...

    desperate633
  • LightOJ - 1197 区间素数筛模版

    给t给样例,每个样例a,b两个数,求区间[a,b]内素数的个数,(1 ≤ a ≤ b < 2^31, b - a ≤ 100000).

    用户2965768
  • LeetCode Weekly Contest 29解题思路

    代码很简单,简单说明下思路就出来了。按照题意,不管怎么二分,整个数组都会被划分成两部分和,这两部分和必然一大一小。如nums = [1,4,3,2],划分如下[...

    用户1147447
  • LeetCode 45 Jump Game II

    这道题目乍一看,我以为是动态规划。可是LeetCode 从来不给数据范围。,又是hard难度的题目,所以我猜测数组长度至少10万吧。

    ShenduCC

扫码关注云+社区

领取腾讯云代金券