Task5-字元串
- 1.理論部分
-
- 1. 串的定義與操作
- 2. 串的存儲與實作
- 2.練習部分
-
- 2.1 無重複字元的最長子串
- 2.2 串聯所有單詞的子串
- 2.3 替換子串得到平衡字元串
1.理論部分
1. 串的定義與操作
- 定義:串(string)是由零個或多個字元組成的有限序列,又名字元串,記為S=”a0a1…an”;串是一種特殊的線性表;
-
串操作:(1)擷取串的長度
(2)擷取或設定指定索引處的字元
(3)在指定位置插入子串
(4)在指定位置移除給定長度的子串
(5)在指定位置取子串
(6)目前串的拷貝
(7)串連接配接
(8)串的比對
2. 串的存儲與實作
同理:串的存儲分為兩種:順序存儲和鍊式存儲
順序存儲:char類型的數組。由于數組是定長的,就存在一個預定義的最大串長度,它規定在串值後面加一個不計入串長度的結束符,比如’\0’來表示串值的終結。
鍊式存儲:SlinkList (浪費存儲空間);
2.練習部分
2.1 無重複字元的最長子串
代碼實作:
class Solution:
"""
:type s: str
:rtype: int
"""
def lengthOfLongestSubstring(self, s):
l = 0
r = 0
maxLength = 0
s_len = len(s)
usedChar = [0] * 256 #通過符号表記錄符号出現次數
while l < s_len:
if r < s_len and usedChar[ord(s[r])] == 0:
usedChar[ord(s[r])] += 1
r += 1
else:
usedChar[ord(s[l])] -= 1
l += 1
maxLength = max(maxLength, r - l)
return maxLength
2.2 串聯所有單詞的子串
代碼實作:
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
if (s.empty() || words.empty()) return {};
vector<int> res;
int n = s.size(), cnt = words.size(), len = words[0].size();
unordered_map<string, int> m1;
for (string w : words) ++m1[w];
for (int i = 0; i < len; ++i) {
int left = i, count = 0;
unordered_map<string, int> m2;
for (int j = i; j <= n - len; j += len) {
string t = s.substr(j, len);
if (m1.count(t)) {
++m2[t];
if (m2[t] <= m1[t]) {
++count;
} else {
while (m2[t] > m1[t]) {
string t1 = s.substr(left, len);
--m2[t1];
if (m2[t1] < m1[t1]) --count;
left += len;
}
}
if (count == cnt) {
res.push_back(left);
--m2[s.substr(left, len)];
--count;
left += len;
}
} else {
m2.clear();
count = 0;
left = j + len;
}
}
}
return res;
}
};
2.3 替換子串得到平衡字元串
代碼實作:
class Solution:
def balancedString(self, s: str) -> int:
n = len(s)
cnt, avg = [None] * (n + 1), n//4
cnt[0] = {'Q':0, 'W':0, 'E':0, 'R':0}
for i, v in enumerate(s):
cnt[i+1] = {k:v for k, v in cnt[i].items()}
cnt[i+1][v] += 1
def check(x):
for st in range(n - x + 1):
t = {k:cnt[n][k] - cnt[st+x][k] + cnt[st][k] for k in cnt[0].keys()}
if all(avg >= t[x] for x in 'QWER'):
return True
return False
l, r = 0, n
while l < r:
mid = l + r >> 1
if check(mid):
r = mid
else:
l = mid + 1
return l