早起刷题（Day 8）
洪笳淏 Lv4
 2022-04-08 06:00:00      

LeetCode536. 从字符串生成二叉树

#递归 #栈 #二叉树

题目描述

你需要用一个包括括号和整数的字符串构建一棵二叉树。
输入的字符串代表一棵二叉树。它包括整数和随后的 0 、1 或 2 对括号。整数代表根的值，一对括号内表示同样结构的子树。
若存在子结点，则从左子结点开始构建。

1
示例 1:

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入： s = "4(2(3)(1))(6(5))"
输出： [4,2,6,3,1,5]

示例 2:
输入： s = "4(2(3)(1))(6(5)(7))"
输出： [4,2,6,3,1,5,7]

示例 3:
输入： s = "-4(2(3)(1))(6(5)(7))"
输出： [-4,2,6,3,1,5,7]
 
提示：
0 <= s.length <= 3 * 104
输入字符串中只包含 '(', ')', '-' 和 '0' ~ '9' 
空树由 "" 而非"()"表示。

解题思路

(1). 很明显的递归题，而且题目中包含有对括号的处理，遇到括号首先就是考虑使用栈来记录下合法括号内的字符串；
(2). 首先要将父节点的值从字符串中抠出来，然后分别记录下左子树和右子树的字符串，这里可以设置一个哨兵，当左子树被分离出来后，用哨兵记录，那么下一次记录的合法字符串就是右子树。

解题代码

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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* 		Val int
* 		Left *TreeNode
* 		Right *TreeNode
* }
*/

func str2tree(s string) *TreeNode {

	if s == "" {
		return nil
	}

	var backTracking func(string) *TreeNode
	backTracking = func(b string) *TreeNode {

		if len(b) == 0 {
			return nil
		}

		var h* TreeNode
		var index int
		var x int
		num := ""

		for ; index<len(b); index++ {
			if b[index] != '(' {
				num += b[index:index+1]
			} else {
				break
			}
		}

		x,_ = strconv.Atoi(num)
		h = &TreeNode{
			Val : x,
		}

		bb := ""
		l := 0
		f := 0

		for ; index<len(b); index++ {

			if b[index] == '(' {
				if l == 0 {
					l++
					continue
				} else {
					l++
					bb += "("
				}
			} else if (b[index] >= '0' && b[index] <= '9') || b[index] == '-' {
				bb += b[index:index+1]
			} else {
				l--
				if l != 0 {
					bb += ")"
				} else {
					if f == 0 {
						leftNode := backTracking(bb)
						h.Left = leftNode
						bb = ""
						f = 1
					} else {
						rightNode := backTracking(bb)
						h.Right = rightNode
					}
				}
			}
		}

		return h
	}
	
	return backTracking(s)
}

LeetCode370. 区间加法

#差分数组

题目描述

假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。
其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex … endIndex]（包括 startIndex 和 endIndex）增加 inc。
请你返回 k 次操作后的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例:
输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
输出: [-2,0,3,5,3]
解释:

初始状态:
[0,0,0,0,0]

进行了操作 [1,3,2] 后的状态:
[0,2,2,2,0]

进行了操作 [2,4,3] 后的状态:
[0,2,5,5,3]

进行了操作 [0,2,-2] 后的状态:
[-2,0,3,5,3]

解题思路

(1). 如果采用暴力的方式，需要在遍历 updates 的同时遍历结果数组，时间代价巨大；
(2). 观察到执行 updates 的顺序与最终结果无关。那么我们可以针对区间进行更新；
(3). 具体的思路是：对于每一组 updates[i]，我们提取出 left、right、val 这三个值分别代表左边界、右边界、更新值。我们只需要建立一个差分数组 diff，对 diff[left] 加上 val，对 diff[right+1] 减去 val，那么之后就可以通过区间的记录还原最终的输出结果；
(4). 最后通过前缀和计算最终的输出结果

时间复杂度

O(N)

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func getModifiedArray(length int, updates [][]int) []int {

	nums := make([]int, length)
	diff := make([]int, length)

	for i:=0; i<len(updates); i++ {
		left, right, val := updates[i][0], updates[i][1], updates[i][2]
		diff[left] += val
		if right+1 >= length {
			continue
		}
		diff[right+1] -= val
	}

	nums[0] = diff[0]
	for i:=1; i<length; i++ {
		nums[i] = nums[i-1]+diff[i]
	}
	
	return nums
}

LeetCode692. 前K个高频单词

#优先队列 #字典序

题目描述

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 1：
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。
 

注意：
1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]
 
进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

解题思路

(1). 以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决，本题适合使用优先队列，对于这种既要考虑优先级，又要考虑字符串构成的情况，怎样构建优先队列可以参考 堆的Go语言实现
(2). 注意考虑在出现次数一样的情况下，要依赖字符串的字典序排序，可以使用 strings.Compare 方法来比较字典序；
(3). 要输出最大的 k 个，可以采取建立容量上限为 k 的小根堆的做法。

解题代码

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
80
81
82
83
84
85
86
87
88
89
90
91
type wordCount struct {
	word string
	priority int
	index int
}

type priorityQueue []*wordCount

func (pq priorityQueue) Len() int {
	return len(pq)
}

func (pq priorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = j
	pq[j].index = i
}

func (pq priorityQueue) Less(i, j int) bool {
	if pq[i].priority == pq[j].priority {
		if strings.Compare(pq[i].word, pq[j].word) == 1 {
			// pq[i].word 的字典序在 pq[j].word 的后面，那在优先队列中就排前面
			return true
		} else if strings.Compare(pq[i].word, pq[j].word) == -1 {
			// pq[i].word 的字典序在 pq[j].word 的前面，那在优先队列中就排后面
			return false
		}
	}
	
	return pq[i].priority < pq[j].priority
}

func (pq *priorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*wordCount)
	item.index = n
	*pq = append(*pq, item)
}

  

func (pq *priorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	item.index = -1
	*pq = old[:n-1]

	return item
}

func topKFrequent(words []string, k int) []string {

	var pq priorityQueue
	m := make(map[string]int)
	for i:=0; i<len(words); i++ {
		m[words[i]]++
	}

	i := 0
	for w, v := range m {
		if i < k {
			wc := &wordCount {
				word : w,
				index : i,
				priority : v,
			}
			i++
			heap.Push(&pq, wc)
		} else {
			if v > pq[0].priority || (v == pq[0].priority && strings.Compare(w, pq[0].word) == -1) {
				heap.Pop(&pq)
				wc := &wordCount {
					word : w,
					index : k-1,
					priority : v,
				}
				heap.Push(&pq, wc)
			}
		}
	}

	ret := make([]string, k)
	for k > 0 {
		ret[k-1] = heap.Pop(&pq).(*wordCount).word
		k--
	}

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