早起刷题（Day 3）
洪笳淏 Lv4
 2022-04-01 05:30:00      

LeetCode269. 火星词典

#拓扑排序

题目描述

现有一种使用英语字母的火星语言，这门语言的字母顺序与英语顺序不同。给你一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 “” 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况：
1.在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
2.如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

1
2
3
4
5
6
7
8
9
10
11
12
示例 1:
输入：words = ["wrt","wrf","er","ett","rftt"]
输出："wertf"

示例 2:
输入：words = ["z","x"]
输出："zx"

示例 3:
输入：words = ["z","x","z"]
输出：""
解释：不存在合法字母顺序，因此返回 "" 。

解题思路

(1). 首先考虑什么情况下会出现不合法的情况：如果在之前判断字母 ‘x’ 的字典序应该大于 ‘y’，可是在后面又出现了 ‘y’ 的字典序应该大于 ‘x’ 的情况，那么此时就出现了矛盾，因此是不合法的；
(2). 对于这种只允许单向依赖的情况，考虑使用拓扑排序。首先就要构建邻接表和入度统计。在建立邻接表的时候要考虑一种情况，那就是如果出现在后面的字符串是前面字符串的前缀字符串，那么可以立即判定是不合法的；
(3). 在构建好两个数据结构后，使用广度优先搜索查找。将入度为 0 的字母放入队列中，然后再将其对应的邻接表中的字母入度减一，此时相当于在拓扑排序中消除了对该字母的依赖，也可以看作访问数 visited 加 1；
(4). 最后判断一下 visited 是否是全体出现过的字母数，相等则说明是一个拓扑排序，不存在循环依赖。

时间复杂度

O(words.length*words[i].length)

解题代码

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
79
func alienOrder(words []string) string {

	adjacency := make(map[byte][]byte) // 邻接表
	inDegree := make(map[byte]int)	// 入度统计
	ret := ""

	var buildGraph func() bool
	buildGraph = func() bool {
		for i:=0; i<len(words); i++ {
			for j:=0; j<len(words[i]); j++ {
				adjacency[words[i][j]] = []byte{}
			}
		}

		for i:=1; i<len(words); i++ {
			w1, w2 := words[i-1], words[i]
			j := 0
			minLength := min(len(w1),len(w2))
			for ; j<minLength; j++ {
				if w1[j] != w2[j] {
					adjacency[w1[j]] = append(adjacency[w1[j]], w2[j])
					inDegree[w2[j]]++
					break
				}
			}

			if j == minLength && len(w1) > len(w2) {
				return false
			}
		}
		
		return true
	}

	var visitedCount func() int
	visitedCount = func() int {
		visited := 0
		q := []byte{}

		for k,_ := range adjacency {
			if inDegree[k] == 0 {
				q = append(q, k)
			}
		}

		for len(q) > 0 {
			p := []byte{}

			for i:=0; i<len(q); i++ {
				w := q[i]
				for j:=0; j<len(adjacency[w]); j++ {
					x := adjacency[w][j]
					inDegree[x]--
					if inDegree[x] == 0 {
						p = append(p, x)
					}
				}
				visited++
			}
			ret += string(q)
			q = p
		}
		
		return visited
	}

	if !buildGraph() || visitedCount() != len(adjacency) {
		return ""
	}
	
	return ret
}

func min(a,b int) int {
	if a < b {
		return a
	}
	return b
}

LeetCode8. 字符串转换整数 (atoi)

#模拟题

题目描述

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
1.读入字符串并丢弃无用的前导空格
2.检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
3.读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
4.将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
5.如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
6.返回整数作为最终结果。

注意：
本题中的空白字符只包括空格字符 ‘ ‘ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

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
示例 1:
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。


示例 2:
输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。


示例 3:
输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

提示：
0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

解题思路

(1). 这是一道很典型的模拟题，对于模拟题，少不了条件判断，建议采用 switch 来代替大量的 if…else，这样代码的逻辑会清晰很多；
(2). 这道题唯一值得关心的点就是越界问题，那么就需要将合法数字字符串取出后先去除前导零，然后再根据符号分别判断是否越界。

时间复杂度

O(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
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
func myAtoi(s string) int {

	if len(s) == 0 {
		return 0
	}

	isNeg := false
	prefixLetter := true
	str := []byte{}
	maxNum, minNum := math.MaxInt32, -1*math.MinInt32

	for i:=0; i<len(s); i++ {
		if prefixLetter {
			switch {
				case s[i] == '-':
					isNeg = true
					prefixLetter = false
				case s[i] == '+':
					prefixLetter = false
				case s[i] == ' ':
				case s[i] == '.' || (s[i] >= 'a' && s[i] <= 'z'):
					return 0
				case s[i] >= '0' && s[i] <= '9':
					prefixLetter = false
					str = append(str, s[i])
			}
		} else {
			switch {
				case s[i] >= '0' && s[i] <= '9':
					str = append(str, s[i])
				default:
					i = len(s)
			}
		}
	}

	if len(str) == 0 {
		return 0
	}

	x := 0
	for i:=0; i<len(str); i++ {
		if str[i] != '0' {
			x = i
			break
		}
	}

	ret := 0
	if !isNeg {
		for i:=x; i<len(str) ;i++ {
			ret *= 10
			ret += int(str[i])-'0'
			if ret > maxNum {
				return maxNum
			}

		}
	} else {
		for i:=x; i<len(str); i++ {
			ret *= 10
			ret += int(str[i])-'0'
			if ret > minNum {
				return math.MinInt32
			}
		}
		ret *= -1
	}

	return ret
}
  • Post title：早起刷题（Day 3）
  • Post author：洪笳淏
  • Create time：2022-04-01 05:30:00
  • Post link：https://jiahaohong1997.github.io/2022/04/01/早起刷题（Day 3）/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments