刷题日记 - 3

class Solution {
    public int romanToInt(String s) {
        // 获取字符串的长度
        int len = s.length();
        // 将字符串转换为字符数组，便于逐个字符处理
        char[] charArray = s.toCharArray();
        
        // 创建一个HashMap来存储罗马数字与整数值的对应关系
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);

        // 初始化结果变量和上一个处理的字符变量
        int res = 0;
        char last = 'I';

        // 从右向左遍历字符数组
        for (int i = len - 1; i >= 0; i--) {
            // 当前处理的字符
            char cur = charArray[i];
            // 如果当前字符代表的值小于上一个字符的值，则减去当前字符的值
            if (map.get(cur) < map.get(last)) {
                res -= map.get(cur);
            } else {
                // 否则，加上当前字符的值，并更新上一个字符为当前字符
                res += map.get(cur);
                last = cur;
            }
        }

        // 返回计算的结果
        return res;
    }
}

class Solution {
    public String intToRoman(int num) {
        // 用于存储结果的StringBuilder
        StringBuilder res = new StringBuilder();

        // 定义数组存储可能的整数值
        int[] vals = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        // 定义数组存储对应的罗马数字
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        // 将数字转换为罗马数字
        for (int i = 0; i < vals.length; i++) {
            while (num >= vals[i]) {
                num -= vals[i];
                res.append(symbols[i]);
            }
        }

        // 返回结果
        return res.toString();
    }
}

class Solution {
    public int lengthOfLastWord(String s) {
        // 将字符串转换为字符数组
        char[] charArray = s.toCharArray();
        
        // res 用于保存最后一个单词的长度，tmp 用于临时保存当前单词的长度
        int res = 0;
        int tmp = 0;
        
        // p 用于遍历字符数组的指针，len 为字符串的长度
        int p = 0;
        int len = s.length();
        
        // 遍历字符串
        while (p < len) {
            // 如果当前字符不是空格，增加 tmp 计数器
            if (charArray[p] != ' ') {
                tmp++;
                p++;
            // 如果当前字符是空格
            } else if (charArray[p] == ' ') {
                // 将 tmp 的值赋给 res 表示当前单词结束
                res = tmp;
                // 将 tmp 重置为 0 为下一个单词做准备
                tmp = 0;
                // 跳过连续的空格
                p++;
                while (p < len && charArray[p] == ' ') {
                    p++;
                }
            }
            // 如果遍历到最后并且 tmp 不为 0，更新 res
            if (p == len && tmp != 0) {
                res = tmp;
            }
        }
        
        // 返回最后一个单词的长度
        return res;
    }
}

class Solution {
    public int lengthOfLastWord(String s) {
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        int res = 0;

        for(int i=len-1;i>=0;i--){
            char cur = charArray[i];
            if(cur==' '&&res==0) continue;
            if(cur!=' ') res++;
            if(cur==' ') break;
        }
        return res;
    }
}

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // StringBuilder 用于构建结果字符串
        StringBuilder sb = new StringBuilder("");
        // 索引，用于遍历字符
        int idx = 0;
        // 标志位，用于控制外层循环
        boolean flag = true;
        // 临时变量，用于保存当前比较的字符
        char hold = ' ';

        // 外层循环，当 flag 为 true 时继续执行
        while (flag) {
            // 遍历每个字符串
            for (String str : strs) {
                // 如果当前索引超过字符串长度，设置 flag 为 false 并跳出循环
                if (idx >= str.length()) {
                    flag = false;
                    break;
                }
                // 获取当前字符串的第 idx 个字符
                char cur = str.charAt(idx);
                // 如果 hold 是空格，说明是第一个字符，将 hold 设置为当前字符
                if (hold == ' ') {
                    hold = cur;
                // 否则检查当前字符是否与 hold 相同，如果不同，设置 flag 为 false 并跳出循环
                } else if (hold != cur) {
                    flag = false;
                    break;
                }
            }
            // 索引加一，准备检查下一个字符
            idx++;
            // 如果 flag 仍然为 true，将 hold 的字符添加到结果字符串中
            if (flag) sb.append(hold);
            // 重置 hold 为空格，为下一个字符比较做准备
            hold = ' ';
        }
        // 返回构建的结果字符串
        return sb.toString();
    }
}

class Solution {
    public String reverseWords(String s) {
        // 使用 LinkedList 作为栈来存储单词
        LinkedList<String> stack = new LinkedList<>();
        
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        StringBuilder sb = new StringBuilder();
        
        int p = 0;
        
        while (p < len) {
            // 跳过所有空格
            while (p < len && charArray[p] == ' ') {
                p++;
            }
            
            // 如果到达字符串末尾，跳出循环
            if (p == len) break;
            
            // 找到下一个单词的结尾
            while (p < len && charArray[p] != ' ') {
                sb.append(charArray[p]);
                p++;
            }
            
            // 将单词推入栈中
            stack.push(sb.toString());
            sb.setLength(0);  // 清空 StringBuilder
        }
        
        // 构建结果字符串
        StringBuilder res = new StringBuilder();
        while (stack.size() > 1) {
            res.append(stack.pop());
            res.append(' ');
        }
        // 处理最后一个单词
        if (!stack.isEmpty()) {
            res.append(stack.pop());
        }
        
        return res.toString();
    }
}

