B站左程云算法视频高级班03

题目一：K伪进制

9       3进制 100

        3伪进制 2 3  每个位置上的进制都是1~k，不能为0

先给每个位置从右往左分一个，再从左往右分

题目二：

public static int snake(int[][] matrix){
    for(int row = 0; row < matrix.length; row++){
        for(int col = 0; col < matrix[0].length; col++){
            Info cur = f(matrix, row ,col);
            ans = Math.max(ans,Math.max(cur.no, cur.yes));
        }
    }
    return ans;
}


public static class Info{
    public int no;
    public int yes;
    
    public Info(int n, int yes){
    
    }
}

//从最左侧出发(具体位置不关心)，当前到达(row,col)
//在这个路程中
//no,一次能力也不用，能到达的最大路径和(如果是负数，表示没有该答案)
//yes，使用了一次能力，能达到的最大路径和(如果是负数，表示没有该答案)
public static Info f(int[][] matrix, int row, int col){
    if(col == 0){
        return new Info(matrix[row][col], -matrix[row][col]);
    }
    //没有在最左列
    int preNo = -1;//我之前的旅程中，一次能力也没用，能达到的最大路径和
    int preYes = -1;//我之前的旅程中，用过一次能力，能达到的最大路径和
    //p1
    if(row > 0){
        Info leftUp = f(matrix, row - 1, col -1);
        if(leftUp.no >= 0){
            preNo = leftUp.no;
        }
        if(leftUp.yes >= 0){
            preYes = leftUp.yes;
        }
    }

    //p2
    Info left = f(matrix, row, col - 1);
    if(left.no >= 0){
        preNo = Math.max(preNo, left.no);
    }
    if(left.yes >= 0){
        preYes = Math.max(preYes, left.yes);
    }

    if(row < matrix.length - 1){
        Info leftDown = f(matrix, row + 1, col - 1);
        if(leftDown.no >= 0){
            preNo = Math.max(preNo, leftDown.no);
        }
        if(leftDown.yes >= 0){
            preYes = Math.max(preYes, leftDown.yes);
        }
    }
    int no = -1;
    int yes = -1;

    if(preNo >= 0){
        no = preNo + matrix[row][col];
        yes = preNo + (-matrix[row][col]);
    }
    if(preYes >= 0){
        yes = Math.max(yes, preYes + matrix[row][col]);
    }
    return new Info(no, yes);
}

改成动态规划（加缓存） 记忆化搜索

public static int snake(int[][] matrix){
    int ans = Integer.MIN_VALUE;
    Info[][] dp = new Info[matrix.length][matrix[0].length];
    for(int row = 0; row < matrix.length; row++){
        for(int col = 0; col < matrix[0].length; col++){
            Info cur = f2(matrix, row ,col, dp);
            ans = Math.max(ans,Math.max(cur.no, cur.yes));
        }
    }
    return ans;
}


public static class Info{
    public int no;
    public int yes;
    
    public Info(int n, int yes){
    
    }
}

