Skip to main content

12-复杂数据结构

1.积分图前缀和​

303. 区域和检索 - 数组不可变​

class NumArray {
    vector<int> num;
public:
    NumArray(vector<int>& nums):num(nums) {
        partial_sum(num.begin(),num.end(),num.begin());
    }
    
    int sumRange(int left, int right) {
        return left > 0 ? num[right] - num[left - 1] : num[right];
    }
};

304. 二维区域和检索 - 矩阵不可变​

class NumMatrix {
    vector<vector<int>> res;
public:
    NumMatrix(vector<vector<int>>& matrix) :res(matrix.size() + 1, vector<int>(matrix[0].size() + 1,0)){
        for(int i = 1; i < res.size();i++)
        {
            for(int j = 1; j < res[0].size();j++)
            {
                res[i][j] = res[i - 1][j] + res[i][j - 1] + matrix[i - 1][j - 1] - res[i - 1][j - 1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return res[row2 + 1][col2 + 1] - res[row1][col2 + 1] -res[row2 + 1][col1] + res[row1][col1];
    }
};

560. 和为 K 的子数组​

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> umap;
        partial_sum(nums.begin(),nums.end(),nums.begin());
        umap[0] = 1;
        int res = 0;
        for(int i = 0;i < nums.size();i++)
        {
            res += umap[nums[i] - k];
            umap[nums[i]]++;
        }
        return res;
    }
};

1031. 两个非重叠子数组的最大和***​

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int res_max = 0;
        partial_sum(nums.begin(),nums.end(),nums.begin());
        nums.insert(nums.begin(),0);
        auto f = [&](int firstLen , int secondLen){
            int maxSumA = 0;
            for(int i = firstLen + secondLen; i < nums.size();i++)
            {
                maxSumA = max(maxSumA, nums[i - secondLen] - nums[i - secondLen - firstLen]);
                res_max = max(res_max, maxSumA + nums[i] - nums[i - secondLen]);
            }
        };
        f(firstLen,secondLen);
        f(secondLen,firstLen);
        return res_max;
    }
};

523. 连续的子数组和**​

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        partial_sum(nums.begin(),nums.end(),nums.begin());
        unordered_set<int> uset;
        for(int i = 0; i < nums.size();i++)
        {
            if(nums[i] % k == 0 && i >= 1) return true;
            if(uset.count(nums[i] % k) > 0) return true;
            uset.insert(nums[i] % k);
        }
        
        return false;
    }   
};

974. 和可被 K 整除的子数组​

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int sum = 0 , res = 0;
        unordered_map<int,int> umap;
        umap[0] = 1;
        for(int i : nums)
        {
            sum += i;
            int psum = (sum % k + k) % k;
            if(umap[psum] > 0) res += umap[psum];
            umap[psum]++;
        }
        return res;
    }
};

2.前缀树​

208. 实现 Trie (前缀树)​

class Trie {
        vector<Trie*> next;
        char ch;
        bool is_end;
public:
    Trie() :is_end(false){
        next.resize(26);
    }
    
    void insert(string word) {
        Trie* cur = this;
        for(char x:word)
        {
            if(!cur->next[x - 'a'])cur->next[x - 'a'] = new Trie();
            cur = cur->next[x - 'a'];
            cur->ch = x;
        }
        cur->is_end = true;
    }
    
    bool search(string word) {
        Trie* cur = this;
        for(char x:word)
        {
            if(!cur->next[x - 'a']) return false;
            cur = cur->next[x - 'a'];
        }
        return cur->is_end;
    }
    
    bool startsWith(string prefix) {
        Trie* cur = this;
        for(char x:prefix)
        {
            if(!cur->next[x - 'a']) return false;
            cur = cur->next[x - 'a'];
        }
        return true;
    }
};

LCR 063. 单词替换​

class Solution {
class Trie {
    class dicttree
    {
    public:
        char val;
        bool isWord;
        vector<dicttree*> trees;
        dicttree()
        {
            val = 0;
            isWord = false;
            trees.resize(26);
            for (int i = 0; i < 26; ++i) {
                trees[i] = nullptr;
            }
        }
    };
    dicttree *root;
public:
    Trie() {
        root = new dicttree();
    }

    void insert(string word) {
        dicttree * cur = root;
        for (int i = 0; i < word.size(); ++i) {
            if (cur->trees[word[i] - 'a'] == NULL)
            {
                cur->trees[word[i] - 'a'] = new dicttree();
                cur->trees[word[i] - 'a']->val = word[i];

            }
            cur = cur->trees[word[i] - 'a'];
        }
        cur->isWord = true;
    }

    string search(string word) {
        dicttree * cur = root;
        for (int i = 0; i < word.size(); ++i) {
            if (cur->trees[word[i] - 'a'] == NULL) return word;
            cur = cur->trees[word[i] - 'a'];
            if(cur->isWord) return word.substr(0,i + 1);
        }
        return word;
    }
};

public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        Trie* tree = new Trie();
        for(int i = 0 ; i < dictionary.size();i++)
        {
            tree->insert(dictionary[i]);
        }
        string res,temp;
        stringstream ss(sentence);
        while(getline(ss,temp,' '))
        {
            res += tree->search(temp) + " ";
        }
        if(res.back() == ' ') res.pop_back();


        return res;
    }
};

LCR 064. 实现一个魔法字典​

class MagicDictionary {
    vector<string> dictionary;
public:
    /** Initialize your data structure here. */
    MagicDictionary() {

    }
    
    void buildDict(vector<string> dictionary) {
        this->dictionary = dictionary;
    }
    
    bool search(string searchWord) {
        for(int i = 0;i < dictionary.size() ;i++)
        {
            if(searchWord.size() != dictionary[i].size()) continue;
            int sums = 0;
            for(int j = 0; j < searchWord.size() ;j++)
            {
                if(dictionary[i][j] != searchWord[j]) sums++;
            }
            if(sums == 1) return true;
        }
        return false;
    }
};

LCR 066. 键值映射​

class MapSum {
    unordered_map<string,int> umap;
public:
    /** Initialize your data structure here. */
    MapSum() {

    }
    
    void insert(string key, int val) {
        umap[key] = val;
    }
    
    int sum(string prefix) {
        int sums = 0;
        for(auto x : umap)
        {
            if(x.first.size() >= prefix.size() && x.first.substr(0,prefix.size()) == prefix) sums += x.second;
        }
        return sums;
    }
};

LCR 065. 单词的压缩编码​

class Solution {
    class Trie {
        vector<Trie*> next;
        char ch;
        bool is_end;
public:
    Trie() :is_end(false){
        next.resize(26);
    }
    
    void insert(string word) {
        Trie* cur = this;
        for(char x:word)
        {
            if(!cur->next[x - 'a'])cur->next[x - 'a'] = new Trie();
            cur = cur->next[x - 'a'];
            cur->ch = x;
        }
        cur->is_end = true;
    }
    
    bool search(string word) {
        Trie* cur = this;
        for(char x:word)
        {
            if(!cur->next[x - 'a']) return false;
            cur = cur->next[x - 'a'];
        }
        return cur->is_end;
    }
    
    bool startsWith(string prefix) {
        Trie* cur = this;
        for(char x:prefix)
        {
            if(!cur->next[x - 'a']) return false;
            cur = cur->next[x - 'a'];
        }
        return true;
    }
};

public:
    int minimumLengthEncoding(vector<string>& words) {
        Trie *tree = new Trie();
        for(auto &x :words)  reverse(x.begin(),x.end());
        sort(words.begin(),words.end(),[&](const string &a,const string &b){
            return a.size() > b.size();
        });
        int sum = 0;
        for(auto x :words)
        {
            if(!tree->startsWith(x)) 
            {
                tree->insert(x);
                sum += x.size() + 1;
            }
        }
        return sum;
    }
};

LCR 067. 数组中两个数的最大异或值​

class Solution {
  class dictTree
  {
      vector<dictTree*> next;
      int val;
  public:
      dictTree():next(vector<dictTree*>(2)){};
      void insert(int num)
      {
          dictTree* cur = this;
          for(int i = 0; i <= 30 ;i++)
          {
             int bit = 1 & (num >> (30 - i));
             if(!cur->next[bit]) cur->next[bit] = new dictTree();
             cur = cur->next[bit];
          }
          cur->val = num;
      }

      int search(int num)
      {
          dictTree* cur = this;
          for(int i = 0; i <= 30 ;i++)
          {
             int bit = 1 & (num >> (30 - i));
             if(cur->next[1 - bit]) cur = cur->next[1 - bit];
             else cur = cur->next[bit];
          }
          return cur->val ^ num;
      }
  };
public:
    int findMaximumXOR(vector<int>& nums) {
        dictTree * tree = new dictTree();
        int maxs = 0;
        for(int num: nums)
        {
            tree->insert(num);
            maxs = max(maxs,tree->search(num));
        }
        return maxs;
    }
};

