深度学习算法算法高级学习2

伪进制转化、尝试（蛇最大长度）、表达式计算（系统压栈）、空间压缩：最长公共子串一、伪26进制转换一个 char 类型的数组 chs ，其中所有的字符都不同。
例如， chs=['A', 'B', 'C', ... 'Z'] ，
则字符串与整数的对应关系如下:
A, B... Z, AA,AB...AZ,BA,BB...ZZ,AAA... ZZZ, AAAA...
1, 2...26,27, 28... 52,53,54...702,703...18278, 18279...
例如， chs=['A', 'B', 'C'] ，则字符串与整数的对应关系如下: A,B,C,AA,AB...CC,AAA...CCC,AAAA... 1, 2,3,4,5...12,13...39,40...
给定一个数组 chs ，实现根据对应关系完成字符串与整数相互转换的两个函数
/** * @Author: 郜宇博 * @Date: 2021/12/9 15:06 * 一个 char 类型的数组 chs ，其中所有的字符都不同。* 例如， chs=['A', 'B', 'C', ... 'Z'] ， * 则字符串与整数的对应关系如下: * A, B... Z, AA,AB...AZ,BA,BB...ZZ,AAA... ZZZ, AAAA... * 1, 2...26,27, 28... 52,53,54...702,703...18278, 18279... * 实现根据对应关系完成字符串与整数相互转换的两个函数。*/public class CharToNum {//number->charpublic static String numberToChar(char[] charsMap,int number){//1.获取转后的字符串长度int strLength = 0;int curPowNumber = 1;int base = charsMap.length;while (number >= curPowNumber){number -= curPowNumber;curPowNumber *= base;strLength++;}//2.获取各位上的字符char[] resultChars = new char[strLength];int index = 0;int nCur = 0;do {curPowNumber /= base;nCur = number / curPowNumber;number %= curPowNumber;//计算出的当前位置的个数加上之前的1个resultChars[index++] = getKthString(charsMap,nCur+1);}while (index != strLength);return String.valueOf(resultChars);}public static char getKthString(char[] charsMap, int i) {if (i == 0 || i > charsMap.length){return 0;}return charsMap[i-1];}//char->numberpublic static int getNum(char[] chs, String str) {if (chs == null || chs.length == 0) {return 0;}char[] strc = str.toCharArray();int base = chs.length;int cur = 1;int res = 0;for (int i = strc.length - 1; i != -1; i--) {res += getNthFromChar(chs, strc[i]) * cur;cur *= base;}return res;}public static int getNthFromChar(char[] chs, char ch) {return (ch-'A')+1;}public static void main(String[] args) {char[] chs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K','L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W','X', 'Y', 'Z' };System.out.println(numberToChar(chs, 18278));System.out.println(getNum(chs, "AB"));}}二、Snake最大长度/** * @Author: 郜宇博 * @Date: 2021/12/9 16:13 * 给定一个二维数组matrix ，每个单元都是一个整数，有正有负。* 最开始的时候小Q操纵一条长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图， * 蛇每次只能够到达当前位置的右上相邻，右侧相邻和右下相邻的单元格。* 蛇蛇到达一个单元格后，自身的长度会瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。* 小Q是个天才，他拥有一个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数 * （注：最多只能改变一个节点）。* 问在小Q游戏过程中，他的蛇蛇最长长度可以到多少？ */public class SnakeMaxLength {public static void main(String[] args) {int[][] matrix = { { 1, -4, 10 }, { 3, -2, -1 }, { 2, -1, 0 }, { 0, 5, -2 } };System.out.println(getMacLengthWithCatch(matrix));}/*** 递归返回结果，两个。* 1.目前位置使用能力的获得的长度* 2.不使用能力获取的长度*/public static class Info{public int withAbilityLength;public int withoutAbilityLength;public Info(int withAbilityLength, int withoutAbilityLength) {this.withAbilityLength = withAbilityLength;this.withoutAbilityLength = withoutAbilityLength;}}public static int getMaxLength(int[][] matrix){int result = Integer.MIN_VALUE;for (int i = 0 ; i < matrix.length;i++){for (int j = 0; j < matrix[0].length;j++){Info info = getLength(matrix, i, j);result =Math.max(result,Math.max(info.withAbilityLength, info.withoutAbilityLength)) ;}}return result;}public static Info getLength(int[][] matrix,int row,int col){//base case->刚进去矩阵if (col == 0){return new Info(-(matrix[row][col]),matrix[row][col]);}//之前是否使用过能力到达的最大长度int preUseAbilityMaxLength = -1;int preNoAbilityMaxLength = -1;//此时有之前最多有三种情况可以到达当前位置左，左上，左下//不在第一行//1.左上if (row >0){Info leftUpInfo = getLength(matrix, row - 1, col - 1);preNoAbilityMaxLength = leftUpInfo.withoutAbilityLength>=0?leftUpInfo.withoutAbilityLength:-1;preUseAbilityMaxLength = leftUpInfo.withAbilityLength>=0?leftUpInfo.withAbilityLength:-1;}//2左Info leftInfo = getLength(matrix,row,col-1);preNoAbilityMaxLength = Math.max(leftInfo.withoutAbilityLength,preNoAbilityMaxLength);preUseAbilityMaxLength = Math.max(leftInfo.withAbilityLength,preUseAbilityMaxLength);//3.左下if (row < matrix.length-1){Info leftDownInfo = getLength(matrix,row+1,col-1);preNoAbilityMaxLength = Math.max(leftDownInfo.withoutAbilityLength,preNoAbilityMaxLength);preUseAbilityMaxLength = Math.max(leftDownInfo.withAbilityLength,preUseAbilityMaxLength);}//封装自己的Infoint curUseMaxLength = -1;int curNoMaxLength = -1;//之前没用，现在可以用可以不用if (preNoAbilityMaxLength > 0){curNoMaxLength = preNoAbilityMaxLength + matrix[row][col];curUseMaxLength = preNoAbilityMaxLength - matrix[row][col];}//现在只能不用if (preUseAbilityMaxLength > 0){//更新用过的长度curUseMaxLength = Math.max(curUseMaxLength,preUseAbilityMaxLength + matrix[row][col]);}return new Info(curUseMaxLength,curNoMaxLength);}/*** 加入缓存机制*/public static int getMacLengthWithCatch(int[][]matrix){int result = Integer.MIN_VALUE;Info[][] dp = new Info[matrix.length][matrix[0].length];for (int i = 0 ; i < matrix.length;i++){for (int j = 0; j < matrix[0].length;j++){Info info = getLengthWithCatch(matrix, i, j,dp);result =Math.max(result,Math.max(info.withAbilityLength, info.withoutAbilityLength)) ;}}return result;}public static Info getLengthWithCatch(int[][] matrix,int row,int col,Info[][]dp){if (dp[row][col] != null){return dp[row][col];}//base case->刚进去矩阵if (col == 0){dp[row][col] = new Info(-(matrix[row][col]),matrix[row][col]);return dp[row][col];}//之前是否使用过能力到达的最大长度int preUseAbilityMaxLength = -1;int preNoAbilityMaxLength = -1;//此时有之前最多有三种情况可以到达当前位置左，左上，左下//不在第一行//1.左上if (row >0){Info leftUpInfo = getLengthWithCatch(matrix, row - 1, col - 1,dp);preNoAbilityMaxLength = leftUpInfo.withoutAbilityLength>=0?leftUpInfo.withoutAbilityLength:-1;preUseAbilityMaxLength = leftUpInfo.withAbilityLength>=0?leftUpInfo.withAbilityLength:-1;}//2左Info leftInfo = getLengthWithCatch(matrix,row,col-1,dp);preNoAbilityMaxLength = Math.max(leftInfo.withoutAbilityLength,preNoAbilityMaxLength);preUseAbilityMaxLength = Math.max(leftInfo.withAbilityLength,preUseAbilityMaxLength);//3.左下if (row < matrix.length-1){Info leftDownInfo = getLengthWithCatch(matrix,row+1,col-1,dp);preNoAbilityMaxLength = Math.max(leftDownInfo.withoutAbilityLength,preNoAbilityMaxLength);preUseAbilityMaxLength = Math.max(leftDownInfo.withAbilityLength,preUseAbilityMaxLength);}//封装自己的Infoint curUseMaxLength = -1;int curNoMaxLength = -1;//之前没用，现在可以用可以不用if (preNoAbilityMaxLength > 0){curNoMaxLength = preNoAbilityMaxLength + matrix[row][col];curUseMaxLength = preNoAbilityMaxLength - matrix[row][col];}//现在只能不用if (preUseAbilityMaxLength > 0){//更新用过的长度curUseMaxLength = Math.max(curUseMaxLength,preUseAbilityMaxLength + matrix[row][col]);}dp[row][col] =new Info(curUseMaxLength,curNoMaxLength);return dp[row][col];}}三、表达式计算/** * @Author: 郜宇博 * @Date: 2021/12/9 19:45 * 给定一个字符串str ， str表示一个公式，公式里可能有整数、加减乘除符号和左右括号，返回公式的计算结果。* str="48*((70-65)-43)+8*1" ，返回-1816 。*/public class Computer {public static void main(String[] args) {String expression = "48*((70-615)-43)+8*1";System.out.println(getComputeResult(expression));}/*** 递归，利用系统压栈特性存储括号内结果* @param expression* @return*/public static int getComputeResult(String expression){char[] chars = expression.toCharArray();int[] partResult = getPartResult(chars, 0);return partResult[0];}//返回两个结果，【0】为计算结果，【1】为到达的位置，上一层递归从下一个位置开始public static int[] getPartResult(char[] chars,int cur){LinkedList<String> queue = new LinkedList<String>();int num = 0;while (cur < chars.length && chars[cur] != ')'){//是数字if (chars[cur] >= '0' && chars[cur] <= '9'){num = num * 10 + (chars[cur++] - '0');}else if (chars[cur] != '('){//运算符compute(queue,num);//压入运算符queue.addLast(String.valueOf(chars[cur++]));num = 0;}else {//左括号int[] partResult = getPartResult(chars, cur + 1);num = partResult[0];cur = partResult[1]+1;}}compute(queue,num);return new int[]{getQueueResult(queue),cur};}private static int getQueueResult(LinkedList<String> queue){int result = 0;boolean add = true;int num = 0;while (! queue.isEmpty()){String cur = queue.pollFirst();if ("+".equals(cur)){add = true;}else if ("-".equals(cur)){add = false;}else {num = Integer.parseInt(cur);result += add? num:(-num);}}return result;}private static void compute(LinkedList<String> queue, int num) {if (! queue.isEmpty()){String top = queue.pollLast();//如果是+ ， -就压入if ("+".equals(top) || "-".equals(top)){queue.addLast(top);}else {//乘除，就int cur = Integer.parseInt(queue.pollLast());num = "*".equals(top)? (num*cur):(cur/num);}}queue.addLast(String.valueOf(num));}}四、最长公共子串（空间压缩）请注意区分子串和子序列的不同，给定两个字符串str1和str2 ，求两个字符串的最长公共子串。
动态规划空间压缩
【深度学习算法算法高级学习2】/** * @Author: 郜宇博 * @Date: 2021/12/9 21:09 * 请注意区分子串和子序列的不同，给定两个字符串str1和str2 ，求两个字符串的最长公共子串。* 动态规划空间压缩的技巧讲解 */public class LongestPublicChildArray {public static void main(String[] args) {String s1 = "ABC1234567MEFG";String s2 = "HILL1234567MNOP";System.out.println(getLength(s1, s2));System.out.println(getLengthBySpaceCompress(s1, s2));}public static int getLength(String s1, String s2) {//dp[i][j],表示s1以i结尾和s2以j结尾，构成的最长子串int[][] dp = new int[s1.length()][s2.length()];for (int i = 0; i < s2.length(); i++) {dp[0][i] = s1.charAt(0) == s2.charAt(i) ? 1 : 0;}for (int i = 1; i < s1.length(); i++) {for (int j = s2.length() - 1; j >= 0; j--) {boolean b = s2.charAt(j) == s1.charAt(i);if (j == 0) {dp[i][0] = b ? 1 : 0;} else {dp[i][j] = dp[i - 1][j - 1] + (b ? 1 : 0);}}}return dp[s1.length() - 1][s2.length() - 1];}/*** 每行元素只和左上角有依赖* 从右上角开始，斜对角线，一直向左下走*/public static String getLengthBySpaceCompress(String s1, String s2) {int row = 0;int col = s2.length() - 1;int max = 0;int end = 0;int length = 0;char[] chs1 = s1.toCharArray();char[] chs2 = s2.toCharArray();while (row < chs1.length) {int curRow = row;int curCol = col;length = 0;while (curRow < s1.length() && curCol < s2.length()){if (chs1[curRow] != chs2[curCol]){length = 0;}else {length++;}//可更新，记录end位置if (length > max){end = curRow;max = length;}curRow++;curCol++;}//起始点没到最左边，向左移动if (col > 0){col--;}else {//起始点在最左边，向下移动row++;}}return s1.substring(end-max+1,end+1);}}

深度学习算法 算法高级学习2

深度学习算法算法高级学习2