脚本宝典收集整理的这篇文章主要介绍了LeetCode Weekly Contest 24,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
https://leetcode.com/contest/...
01 Matrix
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input:
0 0 0
0 1 0
0 0 0
Output:
0 0 0
0 1 0
0 0 0
Learn How to use chan as Queue in Golang
Initially, I was trying to BFS every 1 to find the nearest 0, Timeout O(n^3); then change to start from every 0 to update all the
1s, cut it when encounter any disi < nowDis, still O(n^3)
Put all 0 in Queue as initial, BFS when find a new updating also put it into Queue, as this we can guarantee the accurate within
O(n^2)
func InitData(matrix [][]int) [][]int {
data := make([][]int, 0)
for index, list := range matrix {
data = append(data, make([]int, 0))
for _, item := range list {
if 0 == item {
data[index] = append(data[index], 0)
} else {
data[index] = append(data[index], -1)
}
}
}
return data
}
type Node struct {
X int
Y int
V int
}
const MAX_N = 10001
var queue = make(chan Node, MAX_N)
var Dir = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
func Inrange(x, y int, matrix [][]int) bool {
if x < 0 || y < 0 || x >= len(matrix) || y >= len(matrix[x]) {
return false
}
return true
}
func bfs(data [][]int) {
//fmt.Printf("%v %v, data[%v]n", x, y, data)
for ir, list := range data {
for ic, item := range list {
if 0 == item {
queue <- Node{X: ir, Y: ic, V: 0}
}
}
}
node := Node{}
for {
select {
case node = <-queue:
default: return
}
//fmt.Printf("node %v, min[%v] %vn", node, min, len(queue))
for _, dir := range Dir {
nx := node.X + dir[0]
ny := node.Y + dir[1]
if false == Inrange(nx, ny, data) {
continue
}
if -1 != data[nx][ny] && data[nx][ny] <= node.V + 1 {
continue
}
data[nx][ny] = node.V + 1
queue <- Node{X: nx, Y: ny, V: node.V + 1}
//fmt.Printf("-- %v %v, min%vn", nx, ny, min)
}
}
return
}
func updateMatrix(matrix [][]int) [][]int {
data := InitData(matrix)
bfs(data)
return data
}
Convert BST to Greater Tree
https://leetcode.com/contest/...
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
Input: The root of a Binary Search Tree like this:
5
/
2 13
Output: The root of a Greater Tree like this:
18
/
20 13
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var totalSum int
func dfs(node *TreeNode) {
if nil != node.Right {
dfs(node.Right)
}
nodeVal := node.Val
node.Val += totalSum
totalSum += nodeVal
if nil != node.Left {
dfs(node.Left)
}
}
func convertBST(root *TreeNode) *TreeNode {
totalSum = 0
if nil != root {
dfs(root)
}
return root
}
Diameter of Binary Tree
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Given a binary tree
1
/
2 3
/
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var maxDia int
func dfs(node *TreeNode) int {
leftDia := 0
rightDia := 0
if nil != node.Left {
leftDia = dfs(node.Left)
}
if nil != node.Right {
rightDia = dfs(node.Right)
}
if (leftDia + rightDia > maxDia) {
maxDia = leftDia + rightDia
}
if leftDia > rightDia {
return leftDia+1
} else {
return rightDia+1
}
}
func diameterOfBinaryTree(root *TreeNode) int {
maxDia = 0
if nil != root {
dfs(root)
}
return maxDia
}
以上是脚本宝典为你收集整理的LeetCode Weekly Contest 24全部内容,希望文章能够帮你解决LeetCode Weekly Contest 24所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。