//从最左侧出发(具体位置不关心)，当前到达(row,col)
//在这个路程中
//no,一次能力也不用，能到达的最大路径和(如果是负数，表示没有该答案)
//yes，使用了一次能力，能达到的最大路径和(如果是负数，表示没有该答案)
public static Info f2(int[][] matrix, int row, int col, Info[][] dp){
    if(dp[row][col] != null){
        return dp[row][col];
    }
    
    if(col == 0){
        dp[row][col] = new Info(matrix[row][col], -matrix[row][col]);
        return dp[row][col];
    }
    //没有在最左列
    int preNo = -1;//我之前的旅程中，一次能力也没用，能达到的最大路径和
    int preYes = -1;//我之前的旅程中，用过一次能力，能达到的最大路径和
    //p1
    if(row > 0){
        Info leftUp = f2(matrix, row - 1, col -1, dp);
        if(leftUp.no >= 0){
            preNo = leftUp.no;
        }
        if(leftUp.yes >= 0){
            preYes = leftUp.yes;
        }
    }

    //p2
    Info left = f(matrix, row, col - 1);
    if(left.no >= 0){
        preNo = Math.max(preNo, left.no);
    }
    if(left.yes >= 0){
        preYes = Math.max(preYes, left.yes);
    }

    if(row < matrix.length - 1){
        Info leftDown = f(matrix, row + 1, col - 1, dp);
        if(leftDown.no >= 0){
            preNo = Math.max(preNo, leftDown.no);
        }
        if(leftDown.yes >= 0){
            preYes = Math.max(preYes, leftDown.yes);
        }
    }
    int no = -1;
    int yes = -1;

    if(preNo >= 0){
        no = preNo + matrix[row][col];
        yes = preNo + (-matrix[row][col]);
    }
    if(preYes >= 0){
        yes = Math.max(yes, preYes + matrix[row][col]);
    }
    dp[row][col] = new Info(no, yes);
    return dp[row][col];
}

题目三：给定一个字符串str，str表示公式，公式里可能有整数、加减乘除符号和左右括号，返回公式的计算结果。

f（str，i）返回俩值：1）值 2）算到第几位

举例子：34 - 64 * 9 + 42* 70 * 30 / 4 - 6

遇到符号就把num进栈，符号进栈，num回零，如果栈顶元素是乘除，弹出，计算

最后栈里一定是加减连接

如果有括号串，要用到递归结构

3*（4+2*（5-7）-34）+4

public static int getValue(String str){
    return value(str.toCharArray(), 0)[0];
}
//请从str[i..]往下算，遇到字符串终止位置或者右括号，就停止
//返回两个值，长度为2的数组
// 0)负责的这一段的结果是多少
// 1)负责的这一段计算到了哪个位置
public static int[] value(char[] str, int i){
    LinkedList que = new LinkedList();
    int num = 0;
    int[] bra = null;
    while(i < str.length && str[i] != ')'){
        if(str[i] >= '0' && str[i] <= '9'){
            num = num * 10 + str[i++] - '0';
        } else if(str[i] != '('){ //遇到的是运算符号
            addNum(que, num);
            que.addLast(String.valueOf(str[i++]));
            num = 0;
        } else{//遇到左括号了
            bra = value(str, i + 1);
            num = bra[0];
            i = bra[1] + 1;
        }
    }
    addNum(que, num);
    return new int[] {getNum(que), i};
}

public static void addNum(LinkedList que, int num){
    if (!que.isEmpty()){
        int cur = 0;
        String top = que.pollLast();
        if(top.equals("+") || top.equals("-")){
            que.addLast(top);
        } else{
            cur = Integer.valueOf(que.pollLast());
            num = top.equals("*") ? (cur * num) : (cur / num);
        }
    }
    que.addLast(String.valueOf(num));
}

题目四：请注意区分子串和子序列的不同，给定两个字符串str1和str2，求两个字符串的最长公共子串

public static String lcst2(String s1, String s2){
    if(s1 == null || s2 == null || s1.equals("") || s2.equals("")){
        return "";
    }
}
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    int row = 0;
    int col = str2.length - 1;//斜线开始位置的列
    int max = 0; //t到达的全局最大值
    int end = 0; //忽略
    while(row < str1.length){
        int i = row;
        int j = col;
        int len = 0;
        while(i < str1.length && j < str2.length) {
            if(str1[i] != str2[j]){
                len = 0;
            } else{
                len++;
            }
            if(len > max){
                end = i;
                max = len;
            }
            i++;
            j++;
        }
        if (col > 0){
            col--;
        } else{
            row++;
        }
    } 
    return s1.substring(end - max + 1, end + 1);

 题目五：请注意区分子串和子序列的不同，给定两个字符串str1和str2，求两个字符串的最长公共子序列