算法

最长公共子串问题的java版计算

星期三, 五月 17th, 2023 | algorithm-learn, JAVA-and-J2EE, linux | 没有评论

1.最长公共子串问题
【题目】给定两个字符串str1和str2,返回两个字符串的最长公共子串。

【举例】str1="1AB2345CD",str2="12345EF",返回"2345"。
【要求】如果 str1 长度为 M,str2 长度为N,实现时间复杂度为 O(M×N),额外空间复杂度为 O(1)的方法。
【难度】3星

/**
 * 
 * 1.最长公共子串问题 【题目】给定两个字符串str1和str2,返回两个字符串的最长公共子串。
 * 【举例】str1="1AB2345CD",str2="12345EF",返回"2345"。 【要求】如果 str1 长度为 M,str2 长度为
 * N,实现时间复杂度为 O(M×N),额外空间复杂度为 O(1)的方法。 【难度】3星
 * 
 * @author sara
 *
 */
public class MaxSubStr {
 
	public static void main(String[] args) {
		String str1="1AB2345CD",str2="12345EF";
		String str = getMaxSub(str1,str2);
		System.out.println(str);
	}
 
	public static String getMaxSub(String s1, String s2) {
		String sStr = s1, mStr = s2;
		if (s1.length() > s2.length()) {
			sStr = s2;
			mStr = s1;
		}
		String str = "";
		for (int i = 0; i < sStr.length(); i++) {
			for (int j = 1; j < sStr.length() - i; j++) {
				if (mStr.contains(sStr.substring(i, i + j)) && j > str.length()) {
					str = sStr.substring(i, i + j);
				}
			}
		}
		return str;
	}
 
	public static void getDp(char[] str1, char[] str2) {
 
	}
 
}

Tags:

查找质数的java和perl的代码

星期五, 十二月 5th, 2008 | algorithm-learn, JAVA-and-J2EE | 没有评论

今天看本perl的一个教程的时候看到,查找质数的一个算法,不由自主的就想用java重新了此代码,
感觉效率太低,就优化下,其他更高级的算法方式没有研究,贴出来;记录下

perl代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/perl -w
$maxprimes=100;
$value=1;
$count=0;
while($count <$maxprimes){
	$value++;
	$composite=0;
OUTER: for($i=2;$i<$value;$i++){
		for($j=$i;$j<$value;$j++){
		  if(($j*$i)==$value){
			$composite=1;
			last OUTER;
  			}
		}
	}
	if(!$composite){
		$count++;
		print "$value is prime count is $count \n";}
}

java代码的两种:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package com.liyz.num.test;
public class PrimeNum {
	public static void main(String[] args) {
		long start=System.currentTimeMillis();
		primeMehtodTwo(100);
		long end=System.currentTimeMillis();
		System.out.println("use time is " +(end-start)+" ms");
	}
	//效率太差,取的质数越多,比较的次数也越多,效率也越低
	public static void primeMehtodOne( int number){
		int num=number;
		int value=1;
		int count=0;
		boolean composite;
		while (count<num){
			value++;
			composite=false;
			for(int i=2;i<value;i++){
				for(int j=i;j<value;j++){
					if((j*i)==value){
						composite=true;
						break;
					}
				}
			}
			if(!composite){
				count++;
				System.out.println(value+" is prime!");
			}
		}
	}
	//感觉好多了,更好的算法没有去研究过
	public static void primeMehtodTwo(int number){
		int count=0;
		int fg=1;
		int num=number;
 
		for( int i=2;count<num;i++){
			double k=Math.sqrt(i+1);
			for(int j=2;j<=k;j++){
				if((i%j)==0){
					fg=0;
					break;
				}
			}
			if(fg==1){
				System.out.println(i+" is prime!");
				count++;
			}
			fg=1;
		}
	}
	}

Tags: , ,

Search

相关文章

文章分类

Links

Meta