写点什么

算法训练营 - 学习笔记 - 第四周

用户头像
心在飞
关注
发布于: 2021 年 05 月 03 日
算法训练营 - 学习笔记 - 第四周

杂想

年龄越来越大,感觉自己连发脾气勇气的都被现实生活磨掉了。不敢发脾气。。。

所以会羡慕小孩,想哭哭,想笑笑,喜怒哀乐都不用隐藏。不像成年人的世界,有时候真的是认清现实后,被现实教育的一点脾气都没有。老人、小孩、房贷、车贷。。。


成年人的世界哪有“容易”二字。

第 9 课 深度优先搜索和广度优先搜索

DFS(Deep First Search)

搜索-遍历:

  1. 深度优先

  2. 每个节点访问一次且仅访问一次(非智能搜索 - 非深度学习)

  3. 遍历顺序:总是从根节点开始

visited = set()def dfs(node, visited):  if node in visited:    # already visited    return   visited.add(node)    # process current node  # ... # logic here  # dfs(node.left)  # dfs(node.right)  for next_node in node.children():    if not next_node in visited:      dfs(next_node, visited)  
复制代码
BFS(Breadth First Search)

广度优先搜索更加符合人脑的思考方式

def BFS(graph, start, end):  queue = []  queue.append([start])  visited.add(start)    while queue:    node = queue.popleft()    visited.add(node)        process(node)    nodes = generate_related_nodes(node)    queue.push(nodes)
复制代码

实战例题:

  1. 二叉树的层次遍历

  2. 最小基因变化

  3. 括号生成

  4. Number of islands

第 10 课 贪心算法 Greedy

贪心算法是一种在每一步选择中都采取在当前状态下最好或者最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。


贪心算法与动态规划的不同在于它对每个子问题的方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。


贪心法可以解决一些最优化问题,如求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题,贪心法一般不能得到我们所要求的答案。

适用贪心算法的场景

问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。

实战例题
  1. 零钱兑换(Coin Change)

  2. 分发饼干

  3. 买卖股票的最佳时机

  4. 跳跃游戏(Jump Game)

第 11 课 二分查找

二分查找的前提
  1. 目标函数单调性(单调递增或者递减)- 有序性

  2. 存在上下界(bounded)

  3. 能够通过索引访问(index accessible)

left, right = 0, len(array) - 1while left <= right:  mid = (left + right) / 2  if array[mid] == target:    # find the target!!    break or return result  elif array[mid] < target:    left = mid + 1  else:    right = mid - 1
复制代码
实战题目
  1. Sqrt

  2. isPerfectSquare

  3. 搜索旋转排序数组(Search in rotated sorted array)

  4. 二分查找 O(logN)

Notes
  1. 五毒神掌

  2. 四部做题法

  3. clarification

  4. consideration,所有解法都思考一遍

  5. coding

  6. testing

发布于: 2021 年 05 月 03 日阅读数: 33
用户头像

心在飞

关注

还未添加个人签名 2017.10.15 加入

2个女儿的爸爸 | 程序员 | CS 反恐精英

评论

发布
暂无评论
算法训练营 - 学习笔记 - 第四周