logo头像

待到风起时,扬帆济沧海

常用算法代码模板

深度优先

1
2
3
4
5
6
7
8
9
10
var vistied Set
func dfs(node,vistied){
vistied.add(node)
//doSomething
for next_node in node.chlidren() {
if next_node not in vistied {
dfs(next_node,vistied)
}
}
}

广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//广度搜索的模板
func BFS(graph,start,end){
queue:=[]
var visited Set
queue.append([start])
visited.add(start)
while !queue.isEmpty(){
node=queue.pop()
visited.add(node)
doSomething(node) //节点进行一些操作
nodes:=generate_related_node(node) //去取出当前节点的后继节点,方法
queue.push(nodes)
}
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
left,right=0,len(array)-1
while(left <=right ){
mid= left + (right - left)/2 //防止溢出,这样更安全
if array[mid]==target{
return mid
}eles if array[mid]==target{
left=mid+1
}else{
right=mid-1
}

}

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
fast, slow := head.Next, head
for slow != fast {
if fast == nil || fast.Next == nil {
return false
}
fast = fast.Next.Next
slow = slow.Next
}
return true
}

链表翻转互换

1
2
3
4
5
6
7
8
9
10
11
var prev *ListNode
curr := head

for curr != nil {
//curr.Next, prev, curr = prev, curr, curr.Next
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev

回溯算法(非递归回溯框架)

直接上回溯算法框架。解决一个回溯问题,实际上就是一个决策树的遍历过程。你只需要思考 3 个问题:

  1. 路径:也就是已经做出的选择。
  2. 选择列表:也就是你当前可以做的选择。
  3. 结束条件:也就是到达决策树底层,无法再做选择的条件。
    代码方面,回溯算法的框架:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    result = []
    def backtrack(路径, 选择列表):
    if 满足结束条件:
    result.add(路径)
    return

    for 选择 in 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择
  4. [1,2,3] 全祝贺排列

    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
    func combinationSum(candidates []int, target int) [][]int {
    result := make([][]int, 0)
    track := make([]int, 0)
    var visited = make([]bool, len(candidates))
    backtrack(candidates, track, &result, visited)
    return result

    }

    // 路径:记录在 track 中
    // 选择列表:nums 中的元素
    // 结束条件:nums 中的元素全都在 track 中出现
    func backtrack(nums []int, track []int, result *[][]int, visited []bool) {
    //触发条件
    if len(track) == len(nums) {
    *result = append(*result, track)
    return
    }
    for i := 0; i < len(nums); i++ {
    if !visited[i] {
    visited[i] = true
    track = append(track, nums[i])
    backtrack(nums, track, result, visited)
    track = track[:len(track)-1]
    visited[i] = false
    }
    }
    }

评论系统未开启,无法评论!