(LeetCode)621. 任务调度器+字符串数组重排序

看到题目的瞬间想到了前几天做的一个类似的题目,记不太清题目了,大概题意是:将字符串数组重排序,相同的字母不能相邻。
然后细细的读了一遍题目之后发现这两道题的差别还是很大的。


将字符串数组重排序,相同的字母不能相邻


这个还是挺容易想到的,相同字母不相邻,那就将相同的字母每隔一个位置放一个。首先要放的是出现次数最多的,从0开始隔一个放一个(如果超过了数组的长度,那么就说明没法完成题目的要求)。然后按出现的次数从大到小依次放置。
(这道题是周二的每日一题。周二记得吧~~人工智能期末+隔天c++期末,所以只想了想思路QAQ)



任务调度器


今天早早地爬来了中厅,然鹅有一撮人在高声讨论峰岚,导致我的心思丝毫不在题目上,题目读了好几遍才懂(幸好有他们帮我背锅,才不是因为我没睡醒hiahiahia)

刚看完这道题就觉得与上面的题有些类似,然后就想往上面那道题上靠,觉得无非就是在相同字母之间的距离上加了个限制呗,然后开始推。

把出现次数最多的元素先按距离等于n(这个距离可以扩充)放好。

 (LeetCode)621. 任务调度器+字符串数组重排序

类似上图,此时n=4。除去最后一行的空位不确定外,其余的空位即使没有填入数据,也依然需要计入计数。当然每行也可以扩容空位。

①相同的元素放入不同的行中。因为第一列是出现次数最多的元素,所以后面的每个元素都能够放入不同行中。

②不同的元素在满足①的条件下优先填空位,然后才是选择扩充。

到现在我们可以把公式写出来了。

到此为止是我想到的,然后代码写出来,运行,结果错误。

百思不得其解

从头顺了一遍流程后没发现什么问题,然后直奔讨论区……

在这里我遇到了跟我一样读了好几遍题的同学hahah

然后发现我的公式没有问题,是这个公式没有考虑到扩充和最后一行空位的问题……

于是改进了一下(请忽略草草写的快排)

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        Arrays.fill(count,0);
        for(int i = 0;i < tasks.length;i++){
            count[tasks[i]-65]++;
        }
        //Arrays.sort(count);
        QuickSort(count,0,count.length-1);
        int num = 1;
        for(int i = 24;i>=0;i--){
            if(count[i]==count[25]){
                num++;
            }else{
                break;
            }
        }
        return Math.max(num+(count[25]-1)*(n+1),tasks.length);
    }
    public void QuickSort(int[] array,int begin,int end){
        if(begin>=end){
            return;
        }
        int i = begin;
        int j = end;
        int mid = (i+j)/2;
        int num = array[i];
        while(i<j){
            while(j>i && array[j] >= num){
                j--;
            }
            if(i<j){
                array[i] = array[j];
                i++;
            }
            while(i<j && array[i] < num){
                i++;
            }
            if(i<j){
                array[j] = array[i];
                j--;
            }
        }
        array[i] = num;
        QuickSort(array,begin,i-1);
        QuickSort(array,i+1,end);
    }
}

 

上一篇:python全栈第二十四天


下一篇:《编写高效的 PyTorch 代码技巧》