给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为
无重复字符的最长子串是 “abc”，所以其长度为 3。
来源：力扣（LeetCode）
public int com(String s){
//空字符串返回0
if(s==null||s.equals(""))
return 0;
char[] str=s.toCharArray();
//a数组保存字符串中Acsll码中的上一次的位置坐标，设置为-1当 该字符没有出现重复的字符时相减符合要求
int[] a=new int[256];
for(int i=0;i<a.length;i++)
a[i]=-1;
//此为i-1当前字符的无重复子串的字符长度
int pre=1;
//返回值
int max=1;
//此处容易遗漏，第一个字符设置为0
a[str[0]]=0;
//从i=1字符开始进行遍历，比较前一个相同字符之前的 距离和i-1的无重复子串的字符数目+1,然后取最小值
for(int i=1;i<str.length;i++){
max=Math.max(max,Math.min(i-a[str[i]],pre+1));
pre=Math.min(i-a[str[i]],pre+1);
a[str[i]]=i;
}
return max;
}给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。输入：s = “abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”
首先这一题可以使用动态规划来进行解决：
状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
状态转移方程：当 s[i] == s[j] && (j – i < 2 || dp[i + 1][j – 1]) 时，dp[i][j]=true，否则为false
这个状态转移方程是什么意思呢？
当只有一个字符时，比如 a 自然是一个回文串。
当有两个字符时，如果是相等的，比如 aa，也是一个回文串。
当有三个及以上字符时，比如 ababa 这个字符记作串 1，把两边的 a 去掉，也就是 bab 记作串 2，可以看出只要串2是一个回文串，那么左右各多了一个 a 的串 1 必定也是回文串。所以当 s[i]==s[j] 时，自然要看 dp[i+1][j-1] 是不是一个回文串。
public int countSubstrings(String s) {
char[] array = s.toCharArray();
int result = 0;
boolean[][] dp=new boolean[s.length()][s.length()];
for(int i=s.length()-1;i>=0;i--){
for(int j=i;j<s.length();j++){
if(array[i]==array[j]){
if(j-i<=1){
dp[i][j]=true;
result++;
}
else {
dp[i][j]=dp[i+1][j-1];
if(dp[i][j]==true)
result++;
}
}
}
}
return result;
}给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。
1、确定dp数组及下标含义：dp[j][i],以nums2[j]和nums1[i]结尾的最长重复子数组长度为dp[i][j]
2、确定递推公式： dp[j][i] = dp[j – 1][i – 1] + 1;
public int findLength(int[] A, int[] B) {
int n = A.length;
int m = B.length;
int[][] dp = new int[n + 1][m + 1]; // dp[i][j]表示A的前i项与B的前j项的最长重复子数组长度
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
ans = Math.max(ans,dp[i][j]);
}
}
}
return ans;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/143062.html
