leetcode解题思路分析（三十）214—220题

一时失言乱红尘 2023-02-18 09:56 8阅读 0赞

1.  最短回文串  
    给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

**本题可以用马拉车去取最长回文子串，然后反向添加。也可以采用KMP解决**

class Solution { 
    public:
        string shortestPalindrome(string s)
        { 
            int n = s.size();
            string rev(s);
            reverse(rev.begin(), rev.end());
            string s_new = s + "#" + rev;
            int n_new = s_new.size();
            vector<int> f(n_new, 0);
            for (int i = 1; i < n_new; i++) { 
                int t = f[i - 1];
                while (t > 0 && s_new[i] != s_new[t])
                    t = f[t - 1];
                if (s_new[i] == s_new[t])
                    ++t;
                f[i] = t;
            }
            return rev.substr(0, n - f[n_new - 1]) + s;
        }
    };

1.  数组中的第K个最大元素  
    在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

**看到K个元素就知道堆一定可以解决，除此之外还可以使用选择算法解决。选择算法的思路是通过分治**

#include <stdio.h>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    class Solution
    { 
    public:
        int findKthLargest(vector<int> &nums, int k)
        { 
            int result = 0;
            int numsSize = int(nums.size());
            if (numsSize == 0 || k > numsSize)
            { 
                return 0;
            }
            //寻找第kMIN小的数
            int kMin = numsSize - k + 1;
            result = select(nums, 0, numsSize - 1, kMin);
            return result;
        }
    
        int select(vector<int> &nums, int left, int right, int target)
        { 
            if (left == right)
            { 
                return nums[left];
            }
            int cut = partition(nums, left, right);
            //当前第currentResult小的元素
            int currentResult = cut - left + 1;
            if (target == currentResult)
            { 
                return nums[cut];
            }
            else if (target < currentResult)
            { 
                return select(nums, left, cut - 1, target);
            }
            else
            { 
                //寻找接下来第target - currentResult小的数
                return select(nums, cut + 1, right, target - currentResult);
            }
            return 0;
        }
    
        int partition(vector<int> &nums, int left, int right)
        { 
            int cut = nums[right];
            //i指向大堆的最左边的数，j指向下一个判断的数
            int i = left;
            for (int j = left; j < right; j++)
            { 
                if (nums[j] <= cut)
                { 
                    exchange(nums[i], nums[j]);
                    i++;
                }
            }
            exchange(nums[i], nums[right]);
            return i;
        }
    
        void exchange(int &a, int &b)
        { 
            int tmpInt = a;
            a = b;
            b = tmpInt;
            return;
        }
    };

1.  组合总和3  
    找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

**本题采用回溯法可以轻松得解**

class Solution { 
    public:
        vector<vector<int>> combinationSum3_dfs(int k, int n, int now, int status) { 
            if(k == 0 && n == 0) {   //一个有用的结果
                vector<int> res;
                for(int i = 1; i < 10; i++) { 
                    if((2 << i) & status) res.push_back(i);
                }
                return { res};
            }
            vector<vector<int>> res;
            while(now < 10 && n >= now) {    //能够继续dfs的条件
                auto r = combinationSum3_dfs(k - 1, n - now, now + 1, status | (2 << now));
                res.insert(res.end(), r.begin(), r.end()); //结果合并
                now++;
            }
            return res;
        }
        vector<vector<int>> combinationSum3(int k, int n) { 
            return combinationSum3_dfs(k, n, 1, 0);
        }
    };

1.  存在重复元素  
    给定一个整数数组，判断是否存在重复元素。  
    如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

**很简单的题，哈希表存储查找即可**

class Solution { 
    public:
        bool containsDuplicate(vector<int>& nums) { 
            std::unordered_map<int, int> map;
            for (auto i : nums)
            { 
                map[i]++;
                if (map[i] > 1)
                    return true;
            }
            return false;
        }
    };

1.  天际线问题

**本题有多种解法：最直观的解法就是采取扫描线从左向右扫描一遍，比较当前X轴中保存的各个高度，输出最高值。同样的我们也可以使用双向链表来进行扫描。除此之外，还可以采取分治的思想：没有建筑为0，有一个建筑则为该值，有多个则分治。**

class Solution { 
    public:
        vector<vector<int>> getSkyline(vector<vector<int>>& buildings) { 
            multiset<pair<int, int>> all;
            vector<vector<int>> res;
            
            for (auto& e : buildings) { 
                all.insert(make_pair(e[0], -e[2])); // critical point, left corner
                all.insert(make_pair(e[1], e[2])); // critical point, right corner
            }
            
            multiset<int> heights({ 0}); // 保存当前位置所有高度。
            vector<int> last = { 0, 0}; // 保存上一个位置的横坐标以及高度
            for (auto& p : all) { 
                if (p.second < 0) heights.insert(-p.second); // 左端点，高度入堆
                else heights.erase(heights.find(p.second)); // 右端点，移除高度
                
                // 当前关键点，最大高度
                auto maxHeight = *heights.rbegin();
                
                // 当前最大高度如果不同于上一个高度，说明这是一个转折点
                if (last[1] != maxHeight) { 
                    // 更新 last，并加入结果集
                    last[0] = p.first;
                    last[1] = maxHeight;
                    res.push_back(last);
                }
            }
            
            return res;
        }
    };

1.  存在重复元素2  
    给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums \[i\] = nums \[j\]，并且 i 和 j 的差的 绝对值 至多为 k。

**和第一题一样很简单，哈希表直接解决，但是这里有一个优化细节：我们不需要存储所有的数字，只需要用一个大小为k的滑动窗口即可**

class Solution { 
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) { 
            unordered_map<int, vector<int>> map;
            for (int i = 0; i < nums.size(); i++)
            { 
                map[nums[i]].push_back(i);
                if (map[nums[i]].size() > 1)
                { 
                    for (int j = 1; j < map[nums[i]].size(); j++)
                    { 
                        if (map[nums[i]][j] - map[nums[i]][j - 1] <= k)
                            return true;
                    }
                }
            }
            return false;
        }
    };

1.  存在重复元素3  
    在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums \[i\] 和 nums \[j\] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。  
    如果存在则返回 true，不存在返回 false。

**本题有多种解法，较为优秀的方法是桶排序的思想或者滑动窗口的方式求解**

class Solution { 
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { 
            if (k < 1 || t < 0 || nums.empty()) return false;
            int N = nums.size();
            map<long, int> m{ { nums[0], 1}};
            for (int i = 1; i < N; ++i) { 
                auto it = m.lower_bound(nums[i]);
                if (it != m.end() && abs(it->first - (long)nums[i]) <= t) return true;
                if (it != m.begin() && abs((--it)->first - (long)nums[i]) <= t)  return true;
                ++m[nums[i]];
                if (i - k >= 0 && --m[nums[i - k]] == 0) m.erase(nums[i - k]);
            }
            return false;
        }
    };