力扣第256场周赛_比较器力扣例题

力扣第256场周赛前两题解析

链接: 个人站点.

经过今天上午的周赛，如此惨淡的成绩，令我思考自己的思维方式。对于与数学思考方式相近的算法题，需要多加关注。

力扣周赛

• 学生分数的最小差值

说实话，初见此题，笔者并没有良好审题，一度以为是返回最高分与最低分的差值。所以笔者尝试多次无果后，就跳过开始了下一题。回来的时候，明白了题目的含义，k大小的区间、最大最小值的差值最小。

但是笔者没有很好的抓住题目核心，一直想不明白怎么获得k区间，然后对不同区间的最小值进行比较，实际思路错了。

我们对数组首先进行排序，然后从第一个开始，用这第一个的后k个数减去第一个，是不是得到了一个k区间的差值，那么滑动这个k区间，即为从下一个开始，每个差值都为第i+k个减去第i个数值，同时每次进行比较，留下最小的差值。（***无需担心滑动窗口以外存在的区间，排序后，滑动窗口以外的区间的差值一定大于窗口内的。***）

解题思路：排序+滑动窗口

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for(int i = 0;(i + k - 1) < nums.length;i++){
            ans = Math.min((nums[i+k-1] - nums[i]),ans);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10

• 找出数组中的第K大整数

笔者见此题的第一直觉是将字符串转为数字进行储存，排序后，返回第K大的整数。

class Solution {
    public String kthLargestNumber(String[] nums, int k) {
        int temp = 0;
        int[] ans = new int[nums.length];
        for(int i = 0;i < nums.length;i++){
            ans[i] = (Integer.parseInt(nums[i]));
        }
        Arrays.sort(ans);
        for(int i = ans.length;k>0;k--,i--){
            temp = i;
        }
        return String.valueOf(ans[temp-1]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

可是出现了数据溢出。

所以将数据类型扩大至Long。

class Solution {
    public String kthLargestNumber(String[] nums, int k) {
        int temp = 0;
        long[] ans = new long[nums.length];
        for(int i = 0;i < nums.length;i++){
            ans[i] = (Long.parseLong(nums[i]));
        }
        Arrays.sort(ans);
        for(int i = ans.length;k>0;k--,i--){
            temp = i;
        }
        return String.valueOf(ans[temp-1]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

结果依然溢出，这时候看了一下数据范围，数位有100位，10的100次方……

这肯定不能转换。可是笔者忘记了利用Comparator接口的对象比较属性，这题也直接gg。

• Compatorator的使用方法

  • 一个实现了Comparator接口的类，被称作比较器。

  • 比较器中有一个compare(object o1,object o2)方法，对两个参数对象自定义比较方法。例如o1与o2进行比较。

    • 返回大于0的数代表o1 > o2
    • 返回小于0的数代表o1 < o2
    • 返回等于0的数代表o1 = 02

  • 通过在排序方法中建立新的比较器对象进行排序。

    Arrays.sort(数组名,new 比较器());
    1

知道了比较器的用法，该题迎刃而解。

class Solution {
    public String kthLargestNumber(String[] nums, int k) {
        Arrays.sort(nums,new cmp());
        return nums[nums.length - k];
    }

    class cmp implements Comparator<String>{
        public int compare(String o1,String o2){
            return o1.length() == o2.length() ? o1.compareTo(o2) : o1.length() - o2.length();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

笔者实力有限，最后两题不予解析。

---

2020.8.29