MaggicQ's Blog

路漫漫其修远兮

算法笔记-贪婪技术

贪婪技术贪婪法通过一系列的步骤来构造问题的解，每一步对目前构造的部分解一个拓展，直到获得问题的完整解为止，这个技术的核心是，所做的每一步选择都必须满足以下条件：可行的（feasible），即它必须满足问题的约束。局部最优（locally optimal）：它是当前步骤中所有可选选择中的最佳局部选择不可取消（irrevocable）：即选择一旦做出，在算法的后面步骤中...

Posted by MaggicQ on November 29, 2017

Leetcode题解-数据结构

本文目录最小栈题目描述代码实现 LRU缓存机制题目描述代码实现实现 Trie (前缀树) 题目描述代码实现题目描述代码实现最小栈题目描述设计一个支持 push，pop，top 操作...

Posted by MaggicQ on November 29, 2017

Leetcode题解-二分查找

本文目录定义常见题目二分查找 X的平方根搜索旋转排序数组第一个错误的版本寻找峰值寻找旋转排序数组中的最小值寻找旋转排序数组中的最小值 II Pow(x, n) 有效的完全平方数寻找比目标字母大的最小字母两数之和 II - 输...

Posted by MaggicQ on November 29, 2017

算法笔记-蛮力法

蛮力法蛮力法（brute force）是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。选择排序和冒泡排序选择排序：开始的时候，扫描整个列表，找到最小元素，然后和第一个元素交换，然后从第二个元素开始扫描，找到最后$n-1$ 个元素中的最小元素，再和第二个元素交换位置，把第二小的元素放在它的位置上，依次类推。伪代码: 算法复杂度： $\Th...

Posted by MaggicQ on November 14, 2017

Leetcode题解-链表

本文目录定义常见题目合并两个有序链表反转链表两数相加链表排序相交链表环形链表移除链表元素合并K个排序链表参考定义链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节...

Posted by MaggicQ on November 1, 2017

Leetcode题解-二叉树

本文目录定义常见题型二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树的层次遍历二叉树的最近公共祖先二叉搜索树的最近公共祖先翻转二叉树二叉树中的最大路径和二叉搜索树中第K小的元素左叶子之和定义树（Tre...

Posted by MaggicQ on October 8, 2017

Leetcode题解-贪心算法

本文目录定义常见题型买卖股票的最佳时机买卖股票的最佳时机 II 跳跃游戏最大子序和判断子序列定义贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。贪心算法...

Posted by MaggicQ on September 19, 2017

算法笔记-迭代改进

迭代改进迭代改进的策略是：从某些可行解出发，通过重复应用一些简单的步骤来不断改进它。这些步骤一般会通过一些小的、局部的改变来生成一个可行解，这个解使得目标函数值更为优化，如果目标函数值无法再得到优化，就把最后的可行解作为最优解返回。几个障碍：需要一个初始的可行解对可行解应该做什么样的改变并不总是一目了然如何避免陷入局部极值（最根本的困难）单纯形法 ...

Posted by MaggicQ on July 11, 2017

算法笔记-算法效率分析基础

算法效率分析考虑算法运行时间的度量单位，应该找出算法中最重要的操作，即所谓的基本操作（basic operation），他们对总运行时间的贡献最大，然后计算他们的运行次数。对算法的效率分析包括三个方面：最优效率最差效率平均效率，必要性：有很多重要的算法的平均效率比他们的最差效率要好很多。渐进符号 $O(g(n))$ 是增长次数小于等于 $g(n)$ ...

Posted by MaggicQ on July 1, 2017

算法笔记-动态规划

动态规划动态规划是求解多阶段最优决策问题的通用方法。如果问题是由交叠的子问题构成的，我们可以用动态规划技术来解决它。三个基本例子币值最大化问题：给定一排硬币，其面值均为正整数$c_1, c_2, \cdots , c_n$ ，这些整数并不一定两两不同。请问如何选择硬币，使得在其原始位置互不相邻的条件下，所选硬币的总金额最大。设最大可选金额为$F(n...

Posted by MaggicQ on June 18, 2017