第四周 深度优先搜索、广度优先搜索、二叉堆、二叉搜索树
题目数：13
本周作业
| 百度 | 字节跳动 | 华为 | Amazon | Google |
|---|
| 6 | 2 | 2 | 4 | 7 |
// 公用方向定义
var (
dx = [4]int{1, -1, 0, 0}
dy = [4]int{0, 0, 1, -1}
)
// 方法一：dfs 和 bfs 从上下，左右边界处理进行加速
// dfs 深度优先遍历
var n, m int
func solve(board [][]byte) {
if len(board) == 0 || len(board[0]) == 0 {
return
}
n, m = len(board), len(board[0])
// 第一列和最后一列
for i := 0; i < n; i++ {
dfs(board, i, 0)
dfs(board, i, m-1)
}
// 第一行和最后一行
for i := 1; i < m - 1; i++ {
dfs(board, 0, i)
dfs(board, n-1, i)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if board[i][j] == 'A' {
board[i][j] = 'O'
} else if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}
func dfs(board [][]byte, x, y int) {
if x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O' {
return
}
board[x][y] = 'A'
for i := 0; i < 4; i++ {
dfs(board, x + dx[i], y + dy[i])
}
}
// bfs：广度优先遍历
func solve(board [][]byte) {
if len(board) == 0 || len(board[0]) == 0 {
return
}
n, m := len(board), len(board[0])
queue := [][]int{}
// 第一列和最后一列
for i := 0; i < n; i++ {
if board[i][0] == 'O' {
queue = append(queue, []int{i, 0})
board[i][0] = 'A'
}
if board[i][m-1] == 'O' {
queue = append(queue, []int{i, m - 1})
board[i][m-1] = 'A'
}
}
// 第一行和最后一行
for i := 1; i < m - 1; i++ {
if board[0][i] == 'O' {
queue = append(queue, []int{0, i})
board[0][i] = 'A'
}
if board[n-1][i] == 'O' {
queue = append(queue, []int{n - 1, i})
board[n-1][i] = 'A'
}
}
for len(queue) > 0 {
cell := queue[0]
queue = queue[1:]
x, y := cell[0], cell[1]
for i := 0; i < 4; i++ {
mx, my := x + dx[i], y + dy[i]
if mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O' {
continue
}
queue = append(queue, []int{mx, my})
board[mx][my] = 'A'
}
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if board[i][j] == 'A' {
board[i][j] = 'O'
} else if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}
// 方法二：并差集，两次编译
type Uf struct {
parent []int
}
func NewUf(n int) *Uf {
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
return &Uf{parent: parent}
}
func (u *Uf) find(p int) int {
parent := u.parent
for p != parent[p] {
parent[p] = parent[parent[p]]
p = parent[p]
}
return p
}
func (u *Uf) Union(p, q int) {
rootP, rootQ := u.find(p), u.find(q)
if rootP != rootQ {
u.parent[rootP] = rootQ
}
}
func (u *Uf) IsConnect(p, q int) bool {
return u.find(p) == u.find(q)
}
func solve(board [][]byte) {
m, n := len(board), len(board[0])
u := NewUf(m*n+1)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if (i == 0 || i == m-1 || j == 0 || j == n-1) && board[i][j] == 'O' {
u.Union(i*n+j, m*n)
} else if board[i][j] == 'O' {
for k := 0; k < 4; k++ {
x, y := i+dx[k], j+dy[k]
if x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' {
u.Union(i*n+j, x*n+y)
}
}
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if !u.IsConnect(i*n+j, m*n) && board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}
type Twitter struct {
globalId int
follower map[int][]int
checkFollowed map[string]bool
//这里twitter的value存globalId
twitter map[int][]int
findTwitter []int
}
/** Initialize your data structure here. */
func Constructor() Twitter {
return Twitter{
globalId: 0,
follower: make(map[int][]int),
checkFollowed: make(map[string]bool),
twitter: make(map[int][]int),
findTwitter: make([]int,0),
}
}
/** Compose a new tweet. */
func (this *Twitter) PostTweet(userId int, tweetId int) {
this.twitter[userId]=append(this.twitter[userId],this.globalId)
this.findTwitter=append(this.findTwitter,tweetId)
this.globalId++
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
func (this *Twitter) GetNewsFeed(userId int) []int {
//可以维护一个大小为10的堆,但这里不这么写了(考虑到可能没有10个推特)
var globalId []int
cpy:=make([]int,len(this.follower[userId]))
copy(cpy,this.follower[userId])
key:=strconv.Itoa(userId)+" "+strconv.Itoa(userId)
//因为测试用例里有自己关注自己这种东西，所以加上这一句
if !this.checkFollowed[key]{
cpy=append(cpy,userId)
}
for _,v:=range cpy{
globalId=append(globalId,this.twitter[v]...)
}
sort.Ints(globalId)
var res []int
for i:=len(globalId)-1;i>=0&&i>=len(globalId)-10;i--{
res=append(res,this.findTwitter[globalId[i]])
}
return res
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Follow(followerId int, followeeId int) {
key:=strconv.Itoa(followerId)+" "+strconv.Itoa(followeeId)
if !this.checkFollowed[key]{
//关注关系更新
this.checkFollowed[key]=true
this.follower[followerId]=append(this.follower[followerId],followeeId)
}
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Unfollow(followerId int, followeeId int) {
key:=strconv.Itoa(followerId)+" "+strconv.Itoa(followeeId)
if this.checkFollowed[key]{
this.checkFollowed[key]=false
for i:=0;i<len(this.follower[followerId]);i++{
if this.follower[followerId][i]==followeeId{
this.follower[followerId]=append(this.follower[followerId][:i],this.follower[followerId][i+1:]...)
}
}
}
}
/**
* Your Twitter object will be instantiated and called as such:
* obj := Constructor();
* obj.PostTweet(userId,tweetId);
* param_2 := obj.GetNewsFeed(userId);
* obj.Follow(followerId,followeeId);
* obj.Unfollow(followerId,followeeId);
*/
// 官方题解： 哈希表 + 链表
class Twitter {
private class Node {
// 哈希表存储关注人的 Id
Set<Integer> followee;
// 用链表存储 tweetId
LinkedList<Integer> tweet;
Node() {
followee = new HashSet<Integer>();
tweet = new LinkedList<Integer>();
}
}
// getNewsFeed 检索的推文的上限以及 tweetId 的时间戳
private int recentMax, time;
// tweetId 对应发送的时间
private Map<Integer, Integer> tweetTime;
// 每个用户存储的信息
private Map<Integer, Node> user;
public Twitter() {
time = 0;
recentMax = 10;
tweetTime = new HashMap<Integer, Integer>();
user = new HashMap<Integer, Node>();
}
// 初始化
public void init(int userId) {
user.put(userId, new Node());
}
public void postTweet(int userId, int tweetId) {
if (!user.containsKey(userId)) {
init(userId);
}
// 达到限制，剔除链表末尾元素
if (user.get(userId).tweet.size() == recentMax) {
user.get(userId).tweet.remove(recentMax - 1);
}
user.get(userId).tweet.addFirst(tweetId);
tweetTime.put(tweetId, ++time);
}
public List<Integer> getNewsFeed(int userId) {
LinkedList<Integer> ans = new LinkedList<Integer>();
for (int it : user.getOrDefault(userId, new Node()).tweet) {
ans.addLast(it);
}
for (int followeeId : user.getOrDefault(userId, new Node()).followee) {
if (followeeId == userId) { // 可能出现自己关注自己的情况
continue;
}
LinkedList<Integer> res = new LinkedList<Integer>();
int tweetSize = user.get(followeeId).tweet.size();
Iterator<Integer> it = user.get(followeeId).tweet.iterator();
int i = 0;
int j = 0;
int curr = -1;
// 线性归并
if (j < tweetSize) {
curr = it.next();
while (i < ans.size() && j < tweetSize) {
if (tweetTime.get(curr) > tweetTime.get(ans.get(i))) {
res.addLast(curr);
++j;
if (it.hasNext()) {
curr = it.next();
}
} else {
res.addLast(ans.get(i));
++i;
}
// 已经找到这两个链表合起来后最近的 recentMax 条推文
if (res.size() == recentMax) {
break;
}
}
}
for (; i < ans.size() && res.size() < recentMax; ++i) {
res.addLast(ans.get(i));
}
if (j < tweetSize && res.size() < recentMax) {
res.addLast(curr);
for (; it.hasNext() && res.size() < recentMax;) {
res.addLast(it.next());
}
}
ans = new LinkedList<Integer>(res);
}
return ans;
}
public void follow(int followerId, int followeeId) {
if (!user.containsKey(followerId)) {
init(followerId);
}
if (!user.containsKey(followeeId)) {
init(followeeId);
}
user.get(followerId).followee.add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
user.getOrDefault(followerId, new Node()).followee.remove(followeeId);
}
}
// 方法二：哈希表 + 链表 + 优先队列
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
public class Twitter {
/**
* 用户 id 和推文（单链表）的对应关系
*/
private Map<Integer, Tweet> twitter;
/**
* 用户 id 和他关注的用户列表的对应关系
*/
private Map<Integer, Set<Integer>> followings;
/**
* 全局使用的时间戳字段，用户每发布一条推文之前 + 1
*/
private static int timestamp = 0;
/**
* 合并 k 组推文使用的数据结构（可以在方法里创建使用），声明成全局变量非必需，视个人情况使用
*/
private static PriorityQueue<Tweet> maxHeap;
/**
* Initialize your data structure here.
*/
public Twitter() {
followings = new HashMap<>();
twitter = new HashMap<>();
maxHeap = new PriorityQueue<>((o1, o2) -> -o1.timestamp + o2.timestamp);
}
/**
* Compose a new tweet.
*/
public void postTweet(int userId, int tweetId) {
timestamp++;
if (twitter.containsKey(userId)) {
Tweet oldHead = twitter.get(userId);
Tweet newHead = new Tweet(tweetId, timestamp);
newHead.next = oldHead;
twitter.put(userId, newHead);
} else {
twitter.put(userId, new Tweet(tweetId, timestamp));
}
}
/**
* Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
*/
public List<Integer> getNewsFeed(int userId) {
// 由于是全局使用的，使用之前需要清空
maxHeap.clear();
// 如果自己发了推文也要算上
if (twitter.containsKey(userId)) {
maxHeap.offer(twitter.get(userId));
}
Set<Integer> followingList = followings.get(userId);
if (followingList != null && followingList.size() > 0) {
for (Integer followingId : followingList) {
Tweet tweet = twitter.get(followingId);
if (tweet != null) {
maxHeap.offer(tweet);
}
}
}
List<Integer> res = new ArrayList<>(10);
int count = 0;
while (!maxHeap.isEmpty() && count < 10) {
Tweet head = maxHeap.poll();
res.add(head.id);
// 这里最好的操作应该是 replace，但是 Java 没有提供
if (head.next != null) {
maxHeap.offer(head.next);
}
count++;
}
return res;
}
/**
* Follower follows a followee. If the operation is invalid, it should be a no-op.
*
* @param followerId 发起关注者 id
* @param followeeId 被关注者 id
*/
public void follow(int followerId, int followeeId) {
// 被关注人不能是自己
if (followeeId == followerId) {
return;
}
// 获取我自己的关注列表
Set<Integer> followingList = followings.get(followerId);
if (followingList == null) {
Set<Integer> init = new HashSet<>();
init.add(followeeId);
followings.put(followerId, init);
} else {
if (followingList.contains(followeeId)) {
return;
}
followingList.add(followeeId);
}
}
/**
* Follower unfollows a followee. If the operation is invalid, it should be a no-op.
*
* @param followerId 发起取消关注的人的 id
* @param followeeId 被取消关注的人的 id
*/
public void unfollow(int followerId, int followeeId) {
if (followeeId == followerId) {
return;
}
// 获取我自己的关注列表
Set<Integer> followingList = followings.get(followerId);
if (followingList == null) {
return;
}
// 这里删除之前无需做判断，因为查找是否存在以后，就可以删除，反正删除之前都要查找
followingList.remove(followeeId);
}
/**
* 推文类，是一个单链表（结点视角）
*/
private class Tweet {
/**
* 推文 id
*/
private int id;
/**
* 发推文的时间戳
*/
private int timestamp;
private Tweet next;
public Tweet(int id, int timestamp) {
this.id = id;
this.timestamp = timestamp;
}
}
public static void main(String[] args) {
Twitter twitter = new Twitter();
twitter.postTweet(1, 1);
List<Integer> res1 = twitter.getNewsFeed(1);
System.out.println(res1);
twitter.follow(2, 1);
List<Integer> res2 = twitter.getNewsFeed(2);
System.out.println(res2);
twitter.unfollow(2, 1);
List<Integer> res3 = twitter.getNewsFeed(2);
System.out.println(res3);
}
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 方法一：递归：右 中 左
func convertBST(root *TreeNode) *TreeNode {
var revInorder func(*TreeNode)
var sum int
revInorder = func (root *TreeNode) {
if root == nil {
return
}
revInorder(root.Right)
sum += root.Val
root.Val = sum
revInorder(root.Left)
}
revInorder(root)
return root
}
// 方法二：Morris 遍历
// 1、如果当前节点的右子节点为空，处理当前节点，并遍历当前节点的左子节点；
// 2、如果当前节点的右子节点不为空，找到当前节点右子树的最左节点（该节点为当前节点中序遍历的前驱节点）；
// 2.1、如果最左节点的左指针为空，将最左节点的左指针指向当前节点，遍历当前节点的右子节点；
// 2.2、如果最左节点的左指针不为空，将最左节点的左指针重新置为空（恢复树的原状），处理当前节点，并将当前节点置为其左节点；
// 3、重复步骤 1 和步骤 2，直到遍历结束。
func convertBST(root *TreeNode) *TreeNode {
sum := 0
node := root
for node != nil {
if node.Right == nil {
// 右侧没有节点
sum += node.Val
node.Val = sum
node = node.Left
} else {
// 查找最左节点
cur := node.Right
for cur.Left != nil && cur.Left != node {
cur = cur.Left
}
if cur.Left == nil {
cur.Left = node
node = node.Right
} else {
cur.Left = nil
sum += node.Val
node.Val = sum
node = node.Left
}
}
}
return root
}
实战例题
以下为课上实战例题
第 7 课 深度优先搜索、广度优先搜索
DFS、BFS
| Facebook | eBay | 微软 | Amazon | Google | Morgan Stanley | 华为 | Cisco | Tesla | Apple |
|---|
| 9 | 5 | 15 | 27 | 3 | 3 | 3 | 3 | 3 | 4 |
var phones = map[byte][]byte{
'2': []byte("abc"),
'3': []byte("def"),
'4': []byte("ghi"),
'5': []byte("jkl"),
'6': []byte("mno"),
'7': []byte("pqrs"),
'8': []byte("tuv"),
'9': []byte("wxyz"),
}
// dfs
func letterCombinations(digits string) (ans []string) {
n := len(digits)
if n == 0 {
return ans
}
s := []byte{}
var dfs func(i int)
dfs = func(i int) {
if i == n {
ans = append(ans, string(s))
return
}
for _, c := range phones[digits[i]] {
s = append(s, c)
dfs(i + 1)
s = s[:i]
}
}
dfs(0)
return ans
}
// bfs 或 迭代
func letterCombinations(digits string) []string {
ans := []string{}
if len(digits) == 0 {
return ans
}
ans = append(ans, "")
for _, digit := range []byte(digits) {
for n := len(ans); n > 0; n-- {
str := ans[0]
ans = ans[1:]
for _, char := range phones[digit] {
ans = append(ans, str + string(char))
}
}
}
return ans
}
// dfs
func solveNQueens(n int) (ans [][]string) {
cols, pie, na := map[int]bool{}, map[int]bool{}, map[int]bool{}
queen := []int{}
var dfs func(int)
dfs = func(row int) {
if row == n {
res := make([]string, n)
for i := 0; i < n; i++ {
r := make([]byte, n)
for j := 0; j < n; j++ {
r[j] = '.'
if j == queen[i] {
r[j] = 'Q'
}
}
res[i] = string(r)
}
ans = append(ans, res)
return
}
for col := 0; col < n; col++ {
if cols[col] || pie[row+col] || na[row-col] {
continue
}
cols[col] = true
pie[row+col] = true
na[row-col] = true
queen = append(queen, col)
dfs(row+1)
queen = queen[:row]
cols[col] = false
pie[row+col] = false
na[row-col] = false
}
}
dfs(0)
return ans
}
// dfs+位运算 写法一
func solveNQueens(n int) (ans [][]string) {
size := 1 << n - 1
var dfs func(row, col, pie, na int, queens []int)
dfs = func(row, col, pie, na int, queens []int) {
if row == n {
res := make([]string, n)
for i := 0; i < n; i++ {
r := make([]byte, n)
for j := 0; j < n; j++ {
r[j] = '.'
if queens[i] & (1 << j) > 0 {
r[j] = 'Q'
}
}
res[i] = string(r)
}
ans = append(ans, res)
return
}
bits := (^(col | pie | na)) & size
for bits > 0 {
p := bits & -bits // 获取最后一位1
bits = bits & (bits-1) // 移除最后一位1
queens = append(queens, p)
dfs(row + 1, col | p, (pie|p) << 1, (na|p) >> 1, queens)
queens = queens[:row]
}
}
dfs(0, 0, 0, 0, []int{})
return ans
}
// dfs+位运算 写法二
func solveNQueens(n int) (ans [][]string) {
size := 1 << n - 1
var dfs func(row, col, pie, na int, queens []int)
dfs = func(row, col, pie, na int, queens []int) {
if row == n {
res := make([]string, n)
for i := 0; i < n; i++ {
r := make([]byte, n)
for j := 0; j < n; j++ {
r[j] = '.'
if queens[i] == j {
r[j] = 'Q'
}
}
res[i] = string(r)
}
ans = append(ans, res)
return
}
bit := (^(col | pie | na)) & size
for bit > 0 {
p := bit & -bit // 获取最后一位1
bit = bit & (bit-1) // 移除最后一位1
queens = append(queens, bits.OnesCount(uint(p-1)))
dfs(row + 1, col | p, (pie|p) << 1, (na|p) >> 1, queens)
queens = queens[:row]
}
}
dfs(0, 0, 0, 0, []int{})
return ans
}
| Facebook | 字节跳动 | 微软 | Amazon | Google | Bloomberg | Apple | LinkedIn | 腾讯 | DoorDash |
|---|
| 17 | 35 | 45 | 82 | 17 | 27 | 17 | 13 | 4 | 6 |
// dfs
var dist = [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
func numIslands(grid [][]byte) (ans int) {
m, n := len(grid), len(grid[0])
var dfs func(i, j int)
dfs = func(i, j int) {
grid[i][j] = '0'
for _, d := range dist {
x, y := i + d[0], j + d[1]
if x < 0 || x >=m || y < 0 || y >= n || grid[x][y] != '1' {
continue
}
dfs(x, y)
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
dfs(i, j)
ans++
}
}
}
return ans
}
// bfs
var dist = [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
func numIslands(grid [][]byte) (ans int) {
m, n := len(grid), len(grid[0])
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
ans++
grid[i][j] = '0'
queue := [][2]int{{i, j}}
for len(queue) > 0 {
r, c := queue[0][0], queue[0][1]
queue = queue[1:]
for _, d := range dist {
x, y := r + d[0], c + d[1]
if x < 0 || x >=m || y < 0 || y >= n || grid[x][y] != '1' {
continue
}
grid[x][y] = '0'
queue = append(queue, [2]int{x, y})
}
}
}
}
}
return ans
}
// 并查集
var dist = [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
uf := NewUnionFind(grid)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
grid[i][j] = '0'
for _, d := range dist {
x, y := i + d[0], j + d[1]
if 0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '1' {
uf.Union(x * n + y, i * n + j)
}
}
}
}
}
return uf.Count()
}
type UnionFind struct {
parent []int
rank []int
count int
}
func NewUnionFind(grid [][]byte) *UnionFind {
m, n := len(grid), len(grid[0])
parent := make([]int, m * n)
count := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
idx := i * n + j
if grid[i][j] == '1' {
parent[idx] = idx
count++
} else {
parent[idx] = -1
}
}
}
return &UnionFind{parent, make([]int, m * n), count}
}
func (uf *UnionFind) Count() int {
return uf.count
}
func (uf *UnionFind) Find(p int) int {
// 迭代压缩
for p != uf.parent[p] {
uf.parent[p] = uf.parent[uf.parent[p]]
p = uf.parent[p]
}
return p
}
func (uf *UnionFind) Union(x, y int) {
rootX, rootY := uf.Find(x), uf.Find(y)
if rootX != rootY {
uf.count--
// 状态压缩
if uf.rank[rootX] > uf.rank[rootY] {
uf.parent[rootY] = rootX
uf.rank[rootX]++
} else if uf.rank[rootX] < uf.rank[rootY] {
uf.parent[rootX] = rootY
uf.rank[rootY]++
} else {
uf.parent[rootY] = rootX
uf.rank[rootX]++
}
}
}
| Facebook | Twitter | 微软 | Amazon |
|---|
| Google | 百度 | Adobe | Cisco |
| Dropbox | 腾讯 | - | - |
// bfs
func minMutation(start string, end string, bank []string) (ans int) {
mp := map[string]bool{}
for _, b := range bank {
mp[b] = true
}
if !mp[end] || len(start) != len(end){
return -1
}
ws := []byte{'A', 'C', 'G', 'T'}
used := map[string]bool{}
queue := []string{start}
used[start] = true
n := len(start)
for len(queue) > 0 {
for size := len(queue); size > 0; size-- {
w := queue[0]
if w == end {
return ans
}
queue = queue[1:]
b := []byte(w)
for i := 0; i < n; i++ {
o := b[i]
for _, c := range ws {
b[i] = c
if used[string(b)] {
continue
}
if mp[string(b)] {
queue = append(queue, string(b))
used[string(b)] = true
}
}
b[i] = o
}
}
ans++
}
return -1
}
| Facebook | 字节跳动 | DoorDash | Amazon | Google | Bloomberg | Apple | 猿辅导 |
|---|
| 12 | 6 | 3 | 5 | 13 | 3 | 3 | 3 |
// 拓扑排序
var (
dirs = [][]int{[]int{-1, 0}, []int{1, 0}, []int{0, -1}, []int{0, 1}}
rows, columns int
)
func longestIncreasingPath(matrix [][]int) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
rows, columns = len(matrix), len(matrix[0])
outdegrees := make([][]int, rows)
queue := [][]int{}
for i := 0; i < rows; i++ {
outdegrees[i] = make([]int, columns)
for j := 0; j < columns; j++ {
for _, dir := range dirs {
newRow, newColumn := i + dir[0], j + dir[1]
if newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[i][j] {
outdegrees[i][j]++
}
}
if outdegrees[i][j] == 0 {
queue = append(queue, []int{i, j})
}
}
}
ans := 0
for len(queue) != 0 {
ans++
size := len(queue)
for i := 0; i < size; i++ {
cell := queue[0]
queue = queue[1:]
row, column := cell[0], cell[1]
for _, dir := range dirs {
newRow, newColumn := row + dir[0], column + dir[1]
if newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] < matrix[row][column] {
outdegrees[newRow][newColumn]--
if outdegrees[newRow][newColumn] == 0 {
queue = append(queue, []int{newRow, newColumn})
}
}
}
}
}
return ans
}
第8课 二叉堆、二叉搜索树
二叉堆
| Facebook | 字节跳动 | 微软 | Amazon | Google | Apple | 百度 | 滴滴 | Bloomberg | 快手 |
|---|
| 22 | 26 | 16 | 44 | 5 | 8 | 2 | 3 | 4 | 3 |
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// 方法一：优先级队列，小顶堆 时间： O(kn × logk)
func mergeKLists(lists []*ListNode) *ListNode {
hp := &ListHeap{}
heap.Init(hp)
for _, list := range lists {
if list != nil {
heap.Push(hp, list)
}
}
dummy := &ListNode{}
pre := dummy
for hp.Len() > 0 {
v := heap.Pop(hp).(*ListNode)
pre.Next = v
pre = pre.Next
if v.Next != nil {
heap.Push(hp, v.Next)
}
}
return dummy.Next
}
type ListHeap []*ListNode
func (hp ListHeap) Len() int {
return len(hp)
}
func (hp ListHeap) Less(i, j int) bool {
return hp[i].Val < hp[j].Val
}
func (hp ListHeap) Swap(i, j int) {
hp[i], hp[j] = hp[j], hp[i]
}
func (hp *ListHeap) Push(v interface{}) {
*hp = append(*hp, v.(*ListNode))
}
func (hp *ListHeap) Pop() interface{} {
old := *hp
v := old[len(old)-1]
*hp = old[:len(old)-1]
// *hp, v = (*hp)[:hp.Len()-1], (*hp)[hp.Len()-1]
return v
}
// 方法二：分治两两合并 O(kn × logk) 空间：O(logk)
// 方法三：顺序合并 O(k^2 × n)
| Facebook | 字节跳动 | 微软 | Amazon | Google | Twitter | 高盛集团 | Bloomberg | 阿里巴巴 |
|---|
| 6 | 7 | 5 | 28 | 8 | 2 | 2 | 2 | 2 |
// 方法一：大顶堆
func maxSlidingWindow(nums []int, k int) (ans []int) {
h := &MyHeap{}
heap.Init(h)
for i, num := range nums {
heap.Push(h, pair{i, num})
if i - k + 1 >= 0 {
for (*h)[0].index <= i - k {
heap.Pop(h)
}
ans = append(ans, (*h)[0].num)
}
}
return ans
}
type pair struct{
index, num int
}
type MyHeap []pair
func (h MyHeap) Len() int {
return len(h)
}
func (h MyHeap) Less(i, j int) bool {
return h[i].num > h[j].num
}
func (h MyHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *MyHeap) Push(x interface{}) {
*h = append(*h, x.(pair))
}
func (h *MyHeap) Pop() (v interface{}) {
v, *h = (*h)[h.Len()-1], (*h)[:h.Len()-1]
return v
}
// 方法二：双端队列
// 方法三：分块 + 预处理（官方题解）
二叉搜索树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 方法一：dfs
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
if val < root.Val {
root.Left = insertIntoBST(root.Left, val)
} else {
root.Right = insertIntoBST(root.Right, val)
}
return root
}
// 方法二：迭代
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
p := root
for p != nil {
if val < p.Val {
if p.Left == nil {
p.Left = &TreeNode{Val: val}
break
}
p = p.Left
} else {
if p.Right == nil {
p.Right = &TreeNode{Val: val}
break
}
p = p.Right
}
}
return root
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 方法一：迭代（对标训练营）
func inorderSuccessor(root *TreeNode, p *TreeNode) (ans *TreeNode) {
for root != nil {
if root.Val == p.Val {
if root.Right != nil {
ans = root.Right
for ans.Left != nil {
ans = ans.Left
}
}
return ans
} else if root.Val > p.Val {
if ans == nil || ans.Val > root.Val {
ans = root
}
// if 判断可以取消写成：ans = root
root = root.Left
} else {
root = root.Right
}
}
return ans
}
// 写法二：
// 最基础的解法，按照二叉搜索树的性质来找
// 这个可能不是太好理解
func inorderSuccessor(root *TreeNode, p *TreeNode) (ans *TreeNode) {
for root != nil {
if root.Val > p.Val {
ans = root
root = root.Left
} else {
root = root.Right
}
}
return ans
}
// 写法三：
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
// 第一种情况: p有右子树, 则寻找右子树的最左节点
// 第二种情况: p没有右子树, 则寻找在二叉搜索期间, 最后一次左转的那个父节点, 就是p的后继节点.
var pre *TreeNode
for root != p {
if root.Val < p.Val{
root = root.Right
} else {
pre = root
root = root.Left
}
}
if root.Right == nil {
return pre
}
root = root.Right
for root.Left != nil{
root = root.Left
}
return root
}
// 方法四：递归
// 参考：https://leetcode-cn.com/problems/successor-lcci/solution/zhong-xu-bian-li-de-xia-yi-ge-yuan-su-5da-jie-fa-h/
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
if root == nil {
return nil
}
if p.Val < root.Val {
if left := inorderSuccessor(root.Left, p); left != nil {
return left
}
return root
} else {
return inorderSuccessor(root.Right, p)
}
}
| 字节跳动 | 微软 | Amazon | Bloomberg | eBay | LinkedIn |
|---|
| 3 | 4 | 2 | 3 | 2 | 2 |
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 方法一：递归（对标训练营）
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}
if key == root.Val {
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
// 右子树最小节点，也可以替换为左子树最大节点
// https://leetcode-cn.com/submissions/detail/280417703/
next := root.Right
for next.Left != nil {
next = next.Left
}
root.Right = deleteNode(root.Right, next.Val)
root.Val = next.Val
return root
} else if key < root.Val {
root.Left = deleteNode(root.Left, key)
} else {
root.Right = deleteNode(root.Right, key)
}
return root
}