class Solution {
    public int maxmiumScore(int[] cards, int cnt) {
        // 初始化一个桶数组，用于记录每个卡片值的数量
        int[] bucket = new int[1001];
        
        // 填充桶数组
        for(int card: cards){
            bucket[card]++;
        }

        int oddMin = -1; // 记录选中的奇数最小值
        int evenMin = -1; // 记录选中的偶数最小值
        int p = 1000; // 从最大的可能卡片值开始
        int res = 0; // 最终得分

        // 选择 cnt 张卡片
        while(cnt > 0){
            p = findNextNum(bucket, p); // 找到下一个最大的可用卡片值
            res += p; // 加到总得分中
            bucket[p]--; // 更新桶数组
            cnt--; // 减少剩余需要选择的卡片数
            if(p % 2 == 1) oddMin = p; // 如果是奇数，更新 oddMin
            if(p % 2 == 0) evenMin = p; // 如果是偶数，更新 evenMin
        }

        // 如果总得分是偶数，直接返回结果
        if(res % 2 == 0) return res;
        
        // 寻找可以替换的奇数和偶数
        int nextOdd = (evenMin == -1) ? -1 : findNextOddNum(bucket, p);
        int nextEven = (oddMin == -1) ? -1 : findNextEvenNum(bucket, p);

        // 输出调试信息
        // System.out.println(oddMin);
        // System.out.println(evenMin);
        // System.out.println(nextOdd);
        // System.out.println(nextEven);

        // 如果没有可替换的奇数和偶数，返回 0
        if(nextOdd == -1 && nextEven == -1) return 0;
        // 如果没有可替换的奇数，但有偶数，进行替换并返回结果
        if(nextOdd == -1 && nextEven != -1) return res - oddMin + nextEven;
        // 如果没有可替换的偶数，但有奇数，进行替换并返回结果
        if(nextOdd != -1 && nextEven == -1) return res - evenMin + nextOdd;

        // 返回两种替换方式中的最大值
        return Math.max(res - oddMin + nextEven, res - evenMin + nextOdd);
    }

    // 找到下一个最大的可用卡片值
    private int findNextNum(int[] bucket, int p){
        while(p >= 0 && bucket[p] == 0){
            p--;
        }
        if(p != -1){
            return p;
        }
        return -1;
    }

    // 找到下一个最大的奇数卡片值
    private int findNextOddNum(int[] bucket, int p){
        while((p >= 0 && bucket[p] == 0) || (p % 2 == 0)){
            p--;
        }
        if(p != -1){
            return p;
        }
        return -1;
    }

    // 找到下一个最大的偶数卡片值
    private int findNextEvenNum(int[] bucket, int p){
        while((p >= 0 && bucket[p] == 0) || (p % 2 == 1)){
            p--;
        }
        if(p != -1){
            return p;
        }
        return -1;
    }
}

class Solution {
    public String convert(String s, int numRows) {
        // 获取字符串的长度
        int len = s.length();
        // 如果字符串长度小于等于行数，或者行数为1，直接返回字符串
        if (len <= numRows || numRows == 1) return s;

        // 将字符串转换为字符数组
        char[] charArray = s.toCharArray();
        // 使用 StringBuilder 存储结果字符串
        StringBuilder sb = new StringBuilder();

        // 计算完整的间隔周期
        int interval = 2 * numRows - 2;

        // 遍历每一行
        for (int i = 0; i < numRows; i++) {
            // 处理第一行
            if (i == 0) {
                int p = 0;
                // 每次跳过完整周期间隔
                while (p < len) {
                    sb.append(charArray[p]);
                    p += interval;
                }
            }
            // 处理最后一行
            else if (i == numRows - 1) {
                int p = numRows - 1;
                // 每次跳过完整周期间隔
                while (p < len) {
                    sb.append(charArray[p]);
                    p += interval;
                }
            }
            // 处理中间行
            else {
                int p1 = i; // 当前行的第一个字符
                int p2 = 2 * numRows - 2 - i; // 当前行的第二个字符
                while (p1 < len && p2 < len) {
                    sb.append(charArray[p1]);
                    sb.append(charArray[p2]);
                    p1 += interval;
                    p2 += interval;
                }
                // 如果剩下一个字符
                if (p1 < len) {
                    sb.append(charArray[p1]);
                }
            }
        }
        // 返回结果字符串
        return sb.toString();
    }
}