386. 字典序排数​

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res;
        function<void(int)> dfs = [&](int i)
        {
            if(i > n) return;
            res.push_back(i);
            for(int j = 0;j <= 9;j++)
            {
                dfs(i * 10 + j);
            }
        };
        for(int i = 1;i <= 9;i++)dfs(i);
        return res;
    }
};

440. 字典序的第K小数字​

class Solution {
    using  LL = long long;
    int getNodes(LL u, int n)
    {
        LL next = u + 1; //当前根结点的右边的根结点
        int totNodes = 0;//记录当前结点的所有节点数(包括它本身)
        while(u <= n)
        {
            totNodes += min(n - u + 1, next - u);
            u *= 10;//当前根结点下移
            next *= 10;//当前根结点的右根结点下移
        }
        return totNodes;
    }
public:
    int findKthNumber(int n, int k) {
        LL cur = 1;
        while(k > 1)
        {
            int nodes = getNodes(cur, n); //求出cur下面的节点个数
            if(k > nodes) 
            {
                k -= nodes;
                cur ++;//右移
            }
            else
            {
                k--;//下移
                cur = cur * 10;
            }
        }
        return (LL)cur;
    }
};

1233. 删除子文件夹​

class Solution {
    struct tree
    {
        tree(string path,bool is_end):path(path),is_end(is_end){};
        string path;
        bool is_end;
        unordered_map<string,tree*> umap;
    };
    tree* root;
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(),folder.end(),[](const string &a , const string &b){
            return a.size() < b.size();
        });
        root = new tree("",false);
        vector<string> res;
        for(string x: folder)
        {
            //加入字典树
            stringstream ss(x.substr(1) + "/");
            string tmp;
            tree *cur = root;
            bool flas = false;
            while(getline(ss,tmp,'/'))
            {
                //cout << tmp << endl;
                if(cur->umap.find(tmp) ==cur->umap.end())
                {
                    cur->umap[tmp] = new tree(tmp,false);
                }
                if(cur->is_end) 
                {
                    flas = true;
                    break;
                }
                else cur = cur->umap[tmp];
            }
            if(flas) continue;
            cur->is_end = true;
            res.push_back(x)
        }
        return res;
    }
};

211. 添加与搜索单词 - 数据结构设计​

class WordDictionary {
    struct Tree
    {
        
        bool isWord;
        vector<Tree*> next;
        Tree():isWord(false),next(26){};
    };
    Tree *root;
public:
    WordDictionary() {
        root = new Tree();
    }
    
    void addWord(string word) {
        Tree *cur = root;
        for(char ch : word)
        {
            if(!cur->next[ch - 'a']) cur->next[ch - 'a'] = new Tree();
            cur = cur->next[ch - 'a'];
        }
        cur->isWord = true;
    }
    bool search(string &word,int begin,Tree * cur) {
        //if(begin == word.size()) return true;

        for(int i = begin;i < word.size();i++)
        {
            char ch = word[i];
            if(ch != '.') 
            {
                if(!cur->next[ch - 'a']) return false;
                else cur = cur->next[ch - 'a'];
            }
            else 
            {
                bool flag = false;
                for(char c = 'a';c <= 'z';c++)
                {
                    if(cur->next[c - 'a'])flag = flag || search(word,i + 1,cur->next[c - 'a']);
                }
                return flag;
            }
        }
        return cur->isWord;
    }
    bool search(string word) {
        return search(word,0,root);
    }
};

3.TreeMap红黑树​

729. 我的日程安排表 I***​

class MyCalendar {
public:
    MyCalendar() {

    }
    
    bool book(int start, int end) {
        auto pos = cmap.lower_bound(start);
        auto epos = cmap.lower_bound(end);
        if(pos == epos){
            if(pos != cmap.begin() && (--pos)->second>start) return false;
            cmap[start] = end;
            return true;
        }
        return false;
    }
    map<int, int> cmap;
};

846. 一手顺子​

class Solution {
public:
    bool isNStraightHand(vector<int>& hand , int groupSize) {
        if(groupSize == 1) return true;
        if(hand.size() % groupSize != 0)return false;
        map<int,int> cmap;
        for(int x : hand) cmap[x]++;
        
        while(!cmap.empty())
        {
            int pre = cmap.begin()->first;
            cmap[pre]--;
            if(cmap[pre] == 0) cmap.erase(pre);
            
            for(int i = 1; i < groupSize;i++)
            {
                if(cmap[pre + i] == 0) return false;
                else
                {
                    cmap[pre + i]--;
                    if(cmap[pre + i] == 0) cmap.erase(pre + i);
                }
            }
            
        }
        return true;
    }
};

