2432. 处理用时最长的那个任务的员工5.5

共有 n 位员工，每位员工都有一个从 0 到 n - 1 的唯一 id 。

给你一个二维整数数组 logs ，其中 logs[i] = [idi, leaveTimei] ：

• idi 是处理第 i 个任务的员工的 id ，且leaveTimei 是员工完成第 i 个任务的时刻。所有 leaveTimei 的值都是 唯一 的。
• 注意，第 i 个任务在第 (i - 1) 个任务结束后立即开始，且第 0 个任务从时刻 0 开始。

返回处理用时最长的那个任务的员工的 id 。如果存在两个或多个员工同时满足，则返回几人中 最小 的 id 。
思路

使用枚举法将每一位员工的用时计算出来

public class Sulotion2432 {
    
    public int hardestWorker(int n, int[][] logs) {
    
        if (n == 1) {
    
            return 0;
        }
        int res = logs[0][1];
        int flag = logs[0][0];
        for (int i = 1; i < logs.length; i++) {
    
            int usid = logs[i][0];
            int temp = logs[i][1] - logs[i - 1][1];
            if (temp > res || (temp == res && usid < flag)) {
    
                res = temp;
                flag = logs[i][0];
            }
        }
        return flag;
    }
}

1419. 数青蛙5.6

• 给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 “croak” ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
• 请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
• 要想发出蛙鸣 “croak”，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。

思路

使用计数的方式，创建一个数组，判断当前字符出现的次数以及当前字符的顺序（遍历后面字符的时候会判断前一个是否为0，以此来形成一个有顺序的鸣叫），如果当前字符合理，就将当前的数组计数加一，将前一个数组计数减一。因此当最终遍历完成如果有效的话所有计数应当全部为0；要判断同时有几只青蛙，只需要判断在数组中同时出现的最大数目。

public class Sulotion1419 {
    
    public static int minNumberOfFrogs(String croakOfFrogs) {
    
        if (croakOfFrogs.length() % 5 != 0) {
    
            return -1;
        }
        int[] count = new int[4];
        int res = 0;
        for (int i = 0; i < croakOfFrogs.length(); i++) {
    
            char c = croakOfFrogs.charAt(i);
            if (c != 'c' & c != 'r' & c != 'o' & c != 'a' & c != 'k'){
    
                return -1;
            }
            switch (c){
    
                case 'c': count[0]++; break;
                case 'r': if(count[0]==0) return -1; count[0]--; count[1]++; break;
                case 'o': if(count[1]==0) return -1; count[1]--; count[2]++; break;
                case 'a': if(count[2]==0) return -1; count[2]--; count[3]++; break;
                case 'k': if(count[3]==0) return -1; count[3]--; break;
            }
            // 判断同时有几只青蛙在叫
            res = Math.max(res, count[0]+count[1]+count[2]+count[3]);
        }
        // 判断叫声是否完整
        return count[0]+count[1]+count[2]+count[3] == 0 ? res : -1;
    }
}

1010. 总持续时间可被 60 整除的歌曲5.7

• 在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
• 返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望下标数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。

思路

使用双重for循环显然是可以直接实现的，但是那样的话时间复杂度是O(n^2)。
所以我们的思路是创建一个长度为61数组，用来记录当前索引数下的数字量，当一个数对60取余得到的数加上60减去这个数的值必定可以对60取余为0，所以只需记录遍历的数对60取余对应的数组的索引，然后将所有与之相加为60的数的数量记录下来。

public class Sulotion1010 {
    
    public int numPairsDivisibleBy60(int[] time) {
    
        int res = 0;
        int[] count = new int[61];
        for (int i = 0; i < time.length; i++) {
    
            res += count[(60 - time[i] % 60) % 60];
            count[time[i] % 60]++;
        }
        return res;
    }
}

2290. 到达角落需要移除障碍物的最小数目5.8

• 给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：
  0 表示一个空单元格，
• 1 表示一个可以移除的 障碍物 。
• 你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
• 现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。

这个题优点难度，目前自己完全不能解决，等后续持续学习
这个题主要用到图的广度优先遍历

2437. 有效时间的数目5.9

• 给你一个长度为 5 的字符串 time ，表示一个电子时钟当前的时间，格式为 “hh:mm” 。最早 可能的时间是 “00:00” ，最晚 可能的时间是 “23:59” 。
• 在字符串 time 中，被字符 ? 替换掉的数位是 未知的 ，被替换的数字可能是 0 到 9 中的任何一个。
• 请你返回一个整数 answer ，将每一个 ? 都用 0 到 9 中一个数字替换后，可以得到的有效时间的数目。

思路

时间一共由四个数组组成，将这四个数字分离出来进行单独判断

import java.util.ArrayList;

public class Sulotion2437 {
    

    public int countTime(String time) {
    
        int res = 1;
        ArrayList<Integer> arrayList = new ArrayList();
        String[] str = time.split("");
        if (str[0].equals("?") && str[1].equals("?")) {
    
            res *= 24;
        } else {
    
            if (str[0].equals("?")) {
    
                if (Integer.parseInt(str[1]) < 4) {
    
                    res *= 3;
                } else {
    
                    res *= 2;
                }
            }
            if (str[1].equals("?")) {
    
                if (Integer.parseInt(str[0]) == 2) {
    
                    res *= 4;
                } else {
    
                    res *= 10;
                }

            }
        }
        if (str[3].equals("?")) {
    
            res *= 6;
        }
        if (str[4].equals("?")) {
    
            res *= 10;
        }
        return res;
    }
}

1015. 可被 K 整除的最小整数5.10

• 给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。

• 返回 n 的长度。如果不存在这样的 n ，就返回-1。

思路

要判断有多长的由1组成的数可以被k整除，两种思路

1. 使用1*10+1对k取余余数等于0，返回结果，如果开始循环，证明无解
2. 分析可知，当k能被2和5整除时肯定无解，所以直接返回-1，其他数字肯定有解，所以进行循环查找最短的值就行。

public class Sulotion1015 {
    
    public int smallestRepunitDivByK(int k) {
    
        if (k % 2 == 0 || k % 5 == 0) {
    
            return -1;
        }
        int res = 1;
        int temp = 1 % k;
        while (temp != 0) {
    
            temp = (temp * 10 + 1) % k;
            res++;
        }
        return res;
    }
}

1016. 子串能表示从 1 到 N 数字的二进制串5.11

• 给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回 true，否则返回 false 。
• 子字符串 是字符串中连续的字符序列。

思路

Java中提供数字转为二进制，直接判断此数字的二进制是否存在与这个二进制字符串S中
官方解法使用滑动窗口

public class Sulotion1016 {
    
    public boolean queryString(String s, int n) {
    

        for (int i = 0; i < n; i++) {
    
            String str = Integer.toString(i, 2);
            if(!s.contains(str)){
    
                return false;
            }
        }
        return true;
    }
}

1330. 翻转子数组得到最大的数组值5.12

• 给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。
• 你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次 。
• 请你找到可行的最大 数组值 。

思路

这个题花费的挺长时间在优化上，首先这个题的意思是让你计算数组的值（前一个减去后一个绝对值的和），然后可以翻转一次子数组使其达到最大值，以下记录下当时的思路：

1. 计算出一个方法专门用来计算数组值，然后使用双重for循环直接将范围内的数组翻转，计算新数组的数组值，返回最大值。（超时，时间复杂度O($n^3$)）
2. 根据官方提示，发现后续不需要专门翻转求解数组值，因为需要翻转内部的数据是固定的值，只需要将翻转前后的值与首位值差的绝对值进行比较，这样优化下来时间复杂度是O($n^2$)，还是超时。
3. 最后还是根据官方提示，需要翻转前后的值与首位值差的绝对值进行比较，在这其中一共有四个值，这四个值是有规律的，如下

public class Sulotion1330 {
    
    public static int maxValueAfterReverse(int[] nums) {
    

        int res = shuck(nums);
        int max = 0;
        for (int i = 0; i < nums.length - 1; i++) {
    
            max = Math.max(max, Math.abs(nums[0] - nums[i + 1]) - (Math.abs(nums[i] - nums[i + 1])));
            max = Math.max(max, Math.abs(nums[i] - nums[nums.length - 1]) - (Math.abs(nums[i] - nums[i + 1])));
        }

        int max2 = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 1; i++) {
    
            int x = nums[i], y = nums[i + 1];
            max2 = Math.max(max2,Math.min(x, y));
            min = Math.min(min, Math.max(x, y));
        }
        res = Math.max(res + max, res + 2 * (max2 - min));
        return res;
    }

    public static int shuck(int[] nums) {
    
        int res = 0;
        for (int i = 1; i < nums.length; i++) {
    
            res += Math.abs(nums[i - 1] - nums[i]);
        }
        return res;
    }
}

2441. 与对应负数同时存在的最大正整数5.13

• 给你一个 不包含 任何零的整数数组 nums ，找出自身与对应的负数都在数组中存在的最大正整数 k 。

• 返回正整数 k ，如果不存在这样的整数，返回 -1 。

public class Sulotion2441 {
    
    public static int findMaxK(int[] nums) {
    

        Arrays.sort(nums);

        for (int i = 0,j = nums.length-1; i < j; ) {
    
            if (nums[i]+nums[j]==0){
    
                return nums[j];
            }else if(nums[i]+nums[j]<0){
    
                i++;
            }else{
    
                j++;
            }
        }
        return -1;
    }
}

1054. 距离相等的条形码5.14

• 在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。

• 请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

思路

将所给数组进行排序，然后分为两组，将两组相互交叉即可，因为一定有答案，所以会出现四种特殊情况，当左边全部相等，从左边开始进行交叉，当右边全部相等，从右边开始交叉，当中间分开区域相等，从中间向两边开始交叉。

public class Sulotion1054 {
    
    public static int[] rearrangeBarcodes(int[] barcodes) {
    
        Arrays.sort(barcodes);
        int len = barcodes.length;
        int[] res = new int[len];
        int temp = 0;
        if (barcodes.length % 2 > 0) {
    
            if (barcodes[len - 1] == barcodes[len / 2]) {
    
                for (int i = 0, j = len - 1; i < j; i++, j--) {
    
                    res[temp++] = barcodes[j];
                    res[temp++] = barcodes[i];
                }
                res[temp++] = barcodes[len / 2];
            } else {
    

                if (barcodes[len / 2] == barcodes[len / 2 + 1]) {
    
                    for (int i = 0, j = len - 1, k = len/2,l = len/2+1; i < len/2/2; i++, j--,k--,l++) {
    
                        res[temp++] = barcodes[k];
                        res[temp++] = barcodes[i];
                        res[temp++] = barcodes[l];
                        res[temp++] = barcodes[j];
                    }
                    res[temp++] = barcodes[len/2/2];
                } else {
    
                    for (int i = len / 2, j = len - 1; i > 0; i--, j--) {
    
                        res[temp++] = barcodes[i];
                        res[temp++] = barcodes[j];
                    }
                    res[temp++] = barcodes[0];
                }

            }
        } else {
    
            for (int i = len / 2 - 1, j = len - 1; i >= 0; i--, j--) {
    
                res[temp++] = barcodes[i];
                res[temp++] = barcodes[j];
            }
        }
        return res;
    }
}

1072. 按列翻转得到最大值等行数5.15

• 给定 m x n 矩阵 matrix 。

• 你可以从中选出任意数量的列并翻转其上的 每个 单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）

• 返回 经过一些翻转后，行与行之间所有值都相等的最大行数 。

思路

求相同的行的最多数量，列可以翻转，类似001，110这种，可以将他们当作一类数据，如001就是false,false,true，110为false,false,true，只要将true翻转即可得到相同的行，将矩阵中每一行的数据类型存储到Map中，然后找到最大相同的数量。

public class Sulotion1072 {
    
    public static int maxEqualRowsAfterFlips(int[][] matrix) {
    
        Map<Map<Integer, Boolean>, Integer> map = new HashMap();
        int res = 0;
        for (int[] row : matrix) {
    
            Map<Integer, Boolean> b = new Hashtable<>();
            for (int i = 0; i < matrix[0].length; i++){
    
                // 用第一行第一个表示为true，之后的false是都需要反转的
                b.put(i, (row[0] ^ row[i]) == 1);
            }
            // getOrDefault：若存在b则返回对应的value否则创建默认0
            map.put(b, map.getOrDefault(b, 0) + 1);
            res = Math.max(res, map.get(b));
        }
        return res;
    }
}

1335. 工作计划的最低难度5.16

• 你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。
• 你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。
• 给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
• 返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。

主要用到动态规划，后续学习动态规划一并处理，现在还是实力欠佳

2446. 判断两个事件是否存在冲突5.17

• 给你两个字符串数组 event1 和 event2 ，表示发生在同一天的两个闭区间时间段事件，其中：
• event1 = [startTime1, endTime1] 且
  event2 = [startTime2, endTime2]
• 事件的时间为有效的 24 小时制且按 HH:MM 格式给出。
• 当两个事件存在某个非空的交集时（即，某些时刻是两个事件都包含的），则认为出现 冲突 。
• 如果两个事件之间存在冲突，返回 true ；否则，返回 false 。

思路

简单题我重拳出击，分别判断一个时间段是否在另一个时间段内

public class Sulotion2446 {
    
    public boolean haveConflict(String[] event1, String[] event2) {
    
        return !(event1[1].compareTo(event2[0]) < 0 || event2[1].compareTo(event1[0]) < 0);
    }
}

1073. 负二进制数相加5.18

• 给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。

• 数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。

• 返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。

class Solution1073 {
    
    public int[] addNegabinary(int[] arr1, int[] arr2) {
    
        int i = arr1.length - 1, j = arr2.length - 1;
        int carry = 0;
        List<Integer> ans = new ArrayList<Integer>();
        while (i >= 0 || j >= 0 || carry != 0) {
    
            int x = carry;
            if (i >= 0) {
    
                x += arr1[i];
            }
            if (j >= 0) {
    
                x += arr2[j];
            }
            if (x >= 2) {
    
                ans.add(x - 2);
                carry = -1;
            } else if (x >= 0) {
    
                ans.add(x);
                carry = 0;
            } else {
    
                ans.add(1);
                carry = 1;
            }
            --i;
            --j;
        }
        while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
    
            ans.remove(ans.size() - 1);
        }
        int[] arr = new int[ans.size()];
        for (i = 0, j = ans.size() - 1; j >= 0; i++, j--) {
    
            arr[i] = ans.get(j);
        }
        return arr;
    }
}

1079. 活字印刷5.19

• 你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

• 注意：本题中，每个活字字模只能使用一次。

public class Sulotion1079 {
    
    int sum = 0;

    public int numTilePossibilities(String tiles) {
    

        int length = tiles.length();
        int[] arr = new int[26];
        for (int i = 0; i < length; i++) {
    
            arr[tiles.charAt(i) - 'A']++;
        }
        find(arr, length, 0);
        return sum;
    }

    private void find(int[] arr, int n, int index) {
    
        if (n == 1) {
    
            sum++;
            return;
        }
        if (n > 0) {
    
            int a = 1;
            int b = 1;
            for (int i = 2; i <= n; i++) {
    
                a *= i;
            }
            for (int value : arr) {
    
                if (value > 1) {
    
                    for (int i = 2; i <= value; i++) {
    
                        b *= i;
                    }
                }
            }
            sum += (a / b);
            for (int i = index; i < 26; i++) {
    
                int value = arr[i];
                if (value > 0) {
    
                    arr[i]--;
                    find(arr, n - 1, i);
                    arr[i]++;
                }
            }
        }
    }
}

1080. 根到叶路径上的不足节点5.22

• 给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。

• 假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为 不足节点 ，需要被删除。

• 叶子节点，就是没有子节点的节点。

思路

题目描述不是特别清晰，我重新描述一遍，就是将每条数枝的和加起来，判断是否大于limit如果大于limit则不用管，如果小于，则将该树枝的叶子节点删除，如果一个节点的两个叶子节点都被删除 ，则该节点也被删除。使用dfs遍历，将和加起来分别判断左右节点是否满足条件，然后做出相应的删除操作。

public class Sulotion1080 {
    
    public TreeNode sufficientSubset(TreeNode root, int limit) {
    

        shuck(root, limit, 0);
        return root;
    }

    public static boolean shuck(TreeNode root, int limit, int num) {
    
        if (root == null) {
    
            return false;
        }
        if (root.left == null && root.right == null) {
    
            return num + root.val >= limit;
        }
        boolean left = shuck(root.left, limit, num + root.val);
        boolean right = shuck(root.right, limit, num + root.val);
        if (!left) {
    
            root.left = null;
        }
        if (!right) {
    
            root.right = null;
        }
        return left||right;
    }

    public static class TreeNode {
    
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
    
        }

        TreeNode(int val) {
    
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
    
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

1090. 受标签影响的最大值5.23

• 我们有一个 n 项的集合。给出两个整数数组 values 和 labels ，第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。

• 从 n 个元素中选择一个子集 s :

• 子集 s 的大小 小于或等于 numWanted 。
  s 中 最多 有相同标签的 useLimit 项。
  一个子集的 分数 是该子集的值之和。

• 返回子集 s 的最大 分数 。

public class Sulotion1090 {
    
    public static int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
    

        int n = values.length;
        Integer[] id = new Integer[n];
        for (int i = 0; i < n; i++) {
    
            id[i] = i;
        }
        Arrays.sort(id, (a, b) -> values[b] - values[a]);
        int res = 0, choose = 0;
        Map<Integer, Integer> map = new Hashtable<>();
        for (int i = 0; i < n && choose < numWanted; i++) {
    
            int label = labels[id[i]];
            if (map.getOrDefault(label, 0) == useLimit) {
    
                continue;
            }
            choose++;
            res += values[id[i]];
            map.put(label, map.getOrDefault(label, 0) + 1);
        }
        return res;
    }
}

1093. 大样本统计

• 我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 在样本中出现的次数。

• 计算以下统计数据:

• minimum ：样本中的最小元素。
  maximum ：样品中的最大元素。
  mean ：样本的平均值，计算为所有元素的总和除以元素总数。
  median ：

• 如果样本的元素个数是奇数，那么一旦样本排序后，中位数 median 就是中间的元素。
  如果样本中有偶数个元素，那么中位数median 就是样本排序后中间两个元素的平均值。
  mode ：样本中出现次数最多的数字。保众数是 唯一 的。

• 以浮点数数组的形式返回样本的统计信息 [minimum, maximum, mean, median, mode] 。与真实答案误差在 10-5 内的答案都可以通过。

public class Sulotion1093 {
    
    public static double[] sampleStats(int[] count) {
    

        double[] res = new double[5];
        int flag = 0, temp = 0;
        double  sum1 = 0.0;
        long sum = 0;
        for (int i = 0; i < count.length; i++) {
    
            if (count[i] != 0 && flag == 0) {
    
                res[0] = i;
                flag++;
            }
            if (count[i] != 0) {
    
                res[1] = i;
                sum1 += count[i];
            }
            sum += (long)count[i] * i;
            if (count[i] > temp) {
    
                temp = count[i];
                res[4] = i;
            }
        }
        res[2] = sum / sum1;
        if (sum1 % 2 == 0) {
    
            int tes = 0;
            for (int i = 0; i < count.length; i++) {
    
                tes += count[i];
                if (tes > sum1 / 2) {
    
                    res[3] = i;
                    break;
                }
                if (tes == sum1 / 2) {
    
                    int temp1 = i;
                    while(count[i+1]==0){
    
                        i++;
                    }
                    res[3] = (temp1 + i + 1) / 2.0;
                    break;
                }
            }
        } else {
    
            int tes = 0;
            for (int i = 0; i < count.length; i++) {
    
                tes += count[i];
                if (tes >= (sum1 + 1) / 2) {
    
                    res[3] = i;
                    break;
                }
            }
        }
        return res;
    }