看到题目的瞬间想到了前几天做的一个类似的题目,记不太清题目了,大概题意是:将字符串数组重排序,相同的字母不能相邻。
然后细细的读了一遍题目之后发现这两道题的差别还是很大的。
将字符串数组重排序,相同的字母不能相邻
这个还是挺容易想到的,相同字母不相邻,那就将相同的字母每隔一个位置放一个。首先要放的是出现次数最多的,从0开始隔一个放一个(如果超过了数组的长度,那么就说明没法完成题目的要求)。然后按出现的次数从大到小依次放置。
(这道题是周二的每日一题。周二记得吧~~人工智能期末+隔天c++期末,所以只想了想思路QAQ)
任务调度器
今天早早地爬来了中厅,然鹅有一撮人在高声讨论峰岚,导致我的心思丝毫不在题目上,题目读了好几遍才懂(幸好有他们帮我背锅,才不是因为我没睡醒hiahiahia)
刚看完这道题就觉得与上面的题有些类似,然后就想往上面那道题上靠,觉得无非就是在相同字母之间的距离上加了个限制呗,然后开始推。
把出现次数最多的元素先按距离等于n(这个距离可以扩充)放好。
类似上图,此时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);
}
}