- 浏览: 257136 次
- 性别:
- 来自: 南京
-
文章分类
最新评论
-
mabusyao:
漠北空城 写道请问下,你这个是JDK版本是多少呢?!忘记了,应 ...
HashMap 源码解读 -
漠北空城:
请问下,你这个是JDK版本是多少呢?!
HashMap 源码解读 -
schumee:
完美团队~
项目沉思录 - 1.1 -
winie:
整理下 搞成引擎嘛 国产需要这样的engine
简单工作流引擎 -
mabusyao:
某位同学给我提供的堪称完美的解决方案:1. 将三个int数组放 ...
CraneWork
package palindrome;
/*Problem Statement
A palindrome is a string that reads the same forward and backward.
A palindrome substring is a contiguous sequence of characters taken from a string that form a palindrome.
A palindrome substring of a string is maximal if we can't extend it to get a bigger palindrome substring.
For example, string "acdadc" has 2 maximal palindrome substrings - "a" (the first one) and "cdadc".
All other palindrome substrings (like "dad" or "c") can be extended to "cdadc", so they are not maximal.
You will be given a String[] str.
Concatenate the elements of str to form one long string, and return the number of maximal palindrome substrings contained in that string.
Definition
Class: MaximalPalindromeSubstrings
Method: countMaximalPalindromeSubstrings
Parameters: String[]
Returns: int
Method signature: int countMaximalPalindromeSubstrings(String[] str)
(be sure your method is public)
Constraints
- str will contain between 1 and 50 elements, inclusive.
- Each element of str will contain between 1 and 50 characters, inclusive.
- Each character of each element of str will be a lowercase letter ('a'-'z').
Examples
0) {"acdadc"} Returns: 2 The example from the problem statement.
1) {"ababab"} Returns: 2 The two maximal palindrome substrings here are "ababa" and "babab".
2) {"aaaa","bbb","axxx"} Returns: 3 Remember to use the whole input!
3) {"abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh"} Returns: 14
This problem statement is the exclusive and proprietary property of TopCoder, Inc.
Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited.
(c)2003, TopCoder, Inc. All rights reserved. */
public class MaximalPalindromeSubstrings {
public static int countMaximalPalindromeSubstrings(String[] str) {
int length = 0;
for(int i = 0; i < str.length; i++) {
length = length + str[i].length();
}
char[] array = new char[length];
int p = 0;
for(int i = 0; i < str.length; i++) {
char[] tempArray = str[i].toCharArray();
for(int j = 0; j < tempArray.length; j++) {
array[p] = tempArray[j];
p++;
}
}
p = 0;
while(p<length) {
int index = 0;
while(p - index >=0 && p + index < length) {
if(array[p - index] == array[p + index]) index++;
else break;
}
index--;
save(p - index, p + index);
index = 0;
if((p + 1 < length) && (array[p] == array[p + 1])) {
while(p - index >=0 && p + 1 + index < length) {
if(array[p - index] == array[p + 1 + index]) index++;
else break;
}
index--;
save(p - index, p + 1 + index);
}
p++;
}
print(array);
return root -1;
}
// Stack for the result storage.
private static Pair[] result = new Pair[100];
private static int root = 0;
static class Pair {
int start = 0;
int end = 0;
Pair(int i, int j) {
start = i;
end = j;
}
}
/*
* Check if there is a larger ranger or smaller range.
* Erase the smaller range if needed.
*/
private static void save(int i, int j) {
if(root == 0) {
Pair pair = new Pair(i, j);
result[0] = pair;
root++;
}
else {
int cursor = root - 1;
if (result[cursor].start <= i && result[cursor].end >= j) return;
while(cursor >= 0) {
if(result[cursor].start >= i && result[cursor].end <= j) {
cursor--;
result[root - 1] = null;
root--;
}
else break;
}
Pair pair = new Pair(i, j);
result[root] = pair;
root++;
}
}
/*
* print the result out.
*/
private static void print(char[] array) {
for(int i = 0; i < root; i++) {
for(int j = result[i].start; j <= result[i].end; j++) {
System.out.print(array[j]);
}
System.out.print("\n");
}
}
}
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
try {
String[] a = {"aaaa","bbb","axxx"};
String b = "abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh";
MaximalPalindromeSubstrings.countMaximalPalindromeSubstrings(new String[]{b});
} catch(Exception e) {
e.printStackTrace();
}
}
}
发表评论
-
大数据下的实体解析
2016-07-07 12:03 671大数据时代的实体解析困境 <!--[if !sup ... -
中文相似度匹配算法
2015-12-30 14:44 1921基于音形码的中文字 ... -
各种语言写的wordcount
2015-09-24 16:07 0Java版本: String input ... -
数组双指针算法的研究
2015-07-14 16:59 2484双指针算法在数组/链 ... -
摩尔投票法
2015-06-30 20:13 18466摩尔投票法 提问: 给定一个int型数组,找出该数 ... -
(转)最长回文字串算法
2015-01-18 14:30 1454来自(http://blog.163.com/zhaohai ... -
STRUTS2 源码 - Logging System
2012-05-24 08:51 1428看了STRUTS2的源码,了解了它的logging系统,觉得还 ... -
在线词典的数据结构实现。
2012-05-18 08:37 0昨天在网上看到了一道百度的面试题: Baidu写道 ... -
存储中间计算结果的动态规划算法
2012-04-18 15:50 1238public class RodCutting { ... -
java写的四则运算器
2011-08-19 22:19 2764本打算做一个从RE到NFA的转换器,思路已经理清了,但是在动手 ... -
什么是最小二乘拟合
2007-09-14 21:27 1005对于一个数据点(x1, y1), ... (xn, yn)的集 ... -
CraneWork
2008-07-14 19:14 1077/*Problem Statement There are ... -
SalesRouting
2008-07-15 10:53 826package salesRouting;/*Problem ... -
FactorialSystem
2008-07-21 19:36 874/*Problem StatementIn the facto ... -
RecurringNumbers
2008-07-22 09:41 956/*Problem StatementA rational n ... -
HardDuplicateRemover
2008-07-23 15:17 970/*Problem StatementWe have a se ... -
BlockStructure
2008-07-23 20:55 824/*Problem StatementA group of v ... -
SkipStones
2008-07-28 17:31 839/*Problem StatementWhen a stone ... -
TheaterVisit
2008-07-28 17:31 801/*Problem StatementYou want to ... -
SquareDigits
2010-07-06 12:36 1059Problem Statement ***Note: ...
相关推荐
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
JAVA程序 Palindrome.java 输入任何字母数字组合 检查是否是回文结构? 例:abccba 从左往右看 和 从右往左看一样 为回文结构 包括检查是否带标点符号 检查是否有空格 如a bccba 输入带空格 仍为回文结构
Pku acm 第1159题 Palindrome 代码,有详细的注释,动态规划
Palindrome Sub-Array,Problem Description A palindrome sequence is a sequence which is as same as its reversed order. For example, 1 2 3 2 1 is a palindrome sequence, but 1 2 3 2 2 is not. Given a 2-...
在编程领域,回文是一种特殊的字符串,它从前向后读和从后向前读是一样的,例如"madam"、"racecar"等。本主题主要关注如何使用C++语言来实现回文检测算法。C++作为一门强大的面向对象编程语言,提供了丰富的标准库和...
最近,我接触了一个项目“huiwenshu.rar_palindrome”,该项目的目标是开发一个能够处理1-99999位数回文数判断的程序,同时,这个项目还涉及到了银行管理系统的部分功能,如利率计算、密码管理以及余额管理。...
《LeetCode9:判断回文数——Java实现详解》 在编程的世界里,LeetCode是一个广受欢迎的在线平台,它提供了各种算法问题供程序员们挑战和提升技能。今天我们要探讨的是LeetCode第9题——“回文数”。...
在编程领域,尤其是Python学习和开发中,palindrome_soln.py文件是用于演示如何编写一个检测字符串是否为回文的程序。回文是指一个字符串从前往后读和从后往前读是完全相同的字符串。这个问题通常是编程初学者练习...
《PyPI官网下载:探索check-palindrome-kriti-0.0.1.tar.gz中的Python库知识》 PyPI(Python Package Index)是Python开发者的重要资源库,它提供了丰富的Python库供全球开发者下载和使用。本文将深入探讨标题为...
今天,我们重点分析并解读题名为Palindrome Permutation(回文排列)的Java题解代码,这道题目是关于字符串处理的经典问题之一。 首先,我们需了解Palindrome Permutation问题的实质:给定一个字符串,判断该字符串...
标题中的"Stack3 java.rar_Stack3 java_palindrome"表明这是一个关于使用Java编程语言实现堆栈(Stack)数据结构,并且应用在判断回文(Palindrome)字符串上的项目。回文是指正读反读都能读通的字符串,如“level”...
在探讨JavaScript编程语言以及LeetCode平台上的一道编程题目“Valid Palindrome”的解法时,我们需要了解几个关键点:JavaScript编程、数据结构与算法、以及字符串处理技巧。LeetCode是一个面向IT专业人员和学生的...
而“Palindrome Permutation II”是众多编程题目中的一道,它主要考察了程序员对字符串处理和排列组合的理解。在这道题目中,通常要求编写一个函数,该函数接受一个字符串作为输入,并返回该字符串所有可能的回文...
在Java中实现回文数检测,可以编写一个名为PalindromeNumber的类,并在其中定义一个方法比如isPalindrome,该方法接收一个整型参数并返回一个布尔值,表示该整数是否是回文数。在方法内部,根据上述逻辑来判断并返回...
LeetCode Palindrome Number解决方案 在本节中,我们将讨论如何确定一个整数是否是一个回文数。一个整数是一个回文数当它从左到右读取和从右到左读取相同。 问题描述: 给定一个整数,判断它是否是一个回文数。 ...
while is_palindrome and p2: if p1.val != p2.val: is_palindrome = False p1 = p1.next p2 = p2.next # Step 4 (可选): 恢复链表结构 prev = None current = second_half_head while current: next_...
在LeetCode上,有一道题目叫做“Longest Chunked Palindrome Decomposition”,也就是“最长块状回文分解”。这个问题主要考察的是算法和编程能力,需要解决者了解回文(palindrome)这个概念。回文是指一个字符串...
在JavaScript中,处理leetcode上的编程题目时,正确理解和解决"131.Palindrome Partitioning"这类字符串划分问题是一项重要的技能。本题要求编写一个函数,该函数将给定的字符串划分为尽可能多的回文子字符串,并...
在深入探讨Java实现的LeetCode题解Can Make Palindrome from Substring的详细知识点之前,让我们先了解该题目的背景和要求。该题目要求编写一个Java方法,这个方法需要判断给定字符串的任何子串是否可以通过重新排列...