[Swift]LeetCode1170.比较字符串最小字母出现频次|CompareStringsbyFrequencyoftheSma ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（www.zengqiang.org）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 = ["cbd"], words = ["zaaaz"]
输出：[1]
解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。

示例 2：

输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
输出：[1,2]
解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。

提示：

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

Runtime: 188 ms

Memory Usage: 21.5 MB

 1 class Solution {
 2     func numSmallerByFrequency(_ queries: [String], _ words: [String]) -> [Int] {
 3         let n:Int = queries.count
 4         let m:Int = words.count
 5         var ws:[Int] = [Int](repeating:0,count:m)
 6         for i in 0..<m
 7         {
 8             ws[i] = f(words[i])
 9         }
10         var ret:[Int] = [Int](repeating:0,count:n)
11         for i in 0..<n
12         {
13             var u:Int = f(queries[i])
14             for j in 0..<m
15             {
16                 if u < ws[j]
17                 {
18                     ret[i] += 1
19                 }
20             }
21         }
22         return ret        
23     }
24     
25     func f(_ s:String) -> Int
26     {
27         var f:[Int] = [Int](repeating:0,count:26)
28         for c in s
29         {
30             f[c.ascii - 97] += 1
31         }
32         for i in 0..<26
33         {
34             if f[i] > 0
35             {
36                 return f[i]
37             }
38         }
39         return 0
40     }
41 }
42 
43 //Character扩展 
44 extension Character  
45 {  
46   //Character转ASCII整数值(定义小写为整数值)
47    var ascii: Int {
48        get {
49            return Int(self.unicodeScalars.first?.value ?? 0)
50        }       
51     }
52 }

248ms

 1 class Solution {
 2     func freOf(_ str: String) -> Int {
 3         var lastChar: Character = "z"
 4         let chars = Array(str)
 5         var dic = [Character: Int]()
 6         for c in chars {
 7             dic[c, default: 0] += 1
 8             if c < lastChar {
 9                 lastChar = c
10             }
11         }
12         return dic[lastChar, default: 0]
13     }
14 
15     func numSmallerByFrequency(_ queries: [String], _ words: [String]) -> [Int] {
16         var freword = [Int]()
17         for w in words {
18             freword.append(freOf(w))
19         }
20 
21         freword = freword.sorted()
22         var freq = [Int]()
23         for f in queries {
24             freq.append(freOf(f))
25         }
26         var ans = [Int]()
27         for fi in freq {
28             var l = 0, r = freword.count - 1, idx = 0, valid = false
29             while l <= r {
30                 let mid = (l+r)/2
31                 if fi < freword[mid] {
32                     idx = mid
33                     r -= 1
34                     valid = true
35                 } else {
36                     l += 1
37                 }
38             }
39             if valid {
40                 ans.append(freword.count - idx)
41             } else {
42                 ans.append(0)   
43             }
44         }
45         return ans
46     }
47 }

256ms

 1 class Solution {
 2 func freOf(_ str: String) -> Int {
 3         var lastChar: Character = "z"
 4         let chars = Array(str)
 5         var dic = [Character: Int]()
 6         for c in chars {
 7             dic[c, default: 0] += 1
 8             if c < lastChar {
 9                 lastChar = c
10             }
11         }
12         return dic[lastChar, default: 0]
13     }
14 
15     func numSmallerByFrequency(_ queries: [String], _ words: [String]) -> [Int] {
16         var freword = [Int]()
17         for w in words {
18             freword.append(freOf(w))
19         }
20 
21         freword = freword.sorted()
22         var freq = [Int]()
23         for f in queries {
24             freq.append(freOf(f))
25         }
26         var ans = [Int]()
27         for fi in freq {
28             var l = 0, r = freword.count - 1, idx = 0, valid = false
29             while l <= r {
30                 let mid = (l+r)/2
31                 if fi < freword[mid] {
32                     idx = mid
33                     r -= 1
34                     valid = true
35                 } else {
36                     l += 1
37                 }
38             }
39             if valid {
40                 ans.append(freword.count - idx)
41             } else {
42                 ans.append(0)   
43             }
44         }
45         return ans
46     }
47 }

