天天看點

資料結構算法之字元串1.理論部分2.練習部分

Task5-字元串

  • 1.理論部分
    • 1. 串的定義與操作
    • 2. 串的存儲與實作
  • 2.練習部分
    • 2.1 無重複字元的最長子串
    • 2.2 串聯所有單詞的子串
    • 2.3 替換子串得到平衡字元串

1.理論部分

1. 串的定義與操作

  1. 定義:串(string)是由零個或多個字元組成的有限序列,又名字元串,記為S=”a0a1…an”;串是一種特殊的線性表;
  2. 串操作:(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