3270.求出数字答案

目标

给你三个 正 整数 num1 ,num2 和 num3 。

数字 num1 ,num2 和 num3 的数字答案 key 是一个四位数,定义如下:

  • 一开始,如果有数字 少于 四位数,给它补 前导 0 。
  • 答案 key 的第 i 个数位(1 <= i <= 4)为 num1 ,num2 和 num3 第 i 个数位中的 最小 值。

请你返回三个数字 没有 前导 0 的数字答案。

示例 1:

输入:num1 = 1, num2 = 10, num3 = 1000
输出:0
解释:
补前导 0 后,num1 变为 "0001" ,num2 变为 "0010" ,num3 保持不变,为 "1000" 。
数字答案 key 的第 1 个数位为 min(0, 0, 1) 。
数字答案 key 的第 2 个数位为 min(0, 0, 0) 。
数字答案 key 的第 3 个数位为 min(0, 1, 0) 。
数字答案 key 的第 4 个数位为 min(1, 0, 0) 。
所以数字答案为 "0000" ,也就是 0 。

示例 2:

输入: num1 = 987, num2 = 879, num3 = 798
输出:777

示例 3:

输入:num1 = 1, num2 = 2, num3 = 3
输出:1

说明:

  • 1 <= num1, num2, num3 <= 9999

思路

有三个小于等于 9999 的正整数,求四位数字 key,从左向右第 i 位是这三个数字对应数位(十进制)上数字的最小值。

根据题意模拟即可。

代码


/**
 * @date 2025-01-11 16:55
 */
public class GenerateKey3270 {
    public int generateKey(int num1, int num2, int num3) {
        int res = 0;
        int base = 1000;
        for (int i = 0; i < 4; i++) {
            int a1 = num1 / base;
            int a2 = num2 / base;
            int a3 = num3 / base;
            res += Math.min(a1, Math.min(a2, a3)) * base;
            num1 %= base;
            num2 %= base;
            num3 %= base;
            base /= 10;
        }
        return res;
    }
}

性能

2264.字符串中最大的3位相同数字

目标

给你一个字符串 num ,表示一个大整数。如果一个整数满足下述所有条件,则认为该整数是一个 优质整数 :

  • 该整数是 num 的一个长度为 3 的 子字符串 。
  • 该整数由唯一一个数字重复 3 次组成。

以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数,则返回一个空字符串 "" 。

注意:

  • 子字符串 是字符串中的一个连续字符序列。
  • num 或优质整数中可能存在 前导零 。

示例 1:

输入:num = "6777133339"
输出:"777"
解释:num 中存在两个优质整数:"777" 和 "333" 。
"777" 是最大的那个,所以返回 "777" 。

示例 2:

输入:num = "2300019"
输出:"000"
解释:"000" 是唯一一个优质整数。

示例 3:

输入:num = "42352338"
输出:""
解释:不存在长度为 3 且仅由一个唯一数字组成的整数。因此,不存在优质整数。

说明:

  • 3 <= num.length <= 1000
  • num 仅由数字(0 - 9)组成

思路

判断字符串中是否存在 三个连续相同的数字,如果有多个返回数字最大的那个。

可以使用一个变量记录连续相同的字符个数,如果不同就重置 cnt 为 1。

代码


/**
 * @date 2025-01-08 8:48
 */
public class LargestGoodInteger2264 {

    public String largestGoodInteger(String num) {
        char c = 0;
        int n = num.length();
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (num.charAt(i) == num.charAt(i - 1)) {
                cnt++;
            } else {
                cnt = 1;
                continue;
            }
            if (cnt == 3 && c < num.charAt(i)) {
                c = num.charAt(i);
            }
        }
        return c > 0 ? new String(new char[]{c, c, c}) : "";
    }

}

性能

3019.按键变更的次数

目标

给你一个下标从 0 开始的字符串 s ,该字符串由用户输入。按键变更的定义是:使用与上次使用的按键不同的键。例如 s = "ab" 表示按键变更一次,而 s = "bBBb" 不存在按键变更。

返回用户输入过程中按键变更的次数。

注意:shift 或 caps lock 等修饰键不计入按键变更,也就是说,如果用户先输入字母 'a' 然后输入字母 'A' ,不算作按键变更。

示例 1:

输入:s = "aAbBcC"
输出:2
解释: 
从 s[0] = 'a' 到 s[1] = 'A',不存在按键变更,因为不计入 caps lock 或 shift 。
从 s[1] = 'A' 到 s[2] = 'b',按键变更。
从 s[2] = 'b' 到 s[3] = 'B',不存在按键变更,因为不计入 caps lock 或 shift 。
从 s[3] = 'B' 到 s[4] = 'c',按键变更。
从 s[4] = 'c' 到 s[5] = 'C',不存在按键变更,因为不计入 caps lock 或 shift 。

示例 2:

输入:s = "AaAaAaaA"
输出:0
解释: 不存在按键变更,因为这个过程中只按下字母 'a' 和 'A' ,不需要进行按键变更。

说明:

  • 1 <= s.length <= 100
  • s 仅由英文大写字母和小写字母组成。

思路

已知字符串 s,计算用户输入该字符串时按键的变更次数,不区分大小写。

根据题意比较相邻字符忽略大小写后是否相同,可以使用 |32 将字符都转为小写后比较。

代码


/**
 * @date 2025-01-07 8:46
 */
public class CountKeyChanges3019 {

    /**
     * A 65 010 00001 Z 90  010 11010
     * a 97 011 00001 Z 122 011 11010
     * 31   000 11111
     * 32   001 00000
     * 只有低 5 位不同,因此我们可以 &31 或者 |32
     */
    public int countKeyChanges_v1(String s) {
        int res = 0;
        int n = s.length();
        for (int i = 1; i < n; i++) {
            if ((s.charAt(i) | 32) != (s.charAt(i - 1) | 32)) {
                res++;
            }
        }
        return res;
    }

}

性能

3280.将日期转换为二进制表示

目标

给你一个字符串 date,它的格式为 yyyy-mm-dd,表示一个公历日期。

date 可以重写为二进制表示,只需要将年、月、日分别转换为对应的二进制表示(不带前导零)并遵循 year-month-day 的格式。

返回 date 的 二进制 表示。

示例 1:

输入: date = "2080-02-29"
输出: "100000100000-10-11101"
解释:
100000100000, 10 和 11101 分别是 2080, 02 和 29 的二进制表示。

示例 2:

输入: date = "1900-01-01"
输出: "11101101100-1-1"
解释:
11101101100, 1 和 1 分别是 1900, 1 和 1 的二进制表示。

说明:

  • date.length == 10
  • date[4] == date[7] == '-',其余的 date[i] 都是数字。
  • 输入保证 date 代表一个有效的公历日期,日期范围从 1900 年 1 月 1 日到 2100 年 12 月 31 日(包括这两天)。

思路

将日期转化为二进制表示。

代码


/**
 * @date 2025-01-01 18:53
 */
public class ConvertDateToBinary3280 {

    public String convertDateToBinary(String date) {
        return new StringBuilder().append(Integer.toBinaryString(Integer.parseInt(date.substring(0,4))))
                .append("-")
                .append(Integer.toBinaryString(Integer.parseInt(date.substring(5,7))))
                .append("-")
                .append(Integer.toBinaryString(Integer.parseInt(date.substring(8,10)))).toString();
    }

}

性能

3046.分割数组

目标

给你一个长度为 偶数 的整数数组 nums 。你需要将这个数组分割成 nums1 和 nums2 两部分,要求:

  • nums1.length == nums2.length == nums.length / 2 。
  • nums1 应包含 互不相同 的元素。
  • nums2也应包含 互不相同 的元素。

如果能够分割数组就返回 true ,否则返回 false 。

示例 1:

输入:nums = [1,1,2,2,3,4]
输出:true
解释:分割 nums 的可行方案之一是 nums1 = [1,2,3] 和 nums2 = [1,2,4] 。

示例 2:

输入:nums = [1,1,1,1]
输出:false
解释:分割 nums 的唯一可行方案是 nums1 = [1,1] 和 nums2 = [1,1] 。但 nums1 和 nums2 都不是由互不相同的元素构成。因此,返回 false 。

说明:

  • 1 <= nums.length <= 100
  • nums.length % 2 == 0
  • 1 <= nums[i] <= 100

思路

判断数组中同一元素的出现次数不超过两次。

代码


/**
 * @date 2024-12-28 19:16
 */
public class IsPossibleToSplit3046 {

    public boolean isPossibleToSplit(int[] nums) {
        int[] cnt = new int[101];
        for (int num : nums) {
            if (++cnt[num] > 2) {
                return false;
            }
        }
        return true;
    }
}

性能

3083.字符串及其反转中是否存在同一子字符串

目标

给你一个字符串 s ,请你判断字符串 s 是否存在一个长度为 2 的子字符串,在其反转后的字符串中也出现。

如果存在这样的子字符串,返回 true;如果不存在,返回 false 。

示例 1:

输入:s = "leetcode"
输出:true
解释:子字符串 "ee" 的长度为 2,它也出现在 reverse(s) == "edocteel" 中。

示例 2:

输入:s = "abcba"
输出:true
解释:所有长度为 2 的子字符串 "ab"、"bc"、"cb"、"ba" 也都出现在 reverse(s) == "abcba" 中。

示例 3:

输入:s = "abcd"
输出:false
解释:字符串 s 中不存在满足「在其反转后的字符串中也出现」且长度为 2 的子字符串。

说明:

  • 1 <= s.length <= 100
  • 字符串 s 仅由小写英文字母组成。

思路

判断字符串 s 中长度为 2 的子串是否在其反转后的字符串中出现,返回 truefalse

直接的想法是将 s 中所有长度为 2 的子串放入 hashset,然后判断倒序字符串的长度为 2 的子串是否在集合中。

网友题解使用 int[] 记录所有出现过的长度为 2 的子串,下标表示第一个字母,第二个字母则使用 int 值的 bit 位表示。

代码


/**
 * @date 2024-12-26 8:47
 */
public class IsSubstringPresent3083 {

    public boolean isSubstringPresent(String s) {
        int n = s.length();
        int[] exists = new int[26];
        for (int i = 0; i < n - 1; i++) {
            int a = s.charAt(i) - 'a';
            int b = s.charAt(i + 1) - 'a';
            exists[a] |= 1 << b;
            if ((exists[b] >> a & 1) == 1) {
                return true;
            }
        }
        return false;
    }

}

性能

3285.找到稳定山的下标

目标

有 n 座山排成一列,每座山都有一个高度。给你一个整数数组 height ,其中 height[i] 表示第 i 座山的高度,再给你一个整数 threshold 。

对于下标不为 0 的一座山,如果它左侧相邻的山的高度 严格大于 threshold ,那么我们称它是 稳定 的。我们定义下标为 0 的山 不是 稳定的。

请你返回一个数组,包含所有 稳定 山的下标,你可以以 任意 顺序返回下标数组。

示例 1:

输入:height = [1,2,3,4,5], threshold = 2
输出:[3,4]
解释:
下标为 3 的山是稳定的,因为 height[2] == 3 大于 threshold == 2 。
下标为 4 的山是稳定的,因为 height[3] == 4 大于 threshold == 2.

示例 2:

输入:height = [10,1,10,1,10], threshold = 3
输出:[1,3]

示例 3:

输入:height = [10,1,10,1,10], threshold = 10
输出:[]

说明:

  • 2 <= n == height.length <= 100
  • 1 <= height[i] <= 100
  • 1 <= threshold <= 100

思路

返回数组的稳定下标,如果一个元素的左侧相邻元素严格大于 threshold 称当前元素是稳定的。

代码


/**
 * @date 2024-12-19 21:50
 */
public class StableMountains3285 {

    public List<Integer> stableMountains(int[] height, int threshold) {
        List<Integer> res = new ArrayList<>();
        int prev = height[0];
        int n = height.length;
        for (int i = 1; i < n; i++) {
            if (prev > threshold) {
                res.add(i);
            }
            prev = height[i];
        }
        return res;
    }
}

性能

3264.K次乘运算后的最终数组I

目标

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

你需要对 nums 执行 k 次操作,每次操作中:

  • 找到 nums 中的 最小 值 x ,如果存在多个最小值,选择最 前面 的一个。
  • 将 x 替换为 x * multiplier 。

请你返回执行完 k 次乘运算之后,最终的 nums 数组。

示例 1:

输入:nums = [2,1,3,5,6], k = 5, multiplier = 2
输出:[8,4,6,5,6]
解释:
操作 结果
1 次操作后 [2, 2, 3, 5, 6]
2 次操作后 [4, 2, 3, 5, 6]
3 次操作后 [4, 4, 3, 5, 6]
4 次操作后 [4, 4, 6, 5, 6]
5 次操作后 [8, 4, 6, 5, 6]

示例 2:

输入:nums = [1,2], k = 3, multiplier = 4
输出:[16,8]
解释:
操作 结果
1 次操作后 [4, 2]
2 次操作后 [4, 8]
3 次操作后 [16, 8]

说明:

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

思路

有一个数组 nums,我们需要执行 k 次操作,每次操作选择数组中最小元素 min,并将它的值替换为 min * multiplier,返回最终的数组。

使用最小堆,堆中元素为 [value, index],获取堆顶元素,将其值乘以 multiplier 再放回堆中,操作完 k 次之后,遍历堆中元素,根据 index 重写 nums 即可。需要注意处理值相等的情况,堆排序不稳定。

代码


/**
 * @date 2024-12-13 2:13
 */
public class GetFinalState3264 {

