Avatar
lbbniu
PHP/Go高级工程师 好未来-集团中台
学无止境

算法练习

预习 第一课 预习 第二课 预习知识点 数组:为什么很多编程语言中数组都从 0 开始编号? 链表:如何实现 LRU 缓存淘汰算法? 链表:如何轻松写出正确的链表代码? 跳表:为什么 Redis 一定要用跳表来实现有序集合? 预习题目 移动零 盛最多水的容器 爬楼梯 三数之和 环形链表
第一周 第三课|数组、链表、跳表 参考链接 Java 源码分析(ArrayList) Linked List 的标准实现代码 [Linked List 示例代码](http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/code/LinkedList.java) Java 源码分析(LinkedList) LRU Cache - Linked list:LRU 缓存机制 Redis - Skip List:跳跃表、为啥 Redis 使用跳表(Skip List)而不是使用 Red-Black? Array 实战题目 11. 盛最多水的容器 //方法一: 暴力求解 双循环 class Solution { /** * @param Integer[] $height * @return Integer */ function maxArea($height) { $max = 0; $len = count($height); for ($i = 0; $i < $len - 1; $i++) { for ($j = $i + 1; $j < $len; $j++) { $area = ($j - $i) * min($height[$i], $height[$j]); $max = $area < $max ?
第2周 第4课 | 栈、队列、优先队列、双端队列 参考链接 Java 的 PriorityQueue 文档 Java 的 Stack 源码 Java 的 Queue 源码 Python 的 heapq 高性能的 container 库 预习题目 20. 有效的括号 class Solution { /** * 方法一:栈(spl标准库) * @param String $s * @return Boolean */ function isValid($s) { //构造哈希表 $map = [')'=>'(', ']'=>'[', '}'=>'{']; $stack = new SplStack(); for ($i = 0, $len = strlen($s); $i < $len; $i++) { if (!isset($map[$s[$i]])) { $stack->push($s[$i]); } else if (!$stack->count() || $stack->pop() !
第3周 第6课 | 树、二叉树、二叉搜索树 1. 树、二叉树、二叉搜索树的实现和特性 参考链接 二叉搜索树 Demo 思考题 树的面试题解法一般都是递归,为什么? 说明:同学们可以将自己的思考写在课程下方的留言区一起讨论,也可以写在第 2 周的学习总结中。 2. 实战题目解析:二叉树的中序遍历 参考链接 树的遍历 Demo 实战题目 / 课后作业 94. 二叉树的中序遍历 /** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */ class Solution { private $values = []; /** * 方法一:递归 * @param TreeNode $root * @return Integer[] */ function inorderTraversal1($root) { $this->inorder($root); return $this->values; } function inorder($root) { if ($root) { $this->inorder($root->left); $this->values[] = $root->val; $this->inorder($root->right); } } /** * 方法二:迭代 * @param TreeNode $root * @return Integer[] */ function inorderTraversal2($root) { $stack = $res = []; while ($root || $stack) { while ($root) { $stack[] = $root; $root = $root->left; } $root = array_pop($stack); $res[] = $root->val; $root = $root->right; } return $res; } /** * 方法三:颜色标记法 * @param TreeNode $root * @return Integer[] */ function inorderTraversal3($root) { $white = 0; $gray = 1; $stack = [[$white, $root]]; $res = []; while ($stack) { [$color, $node ] = array_pop($stack); if (!
第4周 第9课 | 深度优先搜索和广度优先搜索 1. 深度优先搜索、广度优先搜索的实现和特性 参考链接 DFS 代码模板(递归写法、非递归写法) 递归写法 visited = set() def dfs(node, visited): if node in visited: # terminator # already visited return visited.add(node) # process current node here. ... for next_node in node.children(): if next_node not in visited: dfs(next_node, visited) 非递归写法 def DFS(self, tree): if tree.root is None: return [] visited, stack = [], [tree.root] while stack: node = stack.pop() visited.add(node) process (node) nodes = generate_related_nodes(node) stack.push(nodes) # other processing work .