leetcode解题思路分析（八十二）718 - 724 题

叁歲伎倆 2022-10-12 06:00 174阅读 0赞

1.  最长重复子数组  
    给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

**哈希记录位置，滑动窗口查询子数组。**

class Solution { 
    public:
        const int mod = 1000000009;
        const int base = 113;
        
        // 使用快速幂计算 x^n % mod 的值
        long long qPow(long long x, long long n) { 
            long long ret = 1;
            while (n) { 
                if (n & 1) { 
                    ret = ret * x % mod;
                }
                x = x * x % mod;
                n >>= 1;
            }
            return ret;
        }
    
        bool check(vector<int>& A, vector<int>& B, int len) { 
            long long hashA = 0;
            for (int i = 0; i < len; i++) { 
                hashA = (hashA * base + A[i]) % mod;
            }
            unordered_set<long long> bucketA;
            bucketA.insert(hashA);
            long long mult = qPow(base, len - 1);
            for (int i = len; i < A.size(); i++) { 
                hashA = ((hashA - A[i - len] * mult % mod + mod) % mod * base + A[i]) % mod;
                bucketA.insert(hashA);
            }
            long long hashB = 0;
            for (int i = 0; i < len; i++) { 
                hashB = (hashB * base + B[i]) % mod;
            }
            if (bucketA.count(hashB)) { 
                return true;
            }
            for (int i = len; i < B.size(); i++) { 
                hashB = ((hashB - B[i - len] * mult % mod + mod) % mod * base + B[i]) % mod;
                if (bucketA.count(hashB)) { 
                    return true;
                }
            }
            return false;
        }
    
        int findLength(vector<int>& A, vector<int>& B) { 
            int left = 1, right = min(A.size(), B.size()) + 1;
            while (left < right) { 
                int mid = (left + right) >> 1;
                if (check(A, B, mid)) { 
                    left = mid + 1;
                } else { 
                    right = mid;
                }
            }
            return left - 1;
        }
    };

1.  找出第K小的距离  
    给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

**排序后采用二分法查找**

class Solution { 
    public:
        int smallestDistancePair(vector<int>& nums, int k) { 
            sort(nums.begin(), nums.end());
            int min = 0, max = nums.back() - nums.front();
            while (min < max) { 
                int mid = (min + max) / 2;
                int count = 0;
                for (int l = 0, r = 0; r < nums.size(); r++) { 
                    while (l < r && nums[r] - nums[l] > mid) l++;
                    count += r - l;
                }
                if (count >= k)
                    max = mid;
                else
                    min = mid + 1;
            }
            return min;
        }
    };

1.  词典中最长的单词  
    给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。

**采用前缀树求解**

short Data[26000]={ 0},cnt;
    short idxes[31000];
    short idxes_cnt[32];
    
    bool insert(string&word,int signal){ 
        int cur=0;
        for(char*c=&word[0];*c;++c){ 
            if(!Data[cur*26+*c-'a']){ 
                if(*(c+1))return false;
                Data[cur*26+*c-'a']=cnt++;
            }
            else{ 
                cur=Data[cur*26+*c-'a'];
            }
        }
        return true;
    }
    
    class Solution { 
    public:
        string longestWord(vector<string>& words) { 
            memset(idxes_cnt,0,sizeof(idxes_cnt));
            for(int i=0;i<words.size();i++){ 
                int l=words[i].size();
                idxes[l*1000+idxes_cnt[l]++]=i;
            }
            cnt=1;
            int ans=-1;
            for(int l=1;idxes_cnt[l];l++){ 
                int res=-1;
                for(int j=0;j<idxes_cnt[l];j++){ 
                    int i=idxes[l*1000+j];
                    if(insert(words[i],i)){ 
                        if(res<0||words[i]<words[res]){ 
                            res=i;
                        }
                    }
                }
                if(res<0)break;
                ans=res;
            }
            memset(Data,0,cnt*26*sizeof(short));
            return ans>=0?move(words[ans]):"";
        }
    };

1.  账户合并  
    给定一个列表 accounts，每个元素 accounts\[i\] 是一个字符串列表，其中第一个元素 accounts\[i\]\[0\] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。  
    合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按字符 ASCII 顺序排列的邮箱地址。账户本身可以以任意顺序返回。

**并查集的使用**

class UnionFind { 
    public:
        vector<int> parent;
    
        UnionFind(int n) { 
            parent.resize(n);
            for (int i = 0; i < n; i++) { 
                parent[i] = i;
            }
        }
    
        void unionSet(int index1, int index2) { 
            parent[find(index2)] = find(index1);
        }
    