4.其余数据结构​

146. LRU 缓存​

我们采用一个链表 list来储存信息的 key 和 value，链表的链接顺序即为最 近使用的新旧顺序，最新的信息在链表头节点。同时我们需要一个嵌套着链表的迭代器的 unordered_map 进行快速搜索，存迭代器的原因是方便调用链表的 splice 函数来直接更新查找成功（cash hit）时的信息，即把迭代器对应的节点移动为链表的头节 点。

list::splice实现list拼接的功能。将源list的内容部分或全部元素删除，拼插入到目的list。

函数有以下三种声明：

void list::splice( iterator pos, list rhs );
void list::splice( iterator pos, list rhs, iterator ix ); 
void list::splice( iterator pos, list rhs, iterator first, iterator last );

splice()把一个或一级元素从一个 list 移到另一个中去 它有三种形式

1、从positon开始，把一个 list rhs的全部元素搬移到另一个中去 pos开始

2、从positon开始，把一个 ix 元素搬移到 rhs 的 pos位置

3、从positon开始，把first 到 last 剪接到要操作的list对象中的pos位置

class LRUCache {
    int capacitys;
    list<pair<int,int>> lists;
    unordered_map<int,list<pair<int, int>>::iterator> umap;
public:
    LRUCache(int capacity): capacitys(capacity){

    }
    
    int get(int key) {
        if(umap.find(key) == umap.end()) return -1;
        else
        {
            lists.splice(lists.begin(), lists, umap[key]);
            return umap[key]->second;
        }
    }
    
    void put(int key, int value) {
        if(umap.find(key) != umap.end()) 
        {
            umap[key]->second  = value;
            lists.splice(lists.begin(), lists, umap[key]);
            return;
        }
        if(capacitys == umap.size())
        {
            pair<int,int> pir = lists.back();
            lists.pop_back();
            umap.erase(pir.first);
        }
        lists.push_front(pair<int,int>(key,value));
        umap[key] = lists.begin();
    }
};

LCR 030. O(1) 时间插入、删除和获取随机元素​

class RandomizedSet {
    unordered_map<int,int> umap;
    vector<int> res;

public:
    /** Initialize your data structure here. */
    RandomizedSet() {

    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(umap.find(val) != umap.end()) return false;
        res.push_back(val);
        umap[val] = res.size() - 1;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(umap.find(val) == umap.end()) return false;
        umap[res.back()] = umap[val];
        swap(res[umap[val]],res[res.size() - 1]);
        umap.erase(val);
        res.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        int pos = rand() % res.size();
        return res[pos];
    }
};

745. 前缀和后缀搜索​

class WordFilter {
    unordered_map<string, vector<int>> prefixMap; 
    unordered_map<string, vector<int>> suffixMap; 
public:
    WordFilter(vector<string>& words) {
        for (int i = 0; i < words.size(); i++) {
            string word = words[i];
            int len = word.length();
            for (int j = 0; j <= len; j++) {
                prefixMap[word.substr(0, j)].push_back(i);
                suffixMap[word.substr(j)].push_back(i);
            }
        }
    }
    
    int f(string pref, string suff) {
        vector<int>& prefixIndexes = prefixMap[pref];
        vector<int>& suffixIndexes = suffixMap[suff];
        int i = prefixIndexes.size() - 1;
        int j = suffixIndexes.size() - 1;
        while (i >= 0 && j >= 0) {
            if (prefixIndexes[i] == suffixIndexes[j]) {
                return prefixIndexes[i];
            } else if (prefixIndexes[i] > suffixIndexes[j]) {
                i--;
            } else {
                j--;
            }
        }
        return -1;
    }
};

1146. 快照数组​

class SnapshotArray {
    unordered_map<int,map<int,int>> data;//每个位置用map保存对应版本号
    int version;
public:
    SnapshotArray(int length):data(length) {
        version = 0;
    }   
    
    void set(int index, int val) {
        data[index][version] = val;
    }
    
    int snap() {
        return version++;
    }
    
    int get(int index, int snap_id) {
        if(data.count(index) == 0) return 0;
        auto it = data[index].upper_bound(snap_id);
        if(it != data[index].begin()) {
            return (--it)->second;
        }
        return 0;
    }
};