leetcode刷题-第 225 场周赛

小咪咪 2023-01-10 14:35 92阅读 0赞

### leetcode刷题-第 225 场周赛 ###

*  1.替换隐藏数字得到的最晚时间
 *   *   *  备注
         *  代码
 *  2.满足三条件之一需改变的最少字符数
 *   *   *  备注
         *  代码
 *  3.找出第 K 大的异或坐标值
 *   *   *  备注
         *  代码
 *  4.放置盒子
 *   *   *  备注
         *  代码
 *  总结

# 1.替换隐藏数字得到的最晚时间 #

### 备注 ###

题目：给你一个字符串 time ，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。  
来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/latest-time-by-replacing-hidden-digits/submissions/  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

class Solution {
        public String maximumTime(String time) {
            char cur = time.charAt(0);
            char next = time.charAt(1);
            if ('?' == cur && '?' == next) {
                time = time.replaceFirst("\\?\\?", "23");
            } else if ('?' == cur) {
                time = time.replaceFirst("\\?", next > '3' ? "1" : "2");
            } else if ('?' == next) {
                time = time.replaceFirst("\\?", cur == '2' ? "3" : "9");
            }
    
            if ('?' == time.charAt(3)) {
                time = time.replaceFirst("\\?", "5");
            }
            if ('?' == time.charAt(4)) {
                time = time.replaceFirst("\\?", "9");
            }
            return time;
        }
    }

# 2.满足三条件之一需改变的最少字符数 #

### 备注 ###

给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。

操作的最终目标是满足下列三个条件 之一 ：

a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。  
b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。  
a 和 b 都 由 同一个 字母组成。  
返回达成目标所需的 最少 操作数。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

class Solution {
        public int minCharacters(String a, String b) {
            int[] countA = new int[26];
            int[] countB = new int[26];
            for (int i = 0; i < a.length(); i++) {
                countA[a.charAt(i) - 'a']++;
            }
            for (int i = 0; i < b.length(); i++) {
                countB[b.charAt(i) - 'a']++;
            }
            // 第一个条件
            int maxA = getMax(countA);
            int minA = getMin(countA);
            int maxB = getMax(countB);
            int minB = getMin(countB);
            // 1.不相交
            if (maxA < minB || maxB < minA) {
                return 0;
            }
            // 2.完全相交的情况
            int count = 0;
            if (minA < minB && maxA > maxB) {
                // A完全包含B
                count = getMinInclude(countA, countB, minA, maxA, minB, maxB);
            } else if (minB < minA && maxB > maxA) {
                count = getMinInclude(countB, countA, minB, maxB, minA, maxB);
            } else {if (minA == minB && maxA == maxB) {
                    // 全交 左右都要算
                    count = getMinInter(countA, countB, minA, maxA, minB, maxB);
                    int count1 = getMinInter(countB, countA, minB, maxB, minA, maxB);
                    if (count > count1) {
                        count = count1;
                    }
                } else if (minA < minB || (minA == minB && maxA <= maxB)) {
                    count = getMinInter(countA, countB, minA, maxA, minB, maxB);
                } else {
                    count = getMinInter(countB, countA, minB, maxB, minA, maxB);
                }
            }
    
            // 计算变为同一字母的情况
            int total = a.length() + b.length();
            for (int i = 0; i < 26; i++) {
                int cur = total - countA[i] - countB[i];
                if (count > cur) {
                    count = cur;
                }
            }
            return count;
        }
        /**
         * count1完全包含count2，即min1 < min2 <= max2 < max1
         * 1) 特殊：全靠边，不要 右交全，改为（右交全 + count1[25], 或(右交全 + count1[0])
         * @param count1
         * @param count2
         * @param min1
         * @param max1
         * @param min2
         * @param max2
         * @return
         */
        private int getMinInclude(int[] count1, int[] count2, int min1, int max1, int min2, int max2) {
            int last = 0;
            for (int i = min2; i <= max1; i++) {
                last += count1[i];
            }
            int result = last;
            for (int i = min2; i < max2; i++) {
                last = last - count1[i] + count2[i];
                if (result > last) {
                    result = last;
                }
            }
    
            last = 0;
            for (int i = min1; i <= max2; i++) {
                last += count1[i];
            }
            for (int i = max2; i > min1; i--) {
                last = last - count1[i] + count2[i];
                if (result > last) {
                    result = last;
                }
            }
    
            // 比较右交全
            last = 0;
            for (int i = min2; i <= max2; i++) {
                last += count2[i];
            }
            last += Math.min(count1[0], count2[25]);
            if (result > last) {
                result = last;
            }
            return result;
        }
    
    
        /**
         * count1与count2相交，其中min1 < min2，或(min1 == min2 && max1 < max2)
         * 相交部分为 min2 - max1
         * 1) 正常相交；左相交 但 左右任一有空；右相交、左右任一有空；全交、左右任一有空
         * 2）左相交、左右无空，（min1 == min == min2 == 0 < max2 == 25）。
         * 3) 右相交、左右无空。
         * 4）全交、左右无空（min1 == min == min2 == 0， max1 == max == max2 == 25）。不要 左交全、右交全。
         * @param count1
         * @param count2
         * @return
         */
        private int getMinInter(int[] count1, int[] count2, int min1, int max1, int min2, int max2) {
            int min = min2;
            int max = max1;
            // 计算count1的相交部分和
            int last = 0;
            for (int i = min; i <= max; i++) {
                last += count1[i];
            }
            int result = last;
            // 1) 左相交、右靠边,不要 左相交边和（记为短交全）, 多 短交全 + count2[25](即左边 全 换到 25位置了）
            // 2）全交，不要短交全
            if (min == 0) {
                if (max == 25) {
                    result = Integer.MAX_VALUE;
                } else if (max2 == 25) {
                    result += count2[25];
                }
            }
    
            // 将 (i + 1, max) 移到左边，(min, i)移到右边
            for (int i = min; i <= max && i < 25; i++) {
                last = last - count1[i] + count2[i];
                // 要小值
                if (result > last) {
                    result = last;
                }
            }
            // 全交，不要 右交全
            if (max == 25 && min != 0) {
                // 右交全
                if (min1 == 0) {
                    // 右相交、左靠边（包含全相交、全靠边），不要 右交全，多 右全交 + count[0]
                    last = last - count1[25] + count2[25];
                    last += count1[0];
                    if (result > last) {
                        result = last;
                    }
                }
            }
            return result;
        }
    
