package huawei.test01;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * 20230410晚华为机考第一题
 * <p>
 * 题目：充电站（回溯）
 *
 * 考试时误以为是01背包问题，实际是回溯
 * <p>
 * 给定一个充电站的最大允许功率maxP，找到充电站内所有设备的任意一种组合，使得这组设备的功率和最接近且不超过整个充电站的最大功率
 * <p>
 * 假设设备总数量为n，每台设备都有自身的功率Pi （1 <= i <= n）
 * <p>
 * 充电站内的某一台设备都有自身的功率，功率不一定相同
 * 找到任意一种组合指的是不限定组内的设备数量，即一组内的设备数量为1到n都可以
 * <p>
 * 如果不存在这样的组，比如当所有设备的功率均大于maxP时，不存在这样的组，返回0
 *
 * 测试用例：输入 4 20 20 50 60 90  输出90
 */
public class t1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(in.nextInt());
        }
        int maxP = in.nextInt();
        List<Integer> filtedList = list.stream().filter(x -> x <= maxP).collect(Collectors.toList());
        int[] ans = new int[]{0};
        resolve(filtedList, ans, 0, 0, maxP);
        System.out.println(ans[0]);
    }

    private static void resolve(List<Integer> filtedList, int[] ans, int curIndex, int curP, int maxP) {
        if (curIndex >= filtedList.size()) {
            if (curP <= maxP && curP > ans[0]) {
                ans[0] = curP;
            }
            return;
        }
        if (curP > maxP) {
            return;
        } else if (curP == maxP) {
            ans[0] = curP;
            return;
        } else if (curP > ans[0]){
            ans[0] = curP;
        }

        // 选择
        curP += filtedList.get(curIndex);
        // 进入下一个
        resolve(filtedList, ans, curIndex + 1, curP, maxP);
        // 撤销选择
        curP -= filtedList.get(curIndex);

        // 不选进入下一个
        resolve(filtedList, ans, curIndex + 1, curP, maxP);
    }
}

package huawei.test01;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 20230410晚华为机考第二题
 * <p>
 * 题目：找到相同数字间的最大距离
 * <p>
 * 一排数字，找到相同数字之间最长的间距，不存在任何一组相同数字则返回-1
 *
 * 测试案例：7 4 5 6 2 3 4 8  输出 5
 */
// 通过率100%
public class t2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        Map<Integer, Integer> firstPos = new HashMap<>();
        int distance = -1;
        for (int i = 0; i < n; i++) {
            Integer firstPosOrDefault = firstPos.getOrDefault(nums[i], -1);
            if (firstPosOrDefault == -1) {
                firstPos.put(nums[i], i);
            } else {
                distance = i - firstPosOrDefault;
            }
        }
        System.out.println(distance);
    }
}

package huawei.test01;

import java.util.Scanner;
import java.util.Stack;

/**
 * 20230410晚华为机考第三题
 * <p>
 * 题目：解压缩
 * <p>
 * 解法跟求解逆波兰表达式类似
 * <p>
 * 三种规则：
 * 规则一：形如A3，解压为AAA，单个字符后直接跟数字
 * 规则二：形如{AB}2，解压为ABAB，括号内为字符串，括号外带数字
 * 规则三：形如{A3B1{C}2}3，解压为AAABCCAAABCCAAABCC，括号嵌套
 * <p>
 * 区分大小写
 * 数字可能存在多位数 （一开始没有考虑这一点导致通过率只有20%）
 * <p>
 * 测试用例：输入 {A3B1{C}2}3  输出 AAABCCAAABCCAAABCC
 * 输入 {A3B12{C}2}3  输出 AAABBBBBBBBBBBBCCAAABBBBBBBBBBBBCCAAABBBBBBBBBBBBCC
 */
public class t3 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String compressedString = in.nextLine();
        char[] charArray = compressedString.toCharArray();
        Stack<String> stack = new Stack<>();
        String num = "";
        for (int i = 0; i < charArray.length; i++) {
            char curChar = charArray[i];
            if (curChar == '{' || curChar == '}') {
                stack.push(String.valueOf(curChar));
            } else if (isAlphabeta(curChar)) {
                stack.push(String.valueOf(curChar));
            } else if (isNumber(curChar)) {
                num = num + curChar;
                // 如果下一位还是数字，则先跳过
                if (i < charArray.length - 1 && isNumber(charArray[i + 1])) {
                    continue;
                }
                if (stack.peek().length() == 1 && !stack.peek().equals("}")) {
                    String pop = stack.pop();
                    StringBuilder sb = new StringBuilder();
                    for (int j = 0; j < Integer.parseInt(num); j++) {
                        sb.append(pop);
                    }
                    stack.push(sb.toString());
                } else if (stack.peek().length() == 1 && stack.peek().equals("}")) {
                    stack.pop();
                    StringBuilder sb = new StringBuilder();
                    while (!stack.peek().equals("{")) {
                        sb.insert(0, stack.pop());
                    }
                    stack.pop();
                    String temp = sb.toString();
                    for (int j = 1; j < Integer.parseInt(num); j++) {
                        sb.append(temp);
                    }
                    stack.push(sb.toString());
                }
                num = "";
            } else {
                stack.push(String.valueOf(curChar));
            }
        }
        System.out.println(stack.pop());
    }

    private static boolean isNumber(char curChar) {
        return curChar >= '0' && curChar <= '9';
    }

    private static boolean isAlphabeta(char curChar) {
        return curChar >= 'a' && curChar <= 'z' || curChar >= 'A' && curChar <= 'Z';
    }
}