分类: 算法

算法本质上是数学的分支。本分类下的文章可能介绍数学知识,但目的是为了编写程序。

树状数组求逆序对

2019年10月3日

第{{index + 2}}步,对于arr[{{index}}],即{{elenemt}},在cArr里进行标记。 cArr= 如果有以{{elenemt}}为后件的逆序对,那么该逆序对的前件一定在cArr索引{{elenemt+1}}到9(左闭右闭)区间内(以下划线表示)。这一步非常重要,请务必多 […]

ACWING 651. 逛画展

2019年9月11日

原题链接:https://www.acwing.com/problem/content/description/653/ 博览馆正在展出由世上最佳的 M 位画家所画的图画,你想到博览馆去看这些才华横溢的大师们的作品。 可是,那里的博览馆有一个很奇怪的规定,就是在购买门票时必须说明两个数字, l和r, […]

单调队列及应用

2019年9月11日

单调队列 单调队列是一种优先队列,要求元素是可排序的,或传入比较器。单调队列继承队列的以下性质: 可从队尾插入元素。 可从队头弹出元素。 在队列中的所有元素里,队头元素一定是最早插入的。在队列中的所有元素里,队尾元素一定是最晚插入的。(FIFO) 单调队列有以下特殊性质: 一个元素插入队列后,即使没 […]

126. Word Ladder II

2019年8月29日

LeetCode是用C# release模式运行的。 解法1: 使用队列进行广度优先搜索,统一在Dequeue后进行终止条件判断。 缺点是生成下一个状态,enqueue前,没有检查是不是解。 using System; using System.Collections.Generic; using […]

如何在图中新增一条边,使任意两点的距离之和最小?

2017年6月24日

游戏《太阳帝国的原罪》里,瓦萨里种族可以建造相位跳跃稳定器,飞船可以直接从一个有相位跳跃稳定器的星球跳跃到另一个有相位跳跃稳定器的星球,无需现有路线。 如图1,粉色是我的星球。如何添加两个相位跳跃稳定器,能够最大程度地减少我方飞船在各个星球之间的飞行距离? 把上图数学化,如图2,红色是可以添加相位跳 […]

Burst Balloons

2015年12月5日

来自https://leetcode.com/problems/burst-balloons/ 题目 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by […]

Manacher最长回文算法

2015年2月3日

本文将一步一步构造Manacher算法,心急的一定看不懂!请先练习下面的习题。 探索最长回文串性质 题1:已知字符串以center为中心对称,求完整的字符串。 abcd??? | center 答 abcdcba | center 题2:接上题,abcdcba后面还有一些字符,以center2为中心 […]

求两个集合/数组的交集

2015年1月15日

A = [9, 1, 4, 2, 5] k个整数 B = [3, 1, 8, 7, 6, 5] n个整数 Intersection => [1, 5] 复杂度理论证明 问题复杂度下限 设A为较小的列表,B为较大的列表,则k<n。 对于A中的每个元素都要查看B中是否有相同元素。查看B中是否有相同 […]

检查链表是否有环,带数学推导

2015年1月9日

推导 给定下列列表(4指回2),若有快慢两个指针,慢指针每次前进一步,快指针每次前进两步,求两指针何处相遇? 1-2-3-4 |___| 解: 设两指针前进n次。n必定大于等于1。 [MathematicaIn n=”1″/]Reduce[Mod[n – 1, 3 […]