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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//广度搜索的模板
func levelOrder(root *TreeNode) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
//存放相邻节点的
que := make([]*TreeNode, 0)
que = append(que, root)
for len(que) > 0 {

lvLenght := len(que) //当前层队列有几个数据
lvArr := make([]int, 0)
lvQue := make([]*TreeNode, 0)
for i := 0; i < lvLenght; i++ {
//弹出数据
node := que[0]
que = que[1:]
lvArr = append(lvArr, node.Val)
if node.Left != nil {
lvQue = append(lvQue, node.Left)
}
if node.Right != nil {
lvQue = append(lvQue, node.Right)
}
}
que = append(que, lvQue...)
res = append(res, lvArr)
}
return res
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}

二分查找-左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回,锁定左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}

二分查找-右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回,锁定右侧边界
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}

快慢指针

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
    }
    }
    }

滑动窗口算法

1
2
3
4
5
6
7
8
9
10
11
12
13
int left = 0, right = 0;

while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;

while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}

滑动窗口算法的思路是这样:
1、我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right),直到窗口中的字符串符合要求(包含了 T 中的所有字符)。
3、此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right),直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。
4、重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。

这个思路其实也不难,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解,也就是最短的覆盖子串。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动,这就是「滑动窗口」这个名字的来历。

动态规划模板(背包类型问题)

第一步要明确两点,「状态」和「选择」。
先说状态,如何才能描述一个问题局面?只要给几个物品和一个背包的容量限制,就形成了一个背包问题呀。所以状态有两个,就是「背包的容量」和「可选择的物品」

1
2
3
4
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 择优(选择1,选择2...)

第二步要明确 dp 数组的定义
再说选择,也很容易想到啊,对于每件物品,你能选择什么?选择就是「装进背包」或者「不装进背包」嘛

1
2
3
4
5
6
7
8
9
10
11
int dp[N+1][W+1]
dp[0][..] = 0
dp[..][0] = 0

for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
把物品 i 装进背包,
不把物品 i 装进背包
)
return dp[N][W]

第三步,根据「选择」,思考状态转移的逻辑。
如果你没有把这第 i 个物品装入背包,那么很显然,最大价值 dp[i][w] 应该等于 dp[i-1][w],继承之前的结果。
如果你把这第 i 个物品装入了背包,那么 dp[i][w] 应该等于 dp[i-1][w - wt[i-1]] + val[i-1]

1
2
3
4
5
6
7
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w - wt[i-1]] + val[i-1]
)
return dp[N][W]

动态规划模板(最长子序列问题)

  • 思路一:一个一维的 dp 数组
    1
    2
    3
    4
    5
    6
    7
    8
    int n = array.length;
    int[] dp = new int[n];

    for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
    dp[i] = 最值(dp[i], dp[j] + ...)
    }
    }

在子数组 array[0..i] 中,我们要求的子序列(最长递增子序列)的长度是 dp[i]。

  • 思路二:一个二维的 dp 数组:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int n = arr.length;
    int[][] dp = new dp[n][n];

    for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
    if (arr[i] == arr[j])
    dp[i][j] = dp[i][j] + ...
    else
    dp[i][j] = 最值(...)
    }
    }
    1. 涉及两个字符串/数组时

    在子数组 arr1[0..i] 和子数组 arr2[0..j] 中,我们要求的子序列(最长公共子序列)长度为 dp[i][j]

    1. 只涉及一个字符串/数组时

    在子数组 array[i..j] 中,我们要求的子序列(最长回文子序列)的长度为 dp[i][j]。

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