减治法(reduce and conquer method)同样是把一个大问题划分为若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。所以，严格地说，减治法应该是一种退化了的分治法。应用减治法技术设计的算法通常具有很高的效率，一般来说其时间复杂性是$O(log_2n)$。 …

  回溯法(back trace method)是一种有组织的系统化搜索技术，可以看作是蛮力法穷举搜索的改进。蛮力法穷举搜索首先生成问题的可能解，然后再去评估可能解是否满足约束条件。而回溯法每次只构造可能解的一部分，然后评估这个部分解，如果这个部分解有可能导致一个完整解，对其进一步构造，否则，就不必继续构造这个部分解了。回溯法常…

  分治者，分而治之也（感觉有点废话）。分治法（divide and conquer method)是最著名的算法设计技术，作为解决问题的一般性策略，分治法在政治和军事领域也是克敌制胜的法宝。 概述   分冶法的设计思想是将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地…

  贪心法(greedy method)是一个把复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是相对于当前解的一个扩展，直到获得问题的完整解。贪心法的典型应用是求解最优化问题，而且对许多问题都能得到整体最优解，即使不能得到整体最优解，通常也是最优解的很好近似。 概述 贪心法的设计思想   贪心法在解…

  蛮力法(brute force method)，也称穷举法，是一种简单而直接地解决问题的方法，常常直接基于问题的描述，因此，也是最容易应用的方法。 蛮力法的设计思想   满立法所依赖的技术是扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。依次处理所有元素是蛮力法的关键，为了…

[TOC] 下界   对于任何待求解的问题，如果能找到一个尽可能大的函数g(n)(n为问题规模)，使得求解该问题的所有算法都可以在$\Omega(g(n))$的时间内完成，则称函数g(n)为该问题计算复杂性的下界(lower bound)。如果已经知道一个和下界的效率类型相同的算法，则称该下界是紧密(close)的。 平凡下界 …

基础概念 算法定义   算法（algorithm)是解决问题的方法。严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列，此外算法还必须满足下列5个重要特性： （1）输入：一个算法有另个或多个输入。算法的输入有两种方式：一种是从外界获得数据，另一种是由算法自己产生并被处理的数据。 （2）输出：一个算法有一个或多个输出。…

一、题目详解 问题描述 给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿由相邻的陆地连接形成，相邻指水平方向或垂直方向（斜向相邻的陆地不视为同一岛屿）。网格的边界和边缘均被水包围。 示例 输入： grid = [ ["1","1",&quo…