Algorithm

tags: Algorithm,Data Structures Make my best effort to move to Nanjing for my son. This is a successor of LeetCode101.

tags: Data Structures,Algorithm

tags: Algorithm,Tree,Graph source: https://en.wikipedia.org/wiki/Minimum%5Fspanning%5Ftree

tags: Algorithm

tags: Algorithm WIKIEPEDIA: https://en.wikipedia.org/wiki/Divide-and-conquer%5Falgorithm The points should been noted: The middle position is not (right - left) / 2, it must be left + ((right - left) / 2).

tags: Algorithm

tags: Algorithm,Two Pointers

tags: Algorithm,Linked List,Fast & Slow Pointers source: https://en.wikipedia.org/wiki/Cycle%5Fdetection Floyd’s tortoise and hare With two pointers: tortoise move slow: move 1 step in each loop. hare move fast: move 2 steps in each loop. If there is a circle existed, tortoise and hare will meet eventually in the circle. Now both tortoise and hare are in the circle, how to figure out the beginning of the circle? We put tortoise back to the beginning they both started. Such as, the first element of the linked list. Then we move both tortoise and hare step by step, they will meet in the beginning of the circle.

tags: Algorithm

tags: Algorithm

tags: Algorithm

tags: Algorithm

tags: Algorithm

tags: Algorithm

tags: Algorithm Slide right to move forward to find the solution. Slide left to keep the solution, and collect to the results. Must avoid left go to backward.

tags: Algorithm,Data Structures 又要开始找工作了，刷题、刷题、刷题！步骤： 按顺序找到题目 解题/学习 总结考察的点（树、双指针、回溯、DP、模拟现实、递归） 刷相同解法框架的题 一些模糊的感觉： 尝试不同的遍历顺序可能是解题关键，正序遍历不行试一下反序遍历，反之亦然！ 以上到达一定量之后在 LeetCode 创建一个新的 session 重新刷起。

tags: Algorithm,Bigdata,Educational Measurement

tags: Algorithm source: https://malisper.me/an-algorithm-for-passing-programming-interviews/

tags: Algorithm,Brute Force Approach

tags: Algorithm,Data Structures,Binary Search Tree 分为三种：前序、后序和中序，其中最容易用栈改写的是后序。 前序(Preorder)：Root -> Left -> Right class Solution { public: void processPreorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processPreorderTraversal(root->left, collector); collector.push_back(root->val); processPreorderTraversal(root->right, collector); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processPreorderTraversal(root, ret); return ret; } }; 中序(Inorder): Left -> Root -> Right class Solution { public: void processInorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processInorderTraversal(root->left, collector); collector.push_back(root->val); processInorderTraversal(root->right, collector); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processInorderTraversal(root, ret); return ret; } }; 后序(Postorder)：Left -> Right -> Root class Solution { public: void processPostorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processPostorderTraversal(root->left, collector); processPostorderTraversal(root->right, collector); collector.push_back(root->val); } vector<int> postorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processPostorderTraversal(root, ret); return ret; } }; 非递归遍历 【刷题】二叉树非递归遍历 ...

tags: Learning,Algorithm

tags: Algorithm 状态转移方程 无后效性 如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。 一旦 \(f(n)\) 确定，“我们如何凑出 \(f(n)\) ”就再也用不着了： 要求出 \(f(15)\)，只需要知道 \(f(14)\),\(f(10)\),\(f(4)\) 的值， 而 \(f(14)\),\(f(10)\),\(f(4)\) 是如何算出来的，对之后的问题没有影响。 “未来与过去无关”，这就是无后效性。 最优子结构 大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”： \(f(n)\) 的定义需要蕴含“最优”，利用 \(f(14)\),\(f(10)\),\(f(4)\) 的最优解，我们即可算出 \(f(15)\) 的最优解。 能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。 DP 思路 参见 LeetCode 讨论： 先写出穷举的方法 找出不必要的重复计算 写出 DP 练习 0x00 硬币找零 描述 假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。 状态转移公式 公式 \(f(n)=min\{f(n-1),f(n-3),f(n-5)\} + 1\) 检查是否满足上面提到的两个特性： 无后效性：对于 \(n\)，一旦 \(f(n)\) 确定，以后只关心 \(f(n)\) 的值，不关心怎么计算的； 最优子结构：对于 \(n\)，只要 \(n - 1\) \(n - 3\) \(n - 5\) 能是最优解，那么就能计算出 n; 推导过程 假设找零 15： 若优先使用 5 元硬币 \(cost = f(10) + 1 = 2 + 1 = 3\) ...

tags: Algorithm,Sorting Wikipedia: 归并排序

alias: Algorithm