    public int[] getFinalState(int[] nums, int k, int multiplier) {
        int n = nums.length;
        // 注意这里需要处理相等的情况,堆排序是不稳定的
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> {
            int compare = nums[a] - nums[b];
            if (compare != 0){
                return compare;
            }
            return a - b;
        });
        for (int i = 0; i < n; i++) {
            q.offer(i);
        }
        for (int i = 0; i < k; i++) {
            int index = q.poll();
            nums[index] *= multiplier;
            q.offer(index);
        }
        return nums;
    }
}

性能

2717.半有序排列

目标

给你一个下标从 0 开始、长度为 n 的整数排列 nums 。

如果排列的第一个数字等于 1 且最后一个数字等于 n ,则称其为 半有序排列 。你可以执行多次下述操作,直到将 nums 变成一个 半有序排列 :

  • 选择 nums 中相邻的两个元素,然后交换它们。

返回使 nums 变成 半有序排列 所需的最小操作次数。

排列 是一个长度为 n 的整数序列,其中包含从 1 到 n 的每个数字恰好一次。

示例 1:

输入:nums = [2,1,4,3]
输出:2
解释:可以依次执行下述操作得到半有序排列:
1 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
2 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明,要让 nums 成为半有序排列,不存在执行操作少于 2 次的方案。

示例 2:

输入:nums = [2,4,1,3]
输出:3
解释:
可以依次执行下述操作得到半有序排列:
1 - 交换下标 1 和下标 2 对应元素。排列变为 [2,1,4,3] 。
2 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
3 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明,要让 nums 成为半有序排列,不存在执行操作少于 3 次的方案。

示例 3:

输入:nums = [1,3,4,2,5]
输出:0
解释:这个排列已经是一个半有序排列,无需执行任何操作。

说明:

  • 2 <= nums.length == n <= 50
  • 1 <= nums[i] <= 50
  • nums 是一个 排列

思路

有一个数组 nums,求将最小值移动到第一个位置,最大值移动到最后一个位置需要的最小操作次数。

我们可以记录数组中第一个出现的最小值以及最后一个出现的最大值的下标,记为 minIndexmaxIndex,如果 minIndex > maxIndex,最少交换次数为 minIndex + n - maxIndex - 2,否则为 minIndex + n - maxIndex - 1

注意:交换次数等于 minIndex 前面的元素个数 加上 maxIndex 后面的元素个数,如果 minIndex > maxIndex,当我们将最小值放到第一个位置时,maxIndex 已经向后移了一位。

代码


/**
 * @date 2024-12-11 8:47
 */
public class SemiOrderedPermutation2717 {

    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length;
        int minIndex = 0;
        int maxIndex = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            } else if (nums[i] >= nums[maxIndex]) {
                maxIndex = i;
            }
        }
        int res = minIndex + n - maxIndex - 1;
        return minIndex > maxIndex ? res - 1 : res;
    }
}

性能

1812.判断国际象棋棋盘中一个格子的颜色

目标

给你一个坐标 coordinates ,它是一个字符串,表示国际象棋棋盘中一个格子的坐标。下图是国际象棋棋盘示意图。

如果所给格子的颜色是白色,请你返回 true,如果是黑色,请返回 false 。

给定坐标一定代表国际象棋棋盘上一个存在的格子。坐标第一个字符是字母,第二个字符是数字。

示例 1:

输入:coordinates = "a1"
输出:false
解释:如上图棋盘所示,"a1" 坐标的格子是黑色的,所以返回 false 。

示例 2:

输入:coordinates = "h3"
输出:true
解释:如上图棋盘所示,"h3" 坐标的格子是白色的,所以返回 true 。

示例 3:

输入:coordinates = "c7"
输出:false

提示:

  • coordinates.length == 2
  • 'a' <= coordinates[0] <= 'h'
  • '1' <= coordinates[1] <= '8'

思路

有一个 8 x 8 的棋盘,行编号为 1 ~ 8,列编号为 a ~ h,给定一个坐标比如 c3,如果格子为白色返回 true,黑色返回 false

经过观察,奇数行奇数列,偶数行偶数列为黑色,偶数行奇数列,奇数行偶数列为白色。我们只需判断横纵坐标之和是否为奇数即可。

需要注意的是,将字符串映射为下标数字 0 ~ 7,并不影响上面的判断。

代码


/**
 * @date 2024-12-09 0:11
 */
public class SquareIsWhite1812 {

    public boolean squareIsWhite(String coordinates) {
        int x = coordinates.charAt(0) - '1';
        int y = coordinates.charAt(1) - 'a';
        return (x + y) % 2 == 1;
    }
}

性能