【算法刷题日志】1044 最长重复子串和75 颜色分类，
颜色分类
这题就是双指针法，指到1的时候就和p1进行交换，然后p1指针往前移动，指到0的时候就和p0指针进行交换，p0和p1同时往前移动，由于可能出现连续的0后面连续的1，所以为了避免1被交换到末尾，当p1>p0的时候 还需要再和p1在交换一次
class Solution {public void sortColors(int[] nums) {int n = nums.length;int p0=0,p1=0;for(int i=0;i<n;i++){if(nums[i]==1){int temp = nums[i];nums[i]=nums[p1];nums[p1]=temp;++p1;}else if(nums[i]==0){int temp=nums[i];nums[i]=nums[p0];nums[p0]=temp;if(p1>p0){temp = nums[i];nums[i]=nums[p1];nums[p1]=temp;}++p1;++p0;}}}
}
1044. 最长重复子串
P是一个很大的数 用与计算幂次值，是一个固定的数，通常选择一个质数作为基数。这是因为选择质数作为基数可以减少哈希碰撞的可能性，从而提高哈希函数的效率和准确性。
所以p这个数组的意义就是 相当于一个哈希因子一样，为了减少哈希冲突的可能性，h数组代表的就是比如h【i】 就是长度为i的字符串的哈希值，用字符串哈希来匹配，关键在于如何 check 函数，即实现「检查某个长度 len 作为最大长度，是否存在合法方案」。 check函数就是判断 用set去重，如果set当中有出现过这个字符串，说明这是一个重复子串。
所以这道题就是先计算出p数组 一个幂次值的数组，以及就是字符串的哈希值，然后再用二分查找的方式去找对应子串是否有合法重复子串，然后再不断对比去找出最长的重复子串。
class Solution {long[] h, p;public String longestDupSubstring(String s) {int P = 1313131, n = s.length();h = new long[n + 10]; p = new long[n + 10];p[0] = 1;for (int i = 0; i < n; i++) {p[i + 1] = p[i] * P;h[i + 1] = h[i] * P + s.charAt(i);}String ans = "";int l = 0, r = n;while (l < r) {int mid = l + r + 1 >> 1;String t = check(s, mid);if (t.length() != 0) l = mid;else r = mid - 1;ans = t.length() > ans.length() ? t : ans;}return ans;}String check(String s, int len) {int n = s.length();Set<Long> set = new HashSet<>();for (int i = 1; i + len - 1 <= n; i++) {int j = i + len - 1;long cur = h[j] - h[i - 1] * p[j - i + 1];if (set.contains(cur)) return s.substring(i - 1, j);set.add(cur);}return "";}
}