• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1177.构建回文串检测|CanMakePalindromefromSubstring

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], ..., s[right], and then choose up to k of them to replace with any lowercase English letter. 

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = "aaa", and k = 2, we can only replace two of the letters.  (Also, note that the initial string s is never modified by any query.)

 

Example :

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

 

Constraints:

  • 1 <= s.length, queries.length <= 10^5
  • 0 <= queries[i][0] <= queries[i][1] < s.length
  • 0 <= queries[i][2] <= s.length
  • s only contains lowercase English letters.

 给你一个字符串 s,请你对 s 的子串进行检测。

每次检测,待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right],并从中选择 最多 k 项替换成任何小写英文字母。 

如果在上述检测过程中,子串可以变成回文形式的字符串,那么检测结果为 true,否则结果为 false

返回答案数组 answer[],其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意:在替换时,子串中的每个字母都必须作为 独立的 项进行计数,也就是说,如果 s[left..right] = "aaa" 且 k = 2,我们只能替换其中的两个字母。(另外,任何检测都不会修改原始字符串 s,可以认为每次检测都是独立的)

 

示例:

输入:s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出:[true,false,false,true,true]
解释:
queries[0] : 子串 = "d",回文。
queries[1] : 子串 = "bc",不是回文。
queries[2] : 子串 = "abcd",只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd",可以变成回文的 "abba"。 也可以变成 "baab",先重新排序变成 "bacd",然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda",可以变成回文的 "abcba"。

 

提示:

  • 1 <= s.length, queries.length <= 10^5
  • 0 <= queries[i][0] <= queries[i][1] < s.length
  • 0 <= queries[i][2] <= s.length
  • s 中只有小写英文字母

Runtime: 1204 ms
Memory Usage: 55.4 MB
 1 class Solution {
 2     func canMakePaliQueries(_ s: String, _ queries: [[Int]]) -> [Bool] {
 3         var s:[Int] = Array(s).map{$0.ascii}
 4         var n:Int = s.count
 5         var m:Int = queries.count
 6         var res:[Bool] = [Bool](repeating:false,count:m)
 7         var sum:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:26),count:n)
 8         for i in 0..<n
 9         {
10             if i > 0
11             {
12                 sum[i] = sum[i-1]
13             }
14             sum[i][s[i] - 97] += 1
15         }
16         for i in 0..<m
17         {
18             var l:Int = queries[i][0]
19             var r:Int = queries[i][1]
20             var k:Int = queries[i][2]
21             var cnt:Int = 0
22             for j in 0..<26
23             {
24                 var tmp:Int = sum[r][j]
25                 if l > 0
26                 {
27                     tmp -= sum[l-1][j]
28                 }
29                 
30                 if tmp & 1 != 0
31                 {
32                     cnt += 1
33                 }
34             }
35             if (r-l+1) & 1 != 0
36             {
37                 cnt -= 1
38             }
39             res[i] = cnt <= k * 2
40         }
41         return res
42     }
43 }
44 
45 //Character扩展 
46 extension Character  
47 {  
48   //Character转ASCII整数值(定义小写为整数值)
49    var ascii: Int {
50        get {
51            return Int(self.unicodeScalars.first?.value ?? 0)
52        }       
53     }
54

1328ms

 

 1 class Solution {
 2     func canMakePaliQueries(_ s: String, _ queries: [[Int]]) -> [Bool] {
 3         let s = Array(s.utf8)
 4         var freqs = [Freq]()
 5         var freq = Freq()
 6         freqs.append(freq)
 7         for char in s {
 8             let f = Freq(freq, char)
 9             freqs.append(f)
10             freq = f
11         }
12         
13         var res = [Bool]()
14         for query in queries {
15             res.append(solve(query, freqs))
16         }
17         
18         return res
19     }
20     
21     func solve(_ query: [Int], _ freqs: [Freq]) -> Bool {
22         let freq1 = freqs[query[0]]
23         let freq2 = freqs[query[1] + 1]
24         let num = query[2]
25         let freq = freq1 - freq2
26         var countOdd = 0
27         for i in 0..<26 {
28             if freq.arr[i] % 2 == 1 {
29                 countOdd += 1
30             }
31         }
32         //print(freq, countOdd, num)
33         return (countOdd - num * 2) <= 1
34     }
35 }
36 
37 struct Freq {
38     var arr: [Int]
39     
40     init() {
41         arr = [Int](repeating: 0, count:  26)
42     }
43     
44     init(_ freq: Freq, _ char: UInt8) {
45         self.arr = freq.arr
46         arr[Int(char) - 97] += 1
47     }
48     
49     init(_ str: [UInt8]) {
50         arr = [Int](repeating: 0, count:  26)
51         for char in str {
52             arr[Int(char) - 97] += 1
53         }
54     }
55     
56     static func -(lhs: Freq, rhs: Freq) -> Freq {
57         var freq = Freq()
58         for i in 0..<26 {
59             freq.arr[i] = rhs.arr[i] - lhs.arr[i]
60         }
61         return freq
62     }
63 }

1452ms

 1 class Solution {
 2     func canMakePaliQueries(_ s: String, _ queries: [[Int]]) -> [Bool] {   
 3         let chars = Array(s), n = chars.count
 4         let table = Array("abcdefghijklmnopqrstuvwxyz")
 5         var freq = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: 26)
 6         for c in 0..<26 {
 7             for i in 0..<n {
 8                 freq[c][i+1] = freq[c][i] + (chars[i] == table[c] ? 1 : 0)
 9             }
10         }
11         var ans = [Bool]()
12         for que in queries {
13             var i = que[0], j = que[1], k = que[2]
14             j += 1
15             var odd_count = 0
16             for c in 0..<26 where (freq[c][j] - freq[c][i])%2 != 0 {
17                 odd_count += 1
18             }
19 
20             let fullfill = (odd_count-1) <= 2*k
21             ans.append(fullfill)
22         }
23         return ans
24     }
25 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap