算法基础提升学习1 算法基础提升学习1

一、并查集题、岛屿问题
【题目】一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛?
【举例】
001010
111010
100100
000000 这个矩阵中有三个岛
进阶使用并发方式计算
答：采用并查集，将大的区域分块，每个cpu计算一块，然后考虑边界问题进行合并。
合并：看边界的被感染的点是由那个点导致的，记录这个点。合并开始的时候将这些导致的点看做一个单独的并查集元素。
? 然后进行判断，如果不是一个集合，就合并两个点为一个集合，并且将岛的数量-1，因为重复计算了一次。
? 最后边界的被感染的点都计算完毕后，剩余的个数就是合并的岛个数。

/** * @Author: 郜宇博 */ public class IsLandProblem { public static void main(String[] args) { int[][] m1 = {{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 }, { 0, 1, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, { 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, }; int[][] m2 = {{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 }, { 0, 1, 1, 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, { 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, }; System.out.println(isLandCount(m2)); } public static int isLandCount(int[][]m){ if (m.length==0||m==null){ return 0; } return process(m); } public static int process(int[][]m){ int row = m.length; int column = m[0].length; int res = 0; //遍历集合 for (int i = 0; i < row; i++) { for (int j = 0; j < column; j++) { if (m[i][j] == 1){ res++; infect(m,i,j,row,column); }} } return res; }/** * 递归 * 感染 * 将1的上下左右为1的，和上下左右的上下左右为1的。。。更改为2 * 也就是连成一片的感染 */ private static void infect(int[][] m, int i, int j, int row, int column) { //不感染,越界的和不等于1的 if (i <0||i >= row||j<0||j>=column ||m[i][j]!=1){ return; } m[i][j] = 2; //上 infect(m,i,j-1,row,column); //下 infect(m,i,j+1,row,column); //上 infect(m,i-1,j,row,column); //上 infect(m,i+1,j,row,column); }}

并查集

文章图片

public class Code04_UnionFind { public static class Element { public V value; public Element(V value) { this.value = https://www.it610.com/article/value; } } public static class UnionFindSet { public HashMap> elementMap; public HashMap, Element> fatherMap; public HashMap, Integer> rankMap; public UnionFindSet(List list) { elementMap = new HashMap<>(); fatherMap = new HashMap<>(); rankMap = new HashMap<>(); for (V value : list) { Element element = new Element(value); elementMap.put(value, element); fatherMap.put(element, element); rankMap.put(element, 1); } }private Element findHead(Element element) { Stack> path = new Stack<>(); while (element != fatherMap.get(element)) { path.push(element); element = fatherMap.get(element); } while (!path.isEmpty()) { fatherMap.put(path.pop(), element); } return element; }public boolean isSameSet(V a, V b) { if (elementMap.containsKey(a) && elementMap.containsKey(b)) { return findHead(elementMap.get(a)) == findHead(elementMap.get(b)); } return false; }public void union(V a, V b) { if (elementMap.containsKey(a) && elementMap.containsKey(b)) { Element aF = findHead(elementMap.get(a)); Element bF = findHead(elementMap.get(b)); if (aF != bF) { Element big = rankMap.get(aF) >= rankMap.get(bF) ? aF : bF; Element small = big == aF ? bF : aF; fatherMap.put(small, big); rankMap.put(big, rankMap.get(aF) + rankMap.get(bF)); rankMap.remove(small); } } } }}

二、KMP

/** * @Author: 郜宇博 */ public class KMP { public static void main(String[] args) { String str = "abcabcababaccc"; String match = "ababa"; System.out.println(getIndexOf(str,match)); } /** 步骤：开始str1,str2索引点为0，依次比较如果字母相等，那么索引点都++ 如果字母不相等，那么将str2的索引更换为next[s2],此时s1不变，继续依次比较。（相当于将str2向后推了）如果next[s2] = -1了，也就是str2不能再向后推了，就将s1向后移动一个，继续比较。一直到s1,s2有一个越界位置如果s2最后的结果为str2的长度，说明都比较完事了，找到了子串，那么s1-s2的就是开始索引位如果不是str2长度，说明找到最后也没找到，返回-1 */ public static int getIndexOf(String str1,String str2){ if (str1 == null || str2 == null || str1.length() == 0 || str2.length()== 0){ return -1; } char[] char1 = str1.toCharArray(); char[] char2 = str2.toCharArray(); //str的索引位置 int s1 = 0; int s2 = 0; //next数组 int[] next = getNextArray(str2); //没有越界 while (s1 < char1.length && s2 < char2.length){ //相等 if (char1[s1] == char2[s2]){ //都向后一位 s1++; s2++; } //不相等 else { //str2推到头了 if (next[s2] == -1){ s1++; } //没推到头 else { //更新str2比较位置 s2 = next[s2]; } } } //返回结果 return s2 == char2.length? s1-s2:-1; }/** * next数组获取 * next[0] = -1，next[1] = 0; * 原理：想要获取i索引位的next，next[i] *那么就需要将 *i-1上的字母 *和 *i-1位置的最长公共前后缀最后一个字母位置的后一个位置 *比较 *也就是char[i-1] 和 char[ next[i-1] ] 比较 *1.如果相等，那么char[i] = next[i-1]+1,因为多了一个i-1这个位置的字母 *2.不相等，继续 *和 *比较位置的字母(char[next[i-1]])的最长公共前后缀最后一个字母位置的后一个位置（next[char[next[i-1]]]）字母（ char[ next[char[next[i-1]]]]）比较 *也就是char[i-1] 和char[ next[char[next[i-1]]]] *3.一直比下去，至到next[x] = -1,那么next[i] = 0; */ private static int[] getNextArray(String str2) { if (str2.length() == 1){ return new int[]{-1}; } int[] next =new int[str2.length()]; //规定 next[0] = -1; next[1] = 0; //索引位,从2开始计算next数组 int i = 2; char[] char2 = str2.toCharArray(); //i-1位置字母要比较的位置索引 /* cn两个含义：1.要比较的位置 2、i-1的最长公共前后缀的个数 */ int cn = next[i-1]; while (i < next.length){ //相等 if (char2[i-1] == char2[cn]){ //赋值 next[i++] = ++cn; } //不相等 else { //比较到了第一个，那么i没有最长公共前后缀 if (cn == 0){ next[i++] = 0; } else { //更新cn cn = next[cn]; } } } return next; } }

三、Manacher算法

/** * @Author: 郜宇博 */ public class Manacher { public static void main(String[] args) { String str1 = "abc1234321ab"; System.out.println(maxLcpsLength(str1)); }/** * 最长回文子串 * 变量：c:导致R右扩的中心点，R：回文右边界 i:当前点， i':i关于c的对称点 *p[]:可以忽略判断的点个数 * 分为两种大情况 * 1.i在R外，那么就正常向两边扩（不确定回文数） * 2.i在R内，有分为三种情况 *2.1。当i'的回文区域在[L,R]内，可以忽略的点个数为i'的回文半径（已经确定该点回文数） *2.2。当i'的回文区域在[L,R]外，也就是超过了L，可以忽略的点个数为R-i（已经确定该点回文数） *2.3.当i'的回文区域在[L,R]上，也就是压线，可以忽略的点个数为R-i（不确定回文数，需要判断下一个位置） * 当走完数组后，数组内最大值就是最大的回文半径 * 因为加入了特殊字符如：#1#2#2#1# * 所以回文长度为半径-1 * */ public static int maxLcpsLength(String str){ if (str == null || str.length() == 0) { return 0; } //添加特殊符号后的数组 char[] charArr = manacherString(str); //半径长度(包括自己) int[] pArr = new int[charArr.length]; int max = Integer.MIN_VALUE; //导致右边界的中心点 int center = -1; //右边界 int right = -1; for (int i = 0; i < charArr.length; i++) { //半径长度, 也就是获取可以忽略的点数+1 pArr[i] = right > i ? Math.min(pArr[2*center-i],right-i):1; //虽然有的情况已经确定了回文数，但是为了减少代码量，因此统一一个扩张接口。 while (i + pArr[i] = 0){ //判断两边是否相等 if (charArr[i + pArr[i] ] == charArr[i-pArr[i] ]){ pArr[i]++; } else { break; } } //扩张后，查看是否超过了R，超过则更新，并保存c if (i + pArr[i] > right){ right = i + pArr[i]; center = i; } //更新max值 max = Math.max(max,pArr[i]); } System.out.println(Arrays.toString(pArr)); return max-1; }private static char[] manacherString(String str) { char[] charArr = str.toCharArray(); char[] res = new char[str.length() * 2 + 1]; int index = 0; for (int i = 0; i != res.length; i++) { res[i] = (i & 1) == 0 ? '#' : charArr[index++]; } return res; } }

四、栈的单调性题 【算法基础提升学习1】定义：数组中累积和与最小值的乘积，假设叫做指标A。给定一个数组，请返回子数组中，指标A最大的值。

/** * @Author: 郜宇博 */ public class AllTimesMinToMax { public static void main(String[] args) { int[] arr = new int[]{5,7,6,3,2,8}; System.out.println(max(arr)); } /** * 计算指标A，要求出累加和与最小值乘积的最大值 * 假定数组内每个数都是当前子数组的最小值，因为这样才可以锁定一个变量 * 要满足这个条件（当前子数组的最小值）就需要子数组不能包括比这个数小的数， * 因此左边界是左边比这个数小的值，右边界是右边比这个数小的值。这个边界内的累加和肯定是满足这个条件，带着当前数的最大和。因此乘积A也是最大。 * 计算出所有数的指标A，在得出最大的A，就是最后的A * 此时就需要栈的单调性 * 步骤： *准备栈结构（存储下标），栈顶元素永远大于栈低元素，保证计算区域时都是大于该值的值的区域， *也就是当出现小于当前数的时候，就开始处理当前数了，此时栈顶元素弹出，因为第i个数是小于当前数的，所以i-1位置的数一定大于当前数，所以区域的最右边界就是i-1 *左边界就是弹出栈顶元素后，栈顶元素，也就是第最后一个小于当前数的元素，记为peak,所以当前数按照之前的方式计算的P=sum[i-1]-sum[peak] *弹出后 *当栈内没有元素时，P 直接等于sum[i-1]，因为没有小于当前数的了 * *此时后续加入的元素如果一直大于前一个数的话，就需要第二个步骤了，因为一直没有小于的数让栈内元素弹出。 *依次弹出栈顶元素，此时右边没有比当前元素小的了，也就是没有右边界了，左边界就是弹出后的栈顶peak *所以P = sum[size -1 ]-sum[peak] * */ public static int max(int[] arr) { //用来存储索引 Stack stack = new Stack<>(); //当前位置 int i; //累加和 int[] sum = new int[arr.length]; sum[0] = arr[0]; //求出累加和 for (i = 1; i < arr.length; i++) { sum[i] = sum[i-1]+arr[i]; } //最大值 int max = Integer.MIN_VALUE; //指标 int P = max; //求每个元素的P for (i = 0; i < arr.length; i++) { //保持加入的永远大于栈顶 while (!stack.isEmpty() && arr[i] <= arr[stack.peek()] ){ //处理弹出元素，也就是计算P int pop = stack.pop(); //弹完判空,计算P P =(stack.isEmpty()? sum[i -1]:sum[i-1]-sum[stack.peek()]) * arr[pop]; //更新max max = Math.max(max,P); } //向栈中加入元素 stack.push(i); } //此时剩下的都是递增的 while (!stack.isEmpty()){ int pop = stack.pop(); //弹完判空,计算P P = (stack.isEmpty()? sum[arr.length -1]:sum[arr.length-1]-sum[stack.peek()]) * arr[pop]; //更新max max = Math.max(max,P); } return max; } }