打家劫舍Doc
打家劫舍基本都可以用 动态规划 来解决。 房屋偷盗 剑指 Offer II 089. 房屋偷盗 环形房屋偷盗 剑指 Offer II 090. 环形房屋偷盗 维护一个 helper，设定 number 的起始位置，自底向上计算两次，取最大值。 js var rob = function(nums) { if (nums.length === 0) { return 0 } if (nums.len …
递归Doc
建立思维 理解递归的关键首先还是弄清楚二叉树的先序遍历、中序遍历和后序遍历的递归实现。任何递归可以说都处在这个模型中。 js void traverse(TreeNode root) { if (root == null) { return; } // 前序位置 traverse(root.left); // 中序位置 traverse(root.right); // 后序位置 } 如果面试官明确 …
前缀树（Trie）Doc
Trie 又称前缀树、字典树、单词查找树，是一种二叉树衍生出来的多叉树，通常用来保存字符串，它的节点和字符串的字符对应，而路径和字符串对应，主要应用场景是处理字符串前缀相关的操作。 核心思想是 空间换时间 。利用字符串的公共前缀来减少无谓的字符串比较以达到提高效率的目的。 常用于统计和排序大量字符串。相比较 hash 表，它支持动态查询。 前缀树的特点 前缀树有几个基本性质： 根节点不包含字符 ， …
贪心算法Doc
贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法策略。 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的 贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与 …
堆（Heap）Doc
AI 协助说明： 本页由 Codex 协助核验和修复站内链接；正文的技术事实和适用范围未因本次修改而改变，仍以文中来源及当前官方文档为准。 介绍 堆（heap）分为最大堆（大根堆/大顶堆）和最小堆（小根堆/小顶堆），通常用 完全二叉树 实现，完全二叉树又可以用 数组 实现，故堆通常以数组形式进行存储，而非二叉树的链式存储。常见的堆有 二叉堆 、 裴波那契堆 等，通常也用堆来实现优先队列（Prior …
线上练习跟老外用英语对话
五月到六月，由于疫情原因，被迫居家隔离了一个月，在家也特别无聊，就下了几个可以和外国人线上对话的 App（Cambly、Preply，需付费）打算练练英语口语，于是开启了一段非常有意思的与老外聊天的经历。 几乎每天都和一位讲英语的外国人通过视频的方式对话半小时，有的时候是课程，有的时候就是闲聊。这里面有英国、印度、南非、菲律宾、加拿大、美国、澳大利亚等等很多讲英语国家的人，年轻人、中老年人都有。 …
滑动窗口Doc
滑动窗口也是一种双指针算法，但是滑动窗口特别强调窗口向一个方向滑动，看起来简单，但是却属于最难的一种双指针技巧，力扣上的题一般都是中等或困难难度。首要问题是识别什么样的问题需要滑动窗口解决，最常见的题型：子串问题。 子串问题 子串问题中，除了需要有 left 和 right 双指针，还需要计算（或比较）滑动窗口中的内容，常见的做法是维护一个（甚至更多）哈希表，需要更多哈希表的原因是一个维护窗口内的 …
动态规划Doc
介绍 动态规划（Dynamic Programming，简称DP）常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。 使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做 无后效性 ，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减 …
双指针Doc
双指针有时也叫滑动窗口，如果一定要和滑动窗口区别，那就是滑动窗口的窗口一般是向一个方向滑动，而双指针一般强调左右两个指针。除此之外，可能还会单独强调快慢指针，快慢指针也是一种双指针，但是两个指针的运动速度是不一样的，一快一慢。 左右指针 二分查找 二分查找算法需要使用左右（或高低）两个指针（或索引）在已经排序的链表（或数组）上来实现。详见 二分查找 专题。 167. 两数之和 II - 输入有序数 …
二分查找Doc
二分查找利用 已经排好序 的数组，每次查找可以将查找范围减半，查找范围内只剩一个数据时查找结束。 代码模板 简单题的模板几乎都是统一的，根据题目的条件再灵活调整就可以了，比如 704. 二分查找 。 js var search = function(nums, target) { let low = 0, high = nums.length - 1; while (low <= hig …