仓酷云

标题: 来看用静态计划算法对最年夜子串成绩的java完成 [打印本页]

作者: 兰色精灵 时间: 2015-1-18 11:24
标题: 来看用静态计划算法对最年夜子串成绩的java完成
C++编译的是本地码,优点是启动快,而且可以精确控制资源因此可以开发很高效的程序.缺点是编程麻烦,而且容易留下安全隐患.跨平台靠源代码在各个平台间分别编译(一处编写到处编译)
最年夜字串成绩形貌也许就是给定2个字符串，找出他们两个共有的最长字符串。好比一个是"tabcfg"别的一个"abckj"那末最年夜子串就是"abc".
静态计划算法最主要的就是分化成绩，找出递回。说一下我的思索思绪，起首拿到2个字符串，怎样找到最宗子串呢？
1.假定他们(字符串a,b)的头字母不不异的话，那末分离往失落首字母对照，也就是说用a.subString(1)和b对照，用b.subString(1)和a对照，最宗子字符串没变吧？谜底是一定的。ok递回呈现了，停止前提就是有一个字符串变空，前往值就是a和b的最宗子串。
b.假定他们头字母不异，那末一向对照下往，晓得二者的第n个字母不不异，然后把前n-1个字母存为子字符串c,把a.subString(1)和b前往了局记为d,b.subString(1)和a前往了局记为e,那末前往c，d和e最长的一个(感激lexy的批评，之前的确漏掉一种情形。不该该间接把后面的不异的往失落间接对照的，如今代码已更新了)。
大概有人说应当从前面往后面对照，找到不异的然后一个个再往前比，实在事理都是一样的，关头要找到分化成绩的办法。这里只是举一反三，上面是详细的java完成。
import　java.util.HashMap;
import　java.util.Map;

