给定一个字符串 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; }
