資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中從子字串生成迴文
假設我們有一個字串 s，我們需要對 s 的子字串進行查詢。對於每個查詢 queries[i]，都有三個部分 [left, right, k]，我們可以重新排列子字串 s[left]，…，s[right]，然後選擇最多 k 個字元替換為任何小寫英文字母。如果子字串在上述操作後可以成為迴文，則查詢結果為 true。否則為 false。我們需要找到一個數組 answer[]，其中 answer[i] 是第 i 個查詢 queries[i] 的結果。
例如，如果輸入是“abcda”，queries 類似於 [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]，則輸出將是 [true, false, false, true, true]
為了解決這個問題，我們將遵循以下步驟：
- 定義一個名為 solve 的方法，它將接收 dp 矩陣和 q。它將按以下方式工作：
- l := q[0]，r := q[1]，k := q[2]，然後將 l 和 r 加 1，one := 0
- 對於 i 的範圍從 0 到 25
- one := one + (dp[r, i] – dp[l – 1, i]) mod 2
- 當 one / 2 的整數除法 <= k 時返回 true，否則返回 false
- 定義另一個名為 makeDP() 的方法，它將接收 dp 矩陣和 s，它將按以下方式工作：
- 對於 i 的範圍從 0 到 s 的長度
- 對於 j 的範圍從 0 到 25
- dp[i, j] := dp[i – 1, j]
- 將 dp[i, s[i] 的 ASCII 值 - ‘a’ 的 ASCII 值] 加 1
- 對於 j 的範圍從 0 到 25
- 主方法將如下所示：
- n := 字串 s 的大小，s := “ ” 連線 s
- dp := 一個 (n + 1) x 26 階矩陣，並將其填充為 0
- 呼叫 makeDP(dp, s)
- res := 一個與 q 的長度相同的陣列，並將其填充為 false
- 對於 i 的範圍從 0 到 q 的長度 - 1
- res[i] := solve(dp, q[i])
- 返回 res
示例（Python）
讓我們看看以下實現以更好地理解：
class Solution(object):
def solve(self,dp,q):
l = q[0]
r = q[1]
k = q[2]
r+=1
l+=1
#arr = [ 0 for i in range(26)]
one = 0
for i in range(26):
one += (dp[r][i]-dp[l-1][i])%2
return one//2<=k
def make_dp(self,dp,s):
for i in range(1,len(s)):
for j in range(26):
dp[i][j] = dp[i-1][j]
dp[i][ord(s[i])-ord('a')]+=1
def canMakePaliQueries(self, s, q):
n = len(s)
s = " "+s
dp = [[0 for i in range(26)] for j in range(n+1)]
self.make_dp(dp,s)
res = [False for i in range(len(q))]
for i in range(len(q)):
res[i] = self.solve(dp,q[i])
return res
ob = Solution()
print(ob.canMakePaliQueries("abcda", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]))輸入
"abcda" [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
輸出
[True, False, False, True, True]
更新於: 2020-04-30
121 次檢視
廣告