        private int getMin(int[] arr) {
            int min = -1;
            while (++min < 26 && arr[min] == 0){}
            return min;
        }
        private int getMax(int[] arr) {
            int max = 26;
            while (--max >= 0 && arr[max] == 0){}
            return max;
        }
    }

# 3.找出第 K 大的异或坐标值 #

### 备注 ###

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix\[i\]\[j\]（下标从 0 开始计数）执行异或运算得到。

请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

// 先算横
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 1; j < matrix[0].length; j++) {
                    matrix[i][j] ^= matrix[i][j - 1];
                }
            }
            // 再算竖
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    matrix[i][j] ^= matrix[i - 1][j];
                }
            }
            int last = Integer.MAX_VALUE;
            int nk = k;
            for (int n = 0; n < nk; n++) {
                int max = -1;
                int count = 0;
                for (int i = 0; i < matrix.length; i++) {
                    for (int j = 0; j < matrix[0].length; j++) {
                        int cur = matrix[i][j];
                        if (cur == max) {
                            count++;
                        } else if (cur >= last) {
                            continue;
                        } else if (cur > max) {
                            max = cur;
                            count = 1;
                        }
                    }
                }
                nk -= count - 1;
                last = max;
            }
            return last;

# 4.放置盒子 #

### 备注 ###

有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：

你可以把盒子放在地板上的任何地方。  
如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。  
给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/building-boxes  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

class Solution {
        public int minimumBoxes(int n) {
            if (n <= 3) {
                return n;
            } else if (n == 4) {
                return 3;
            }
            int i = 1;
            int prev = 1;
            int last = 1;
            int result = 0;
            while ((result + last) < n) {
                prev = last;
                result += last;
                i++;
                last = ((i + 1) * i) / 2;
            }
            int j = 1;
            while (result < n) {
                result += j++;
                prev += 1;
            }
            return prev;
        }
    }

# 总结 #

*  做下来1、4较为简单；
 *  3最后排序时使用时间比较多（好好复习下top k排序了）
 *  2是最难的，分析数学的情况高达十几种，应该是姿势不对吧，后续可以看下别人的答案