文章目录
  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%的人都慢了😂,算法应该有很大的优化空间,这里就不多说了,毕竟这道题没有超时,说明我的解法是被认可的🙈.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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

阅读推荐

贪心算法

文章目录
  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. 阅读推荐