完成所有任务最少初始能量值
public int minimumEffort(int[][] tasks){
Arrays.sort(tasks,(a,b)->(a[0]-a[1])-(b[0]-b[1]));
int res=0;
int sum=0;
for(int i=0;i<tasks.length;i++){
res=Math.max(res,sum+tasks[i][1]);
sum+=tasks[i][0];
}
return res;
}
雇佣k名工人的最低成本
雇佣k名工人的最低成本
通过将对应的单位成本(wage[i]/quality[i])进行排序
对于每一个单位成本,小于该单位成本的都可以达到期望薪资,大于该单位成本的员工都不能达到期望薪资
每次都通过小于该单位成本员工进行结果更新,通过大根堆维护更大的成本删除
单位成本d*(quality[i]+quality[i+1]+....+quality[i+k-1])
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
int n=quality.length;
int[][] workers=new int[n][2];
for(int i=0;i<n;i++){
workers[i]=new int[]{wage[i],quality[i]};
}
Arrays.sort(workers,(a, b)->a[0]*b[1]-a[1]*b[0]);
double res=1e9;
int sum=0;
PriorityQueue<Integer> queue=new PriorityQueue<Integer>((a,b)->b-a);
for(int i=0;i<n;i++){
queue.offer(workers[i][1]);
sum+=workers[i][1];
if(queue.size()>k){
sum-=queue.poll();
}
if(queue.size()==k){
res=Math.min(res,sum*(1d*workers[i][0]/workers[i][1]));
}
}
return res;
}
}
会议安排
会议安排
按照技术时间进行贪心,优先选择结束时间早的会议
class Solution {
public int maxEvents(int[][] events) {
//将所有的会议按开始时间排序
Arrays.sort(events,(a,b)->a[0]-b[0]);
PriorityQueue<Integer> queue=new PriorityQueue<>();
//当前时间
int last=1;int res=0;int i=0;int n=events.length;
while(i<n||!queue.isEmpty()){
//将开始时间相同贪心
while(i<n&&events[i][0]==last){
queue.offer(events[i++][1]);
}
//对于不能参加会议
while(!queue.isEmpty()&&queue.peek()<last){
queue.poll();
}
if (!queue.isEmpty()) {
queue.poll();
res++;
}
last++;
}
return res;
}
}
两地调度
两地调度
现将所有的人安排到一个地方,在进行n个人转移,转移的排序关键字,即代价差值
class Solution {
public int twoCitySchedCost(int[][] costs) {
//排序关键字为飞往不同城市代价差值
Arrays.sort(costs,(a,b)->a[0]-a[1]-(b[0]-b[1]));//从小到大进行排序
int n=costs.length/2;
int res=0;
for(int i=0;i<n;i++){
res+=costs[i][0]+costs[i+n][1];
}
return res;
}
}
划分数组为连续数字的集合
class Solution {
public boolean isPossibleDivide(int[] nums, int k) {
int n=nums.length;
if(n%k!=0){
return false;
}
Arrays.sort(nums);
Map<Integer,Integer> cnt=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
cnt.put(nums[i],cnt.getOrDefault(nums[i],0)+1);
}
for(int i=0;i<n;i++){
if(!cnt.containsKey(nums[i])){
continue;
}
for(int j=0;j<k;j++){
int num=nums[i]+j;
if(!cnt.containsKey(num)){
return false;
}
//将计数减一
cnt.put(num,cnt.getOrDefault(num,0)-1);
if(cnt.get(num)==0){
cnt.remove(num);
}
}
}
return true;
}
}
可以到达的最远建筑
可以到达的最远建筑
每次将砖头使用,直到砖头的数量小于0,与之前使用最多的砖头进行交换
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
int n=heights.length;
PriorityQueue<Integer> queue=new PriorityQueue<Integer>((a,b)->b-a);
for(int i=0;i+1<n;i++){
int height=heights[i+1]-heights[i];
if(height>0){
bricks-=height;
queue.offer(height);
if(bricks<0){
if(ladders>0){
ladders--;
bricks+=queue.poll();
}else{
return i;
}
}
}
}
return n-1;
}
}
删除子字符串的最大的分
class Solution {
public int maximumGain(String s,int x,int y){
//优先删除ab
if(x<y){
//交换
int t=x;
x=y;
y=t;
s=swap(s);
}
int n=s.length();
int i=0;
int res=0;
while(i<n){
//如果对应的字符不是a,b直接跳过
while(i<n&&s.charAt(i)!='a'&&s.charAt(i)!='b'){
i++;
}
//进行计数
int cnt_a=0;int cnt_b=0;
while(i<n&&(s.charAt(i)=='a'||s.charAt(i)=='b')){
if(s.charAt(i)=='a'){
cnt_a++;
}else{
if(cnt_a>0){
cnt_a--;
res+=x;
}else{
cnt_b++;
}
}
i++;
}
//对于剩下的ba进行删除
res+=Math.min(cnt_a,cnt_b)*y;
}
return res;
}
public String swap(String s){
StringBuilder sb=new StringBuilder(s);
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='a'){
sb.setCharAt(i,'b');
}else if(s.charAt(i)=='b'){
sb.setCharAt(i,'a');
}
}
return new String(sb);
}
}
方式二
通过栈维护字符串的匹配删除
class Solution {
public int maximumGain(String s,int x,int y){
if(x<y){
//交换
int t=x;
x=y;
y=t;
s=swap(s);
}
int res=0;
Stack<Character> stack01=new Stack<Character>();
Stack<Character> stack02=new Stack<Character>();
for(int i=0;i<s.length();i++){
if(s.charAt(i)!='b'){
stack01.push(s.charAt(i));
}else {
if(!stack01.isEmpty()&&stack01.peek()=='a'){
stack01.pop();
res+=x;
}else{
stack01.push(s.charAt(i));
}
}
}
//将剩下的元素进行处理
while (!stack01.isEmpty()) {
char ch=stack01.pop();
if(ch!='b'){
stack02.push(ch);
}else{
if (!stack02.isEmpty()&&stack02.peek()=='a') {
stack02.pop();
res+=y;
}else{
stack02.push(ch);
}
}
}
return res;
}
public String swap(String s){
StringBuilder sb=new StringBuilder(s);
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='a'){
sb.setCharAt(i,'b');
}else if(s.charAt(i)=='b'){
sb.setCharAt(i,'a');
}
}
return new String(sb);
}
}
距离相等的条形码
距离相等的条形码
贪心,出现次数最多的最可能相邻,所以优先将出现频率最多的元素安排
初始每一次从堆中取一个元素,将该元素放入结果集合中,如果初始时候结果集中没有元素直接堆顶出现次数最多的元素安排,如果对顶元素依然出现次数最多,之前安排过,将一个出现次数此多的元素取出堆,放完之后将出现最多和次多的元素重新放回堆中
class Solution {
public int[] rearrangeBarcodes(int[] barcodes){
//将所有的元素放入堆中
PriorityQueue<Item> queue=new PriorityQueue<Item>((a,b)->b.freq-a.freq);
//将所有的元素统计频率
int[] cnt=new int[10010];
for(int i=0;i<barcodes.length;i++){
cnt[barcodes[i]]++;
}
for(int i=0;i<cnt.length;i++){
if(cnt[i]!=0){
queue.offer(new Item(i,cnt[i]));
}
}
int[] res=new int[barcodes.length];
int index=0;
while (!queue.isEmpty()) {
Item node=queue.poll();
if(index==0||res[index-1]!=node.value){
res[index++]=node.value;
if(--node.freq!=0){
queue.offer(new Item(node.value, node.freq));
}
}else{
Item newNode=queue.poll();
res[index++]=newNode.value;
if(--newNode.freq!=0){
queue.offer(new Item(newNode.value,newNode.freq));
}
queue.offer(new Item(node.value,node.freq));
}
}
return res;
}
}
class Item{
int value;
int freq;
public Item(int value,int freq){
this.value=value;
this.freq=freq;
}
}
受标签影响的最大值
class Solution {
public int largestValsFromLabels(int[] values,int[] labels,int numWanted,int useLimit){
//通过优先队列进行排列
PriorityQueue<Info> queue=new PriorityQueue<Info>((a,b)->b.value-a.value);
//将所有的数据封装对应的数据和标签
for(int i=0;i< values.length;i++){
queue.offer(new Info(values[i],labels[i]));
}
//对于所有的标签
Arrays.sort(labels);
int[] limit=new int[labels[labels.length-1]+1];
//将所有的元素数量设置为useLimit
Arrays.fill(limit,useLimit);
int ans=0;
while(!queue.isEmpty()&&numWanted>0){
Info node=queue.poll();
if(limit[node.label]>0){
ans+=node.value;
numWanted--;
limit[node.label]--;
}
}
return ans;
}
}
class Info{
int value;
int label;
public Info(int value,int label){
this.value=value;
this.label=label;
}
}
使绳子变成彩色的最短时间
使绳子变成彩色的最短时间
对于所有的相邻的颜色的球,将所有的小于最大值的所有的求进行累加即可 将最大的求留下来即可
class Solution {
public int minCost(String colors, int[] neededTime) {
//贪心,每次移除花费时间最少的
int res=0;
int i=0;
int n=colors.length();
while(i<n){
//对于
char ch=colors.charAt(i);
int sum=0;
int maxTime=0;
while(i<n&&colors.charAt(i)==ch){
sum+=neededTime[i];
maxTime=Math.max(maxTime,neededTime[i]);
i++;
}
res+=sum-maxTime;
}
return res;
}
}
从房屋收集雨水需要的最少的水桶数
最少的水桶数
从左往右进行遍历,对于房屋,如果有便可以放置空桶,优先将空桶放到右边,如果右边不能放空桶,将空桶尝试放置在左边,如果左边不能放,当前房屋不能满足要求
class Solution {
public int minimumBuckets(String street) {
//通过贪心策略优先在右侧放置空桶
int ans=0;
int n=street.length();
for(int i=0;i<street.length();i++){
if(street.charAt(i)=='H'){
if(i+1<n&&street.charAt(i+1)=='.'){
ans++;
i=i+2;
}else if(i-1>=0&&street.charAt(i-1)=='.'){
ans++;
}else{
return -1;
}
}
}
return ans;
}
}
给定行和列的和求一个可行矩阵
class Solution {
public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
int n=rowSum.length;
int m=colSum.length;
int[][] res=new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
res[i][j]=Math.min(rowSum[i],colSum[j]);
rowSum[i]-=res[i][j];
colSum[j]-=res[i][j];
}
}
return res;
}
}
重构两行二进制矩阵
重构两行二进制矩阵
两行,只有对于列和为1的分配不一致,可以优先将1放在第一行
class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
List<List<Integer>> res=new ArrayList<>();
int n=colsum.length;
int sum=0;//记录所有的列和
for(int i=0;i<n;i++){
if(colsum[i]==2){
upper--;
lower--;
}else if(colsum[i]==1){
//待定
sum++;
}
}
if(upper+lower!=sum||upper<0||lower<0){
return res;
}
List<Integer> row1=new ArrayList<>();
List<Integer> row2=new ArrayList<>();
for(int i=0;i<n;i++){
if(colsum[i]==2){
row1.add(1);
row2.add(1);
}else if(colsum[i]==0){
row1.add(0);
row2.add(0);
}else{
if(--upper>=0){
row1.add(1);
row2.add(0);
}else{
row1.add(0);
row2.add(1);
}
}
}
res.add(row1);
res.add(row2);
return res;
}
}