lcp346

2696. 删除子串后的字符串最小长度

方法一：暴力枚举

class Solution {
    public int minLength(String s) {
        int res = s.length();
        int[] last = new int[s.length()];
        int lastIndex = -1;
        for (int i = 1; i < s.length(); ++i) {
            char ch1 = s.charAt(i - 1), ch2 = s.charAt(i);
            if (ch1 == 'A' || ch1 == 'C') {
                if (ch2 != 'B' && ch2 != 'D') {
                    last[++lastIndex] = i - 1;
                } else if ((ch1 == 'A' && ch2 == 'B') || (ch1 == 'C' && ch2 == 'D')) {
                    res -= 2;
                    int step = 1;
                    for (int r = i + 1; lastIndex >= 0 && r < s.length(); ++r) {
                        char ch3 = s.charAt(last[lastIndex]), ch4 = s.charAt(r);
                        if ((ch3 == 'A' && ch4 == 'B') || (ch3 == 'C' && ch4 == 'D')) {
                            res -= 2;
                            ++step;
                            --lastIndex;
                        }
                        else {
                            i += step;
                            break;
                        }
                    }
                }
            }
            else { // ch1 != AC
                lastIndex = -1;
            }
        }
        return res;
    }
}

方法二：栈

class Solution {
    public int minLength(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (!stack.isEmpty() && ((stack.peek() == 'A' && ch == 'B') || (stack.peek() == 'C' && ch == 'D')))
                stack.pop();
            else
                stack.push(ch);
        }
        return stack.size();
    }
}	

2697. 字典序最小回文串

方法一：DP(超时)

class Solution {
    public String makeSmallestPalindrome(String s) {
        int n = s.length();
        String[][] dp = new String[n][n];
        for (int i = 0; i < n; ++i) {
            char chI = s.charAt(i);
            for (int j = 0; j <= i; ++j) {
                char chJ = s.charAt(j);
                char small = chJ - chI < 0 ? chJ : chI;
                if (i == j)
                    dp[j][i] = String.valueOf(chI);
                else if (i - j == 1)
                    dp[j][i] = String.valueOf(small) + small;
                else if (i - j == 2)
                    dp[j][i] = String.valueOf(small) + s.charAt(j + 1) + small;
                else {
                    dp[j][i] = String.valueOf(small) + dp[j + 1][i - 1] + small;
                }
            }
        }
        return dp[0][n - 1];
    }
}

方法二：贪心

class Solution {
    public String makeSmallestPalindrome(String s) {
        char[] arr = s.toCharArray();
        for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
            char small = arr[i] < arr[j] ? arr[i] : arr[j];
            arr[i] = small;
            arr[j] = small;
        }
        return new String(arr);
    }
}

求一个整数的惩罚数

方法一：回溯

class Solution {
 public int punishmentNumber(int n) {
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            if (check(i))
                res += i * i;
        }
        return res;
    }

    private boolean check(int x) {
        path.clear();
        return dfs(x, String.valueOf(x * x), 0);
    }

    Deque<String> path = new LinkedList<>();
    private boolean dfs(int x, String str, int index) {
        if (index == str.length()) {
            int sum = 0;
            for (String s : path)
                sum += Integer.parseInt(s);
            return sum == x;
        }
        for (int i = index; i < str.length(); ++i) {
            String sub = str.substring(index, i + 1);
            path.offerLast(sub);
            if (dfs(x, str, i + 1))
                return true;
            path.pollLast();
        }
        return false;
    }
}	

修改图中的边权

方法一：