第71场 双周赛补题

第一题 2160. 拆分数位后四位数字的最小和

题目

思路

首先我们知道,两个两位数相加一般来说都是比一个一位数加上一个三位数来的小的。所以这里我们只需要把这四个数变成两个两位数即可,这样我们只需要把这两个两位数的十位为最小的两个数,然后剩下的两个数作为百位即可。

  • 2932 --拆分->[2, 9, 3, 2] --排序--> [2, 2, 3 ,9] --重组-> [2, 3] + [2, 9] = 52
class Solution {
    public int minimumSum(int num) {
        int[] nums = new int[4];
        int cnt = 0;
        while(num > 0) {
            int remind = num % 10;
            num /= 10;
            nums[cnt++] = remind;
        }
        Arrays.sort(nums);
        return nums[0]*10 + nums[1] * 10 + nums[2] + nums[3];
    }
}

第二题 2161. 根据给定数字划分数组

题目

思路

一开始我想用快速排序的思路写的,然后xjb写了一通不太对,然后干脆就暴力一点开三个数组,一个存比Pivot小的叫做left[], 比pivot大的叫做right[], 和Pivot一样大的叫做mid[],然后把他们合并,复杂度应该是O(N)

代码

class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        int posl = 0;
        int posr = 0;
        int posm = 0;
        int n = nums.length;
        int[] l = new int[n];
        int[] r = new int[n];
        int[] m = new int[n];
        for (int num : nums) {
            if (num < pivot) {
                l[posl++] = num;
            } else if (num > pivot) {
                r[posr++] = num;
            } else {
                m[posm++] = num;
            }
        }
        int cnt = 0;
        for (int i = 0; i < posl; i++) {
            nums[cnt++] = l[i];
        }
        for (int i = 0; i < posm; i++) {
            nums[cnt++] = m[i];
        }
        for (int i = 0; i < posr; i++) {
            nums[cnt++] = r[i];
        }
        return nums;
    }
}

第三题 2162. 设置时间的最少代价

题目

这题读题有点难受,我看了一些别人的理解才想清楚是怎么回事。

看了一下才理解,startAt就是初始数字是多少,move就是换数字,push就是确定键。 然后就能理解下面的行为。

- 1 0 0 0 ,表示 10 分 0 秒。
  手指一开始就在数字 1 处,输入 1 (代价为 1),移到 0 处(代价为 2),输入 0(代价为 1),输入 0(代价为 1),输入 0(代价为 1)。
  总代价为:1 + 2 + 1 + 1 + 1 = 6 。这是所有方案中的最小代价。

思路

这题读懂题后我们知道如果前导为0的话我们直接不用管前面的0,比如输入 0 0 0 8 (四个数字),表示 08 秒。所以只用设定8秒就行。当然这里我们要考虑两种情况,就是后面的秒大于60和小于60的情况,我们只需要考虑(分钟数,秒数)(分钟数-1, 秒数+60)两种情况,并且判断分钟数和秒数是否合法即可。我们以startAt = 1, , moveCost = 2, pushCost = 1, targetSeconds = 600为例子,我们计算第一种情况下的数据(minutes=10, seconds=00),我们的startAt1所以我们不需要移动只需要执行push即可,所以ansCost += pushCost,然后我们发现当前为0, 0 != 1所以移动一位有ansCost += moveCost, 这时候我们需要更新下当前的startAt = now.

代码

class Solution {
   public int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        // case 1
        int minute = targetSeconds / 60;
        int second = targetSeconds % 60;
        int ans1 = minCostTime(startAt, moveCost, pushCost, minute, second);
        int ans2 = minCostTime(startAt, moveCost, pushCost, minute-1, second+60);
        return Math.min(ans1, ans2);
    }

    public int minCostTime(int startAt, int moveCost, int pushCost, int minute, int second) {
        if (minute > 99 || minute < 0 || second > 99) {
            return Integer.MAX_VALUE;
        }
        // section1 60秒的情况
        int[] nums = new int[4];
        nums[0] = minute/10;
        nums[1] = minute%10;
        nums[2] = second/10;
        nums[3] = second%10;
        int cnt = 0;
        while (cnt  < 4 && nums[cnt] == 0) {
            cnt++;
        }
        int ansCost = 0;
        int prev = startAt;
        for (int i = cnt; i < 4; i++) {
            int d = nums[i];
            if (d != prev) {
                prev = d;
                ansCost += moveCost;
            }
            ansCost += pushCost;
        }
        return ansCost;
    }
}
最后修改:2022 年 03 月 04 日
如果觉得我的文章对你有用,请随意赞赏