        int find(int index) { 
            if (parent[index] != index) { 
                parent[index] = find(parent[index]);
            }
            return parent[index];
        }
    };
    
    class Solution { 
    public:
        vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) { 
            map<string, int> emailToIndex;
            map<string, string> emailToName;
            int emailsCount = 0;
            for (auto& account : accounts) { 
                string& name = account[0];
                int size = account.size();
                for (int i = 1; i < size; i++) { 
                    string& email = account[i];
                    if (!emailToIndex.count(email)) { 
                        emailToIndex[email] = emailsCount++;
                        emailToName[email] = name;
                    }
                }
            }
            UnionFind uf(emailsCount);
            for (auto& account : accounts) { 
                string& firstEmail = account[1];
                int firstIndex = emailToIndex[firstEmail];
                int size = account.size();
                for (int i = 2; i < size; i++) { 
                    string& nextEmail = account[i];
                    int nextIndex = emailToIndex[nextEmail];
                    uf.unionSet(firstIndex, nextIndex);
                }
            }
            map<int, vector<string>> indexToEmails;
            for (auto& [email, _] : emailToIndex) { 
                int index = uf.find(emailToIndex[email]);
                vector<string>& account = indexToEmails[index];
                account.emplace_back(email);
                indexToEmails[index] = account;
            }
            vector<vector<string>> merged;
            for (auto& [_, emails] : indexToEmails) { 
                sort(emails.begin(), emails.end());
                string& name = emailToName[emails[0]];
                vector<string> account;
                account.emplace_back(name);
                for (auto& email : emails) { 
                    account.emplace_back(email);
                }
                merged.emplace_back(account);
            }
            return merged;
        }
    };

1.  删除注释  
    删除源码中的注释

**逐步处理即可**

class Solution { 
    public:
        vector<string> removeComments(vector<string>& source) { 
            bool isComment = false;
            vector<string> res;
            string curr = "";
            for (string s : source)
            { 
                // cout << s << endl;
                int i = 0;
                if (!isComment)
                { 
                    curr = "";
                }
                int n = s.size();
                while (i < n)
                { 
                    if (!isComment && i < n-1 && s[i] == '/' && s[i+1] == '*')
                    { 
                        isComment = true;
                        // 继续找下去,这里实际要+2，但是后面会+1
                        ++i;
                    }
                    else if (isComment && i < n-1 && s[i] == '*' && s[i+1] == '/')
                    { 
                        isComment = false;
                        // 继续找下去,这里实际要+2，但是后面会+1
                        ++i;
                    }
                    else if (!isComment && i < n-1 && s[i] == '/' && s[i+1] == '/')
                    { 
                        break;
                    }
                    else if (!isComment)
                    { 
                        curr += s[i];
                        // cout << curr<< " " << endl;
                    }
                    
                    ++i;
                }
                if (!isComment && !curr.empty())
                { 
                    res.push_back(curr);
                }
            }
            return res;
        }
    };

1.  寻找数组的中心下标  
    给你一个整数数组 nums ，请计算数组的 中心下标 。数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

**累加之后遍历即可**

class Solution { 
    public:
        int pivotIndex(vector<int>& nums) 
        { 
            int sum = 0;
            int index = 0;
            int left = 0, right = 0;
    
            if (nums.size() == 0) return -1;
            for (auto n : nums)
            { 
                sum += n;
            }
    
            right = sum - nums[0];
            while (index < nums.size())
            { 
                if (left == right)
                { 
                    return index;
                }
    
                index++;
                left += nums[index - 1];
                right -= nums[index];
            }
            return -1;
        }
    };

1.  分隔链表  
    给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

**双指针快慢滑动则可以获取中间点，三指针可以获得三分点，由此类推即可**

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
    class Solution { 
    public:
        vector<ListNode*> splitListToParts(ListNode* root, int k) { 
            vector<ListNode*> ans(k, nullptr);
            ans[0] = root;
            /* 初始化指针数组，按顺序指向前k个结点 */
            for (int i = 1; i < k; ++i)
                if (ans[i - 1] != nullptr)
                    ans[i] = ans[i - 1]->next;
            /* 移动指针，数组下标为 i 的指针每次前进 i + 1 */
            while (ans[k - 1] != nullptr) { 
                for (int i = 0; i < k - 1; ++i) { 
                    ans[k - 1] = ans[k - 1]->next;
                    if (ans[k - 1] == nullptr) break;
                    for (int j = i; j < k - 1; ++j)
                        ans[j] = ans[j]->next;
                }
                if (ans[k - 1] != nullptr) ans[k - 1] = ans[k - 1]->next;
            }
            /* 此时链表已经由 k - 1 个指针划分为 k 段，数组中的指针均指向各段最后一个结点 */
            /* 将链表分割成 k 段，并将数组指针设为各段的头结点, 即上一段最后一个结点的next指针指向的结点 */
            for (int i = k - 1; i > 0; --i)
                if (ans[i - 1] != nullptr) { 
                    ans[i] = ans[i - 1]->next;
                    ans[i - 1]->next = nullptr;
                }
            /* 第一段的头结点为 root */
            ans[0] = root;
            return ans;
        }
    };