Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。

PAT 1005. Spell It Right

Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.

继续阅读»

PAT 1004. Counting Leaves

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

继续阅读»

PAT 1003. Emergency

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

继续阅读»

PAT 1002. A+B for Polynomials

This time, you are supposed to find A+B where A and B are two polynomials.

继续阅读»

PAT 1001. A+B Format

Calculate a + b and output the sum in standard format — that is, the digits must be separated into groups of three by commas (unless there are less than four digits).

继续阅读»

Project Euler一句话题目

欧拉计划(Project Euler)是一个好玩的编程网站,其网址为http://projecteuler.net/
类似于各大ACM比赛的OJ(Online Judge),上面提供了许多有趣的数学、编程题目。不同的是,其题目很简洁,只需提交最终答案,可以使用任何语言,任何复杂度的算法。如果不想做ACM里面题目很长、意思很复杂、输入输出限制很严格的题目,可以选择上面的题目娱乐一番。不过后面的题目会越来越难。

LCA与RMQ互相转化

前面我们介绍过LCARMQ问题各自的解法,其实这两个问题非常类似,本质上是等价的。他们之间可以互相进行转化,并且复杂度不高,有时恰当的转化可以大大提升算法解决问题的性能,这里主要介绍二者之间互相转化的算法思想及核心代码实现。

RMQ问题的ST算法

RMQ问题(Range Minimum/Maximum Query,区间最值问题),是指给定一个长度为n的数列A,回答若干次询问RMQ(A,i,j)(i,j<=n)(通常次数非常巨大),每次返回数列A中下标在i,j里的最小(大)值。
RMQ问题解法很多,如朴素算法、线段树、ST算法RMQ与LCA互相转化等,不同算法思想及复杂度均有所差异。本文主要讲解其中非常高效的稀疏表算法(Sparse Table,ST算法)。

继续阅读»

LCA问题的跳表算法

LCA问题(Least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u, v)(通常查询数量较大),每次求树T中两个顶点u和v的最近公共祖先,即找一个节点,同时是u和v的祖先,并且深度尽可能大(尽可能远离树根)。
LCA问题有很多解法:线段树、Tarjan算法跳表RMQ与LCA互相转化等。本文主要讲解跳表算法的原理及详细实现,相对于Tarjan等算法而言,其不太为人所熟知,但同样是非常有效。

继续阅读»

LCA问题的Tarjan算法

LCA问题(Least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u, v)(通常查询数量较大),每次求树T中两个顶点u和v的最近公共祖先,即找一个节点,同时是u和v的祖先,并且深度尽可能大(尽可能远离树根)。
LCA问题有很多解法:线段树、Tarjan算法跳表RMQ与LCA互相转化等。本文主要讲解Tarjan算法的原理及详细实现。

继续阅读»

BFPRT算法

BFPRT算法是解决从n个数中选择第k大或第k小的数这个经典问题的著名算法,但很多人并不了解其细节。本文将首先介绍求解这个第k小数字问题的几个思路,然后重点介绍在最坏情况下复杂度仍然为O(n)的BFPRT算法。

继续阅读»

C++类型转换

类型转换可以将一种类型的数据转化为另一种类型的数据以满足精度或者其他方面的要求,是程序设计过程中经常遇到的问题。
C++在C语言的类型转换基础上添加了很多新的特性,可以更清晰地表明程序员的意图,以及进行更安全的转换,需要根据不同的场景适当地选择使用。本文主要介绍C和C++中关于类型转换的相关内容。这里主要关心显示的强制类型转化,隐式类型转换由编译程序按照一定规则自动完成,而不需人为干预,较危险的转换通常伴有警告提醒,唤起程序员的注意。

继续阅读»

并查集及其在最小生成树中的应用

并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用,。
本文首先介绍并查集的定义、原理及具体实现,然后以其在最小生成树算法中的一个经典应用为例讲解其具体使用方法。

继续阅读»

二分查找

二分查找是一种经典的算法,是每个程序员的入门内容之一,但是根据《编程珠玑》上面介绍,90%的程序员写的二分查找的程序中有bug,并且他并不认为没有bug的代码就是正确的。
可见二分查找是比较考验程序员的编码基本功的。那么如何查找数组中一个元素是否存在并且如何找出其第一次或最后一次出现的位置呢?本文接下来将对这个问题进行仔细分析并提供相应的代码。

继续阅读»

CPU占用率正弦曲线

编程之美上有这么一道题:写一个程序,让用户来决定Windows任务管理器(Task Manager)的CPU占用率。程序越精简越好,计算机语言不限。例如,可以实现下面三种情况:

继续阅读»

分页: 第一页 «上一页 6789101112131415 下一页 » 最后一页

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论