MaggicQ's Blog

路漫漫其修远兮

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

算法笔记-分治法

分治法主定理对于通用分治递推式： $T(n) = aT(n/b) + f(n)$ 那么：合并排序对于一个需要排序的数组，合并排序将它一分为二，并对每个子数组递归排序，然后把这两个排好序的子数组组合并为一个有序数组。其中 $Merge$ 函数是将两个有序数据进行合并：复杂度分析：键值比较次数 $C(n)$ 当 $n > 1$ 时， $C(n...

Posted by MaggicQ on May 29, 2017

算法笔记-变治法

变治法变治法（transform-and-conquer），将问题分解成两个阶段工作： ”变“的阶段，把问题的实例变得更容易求解， ”治“的阶段，对实例进行求解。变治思想有三种主要的类型：变换为同样问题的一个更简单或者更方便的实例，实例化简。变换为同样实例的不同表现，称为改变表现。变换为另一个问题的实例，这种问题的算法是已知的，称为问题化简。下面是一...

Posted by MaggicQ on May 28, 2017