相关信息
广度优先搜索学习
以下代码段摘录自算法图解中,可以很好的理解广度优先算法
python
def search(name):
search_queue = deque() # 创建队列用于 BFS
search_queue += graph[name] # 将起点的邻居加入队列
searched = [] # 用于记录已检查过的人
while search_queue: # 当队列不为空时循环
person = search_queue.popleft() # 从队列左侧取出下一个人
if person not in searched: # 只检查未检查过的人
if person_is_seller(person): # 如果这个人是芒果卖家
print(person + " is a mango seller!")
return True # 找到后返回 True
else:
search_queue += graph[person] # 将此人的邻居加入队列
searched.append(person) # 标记为已检查
return False # 队列为空仍未找到,返回 False
gopackage main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
// 计算链表长度
lenA := 0
lenB := 0
currA, currB := headA, headB
for currA != nil {
lenA++
currA = currA.Next
}
for currB != nil {
lenB++
currB = currB.Next
}
// 对齐起点
currA, currB = headA, headB
if lenA > lenB {
for i := 0; i < lenA-lenB; i++ {
currA = currA.Next
}
} else {
for i := 0; i < lenB-lenA; i++ {
currB = currB.Next
}
}
// 同步遍历直到找到相交节点或遍历结束
for currA != nil && currB != nil {
if currA == currB {
return currA
}
currA = currA.Next
currB = currB.Next
}
return nil
}
// 测试代码
func main() {
// 构造链表A: 1 -> 2 -> 3 \
// 6 -> 7
// 4 -> 5 /
// 链表B: 4 -> 5 /
common := &ListNode{6, &ListNode{7, nil}}
headA := &ListNode{1, &ListNode{2, &ListNode{3, common}}}
headB := &ListNode{4, &ListNode{5, common}}
intersection := getIntersectionNode(headA, headB)
if intersection != nil {
fmt.Printf("相交节点值: %d\n", intersection.Val)
} else {
fmt.Println("没有相交节点")
}
}