列表

详情

100249. 替换字符串中的问号使分数最小

给你一个字符串 s 。s[i] 要么是小写英文字母，要么是问号 '?' 。

对于长度为 m 且 只 含有小写英文字母的字符串 t ，我们定义函数 cost(i) 为下标 i 之前（也就是范围 [0, i - 1] 中）出现过与 t[i] 相同 字符出现的次数。

字符串 t 的 分数 为所有下标 i 的 cost(i) 之 和 。

比方说，字符串 t = "aab" ：

你的任务是用小写英文字母 替换 s 中 所有 问号，使 s 的 分数最小 。

请你返回替换所有问号 '?' 之后且分数最小的字符串。如果有多个字符串的 分数最小 ，那么返回字典序最小的一个。

 

示例 1：

输入：s = "???"

输出： "abc"

解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abc" 。

对于字符串 "abc" ，cost(0) = 0 ，cost(1) = 0 和 cost(2) = 0 。

"abc" 的分数为 0 。

其他修改 s 得到分数 0 的字符串为 "cba" ，"abz" 和 "hey" 。

这些字符串中，我们返回字典序最小的。

示例 2：

输入： s = "a?a?"

输出： "abac"

解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abac" 。

对于字符串 "abac" ，cost(0) = 0 ，cost(1) = 0 ，cost(2) = 1 和 cost(3) = 0 。

"abac" 的分数为 1 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: string minimizeStringValue(string s) { } };

golang 解法, 执行用时: 17 ms, 内存消耗: 6.6 MB, 提交时间: 2024-03-19 20:06:56 

func minimizeStringValue(s string) string {
	freq := [27]int{26: math.MaxInt / 26} // 哨兵
	for _, c := range s {
		if c != '?' {
			freq[c-'a']++
		}
	}

	f := freq
	slices.Sort(f[:])

	var limit, extra int
	q := strings.Count(s, "?")
	for i := 1; ; i++ {
		sum := i * (f[i] - f[i-1])
		if q <= sum {
			limit, extra = f[i-1]+q/i, q%i
			break
		}
		q -= sum
	}

	target := freq
	for i, c := range freq[:26] {
		if c > limit {
			continue
		}
		target[i] = limit
		if extra > 0 { // 还可以多分配一个
			extra--
			target[i]++
		}
	}

	ans := []byte(s)
	j := byte(0)
	for i, c := range ans {
		if c != '?' {
			continue
		}
		for freq[j] == target[j] {
			j++
		}
		freq[j]++
		ans[i] = 'a' + j
	}
	return string(ans)
}

golang 解法, 执行用时: 56 ms, 内存消耗: 6.6 MB, 提交时间: 2024-03-19 20:06:43 

func minimizeStringValue(s string) string {
	h := make(hp, 26)
	for i := byte(0); i < 26; i++ {
		h[i].c = 'a' + i
	}
	for _, b := range s {
		if b != '?' {
			h[b-'a'].f++
		}
	}
	heap.Init(&h)

	t := make([]byte, strings.Count(s, "?"))
	for i := range t {
		t[i] = h[0].c
		h[0].f++ // 出现次数加一
		heap.Fix(&h, 0)
	}
	slices.Sort(t) // 排序，因为要求字典序最小

	ans := []byte(s)
	j := 0
	for i, b := range ans {
		if b == '?' {
			ans[i] = t[j] // 填入字母
			j++
		}
	}
	return string(ans)
}

type pair struct {
	f int
	c byte
}
type hp []pair
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { a, b := h[i], h[j]; return a.f < b.f || a.f == b.f && a.c < b.c }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (hp) Push(any)             {}
func (hp) Pop() (_ any)         { return }

java 解法, 执行用时: 13 ms, 内存消耗: 44.9 MB, 提交时间: 2024-03-19 20:06:27 

