中级提升班8

题目二 express的组合

给定一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的字符串express，再给定一个布尔值desired。返回express能有多少种组合方式，可以达到desired的结果。
【举例】
express="1^0|0l1"，desired=false
只有1^((0|0)|1)和1^(0|(0/1))的组合可以得到false，返回2。

express="1"，desired=false
无组合则可以得到false，返回0

解：

写一个函数，这个函数负责计算在L-R上满足desired的可能性有多少种,范围尝试

public static int num1(String express, boolean desired) {
    if (express == null || express.equals("")) {
        return 0;
    }
    char[] exp = express.toCharArray();
    if (!isValid(exp)) {
        return 0;
    }
    return p(exp, desired, 0, exp.length - 1);
}

// 偶数位置的字符不是0就是1，奇数位必须是逻辑运算符
private static boolean isValid(char[] exp) {
    if ((exp.length & 1) == 0) {
        return false;
    }
    for (int i = 0; i < exp.length; i = i + 2) {
        if (exp[i] != '1' && exp[i] != '0') {
            return false;
        }
    }
    for (int i = 1; i < exp.length; i = i + 2) {
        if (exp[i] != '&' && exp[i] != '|' && exp[i] != '^') {
            return false;
        }
    }
    return true;
}

// exp[L,R] 返回期待为desired的组合方法数
// L和R不要是符号
public static int p(char[] exp, boolean desired, int L, int R) {
    // basecase
    if (L == R) {
        if (exp[L] == '1') {
            return desired ? 1 : 0;
        } else {
            return desired ? 0 : 1;
        }
    }
    int res = 0;
    if (desired) {
        for (int i = L + 1; i < R; i += 2) {
            switch (exp[i]) {
                case '&':
                    res += p(exp, true, L, i - 1) * p(exp, true, i + 1, R);
                    break;
                case '|':
                    res += p(exp, true, L, i - 1) * p(exp, false, i + 1, R);
                    res += p(exp, false, L, i - 1) * p(exp, true, i + 1, R);
                    res += p(exp, true, L, i - 1) * p(exp, true, i + 1, R);
                    break;
                case '^':
                    res += p(exp, true, L, i - 1) * p(exp, false, i + 1, R);
                    res += p(exp, false, L, i - 1) * p(exp, true, i + 1, R);
                    break;
            }
        }
    }else {
        for (int i = L + 1; i < R; i += 2) {
            switch (exp[i]) {
                case '&':
                    res += p(exp, true, L, i - 1) * p(exp, false, i + 1, R);
                    res += p(exp, false, L, i - 1) * p(exp, true, i + 1, R);
                    res += p(exp, false, L, i - 1) * p(exp, false, i + 1, R);
                    break;
                case '|':
                    res += p(exp, false, L, i - 1) * p(exp, false, i + 1, R);
                    break;
                case '^':
                    res += p(exp, true, L, i - 1) * p(exp, true, i + 1, R);
                    res += p(exp, false, L, i - 1) * p(exp, false, i + 1, R);
                    break;
            }
        }
    }
    return res;
}

改为动态规划

看可变参数，3个可变参数， L，R，desired

2张2维表，true表和false表

public static int dpLive(String express, boolean desired) {
    char[] str = express.toCharArray();
    int N = str.length;
    int[][] tDP = new int[N][N];
    int[][] fDP = new int[N][N];
    for (int i = 0; i < N; i += 2) {
        tDP[i][i] = str[i] == '1' ? 1 : 0;
        fDP[i][i] = str[i] == '0' ? 1 : 0;
    }
    // L < R L和R不可能为奇数
    // 从左到右，从下向上
    for (int row = N - 3; row >= 0; row -= 2) {
        for (int col = row + 2; col < N; col += 2) {
            // 符号位
            for (int i = row + 1; i < col; i += 2) {
                switch (str[i]) {
                    case '&':
                        tDP[row][col] += tDP[row][i - 1] * tDP[i - 1][col];
                        break;
                    case '|':
                        tDP[row][col] = tDP[row][i - 1] * fDP[i - 1][col];
                        tDP[row][col] = fDP[row][i - 1] * tDP[i - 1][col];
                        tDP[row][col] = tDP[row][i - 1] * tDP[i - 1][col];
                        break;
                    case '^':
                        tDP[row][col] = tDP[row][i - 1] * fDP[i - 1][col];
                        tDP[row][col] = fDP[row][i - 1] * tDP[i - 1][col];
                        break;
                }

                switch (str[i]) {
                    case '&':
                        fDP[row][col] = tDP[row][i - 1] * fDP[i - 1][col];
                        fDP[row][col] = fDP[row][i - 1] * tDP[i - 1][col];
                        fDP[row][col] = fDP[row][i - 1] * fDP[i - 1][col];
                        break;
                    case '|':
                        fDP[row][col] = fDP[row][i - 1] * fDP[i - 1][col];
                        break;
                    case '^':
                        fDP[row][col] = tDP[row][i - 1] * tDP[i - 1][col];
                        tDP[row][col] = fDP[row][i - 1] * fDP[i - 1][col];
                        break;
                }
            }
        }
    }
    return desired ? tDP[0][N - 1] : fDP[0][N - 1];
}

