2007-08-19
全文显示

《程序员》2007第八期之算法擂台

关键字: 算法 程序员 动态规划
题目描述（手头没书，不知道有没有记错）：有v个在一条直线上的村庄，要在其中的p个村庄上修建邮局。每个村庄将会选择离其最近的村庄收发邮件。现在要选择这p个邮局的修建地址，使得这v个村庄到邮局的总路程尽可能少。 输入：首先是两个正整数v,p，表示村庄个数与邮局个数。 然后是v个不小于零的整数，表示v个村庄的坐标。 输出：p从小到大个用空格分开的整数，表示p个邮局的坐标。 这个题目用简单的重举法显然是行不通的，那样时间复杂度将达到阶乘级别。 我用的是动态规划，时间复杂度为O(n*n*(n+p)).不知道有没有更好的算法。 注意：这个题目的解实际上不唯一，比如v=2,p=1的情形，邮 ...
2007-08-01
全文显示

一个关于字符串操作的算法题

关键字: 算法 字符串 行程编码
最近在网上看到一道关于字符串操作的算法题,不过原题的表述以及给出的数据都有问题.这里我给出修正后的题目: 题目:设计一个方法 String encode(String str),对字符串str进行如下转换操作为一个新字符串:          逐个扫描str的每个字符,          1.若当前字符为'_',则添加"\UL"到新字符串; 否则:       ...
Eastsun
搜索本博客
我的相册
1b680e5a-efae-3ec3-8ccd-970a4a72a056-thumb
6.5beta.PNG
共 61 张
最近加入圈子
存档
最新评论