算法

N皇后51. N皇后 题目描述 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 示例： 12345678910111213输入: 4输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."]]解释: 4 皇后问题存在两个不同的解法。 问题分析约束条件为每个棋子所在的行、列、对角线都不能有另一个棋子。 使用一维数组表示一种解法，下标（index）表示行，值（value）表示该行的Q（皇后）在哪一列。每行只存储一个元素，然后递归到下一行 ...

状态转移方程定义动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。若给定了第K阶段的状态Sk以及决策uk(Sk),则第K+1阶段的状态Sk+1也就完全确定。也就是说Sk+1与Sk,uk之间存在一种明确的数量对应关系，记为Tk(Sk,uk),即有Sk+1= Tk(Sk,uk)。 这种用函数表示前后阶段关系的方程，称为状态转移方程。在上例中状态转移方程为 Sk+1= uk(Sk) 。 设计适用条件 任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。 1.最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。 2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过 ...

Union-Find 算法（并查集算法）⼀、问题介绍简单说，动态连通性其实可以抽象成给⼀幅图连线。⽐如下⾯这幅图，总共 有 10 个节点，他们互不相连，分别⽤ 0~9 标记： 现在我们的 Union-Find 算法主要需要实现这两个 API： 12345678class UF {     /* 将 p 和 q 连接 */     public void union(int p, int q);     /* 判断 p 和 q 是否连通 */     public boolean connected(int p, int q);     /* 返回图中有多少个连通分量 */     public int count(); } 这⾥所说的「连通」是⼀种等价关系，也就是说具有如下三个性质： 1、⾃反性：节点 p 和 p 是连通的。 2、对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。 3、传递性：如果节点 p 和 q 连通， q 和 r 连通，那么 p 和 r 也连通。 ⽐如说之前那幅图，0〜9 任意两个不同的点都不连通，调⽤ connected 都 会 ...

「游戏」寻路算法之A Star算法原理及实现前言自动寻路是在一些如MMORPG等类型游戏中常见的一种功能，其给了玩家良好的游戏体验，使得玩家在游戏过程中省去了大量游戏坐标点的记录以及长时间的键盘操作，不必记忆坐标，不必担心迷路，用最快捷的方法移动到指定地点。 寻路算法（自动寻路算法，下同），其实可以看作是一种路径查找算法以及图搜索算法，图搜索（Graph Search）算法是用于在图上进行一般性发现或显式地搜索的算法。这些算法在图上找到出路径，但没有期望这些路径是在计算意义上是最优的。 路径查找算法（Pathfinding）是建立在图搜索算法的基础上，它探索节点之间的路径，从一个节点开始，遍历关系，直到到达目的节点。这些算法用于识别图中的最优路由，算法可以用于诸如物流规划、最低成本呼叫或IP路由以及游戏模拟等用途。 常见的路径搜索算法和图搜索算法有：A（A Star）算法、Dijkstra算法、广（深）度优先搜索、最佳优先搜索、Jump Point Search算法等，今天本文主要讲解的是A（A Star）算法的原理以及实现。 常见搜索算法Dijkstra算法迪杰斯特拉算法(Dijks ...

二分查找模版模版第⼀个，最基本的⼆分查找算法： 因为我们初始化 right = nums.length - 1 所以决定了我们的「搜索区间」是 [left, right] 所以决定了 while (left <= right) 同时也决定了 left = mid+1 和 right = mid-1 因为我们只需找到⼀个 target 的索引即可 所以当 nums[mid] == target 时可以⽴即返回 1234567891011121314int binary_search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { ...