标签： easy

目标

给你一个整数数组 nums 和一个整数 k 。

如果一个数组中所有 严格大于 h 的整数值都 相等 ，那么我们称整数 h 是 合法的 。

比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个 合法 整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是 合法 整数。

你可以对 nums 执行以下操作：

• 选择一个整数 h ，它对于 当前 nums 中的值是合法的。
• 对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。

你的目标是将 nums 中的所有元素都变为 k ，请你返回 最少 操作次数。如果无法将所有元素都变 k ，那么返回 -1 。

示例 1：

输入：nums = [5,2,5,4,5], k = 2
输出：2
解释：
依次选择合法整数 4 和 2 ，将数组全部变为 2 。

示例 2：

输入：nums = [2,1,2], k = 2
输出：-1
解释：
没法将所有值变为 2 。

示例 3：

输入：nums = [9,7,5,3], k = 1
输出：4
解释：
依次选择合法整数 7 ，5 ，3 和 1 ，将数组全部变为 1 。

说明：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100

思路

每次操作可以将数组中所有大于 h 的数变为 h，求将数组中所有元素变为 k 所需的最小操作数，如果无法实现返回 -1。

如果数组中存在小于 k 的元素，无论如何也无法实现。否则，每次操作可以将最大元素全部变为次最大元素，问题变为统计数组中严格大于 k 的元素个数。

代码

/**
 * @date 2025-04-09 8:48
 */
public class MinOperations3375 {

    public int minOperations(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        boolean lt = false;
        for (int num : nums) {
            if (num > k) {
                set.add(num);
            } else if (num < k) {
                lt = true;
            }
        }
        return lt ? -1 : Math.max(set.size(), 0);
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。 

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

说明：

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 10^6

思路

求数组 nums 的下标 0 <= i < j < k < n 时 (nums[i] - nums[j]) * nums[k] 的最大值。

数据范围不大可以暴力解。

由于数组元素为正数，nums[k] > 0，要使 (nums[i] - nums[j]) * nums[k] 最大，我们可以枚举 k，在区间 [0, k) 上找到 i < j 使 (nums[i] - nums[j]) 最大，如果是负数直接取 0。

维护 [0, i] 的最大值，用最大值减去当前值得到最大差值，有了最大差值直接乘以 nums[i + 1]，在遍历过程中取最大值即可。

代码

/**
 * @date 2025-04-02 0:54
 */
public class MaximumTripletValue2873 {

    public long maximumTripletValue_v1(int[] nums) {
        long res = 0L;
        int n = nums.length;
        int max = 0;
        long maxDiff = 0;
        for (int i = 0; i < n - 1; i++) {
            max = Math.max(max, nums[i]);
            maxDiff = Math.max(maxDiff, max - nums[i]);
            res = Math.max(res, maxDiff * nums[i + 1]);
        }
        return res;
    }

    public long maximumTripletValue(int[] nums) {
        long res = 0L;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    res = Math.max((long)(nums[i] - nums[j]) * nums[k], res);
                }
            }
        }
        return res;
    }
}

性能

目标

给你一个字符串 s 和一个字符 letter ，返回在 s 中等于 letter 字符所占的 百分比 ，向下取整到最接近的百分比。

示例 1：

输入：s = "foobar", letter = "o"
输出：33
解释：
等于字母 'o' 的字符在 s 中占到的百分比是 2 / 6 * 100% = 33% ，向下取整，所以返回 33 。

示例 2：

输入：s = "jjjj", letter = "k"
输出：0
解释：
等于字母 'k' 的字符在 s 中占到的百分比是 0% ，所以返回 0 。

说明：

• 1 <= s.length <= 100
• s 由小写英文字母组成
• letter 是一个小写英文字母

思路

统计给定字符在字符串中出现的百分比，要求向下取整。即 100 * cnt / total。

代码

/**
 * @date 2025-03-31 8:43
 */
public class PercentageLetter2278 {

    public int percentageLetter(String s, char letter) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == letter) {
                res++;
            }
        }
        return res * 100 / n;
    }
}

性能

目标

给你一个字符串数组 words 和一个字符串 s ，其中 words[i] 和 s 只包含 小写英文字母 。

请你返回 words 中是字符串 s 前缀 的 字符串数目 。

一个字符串的 前缀 是出现在字符串开头的子字符串。子字符串 是一个字符串中的连续一段字符序列。

示例 1：

输入：words = ["a","b","c","ab","bc","abc"], s = "abc"
输出：3
解释：
words 中是 s = "abc" 前缀的字符串为：
"a" ，"ab" 和 "abc" 。
所以 words 中是字符串 s 前缀的字符串数目为 3 。

示例 2：

输入：words = ["a","a"], s = "aa"
输出：2
解释：
两个字符串都是 s 的前缀。
注意，相同的字符串可能在 words 中出现多次，它们应该被计数多次。

说明：

• 1 <= words.length <= 1000
• 1 <= words[i].length, s.length <= 10
• words[i] 和 s 只 包含小写英文字母。

思路

计算字符串数组 words 中有多少个字符串是 s 的前缀。

代码

/**
 * @date 2025-03-24 8:44
 */
public class CountPrefixes2255 {

    public int countPrefixes(String[] words, String s) {
        int res = 0;
        for (String word : words) {
            if (word.length() > s.length()){
                continue;
            }
            int cnt = 1;
            for (int i = 0; i < word.length(); i++) {
                if (word.charAt(i) != s.charAt(i)) {
                    cnt = 0;
                    break;
                }
            }
            res += cnt;
        }
        return res;
    }
}

性能

目标

给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。

如果有多行包含最多的 1 ，只需要选择 行下标最小 的那一行。

返回一个由行下标和该行中 1 的数量组成的数组。

示例 1：

输入：mat = [[0,1],[1,0]]
输出：[0,1]
解释：两行中 1 的数量相同。所以返回下标最小的行，下标为 0 。该行 1 的数量为 1 。所以，答案为 [0,1] 。 

示例 2：

输入：mat = [[0,0,0],[0,1,1]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

示例 3：

输入：mat = [[0,0],[1,1],[0,0]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

说明：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• mat[i][j] 为 0 或 1

思路

返回二进制矩阵中 1 最多的行下标以及 1 的个数。

代码

/**
 * @date 2025-03-22 19:55
 */
public class RowAndMaximumOnes2643 {

    public int[] rowAndMaximumOnes(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] res = new int[2];
        for (int i = 0; i < m; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                cnt += mat[i][j];
            }
            if (cnt > res[1]) {
                res[0] = i;
                res[1] = cnt;
            }
        }
        return res;
    }
}

性能