1170. Compare Strings by Frequency of the Smallest Character

1170. Compare Strings by Frequency of the Smallest Character #

题目 #

Let’s define a function f(s) over a non-empty string s, which calculates the frequency of the smallest character in s. For example, if s = "dcce" then f(s) = 2 because the smallest character is "c" and its frequency is 2.

Now, given string arrays queries and words, return an integer array answer, where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words.

Example 1:

Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

Example 2:

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").

Constraints:

  • 1 <= queries.length <= 2000
  • 1 <= words.length <= 2000
  • 1 <= queries[i].length, words[i].length <= 10
  • queries[i][j]words[i][j] are English lowercase letters.

题目大意 #

我们来定义一个函数 f(s),其中传入参数 s 是一个非空字符串;该函数的功能是统计 s  中(按字典序比较)最小字母的出现频次。

例如,若 s = “dcce”,那么 f(s) = 2,因为最小的字母是 “c”,它出现了 2 次。

现在,给你两个字符串数组待查表 queries 和词汇表 words,请你返回一个整数数组 answer 作为答案,其中每个 answer[i] 是满足 f(queries[i]) < f(W) 的词的数目,W 是词汇表 words 中的词。

提示:

  • 1 <= queries.length <= 2000
  • 1 <= words.length <= 2000
  • 1 <= queries[i].length, words[i].length <= 10
  • queries[i][j], words[i][j] 都是小写英文字母

解题思路 #

  • 给出 2 个数组,querieswords,针对每一个 queries[i] 统计在 words[j] 中满足 f(queries[i]) < f(words[j]) 条件的 words[j] 的个数。f(string) 的定义是 string 中字典序最小的字母的频次。
  • 先依照题意,构造出 f() 函数,算出每个 words[j]f() 值,然后排序。再依次计算 queries[i]f() 值。针对每个 f() 值,在 words[j]f() 值中二分搜索,查找比它大的值的下标 kn-k 即是比 queries[i]f() 值大的元素个数。依次输出到结果数组中即可。

代码 #


package leetcode

import "sort"

func numSmallerByFrequency(queries []string, words []string) []int {
	ws, res := make([]int, len(words)), make([]int, len(queries))
	for i, w := range words {
		ws[i] = countFunc(w)
	}
	sort.Ints(ws)
	for i, q := range queries {
		fq := countFunc(q)
		res[i] = len(words) - sort.Search(len(words), func(i int) bool { return fq < ws[i] })
	}
	return res
}

func countFunc(s string) int {
	count, i := [26]int{}, 0
	for _, b := range s {
		count[b-'a']++
	}
	for count[i] == 0 {
		i++
	}
	return count[i]
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者