题目三

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26个小写英文字母组成，即A={a, b…z}。该字母表产生的长序字符串是指定字符串中字母从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。例如，a，b，ab，bc，xyz等字符串是升序字符串。对字母表A产生的所有长度不超过6的升序字符串按照字典排列编码如下: a(1)，b(2)，c(3)……，z(26)，ab(27)，
ac(28)……对于任意长度不超过16的升序字符串，迅速计算出它在上述字典中的编码。
输入描述:
第1行是一个正整数N，表示接下来共有N行，在接下来的N行中，每行给出一个字符串。输出描述:输出N行，每行对应于一个字符串编码。
示例1:

输入
3
a
b
ab
输出
1

题目四 最长无重复子串

在一个字符串中找到没有重复字符子串中最长的长度。例如:
abcabcbb没有重复字符的最长子串是abc，长度为3bbbbb，答案是b，长度为1
pwwkew，答案是wke，长度是3
要求:答案必须是子串，“pwke”是一个子字符序列但不是一个子字符串。

解：

以每个字符结尾的情况下，最长无重复子串是多少

1. i位置上次出现的位置
2. i-1结尾的时候，最长无重复子串

2个瓶颈谁近，谁是最长无重复子串

public static int maxUnique(String str){
    if (str == null || str.length() == 0){
        return 0;
    }
    char[] chars = str.toCharArray();
    int len = 0;
    int pre = -1;
    int cur = 0;
    HashMap<Character, Integer> map = new HashMap<>();
    for(int i = 0; i != chars.length ; i++){
        if (map.containsKey(chars[i])){
            // 位置的最大值，pre i向前的位置，字符上次出现的位置
            pre = Math.max(pre, map.get(chars[i]));
        }
        cur = i - pre;
        len = Math.max(len, cur);
        map.put(chars[i], i);
    }
    return len;
}

题目五 编辑距离

给定两个字符串str1和str2，再给定三个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。
【举例】
str1="abc",str2="adc",ic=5，dc=3，rc=2
从”abc”编辑成”adc”，把”b’替换成’d’是代价最小的，所以返回2

str1="abc",str2="adc",ic=5，dc=3，rc=100
从”abc”编辑成”adc”，先删除’b’，然后插入’d’是代价最小的，所以返回8

str1="abc",str2="abc",ic=5，dc=3，rc=2
不用编辑了，本来就是一样的字符串，所以返回0

解：

准备一个mxn的数组，str[i]编辑为str[j]的代价为多少，str1[0,i-1]编辑为str2[0,i-1]的代价是多少

准备basecase，第一行由空串变为str2[0,i]代价为插入i*插入代价，第一列为i*删除代价

普遍情况的可能性：

• str1[0,i]的0,i-2变为前面，然后删除最后一位,dp[i-1][j]+del
• str1[0,i]的0,i-1变为前面，然后新增最后一位,dp[i][j-1]+add
• str1[0,i]的0,i-2变为前面，然后修改最后一位,dp[i-1][j-1]+replace
• i-1与j-1相同，把i-1变为j-1,dp[i-1][j-1]

public static int minCost(String str1, String str2, int ic, int dc, int rc) {
    if (str1 == null || str2 == null) {
        return 0;
    }
    if (str1.length() == 0 && str2.length() == 0){
        return 0;
    }
    char[] chs1 = str1.toCharArray();
    char[] chs2 = str2.toCharArray();
    int row = chs1.length + 1;
    int col = chs2.length + 1;
    int dp[][] = new int[row][col];
    for (int i = 0; i < row; i++) {
        dp[i][0] = dc * i;
    }
    for (int i = 0; i < col; i++) {
        dp[0][i] = ic * i;
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            if (chs1[i - 1] == chs2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j - 1] + rc;
            }
            dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
            dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
        }
    }
    return dp[row - 1][col - 1];
}

题目六 无重复字典序最小

给定一个全是小写字母的字符串str，删除多余字符，使得每种字符只保留一个，并让最终结果字符串的字典序最小
【举例】
str = “acbc”，删掉第一个’c’，得到”abc”，是所有结果字符串中字典序最小的。
str = “dbcacbca”，删掉第一个’b’、第一个’c’、第二个’c’、第二个’a’，得到”dabc”，是所有结果字符串中字典序最小的。

解

建立词频表，从开始位置向右扩充字符串，直到，有一个词频全部出现，删除

public String remove(String str) {
    if (str == null || str.length() < 2) {
        return str;
    }

    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < str.length(); i++) {
        map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) + 1);
    }
    int minASCIndex = 0;
    for (int i = 0; i < str.length(); i++) {
        minASCIndex = str.charAt(minASCIndex) > str.charAt(i) ? i : minASCIndex;
        if (map.get(str.charAt(i)) - 1 == 0) {
            break;
        }
        // ascii最小且靠左的位置
        map.put(str.charAt(i), map.get(str.charAt(i)) - 1);
    }
    // minACSIndex + {minASCIndex +1} 去掉minASCIndex字符
    return str.charAt(minASCIndex) +
            remove(str.substring(minASCIndex +1)
                    .replaceAll(String.valueOf(str.charAt(minASCIndex)),
                            ""));
}