人太懒了,好久没发文章了。今天就写点自己的算法实现吧。比较简单恐贻笑大方之家,但又觉得还是记录下来比较好。
前两天qq的群里有人再说他老大不懂java但在招聘Java工程师。所以就选择语言无关又能考察下能力的最大公约数----算法。大概是冒泡排序、快速排序(快排)、二分查找、KMP算法。
做Java大家都懂,可以通过comparable和Comparator的方式来方便的排序,所以大家平常对这些基础的算法都生疏了。也为了锻炼下自身的算法逻辑,就自己试着实现了一遍。可能会和大家找的算法实现很相似,只能说简单算法的实现还是比较难创新的。
通过Junit的方式测试的,引入了apache common的一点工具方法,但这些不重要,大家看代码吧。
package algorithm;
import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.stream.Stream;
import org.junit.Test;
public class SortTest {
private Integer[] generateTestArray() {
ArrayList<Integer> originList = new ArrayList<>();
Random random = new Random(LocalDateTime.now().toEpochSecond(ZoneOffset.ofHours(8)));
Stream.generate(random::nextInt).limit(20).forEach(originList::add);
System.out.println(originList);
Integer[] tempArr = new Integer[20];
originList.toArray(tempArr);
return tempArr;
}
@Test
public void nnnnn() {
Integer[] tempArr = generateTestArray();
for (int i = 0; i < tempArr.length - 1; i++) {
boolean swapFlag = false;
for (int j = 0; j < tempArr.length - 1 - i; j++) {
if (tempArr[j] > tempArr[j + 1]) {
int temp = tempArr[j];
tempArr[j] = tempArr[j + 1];
tempArr[j + 1] = temp;
swapFlag = true;
}
}
if (swapFlag == false) {
break;
}
}
Arrays.stream(tempArr).forEach(System.out::println);
}
public int middleIndex(Integer[] tempArray, int low, int high) {
int temp = tempArray[low];
while (low < high) {
while (low < high && tempArray[high] > temp) {
high--;
}
tempArray[low] = tempArray[high];
while (low < high && tempArray[low] < temp) {
low++;
}
tempArray[high] = tempArray[low];
}
tempArray[high] = temp;
return high;
}
public void recursiveByQuickSort(Integer[] tempArray, int low, int high) {
if (low < high) {
int middleIndex = middleIndex(tempArray, low, high);
recursiveByQuickSort(tempArray, low, middleIndex - 1);
recursiveByQuickSort(tempArray, middleIndex + 1, high);
}
}
@Test
public void quickSort() {
Integer[] tempArray = generateTestArray();
recursiveByQuickSort(tempArray, 0, tempArray.length - 1);
System.out.println(Arrays.asList(tempArray));
tempArray = new Integer[]{-2127313485, -2022230754, -1525774655, -1266487529, -1246088751, -1237557299, -1220678150, -669061349, -587792801, -441728115, -388929620, -228781073, -5476750, 424415588, 631901841, 878929975, 1519073389, 1526646025, 1791609759, 2002233420};
System.out.println(Arrays.asList(tempArray));
System.out.println(binaryQuery(tempArray, -587792801));
}
private int binaryQuery(Integer[] tempArray, int val) {
int low = 0, high = tempArray.length - 1;
while (low < high) {
int middle = (low + high) / 2;
if (tempArray[middle] < val) {
low = middle + 1;
} else if (tempArray[middle] > val) {
high = middle - 1;
} else {
return middle;
}
}
if (low == high && tempArray[low] == val) {
return low;
}
return -1;
}
}
package algorithm;
import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;
import org.junit.Test;
public class KMPTest {
private int[] suffixMatchPrefixMatchSequence(String queryStr) {
char[] charArray = queryStr.toCharArray();
int charLength = charArray.length,
lastIndex = charLength - 1;
if (charLength <= 2) {
return null;
}
final int[] matchSequence = new int[charLength];
outFor : for (int i = 1; i < charLength; i++) {
int tempI = i;
for (int j = 0; j <lastIndex && tempI < charLength; j++, tempI++) {
char ic = charArray[tempI];
char jc = charArray[j];
if (ic != jc) {
matchSequence[tempI] = 0;
break;
}
matchSequence[tempI] = j + 1;// 做偏移的减法操作,所以从1开始
if (tempI == lastIndex) {
break outFor;
}
}
}
System.out.println(StringUtils.join(matchSequence, ','));
return matchSequence;
}
public int matchedStartIndex(String targetStr, String queryStr) {
char[] targetCharArray = targetStr.toCharArray(),
queryCharArray = queryStr.toCharArray();
int targetCharArrayLength = targetCharArray.length,
queryCharArrayLength = queryCharArray.length,
matchStartIndex = 0,
queryLastIndex = queryCharArrayLength - 1;
final int[] matchSequence = this.suffixMatchPrefixMatchSequence(queryStr);
while (matchStartIndex < targetCharArrayLength) {
int tempMatchStartIndex = matchStartIndex;
int i = 0;
for (; i < queryCharArrayLength && tempMatchStartIndex < targetCharArrayLength; i++, tempMatchStartIndex++) {
char qc = queryCharArray[i],
tc = targetCharArray[tempMatchStartIndex];
if (qc == tc) {
continue;
}
break;
}
if (i > queryLastIndex) {// 完全匹配后还会做+1操作,所以条件加上>
return matchStartIndex;
}
matchStartIndex += ArrayUtils.isEmpty(matchSequence) ? 1 : (i - matchSequence[i]) == 0 ? 1 : i - matchSequence[i];
}
return -1;
}
@Test
public void test() {
String targetStr = "56132asdasdasfsf4dasa123",
queryStr = "dasa123";
System.out.println(this.matchedStartIndex(targetStr, queryStr));
}
}
分享到:
相关推荐
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
KMP算法实现,用Java语言实现的KMP字符串匹配算法
JAVA实现KMP算法,使用java语言实现的kmp算法
java实现的kmp算法,参照原论文实现的,希望能有用
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
欢迎讨论
C语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法C语言实现kmp算法的C语言实现源码.zipC语言实现kmp算法的C语言实现源码.zipC语言实现...
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
KMP算法的JAVA实现
下面我们将详细探讨KMP算法的原理、Java实现以及“next”数组的计算方法。 ### KMP算法原理 1. **模式匹配问题**:给定一个文本串s和一个模式串p,我们需要找出模式串在文本串中的所有出现位置。 2. **next数组**...
Java实现的KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由唐纳德·克努斯、莫里斯和弗雷德里克·普拉特在1970年代提出。该算法避免了对每一个模式字符进行多次比较,通过构建一个“部分匹配表”(也...
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
KMP算法的实现, 这程序代码是基于KMP算法来实现的,虽然很简单,但是可能也会对你有帮助的
在Java中实现KMP算法,我们需要理解其核心思想和步骤。 1. **KMP算法的核心思想**: - KMP算法的关键在于构造一个部分匹配表(也称为失配表),它记录了当模式串在某个位置不匹配时,如何利用已知的信息避免回溯。...
《KMP算法与Java实现详解》 在计算机科学中,字符串搜索算法是处理文本和数据的重要工具,其中KMP(Knuth-Morris-Pratt)算法因其高效性和实用性而备受青睐。KMP算法是由Donald Knuth、Vaughan Pratt和James H. ...
在Java中实现KMP算法,我们需要理解以下几个关键概念: 1. **部分匹配表(Partial Match Table)**:这是KMP算法的核心,用于存储字符串的前缀和后缀的最大公共长度。通过预处理输入字符串,我们可以得到一个数组,...
KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。 #! /usr/bin/python # coding=utf-8 """ ...
kmp算法的java代码
模式匹配的KMP算法是计算机科学领域中的一种经典算法,具有广泛的应用前景,本课程设计旨在通过模式匹配的KMP算法的设计和实现,帮助学生深入了解数据结构、算法设计、程序实现等知识点,并提高学生的编程能力和问题...
BF 算法和 KMP 算法在字符串匹配中的应用 ...BF 算法和 KMP 算法都是字符串匹配中常用的算法,但它们的时间复杂度和实现难度不同。在实际应用中,需要根据实际情况选择合适的算法,以提高matching效率。