`
mycream
  • 浏览: 55597 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

POJ 1007 DNA Sorting(待改善)

 
阅读更多

POJ 1007 DNA Sorting

这道题做的不舒服,明白题目的意思后就想到一种最笨的解题思路——双重 for 循环来计算 DNA 序列的数值(左边字母大于右边字母的总个数)。但我始终觉得这不是好的算法,隐约觉得应该用“动态规划”。可惜学艺不精,一直没明白动态规划的原理。标记出来,期望改善之。

 

双重 for 循环的做法很快就实现了,开始使用 TreeMap 来存储数据,期望使用它的排序功能。结果忽略了值相等的情况,老是报 WA。所以改成将值拼凑入 DNA 序列开头的做法,并自定义 compare 方法进行比较。

代码如下:

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Collections;

public class Main {
	private List<String> dnaList;

	public int countValue(String dna) {
		int value = 0;
		char[] c = dna.toCharArray();
		for (int i = 0; i < c.length; i++) {
			for (int j = i + 1; j < c.length; j++) {
				if (c[i] > c[j]) {
					value++;
				}
			}
		}
		return value;
	}

	public void run() throws Exception {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(); // string length
		int m = scan.nextInt(); // lines limit

		dnaList = new ArrayList<String>(m);

		scan.nextLine();
		for (int i = 0; i < m; i++) {
			String dna = scan.nextLine();
			int count = countValue(dna);
			dnaList.add((char)count + dna);
		}

		// sort
		Collections.sort(dnaList, new Comparator<String>() {
			public int compare(String o1, String o2) {
				return o1.charAt(0) - o2.charAt(0);
			}
		});

		// output
		Iterator<String> iter = dnaList.iterator();
		while (iter.hasNext()) {
			String dna = iter.next();
			System.out.println(dna.substring(1, dna.length()));
		}
	}

	public static void main(String[] args) {
		Main m = new Main();
		try {
			m.run();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}
 
0
1
分享到:
评论

相关推荐

    poj 1007 DNA Sorting

    DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34868 Accepted: 13480 Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are ...

    POJ1007-DNA Sorting

    【标题】"POJ1007-DNA Sorting"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目要求参赛者编写程序,对DNA序列进行排序,具体而言,就是对一系列由ATCG四种碱基组成的DNA字符...

    poj dna sorting

    poj dna sorting 问题,研究的ac coderrrrrrr

    poj1007AC代码

    poj1007 AC代码 0MS过题写法 不过是个水题 哈哈哈哈

    poj1007代码

    poj1007题代码,DNA问题,C++语言,map

    POJ1094-Sorting It All Out

    【标题】"POJ1094-Sorting It All Out" 是一道来自北京大学在线判题系统POJ(Problem Set)的编程题目。这道题目主要考察的是排序算法的应用与优化,旨在提高参赛者的算法设计和实现能力。 【描述】"北大POJ1094-...

    poj 1007代码

    ACM是很好的,多在OJ上练习,你会有惊喜的。很能增加您的技能。

    poj DNA排序

    简单的字符串操作和求逆序对数,是程设poj习题

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    描述中提到的"三道几何题:hdu 1007、hdu 2289、poj 3714"暗示了这是一个关于几何算法的题目集,涉及到三个不同的在线判题系统:HDU(杭州电子科技大学在线评测系统)的1007题和2289题,以及POJ的3714题。...

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

    East Central North America 1998测试数据

    "East Central North America 1998测试数据" 提供的是一组与1998年东中北美地区编程竞赛相关的测试资源,特别提及了POJ(Problem Set of Peking University Online Judge)中的1007DNA Sorting问题。这个标题暗示了...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    ACM-POJ 算法训练指南

    1. **状态转移方程**:设计复杂的动态规划状态转移方程(poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034)。 2. **记忆化搜索**:结合动态规划和递归搜索(POJ3254, poj2411, poj1185)。 3. **...

    poj训练计划.doc

    根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...

    poj题目分类

    * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    poj各种分类

    标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...

    poj 3414解题报告

    poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告

Global site tag (gtag.js) - Google Analytics