1220ms

 1 class Solution {
 2     func numSmallerByFrequency(_ queries: [String], _ words: [String]) -> [Int] {
 3         var ret = [Int]()
 4         var wArr = [Int]()
 5         for w in words {
 6             wArr.append(f(w))
 7         }
 8         for q in queries {
 9             let freq = f(q)
10             var count = 0
11             for w in wArr {
12                 if freq < w { count += 1 }
13             }
14             ret.append(count)
15         }
16         return ret
17     }
18     
19     private func f(_ str: String) -> Int {
20         guard str.count > 0 else { return 0 }
21         
22         var minC = str[str.index(str.startIndex, offsetBy: 0)]
23         var minCount = 0
24         for c in str {
25             if c == minC { minCount += 1 }
26             else if c < minC {
27                 minCount = 1
28                 minC = c
29             }
30         }
31         return minCount
32     }
33 }

1268ms

 1 class Solution {
 2     func numSmallerByFrequency(_ queries: [String], _ words: [String]) -> [Int] {
 3         var res = [Int]()
 4         
 5         let f = { (s: String) -> Int in
 6             var a = [Int](repeating: 0, count: 26)
 7             let chars = s.map{ $0 }
 8             for c in chars {
 9                 a[Int(c.asciiValue! - Character("a").asciiValue!)] += 1
10             }
11             
12             for t in a where t > 0 {
13                 return t
14             }
15             
16             return 0
17         }
18         
19         var ws = [Int]()
20         for w in words {
21             ws.append(f(w))
22         }
23         
24         for q in queries {
25             let a = f(q)
26             var c = 0
27             for w in ws where a < w {
28                 c += 1
29             }
30             res.append(c)
31         }
32         
33         return res
34     }
35 }

1284ms

 1 class Solution {
 2     func f(_ str: String) -> Int? {
 3     guard str.count > 0 else {return nil}
 4     var freq : [Character: Int] = [:]
 5     for ch in str {
 6         freq[ch, default: 0] += 1
 7     }
 8 
 9     return freq.min{a, b in
10         a.key <= b.key
11     }?.value
12 }
13     func numSmallerByFrequency(_ queries: [String], _ words: [String]) -> [Int] {
14     var output : [Int] = []
15     var fwords : [Int] = []
16     
17     for word in words {
18         fwords.append(f(word)!)
19     }
20     
21     for query in queries {
22         var localOutput = 0
23         let fquery = f(query)!
24         for word in fwords {
25             if fquery < word {
26                 localOutput += 1
27             }
28         }
29         output.append(localOutput)
30     }
31     return output  
32     }
33 }

1292ms

 1 class Solution {
 2     func f(_ str: String) -> Int? {
 3     guard str.count > 0 else {return nil}
 4     var freq : [Character: Int] = [:]
 5     for ch in str {
 6         freq[ch, default: 0] += 1
 7     }
 8 
 9     return freq.min{a, b in
10         a.key <= b.key
11     }?.value
12 }
13     func numSmallerByFrequency(_ queries: [String], _ words: [String]) -> [Int] {
14     var output : [Int] = []
15     var fwords : [Int] = []
16     
17     for word in words {
18         fwords.append(f(word)!)
19     }
20     
21     for query in queries {
22         var localOutput = 0
23         let fquery = f(query)!
24         for word in fwords {
25             if fquery < word {
26                 localOutput += 1
27             }
28         }
29         output.append(localOutput)
30     }
31     return output  
32     }
33 }

1436ms

 1 class Solution {
 2     func numSmallerByFrequency(_ queries: [String], _ words: [String]) -> [Int] {
 3         let worsCounter = words.map { (s) -> Int in
 4             return f(s: s)
 5         }
 6         let queriesCounter = queries.map { (s) -> Int in
 7             return f(s: s)
 8         }
 9         
10         return queriesCounter.map({ (val) -> Int in
11             worsCounter.filter({ (v) -> Bool in
12                 v >  val
13             }).count
14         })
15     }
16     private func f(s: String) -> Int {
17         var  arr = Array<Int>(repeating: 0, count: 26)
18         let  aToInt = Character("a").asciiValue!
19         for ch in s {
20             let index = ch.asciiValue! - aToInt
21             arr[Int(index)] += 1
22         }
23         for i in 0...25 {
24             if arr[i] != 0 {
25                 return arr[i]
26             }
27         }
28         return  -1
29     }
30 }