String常见笔试题（算法）

63 阅读 0 评论 42 点赞

我是靠谱客的博主寂寞小懒猪，最近开发中收集的这篇文章主要介绍String常见笔试题（算法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1、统计最长不重复子串（利用HashMap是最简单的）

public static String lengthOfLongestSubstring(String s) {
int star = 0;
int head = 0;
int ans = 0;
Map<Character, Integer> hashMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
/* 如果重复出现 则更新下标 */
if (hashMap.containsKey(s.charAt(i)))
star = Math.max(hashMap.get(s.charAt(i)), star);
//
star = hashMap.get(s.charAt(i)); //同上
if (ans < i - star + 1) {
ans = i - star + 1;
head = star;
}
hashMap.put(s.charAt(i), i + 1);
}
return s.substring(head, head + ans);
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcdeabcdefg")); //abcdefg
}

2、统计最长重复子串

public static String MaxLongSubString(String str) {
int first = 0;
int k = 0;
int maxLen = 0;
// 相隔1,2,3,4.。。str.length()-1
for (int i = 1; i < str.length(); i++)
for (int j = 0; j < str.length() - i; j++) {
if (str.charAt(j) == str.charAt(j + i))
k++;
else
k = 0;
if (maxLen < k) {
maxLen = k;
first = j - k + 1;
}
}
return str.substring(first, maxLen + first);
}
public static void main(String[] args) {
System.out.println(MaxLongSubString("abcdeabcdefg"));//abcde
}

3、最长公共子串，问题：有两个字符串str和str2，求出两个字符串中最长公共子串长度？
比如：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5

/*
算法思路：
1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。
*/
public static String longestPublicSubstring(String str1, String str2) {
int n1 = str1.length();
int n2 = str2.length();
int result = 0;
int maxend = 0;
int i = 0;
int j = 0;
int[][] ints = new int[n1][n2];
for (i = 0; i < str1.length(); i++)
for (j = 0; j < str2.length(); j++) {
if (str1.charAt(i) == str2.charAt(j))
if (i == 0 || j == 0) {
ints[i][j] = 1;
} else
ints[i][j] = ints[i - 1][j - 1] + 1;
else
ints[i][j] = 0;
if (result < ints[i][j]) {
result = ints[i][j];/* 表示结果的长度 */
maxend = i + 1;// 结束位置
}
}
return str1.substring(maxend - result, maxend);
}
public static void main(String[] args) {
String str1 = "abcfrfrdasda";
String str2 = "fgfrfrdadd";
System.out.println(longestPublicSubstring(str1, str2)); //frfrda
}

4、最长公共子序列

/**
* 算法解析：https://blog.csdn.net/weixin_40673608/article/details/84262695
* str1和str2逐个字符串进行比较,假如此时的需要填的矩阵的位置是dp[i][j]:
* 公式：
* 如果字符相等：则矩阵dp[i-1][j-1]+1=dp[i][j]的左上角+1
* 如果字符不相等：则dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])=dp[i][j]的上面或者左面， 谁大谁赋值给dp[i][j];
*
*/
public static int getLCS(String str1, String str2) {
int n1 = str1.length();
int n2 = str2.length();
int[][] ints = new int[n1][n2];
/*
* 不从0开始就是为了避免讨论ints[i-1][j-1]越界，所以直接从1开始
*/
for (int i = 0; i < n1; i++)
for (int j = 0; j < n2; j++)
if (str1.charAt(i) == str2.charAt(j))
if (i == 0 || j == 0)
ints[i][j] = 1;
else
ints[i][j] = ints[i - 1][j - 1] + 1;
else if (i == 0 || j == 0)
ints[i][j] = 0;
else
ints[i][j] = Math.max(ints[i - 1][j], ints[i][j - 1]);
System.out.println(Arrays.deepToString(ints));
return ints[n1 - 1][n2 - 1];
}
public static void main(String[] args) {
String str1 = "ABECDA";
String str2 = "BDCA";
System.out.println(getLCS(str1, str2)); //最长公共子序列 BCA/BDA
}

5、最长回文子串

public static String longestPalindrome(String s) {
int n = s.length();
int right = 0, left = 0;
int[][] flag = new int[n][n];// 申请一个二维数组
for (int i = 0; i < n; ++i) {
flag[i][i] = 1;
for (int j = 0; j < i; ++j) {
if (s.charAt(i) == s.charAt(j) && (j == i - 1 || flag[j + 1][i - 1] == 1)) {
if (i - j > right - left) {
right = i;
left = j;
}
flag[j][i] = 1;
}
}
//
System.out.println(Arrays.deepToString(flag));
}
return s.substring(left, right + 1);
}
public static void main(String[] args) {
System.out.println(longestPalindrome("abacdfgdcaba")); //aba
System.out.println(longestPalindrome("cbbd")); //bb
System.out.println(longestPalindrome("babab")); //babab
}