LetCode in Swift (763. Partition Labels)

文章目录

1. 1. 文档更新说明
2. 2. 前言
3. 3. 763. Partition Labels
   1. 3.1. Example
   2. 3.2. Explanation:
   3. 3.3. Note
   4. 3.4. Solution
4. 4. 阅读推荐

文档更新说明

• 最后更新 2018年03月19日
• 首次更新 2018年03月19日

前言

　　使用Swift语言完成LetCode题目,中等难度,是一道关于贪心算法的题目,贪心算法的介绍请看文章最底部.
　　简单说一下,贪心算法的思想就是保证从初始状态开始,算法每一个步骤都是局部最优解,最后得到的结果就是全局最优解.当然并不是所有问题都可以通过贪心算法解决,具体请看文章底部链接.

763. Partition Labels

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

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

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

Solution

　　这道题的意思是说,给一个字符串,让我们分割成尽量多个部分(Parts),保证每一个字母都最多出现在其中一个Part里面.
　　我下面做出来的结果是Accepted的,但是比90%的人都慢了😂,算法应该有很大的优化空间,这里就不多说了,毕竟这道题没有超时,说明我的解法是被认可的🙈.

import Foundation

class Solution {
    func partitionLabels(_ S: String) -> [Int] {
        //题意是把数组分割成多个部分之后,确保每一个字符都最多出现在一个部分里,而且分割之后的字串数量要求是最多的.
        //本题使用贪心算法, 先确保第一个字符符合条件:先从第一个字符开始,查找第一个字符最后出现的位置作为第一部分的分割点.
        //再依次让下一个字符符合条件,直到所有字符都符合条件
        var parts = [Int]()
        
        //Swift中无法直接用下标获取对应位置的字符,为了方便起见,先把字符串转成一个数组再来操作
        var s = Array(S)
        //用于记录检索的位置.
        var searchIndex = 0
        //true,表示需要寻找下一个part了
        var nextPart = true
        
        while searchIndex < s.count {
            if let lastIndex = parts.last, searchIndex > lastIndex {
                nextPart = true
            }
            
            let c = s[searchIndex]
            for i in stride(from: s.count - 1, through: 0, by: -1) {
                //下一个字符匹配到最后一个part的末尾就可以了,无须继续往左边对比,因为lastIndex往左已经是最后一个part内部了
                if let lastIndex = parts.last, i <= lastIndex {
                    break
                }
                if c == s[i] {
                    if nextPart == true {
                        parts.append(i)
                        nextPart = false
                    }else {
                        //update last one
                        parts.removeLast()
                        parts.append(i)
                    }
                    break
                }
            }
            searchIndex = searchIndex + 1
        }
        
        //这里parts里面的元素就表示S字符串需要分割成的字串的位置,分别是0-S[0], S[0]+1 - S[1], ... , S[n-1]-1 - S[n]
        //题目需要返回的是每一个字串的长度,所以需要调整一下数组再返回.
        var local = parts[0]
        var res = [Int]()
        for e in parts {
            if e == local {
                res.append(e + 1)
            }else {
                res.append(e - local)
            }
            local = e
        }
        
        return res
    }
}

let s = Solution()
print(s.partitionLabels("adadsfzxcxzcvvpoiulopiukj"))
//ababcbacadefegdehijhklij

阅读推荐

贪心算法