算法基础提升学习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;
}
}
推荐阅读
- 画解算法(1.|画解算法:1. 两数之和)
- Guava|Guava RateLimiter与限流算法
- Python基础|Python基础 - 练习1
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- Java|Java基础——数组
- 《算法》-图[有向图]
- Java基础-高级特性-枚举实现状态机
- 【#2-戴栋】区块链可以提升哪些商业上的效率改进
- 营养基础学20180331(课间随笔)??