leetcode解题思路分析（五十）432 - 438 题

小灰灰 2022-12-22 11:12 143阅读 0赞

1.  全O(1)的数据结构

**哈希表+链表即可**

class AllOne { 
    public:
        /** Initialize your data structure here. */
        struct Node{ 
            unordered_set<string> container;
            int val = 0;
            Node(int v):val(v){ }
        };
        unordered_map<string, list<Node>::iterator> kv;
        list<Node> List;
        AllOne() { }
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        void inc(string key) { 
            if(kv.count(key)){ 
                auto oldNode = kv[key];
                auto newNode = next(oldNode, 1);
                if(newNode == List.end() || newNode->val>oldNode->val+1){ 
                    newNode = List.insert(newNode, Node(oldNode->val+1));
                }
    
                newNode->container.insert(key);
                oldNode->container.erase(key);
    
                if(oldNode->container.empty()){ 
                    List.erase(oldNode);
                }
                kv[key] = newNode;
            } else { 
                auto newNode = List.begin();
                if(List.empty() || List.begin()->val>1)
                    newNode = List.insert(List.begin(), Node(1));
                newNode->container.insert(key);
                kv[key] = newNode;
            }
        }
    
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        void dec(string key) { 
            if(kv.count(key)){ 
                auto oldNode = kv[key];
                if(oldNode->val==1) { 
                    kv.erase(key);
                } else { 
                    auto newNode = next(oldNode, -1);
                    if(oldNode==List.begin() || newNode->val<oldNode->val-1){ 
                        newNode = List.insert(oldNode, Node(oldNode->val-1));
                    }
                    newNode->container.insert(key);
                    kv[key] = newNode;
                }
    
                oldNode->container.erase(key);
                if(oldNode->container.empty()){ 
                    List.erase(oldNode);
                }
            }
        }
    
        /** Returns one of the keys with maximal value. */
        string getMaxKey() { 
            if(List.empty()) return "";
            return *List.rbegin()->container.begin();
        }
    
        /** Returns one of the keys with Minimal value. */
        string getMinKey() { 
            if(List.empty()) return "";
            return *List.begin()->container.begin();
        }
    };

1.  最小基因变化  
    现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。

**依次从基因库找变换一个字母可以构成的，然后删除基因库中的对应基因，继续查找直至找到或者找不到**

class Solution { 
    public:
    	int Dif_num(string& s1, string& s2){ 
    		int cnt = 0;
    		for (int i = 0; i < s1.size(); i++){ 
    			if (s1[i] != s2[i])cnt++;
    		}
    		return cnt;
    	}
    	int minMutation(string start, string end, vector<string>& bank) { 
    		queue<string>qu;
    		qu.push(start);
    		int res = 0;
    		unordered_map<string, int>vis;
    		while (!qu.empty()){ 
    			int size = qu.size();
    			for (int i = 0; i < size; i++){ 
    				string cur = qu.front();
    				vis[cur] = 1;
    				qu.pop();
    				if (cur == end)return res;
    				for (int i = 0; i < bank.size(); i++){ 
    					if (Dif_num(cur, bank[i]) == 1 && !vis[bank[i]]){ 
    						qu.push(bank[i]);
    					}
    				}
    			}
    			res++;
    		}
    		return -1;
    	}
    };

1.  字符串中的单词数  
    统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

**考察一个边界条件，十分简单了**

class Solution { 
    public:
        int countSegments(string s) { 
            int ret = 0;
    
            if (s.size() == 0) 
                return ret;
            else if (s[0] != ' ') 
                ret++;
    
            for (int i  = 0; i < s.size() - 1; i++)
            { 
                if (s[i] == ' ' && s[i + 1] != ' ') 
                { 
                    ret++;
                    i++;
                }
            }
            return ret;
        }
    };

1.  无重叠区间  
    给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

**贪心算法的经典运用。先排序，然后挨个判断：如果包含关系则取小的，如果交错则抛弃后者，如果不相交则都存着**

class Solution { 
    public:
        int eraseOverlapIntervals(vector<vector<int>>& intervals) 
        { 
            if (intervals.empty()) return 0;
            sort(intervals.begin(), intervals.end());
            int left = intervals[0][1];
            int res = 0;
            for (int i = 1; i < intervals.size(); ++i) { 
                if (intervals[i][0] < left) { 
                    ++res;
                    left = min(left, intervals[i][1]);
                } else { 
                    left = intervals[i][1];
                }
            }
            return res;
        }
    };

1.  寻找右区间  
    给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。

**分别存两份数组以区间起点和终点排序，然后进行比较得出右侧区间**

// 利用两个数组，分别排序起点和终点位置
    class Solution { 
    public:
        vector<int> findRightInterval(vector<vector<int>>& intervals) { 
            vector<pair<int, int>> start;
            vector<pair<int, int>> end;
            int len = intervals.size();
            for(int i = 0; i < len; i++){ 
                start.push_back(make_pair(intervals[i][0], i));
                end.push_back(make_pair(intervals[i][1],i));
            }
            sort(start.begin(), start.end());
            sort(end.begin(), end.end(),[](pair<int, int> p1, pair<int, int> p2){ 
                if(p1.first == p2.first)
                    return p1.second < p2.second;
                return p1.first < p2.first;//如果两个终点相同，会返回那个索引小的
            });
            vector<int> ans(len, -1);
            int indexS = 0;
            int indexE = 0;
            while(indexS < len && indexE < len){ 
                while(indexS < len && (start[indexS].second == end[indexE].second || start[indexS].first < end[indexE].first))
                    indexS++;
                if(indexS < len)
                    ans[end[indexE++].second] = start[indexS].second;
            }
            return ans;
        }
    };

1.  路径总和3  
    给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。

**使用前缀和记录从而减小内存消耗，只需遍历一次树即可。**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution { 
    public:
        unordered_map<int, int> m;
        int sum, res = 0;
    public:
        void dfs(TreeNode* root, int cur_sum)
        { 
            if (root == nullptr) return;
            if (m.count(cur_sum - sum))
                res += m[cur_sum - sum];
            m[cur_sum] ++;
            if (root->left)  dfs(root->left, cur_sum + root->left->val);
            if (root->right) dfs(root->right, cur_sum + root->right->val);
            m[cur_sum]--;
        }
        int pathSum(TreeNode* root, int sum) 
        { 
            if (root == nullptr) return 0;
            this->sum = sum;
            // 构建前缀和
            m[0] = 1;
            dfs(root, root->val);
            return res;
        }
    };

1.  找到字符串中所有字母异位词  
    给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

**采用双指针滑动，用一个字典数组保存P的特征，滑动的过程中–，如果恰好为0且长度相等则说明找到了，否则滑动指针并++**

class Solution { 
    public:
        vector<int> findAnagrams(string s, string p) { 
            vector<int> res;
            int m[128] = { 0};
            int left = 0, right = 0, need = 0;
            for (char c : p)
                ++m[c];
            while (right < s.size())
            { 
                if (m[s[right]] > 0)     ++need;
                --m[s[right]];
                ++right;
                while (need == p.size())
                { 
                    if (right - left == p.size())   
                        res.push_back(left);      //通过长度判断异位词，加入res中
                    if (m[s[left]] == 0)     
                        --need;
                    ++m[s[left]];
                    ++left;
                }
            }
            return res;
        }
    };