欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-04 17:26:27
...

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


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


这个还是挺容易想到的,相同字母不相邻,那就将相同的字母每隔一个位置放一个。首先要放的是出现次数最多的,从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);
    }
}

 

相关标签: java练习 leetcode