LeetCode 1405. 最长快乐字符串

Categories:

题目描述
思路分析
1. 解法一：最大堆贪心（推荐）
相似题目

题目描述

✅ 1405. 最长快乐字符串

思路分析

解法一：最大堆贪心（推荐）

核心思路：

使用最大堆保存剩余数量最多的字符。

每次取堆顶字符，若会形成三连，则取第二大字符。

用完后将更新后的计数重新入堆。

复杂度分析：

时间复杂度：O(n log 3) = O(n)。

空间复杂度：O(1)。

import java.util.PriorityQueue;

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> y[0] - x[0]);
        if (a > 0) {
            pq.offer(new int[] {a, 'a'});
        }
        if (b > 0) {
            pq.offer(new int[] {b, 'b'});
        }
        if (c > 0) {
            pq.offer(new int[] {c, 'c'});
        }

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            int n = sb.length();
            if (n >= 2 && sb.charAt(n - 1) == first[1] && sb.charAt(n - 2) == first[1]) {
                if (pq.isEmpty()) {
                    break;
                }
                int[] second = pq.poll();
                sb.append((char) second[1]);
                second[0]--;
                if (second[0] > 0) {
                    pq.offer(second);
                }
                pq.offer(first);
            } else {
                sb.append((char) first[1]);
                first[0]--;
                if (first[0] > 0) {
                    pq.offer(first);
                }
            }
        }
        return sb.toString();
    }
}

import "container/heap"

type Item struct {
    cnt int
    ch  byte
}

type MaxHeap []Item

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].cnt > h[j].cnt }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func longestDiverseString(a int, b int, c int) string {
    h := &MaxHeap{}
    if a > 0 {
        heap.Push(h, Item{cnt: a, ch: 'a'})
    }
    if b > 0 {
        heap.Push(h, Item{cnt: b, ch: 'b'})
    }
    if c > 0 {
        heap.Push(h, Item{cnt: c, ch: 'c'})
    }

    res := make([]byte, 0)
    for h.Len() > 0 {
        first := heap.Pop(h).(Item)
        n := len(res)
        if n >= 2 && res[n-1] == first.ch && res[n-2] == first.ch {
            if h.Len() == 0 {
                break
            }
            second := heap.Pop(h).(Item)
            res = append(res, second.ch)
            second.cnt--
            if second.cnt > 0 {
                heap.Push(h, second)
            }
            heap.Push(h, first)
        } else {
            res = append(res, first.ch)
            first.cnt--
            if first.cnt > 0 {
                heap.Push(h, first)
            }
        }
    }
    return string(res)
}

相似题目

题目	难度	考察点
767. 重构字符串	中等	贪心、堆
1054. 距离相等的条形码	中等	贪心、堆
984. 不含 AAA 或 BBB 的字符串	中等	贪心
621. 任务调度器	中等	贪心
1673. 找出最具竞争力的子序列	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/22641477