#排序
题目描述
给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。
1
2
3
4
5
6
7
8
9
10
11
12
13
| 示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：false
示例 2：
输入：intervals = [[7,10],[2,4]]
输出：true
提示：
0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti < endi <= 10^6
|
解题思路
按照会议开始时间对二维数组进行升序排序，当当前会议的开始时间小于前一个会议的结束时间，表明无法参加全部会议。
时间复杂度
O(Nlog(N))
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func canAttendMeetings(intervals [][]int) bool {
sort.Slice(intervals, func(i,j int) bool {
return intervals[i][0] < intervals[j][0]
})
for i:=1; i<len(intervals); i++ {
if intervals[i][0] < intervals[i-1][1] {
return false
}
}
return true
}
|
#重合区间 #排序 #堆
题目描述
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。
1
2
3
4
5
6
7
8
9
10
11
| 示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2
示例 2：
输入：intervals = [[7,10],[2,4]]
输出：1
提示：
1 <= intervals.length <= 10^4
0 <= starti < endi <= 10^6
|
解题思路
方法一：
(1). 本题的本质是要求最大的重合区间数量，那么就可以参考 早起刷题（Day 17）中的 花期内花的数目 这道题；
(2). 那么就可以将 intervals[i] 分成两个点：(intervals[i][0], INF) 表示会议的开始，(intervals[i][1], -1*INF) 表示会议的结束；
(3). 对上述点构成的二维数组排序，排序优先级根据会议的开始/结束时间升序排序，当开始/结束时间相同，则根据先结束会议再开始会议的顺序排序；
(3). 然后创建两个变量 room 和 ret，当会议开始则 room++ 并更新 ret 为 room 的最大值，会议结束则 room--。
方法二：
(1). 使用堆排序；
(2). 将 intervals 先按照开始时间升序排序，开始时间相同则按照结束时间升序排序；
(3). 然后将第一场会议的结束时间入堆；
(4). 从第二场会议遍历到末尾，当当前会议的开始时间小于堆顶元素，会议室数量+1；当当前会议的开始时间大于堆顶元素，将堆顶元素出堆；
(5). 将当前会议的结束时间入堆。
时间复杂度
$O(N*log(N))$
解题代码
方法一：
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
| func minMeetingRooms(intervals [][]int) int {
const MaxNum = math.MaxInt32
room := 0
ret := 0
var max func(a, b int) int
max = func(a, b int) int {
if a > b {
return a
}
return b
}
pair := make([][]int, 0)
for i:=0; i<len(intervals); i++ {
begin, end := intervals[i][0], intervals[i][1]
pair = append(pair, []int{begin, MaxNum})
pair = append(pair, []int{end, -1*MaxNum})
}
sort.Slice(pair, func(i, j int) bool {
if pair[i][0] == pair[j][0] {
return pair[i][1] < pair[j][1]
}
return pair[i][0] < pair[j][0]
})
for i:=0; i<len(pair); i++ {
if pair[i][1] == MaxNum {
room++
ret = max(ret, room)
} else if pair[i][1] == -1*MaxNum {
room--
}
}
return ret
}
|
方法二：
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
| type intHeap []int
func (h intHeap) Len() int {
return len(h)
}
func (h intHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h intHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h *intHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *intHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func minMeetingRooms(intervals [][]int) int {
sort.Slice(intervals, func(i,j int) bool {
if intervals[i][0] == intervals[j][0] {
return intervals[i][1] < intervals[j][1]
}
return intervals[i][0] < intervals[j][0]
})
var h intHeap
heap.Push(&h, intervals[0][1])
room := 1
for i:=1; i<len(intervals); i++ {
if intervals[i][0] >= h[0] {
heap.Pop(&h)
} else {
room++
}
heap.Push(&h, intervals[i][1])
}
return room
}
|
#排列 #map #回溯
题目描述
给定一个字符串 s ，返回 其重新排列组合后可能构成的所有回文字符串，并去除重复的组合 。
你可以按 任意顺序 返回答案。如果 s 不能形成任何回文排列时，则返回一个空列表。
1
2
3
4
5
6
7
8
9
10
11
12
| 示例 1：
输入: s = "aabb"
输出: ["abba", "baab"]
示例 2：
输入: s = "abc"
输出: []
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
|
解题思路
(1). 首先很容易想到枚举出全部的排列并判断每一个排列是否是回文字符串，但这样会超时；
(2). 那么就换一种思路，判断该字符串能否生成回文串的排列；
(3). 首先字典存储字符串中每个字符的数量；
(4). 如果字符数量为奇数的字符个数大于1，直接返回空数组；否则记录该字符，作为回文字符串中心；
(5). 将每个字符数量/2，并重新组成字符数组，只需要获得该数组字符的所有组合情况即可；
(6). 每一种字符组合情况组成的字符串 + 数量为奇数的字符 + 倒序的字符串 即为回文字符串；
(7). 期间有两个字典，一个用来记录每个字符使用情况，一个用来记录字符串是否为访问过。
解题代码
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| func generatePalindromes(s string) []string {
cnt := make(map[byte]int)
for i:=0; i<len(s); i++ {
cnt[s[i]]++
}
letterSet := make([]byte, 0)
ret := []string{}
oddNum := 0
var midLetter byte
for k, v := range cnt {
if v%2 == 1 {
oddNum++
midLetter = k
if oddNum > 1 {
return ret
}
}
n := v/2
for j:=0; j<n; j++ {
letterSet = append(letterSet, k)
}
}
path := []byte{}
allPath := [][]byte{}
var backTracking func([]byte)
backTracking = func(ss []byte) {
if len(ss) == 0 {
t := make([]byte, len(path))
copy(t, path)
allPath = append(allPath, t)
return
}
m := make(map[byte]bool)
for i:=0; i<len(ss); i++ {
x := ss[i]
if m[x] {
continue
}
m[x] = true
ss = append(ss[:i], ss[i+1:]...)
path = append(path, x)
backTracking(ss)
path = path[:len(path)-1]
ss = append(ss[:i], append([]byte{x}, ss[i:]...)...)
}
}
var reverse func([]byte) []byte
reverse = func(b []byte) []byte {
b1 := make([]byte, len(b))
for i:=0; i<len(b); i++ {
b1[len(b)-1-i] = b[i]
}
return b1
}
backTracking(letterSet)
for i:=0; i<len(allPath); i++ {
b := allPath[i]
b1 := reverse(b)
if oddNum == 0 {
ret = append(ret, string(b)+string(b1))
} else {
ret = append(ret, string(b)+string(midLetter)+string(b1))
}
}
return ret
}
|