class Solution {
    public String minimizeStringValue(String S) {
        char[] s = S.toCharArray();
        int[] freq = new int[27];
        freq[26] = Integer.MAX_VALUE / 26; // 哨兵
        int q = 0;
        for (char c : s) {
            if (c != '?') {
                freq[c - 'a']++;
            } else {
                q++;
            }
        }

        int[] f = freq.clone();
        Arrays.sort(f);

        int limit, extra;
        for (int i = 1; ; i++) {
            int sum = i * (f[i] - f[i - 1]);
            if (q <= sum) {
                limit = f[i - 1] + q / i;
                extra = q % i;
                break;
            }
            q -= sum;
        }

        int[] target = freq.clone();
        for (int j = 0; j < 26; j++) {
            if (freq[j] > limit) {
                continue;
            }
            target[j] = limit;
            if (extra > 0) { // 还可以多分配一个
                extra--;
                target[j]++;
            }
        }

        int j = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i] != '?') {
                continue;
            }
            while (freq[j] == target[j]) {
                j++;
            }
            freq[j]++;
            s[i] = (char) ('a' + j);
        }
        return new String(s);
    }

    // 最小堆
    public String minimizeStringValue2(String S) {
        char[] s = S.toCharArray();
        int[] freq = new int[26];
        int q = 0;
        for (char c : s) {
            if (c != '?') {
                freq[c - 'a']++;
            } else {
                q++;
            }
        }
        PriorityQueue<Pair<Integer, Character>> pq = new PriorityQueue<>(26, (a, b) -> {
            int c = a.getKey().compareTo(b.getKey());
            return c != 0 ? c : a.getValue().compareTo(b.getValue());
        });
        for (char c = 'a'; c <= 'z'; c++) {
            pq.add(new Pair<>(freq[c - 'a'], c));
        }

        char[] t = new char[q];
        for (int i = 0; i < q; i++) {
            Pair<Integer, Character> p = pq.poll();
            char c = p.getValue();
            t[i] = c;
            pq.add(new Pair<>(p.getKey() + 1, c)); // 出现次数加一
        }
        Arrays.sort(t); // 排序，因为要求字典序最小

        for (int i = 0, j = 0; i < s.length; i++) {
            if (s[i] == '?') {
                s[i] = t[j++]; // 填入字母
            }
        }
        return new String(s);
    }
}

python3 解法, 执行用时: 281 ms, 内存消耗: 18.7 MB, 提交时间: 2024-03-19 20:05:41 

class Solution:
    # 最小堆
    def minimizeStringValue(self, s: str) -> str:
        freq = Counter(s)
        h = [(freq[c], c) for c in ascii_lowercase]
        heapify(h)

        t = []
        for _ in range(s.count('?')):
            f, c = h[0]
            t.append(c)
            heapreplace(h, (f + 1, c))  # 出现次数加一
        t.sort()  # 排序，因为要求字典序最小

        s = list(s)
        j = 0
        for i in range(len(s)):
            if s[i] == '?':
                s[i] = t[j]  # 填入字母
                j += 1
        return ''.join(s)
        
    # 贪心
    def minimizeStringValue2(self, s: str) -> str:
        freq = [0] * 26
        for c in s:
            if c != '?':
                freq[ord(c) - ord('a')] += 1

        f = sorted(freq) + [inf]  # 哨兵
        q = s.count('?')
        for i in count(1):
            need = i * (f[i] - f[i - 1])
            if q <= need:
                limit, extra = f[i - 1] + q // i, q % i
                break
            q -= need

        target = freq.copy()
        for i in range(26):
            if target[i] > limit:
                continue
            target[i] = limit
            if extra:  # 还可以多分配一个
                extra -= 1
                target[i] += 1

        ans = list(s)
        j = 0
        for i, c in enumerate(ans):
            if c != '?':
                continue
            while freq[j] == target[j]:
                j += 1
            freq[j] += 1
            ans[i] = ascii_lowercase[j]
        return ''.join(ans)

上一题

© 2024 leetcode.cn