/**
*　@author　HEACK
*
*/
public　class　CompareStr　{

　　　　　　　　/**
　　　　　　　　*　@param　args
　　　　　　　　*/
　　　　　　　　public　static　void　main(String[]　args)　{
　　　　　　　　　　　　　　　　//　TODO　Auto-generated　method　stub
　　　　　　　　　　　　　　　　String　str1　=　"abcde1234567abcdefghijk";
　　　　　　　　　　　　　　　　String　str2　=　"abcdefgh12345";

　　　　　　　　　　　　　　　　//String　str2　=　"abc　happyies　dutcbirthday　peter";
　　　　　　　　　　　　　　　　CompareStr　cj　=　new　CompareStr();
　　　　　　　　　　　　　　　　System.out.println(cj.getLongestString(str1,str2));

　　　　　　　　}

　　　　　　　　private　boolean　isEmpty(String　str)　{
　　　　　　　　　　　　　　　　return　str　==　null　||　str.trim().length()　==　0;
　　　　　　　　}
　　　　　　　　private　Map　map　=　new　HashMap();

　　　　　　　　private　String　getLongestString(String　str1,　String　str2)　{
　　　　　　　　　　　　　　　　if　(isEmpty(str1)　||　isEmpty(str2))　{
　　　　　　　　　　　　　　　　　　　　　　　　return　"";
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　StringBuffer　key　=　new　StringBuffer();
　　　　　　　　　　　　　　　　key.append(str1).append("&&").append(str2);
　　　　　　　　　　　　　　　　if　(map.containsKey(key.toString()))　{
　　　　　　　　　　　　　　　　　　　　　　　　return　(String)map.get(key.toString());
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　StringBuffer　longestStr　=　new　StringBuffer();
　　　　　　　　　　　　　　　　char[]　str1List　=　str1.toCharArray();
　　　　　　　　　　　　　　　　char[]　str2List　=　str2.toCharArray();
　　　　　　　　　　　　　　　　int　i　=　0;
　　　　　　　　　　　　　　　　for　(i　=　0;　i　<　str1List.length　&&　i　<　str2List.length;　i++)　{
　　　　　　　　　　　　　　　　　　　　　　　　if　(str1List[i]　==　str2List[i])　{
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　longestStr.append(str1List[i]);
　　　　　　　　　　　　　　　　　　　　　　　　}　else　{
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　String　subStr1　=　str1.substring(i);
　　　　　　　　　　　　　　　　String　subStr2　=　str2.substring(i);
　　　　　　　　　　　　　　　　if　(i　==　0)　{
　　　　　　　　　　　　　　　　　　　　　　　　String　retStr1　=　getLongestString(subStr1.substring(1),　subStr2);
　　　　　　　　　　　　　　　　　　　　　　　　String　retStr2　=　getLongestString(subStr1,　subStr2.substring(1));
　　　　　　　　　　　　　　　　　　　　　　　　String　returnStr　=　retStr1.length()　>=　retStr2.length()　?　retStr1　:　retStr2;
　　　　　　　　　　　　　　　　　　　　　　　　map.put(key.toString(),　returnStr);
　　　　　　　　　　　　　　　　　　　　　　　　return　returnStr;
　　　　　　　　　　　　　　　　}　else　{
　　　　　　　　　　　　　　　　　　　　　　　　String　retStr1　=　getLongestString(str1.substring(1),　str2);
　　　　　　　　　　　　　　　　　　　　　　　　String　retStr2　=　getLongestString(str1,　str2.substring(1));
　　　　　　　　　　　　　　　　　　　　　　　　String　retStr　=　retStr1.length()　>　retStr2.length()　?　retStr1
　　　　　　　　　　　　　　　　　　　　:　retStr2;
　　　　　　　　　　　　　　　　　　　　　　　　String　returnStr　=　retStr.length()　>=　longestStr.toString().length()　?　retStr
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　:　longestStr.toString();
　　　　　　　　　　　　　　　　　　　　　　　　map.put(key.toString(),　returnStr);
　　　　　　　　　　　　　　　　　　　　　　　　return　returnStr;
　　　　　　　　　　　　　　　　}
　　　　　　　　}

}
HashMap用来存储已盘算过的字符串，用空间换工夫。代码固然还能够优化，您也能够一试技艺哦。

最后我再次声明，我并没有说不看好java，实际上我对java很乐观的，毕竟她正在不断改进中，我相信她总有一天会和.net网页编程并驾齐驱的

作者: 莫相离 时间: 2015-1-20 23:53
J2SE开发桌面应用软件比起 VC,VB,DEPHI这些传统开发语言来说，优势好象并不明显。J2ME对于初学者来说，好象又有点深奥，而且一般开发者很难有开发环境。

作者: 简单生活 时间: 2015-1-26 21:59
吧，现在很流行的Structs就是它的一种实现方式，不过Structs用起来实在是很繁，我们只要学习其精髓即可，我们完全可以设计自己的MVC结构。然后你再研究一下软件Refactoring (重构)和极限XP编程，相信你又会上一个台阶。做完这些，你不如整理一下你的Java代码，把那些经典的程序和常见的应用整理出来，再精心打造一番，提高其重用性和可扩展性。你再找几个志同道合的朋友成立一个工作室吧

作者: 飘飘悠悠 时间: 2015-2-4 20:42
象、泛型编程的特性，广泛应用于企业级Web应用开发和移动应用开发。

作者: 山那边是海 时间: 2015-2-9 03:46
[url]http://www.jdon.com/[/url]去下载，或到同济技术论坛的服务器[url]ftp://nro.shtdu.edu.cn[/url]去下，安装上有什么问题，可以到论坛上去提问。

作者: 因胸联盟 时间: 2015-2-10 06:50
一直感觉JAVA很大，很杂，找不到学习方向，前两天在网上找到了这篇文章，感觉不错，给没有方向的我指了一个方向，先不管对不对，做下来再说。

作者: 小女巫 时间: 2015-2-28 23:52
象、泛型编程的特性，广泛应用于企业级Web应用开发和移动应用开发。

作者: 分手快乐 时间: 2015-3-10 10:51
是一种由美国SUN计算机公司(Sun Microsystems, Inc.)所研究而成的语言

作者: 透明 时间: 2015-3-17 06:11
一直感觉JAVA很大，很杂，找不到学习方向，前两天在网上找到了这篇文章，感觉不错，给没有方向的我指了一个方向，先不管对不对，做下来再说。

欢迎光临仓酷云 (http://ckuyun.com/)