LeetCode 767. 重构字符串

Categories:

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

题目描述

✅ 767. 重构字符串

思路分析

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

核心思路：

统计每个字符频次，若最大频次超过 (n + 1) / 2 则无法重构。

使用大根堆每次取出频次最高的两个字符交替放入结果。

频次减一后若仍有剩余则放回堆中。

复杂度分析：

时间复杂度：O(n log σ)，其中 n 表示字符串长度，σ 表示字符集大小。

空间复杂度：O(σ)，存储字符频次与堆。

class Solution {
    public String reorganizeString(String s) {
        int[] cnt = new int[26];
        int max = 0;
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
            max = Math.max(max, cnt[c - 'a']);
        }

        if (max > (s.length() + 1) / 2) {
            return "";
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) {
                pq.offer(new int[]{i, cnt[i]});
            }
        }

        StringBuilder sb = new StringBuilder();

        // 每次取出频次最高的两个字符
        while (pq.size() >= 2) {
            int[] a = pq.poll();
            int[] b = pq.poll();

            sb.append((char) ('a' + a[0]));
            sb.append((char) ('a' + b[0]));

            if (--a[1] > 0) {
                pq.offer(a);
            }
            if (--b[1] > 0) {
                pq.offer(b);
            }
        }

        if (!pq.isEmpty()) {
            sb.append((char) ('a' + pq.poll()[0]));
        }

        return sb.toString();
    }
}

func reorganizeString(s string) string {
	cnt := make([]int, 26)
	maxCnt := 0
	for i := 0; i < len(s); i++ {
		idx := int(s[i] - 'a')
		cnt[idx]++
		if cnt[idx] > maxCnt {
			maxCnt = cnt[idx]
		}
	}

	if maxCnt > (len(s)+1)/2 {
		return ""
	}

	h := &CharHeap{}
	heap.Init(h)
	for i := 0; i < 26; i++ {
		if cnt[i] > 0 {
			heap.Push(h, Pair{idx: i, cnt: cnt[i]})
		}
	}

	res := make([]byte, 0, len(s))

	// 每次取出频次最高的两个字符
	for h.Len() >= 2 {
		a := heap.Pop(h).(Pair)
		b := heap.Pop(h).(Pair)

		res = append(res, byte('a'+a.idx))
		res = append(res, byte('a'+b.idx))

		a.cnt--
		b.cnt--
		if a.cnt > 0 {
			heap.Push(h, a)
		}
		if b.cnt > 0 {
			heap.Push(h, b)
		}
	}

	if h.Len() == 1 {
		last := heap.Pop(h).(Pair)
		res = append(res, byte('a'+last.idx))
	}

	return string(res)
}

type Pair struct {
	idx int
	cnt int
}

type CharHeap []Pair

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

相似题目

题目	难度	考察点
621. 任务调度器	中等	贪心 + 堆
1054. 距离相等的条形码	中等	贪心
767. 重构字符串	中等	贪心
451. 根据字符出现频率排序	中等	计数
692. 前 K 个高频单词	中等	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/93774079