LeetCode高级算法之数学与其他

客官°小女子只卖身不卖艺 2022-12-28 14:04 100阅读 0赞

[179. Largest Number][]

比较最大数的问题， 很容易想到应该把首位越大的数排到前面， 关键在于首位相同的话如何比较两个字符串的大小，

一个很直观的想法就是s1 + s2和 s2 + s1， 两个相比，谁大谁在前， 证明有点复杂， 可以把字符串按幂转换成一个整数来比较， 也可以尝试反证法， 具体见题解区

要注意的边界条件是多个0的情况， 最后只留下一个0，代码如下

class Solution {
    public:
        static bool mycmp(const string& s1, const string& s2)  //这里要写成静态函数， 成员函数无法传给sort的第三个参数
        {
            string ss1 = s1 + s2;
            string ss2 = s2 + s1;
            return ss1 > ss2;
        }
        string largestNumber(vector<int>& nums) {
            vector<string>vs;
            if (nums.empty()) return "";
            for (int x:nums)
            {
                vs.push_back(to_string(x));
            }
            sort(vs.begin(), vs.end(), mycmp);
            string ans = "";
            ans = accumulate(vs.begin(), vs.end(), ans);
            int i=0;
            while (i<ans.length() && ans[i]=='0') ++i;     // 处理多个0的情况， 其实可以在sort后面判断，第一个数为‘0’表示全为0
            ans = string(ans.begin()+i, ans.end());
            if (ans.empty()) ans = "0";
            return ans;
    
        }
    };

[149. Max Points on a Line][]

找在一条直线上的点的最多的数量， 很新颖的一道题， 唯一能想到的就是暴力法， 计算每个点与其他点的连线的斜率， 用几个特殊值来区分同一个点和斜率不存在的点

还有一个要注意点就是用double来表示斜率时精度的问题， 目前看到的解决方案有1. 给结果乘一个大数， 2.用分数约分后表示， 第2种方法要解决一个负数在分子还是分母的情况

据说有nlogn的解法， 留着以后慢慢研究

代码如下：

class Solution {
    public:
        int maxPoints(vector<vector<int>>& points) {
            int size = points.size();
            int ans = 0;
            for (int i=0; i<size; ++i)
            {
                unordered_map<double, int>mmap;
                int cnt = 0;
                for (int j=i; j<size; ++j)
                {
                    double temp;
                    auto p1 = points[i];
                    auto p2 = points[j];
                    if(p1==p2)
                    {
                        temp = INT_MIN;        //用 INT_MIN来表示起始点相同的点
                        
                    }
                    else
                    {
                        temp = (p1[0]==p2[0])? INT_MAX: 1000000.0*(p2[1]-p1[1])/(p2[0]-p1[0]);    // 处理精度问题
                    }
                    mmap[temp]++;
                }
                for (auto &pr: mmap)
                {
                    if(pr.first != INT_MIN) cnt = max(cnt, pr.second);
                }
                ans = max(ans, cnt+mmap[INT_MIN]);
    
            }
            
            return ans;
    
        }
    };

[406. Queue Reconstruction by Height][]

根据身高重新排队， 首先想到的是从低到高排列， 然后根据从低到高在空队列里插空，要注意同身高的顺序如何排列的情况， 从高到低的思路同理

代码如下：

class Solution {
    public:
        vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
            int size = people.size();
            vector<vector<int>>ans(size, vector<int>());
            sort(people.begin(), people.end());         // 先比较身高， 再比较序号
            int preheight = -1;
            for (int i=0; i<size; ++i)
            {
                auto person = people[i];
                int step = person[1];
                int tempheight = person[0];
                for (int j=0; j<size; ++j)
                {
                    if (step==0 && ans[j].empty())
                    {
                        ans[j] = person;
                        break;
                    }
                    if ((ans[j].empty() || ans[j][0]==tempheight) && step>0 ) --step;
                }
            }
            return ans;
    
        }
    };

[42. Trapping Rain Water][]

接雨水经典问题，一旦出现根据“凹槽”判断的情况， 都可以考虑使用单调栈， 能接到的雨水取决于凹槽两边的柱子中较低的那根， 要注意往上走的一半和往下走的一半；

另外还有双指针法， 说实话面试的时候一下子真的不好想出来， 老老实实用单调栈吧，先学会通用方法在折腾奇技淫巧

另外还有一个进阶的3D版接雨水， 思路完全不一样 ，不能被这个2D的带跑偏了

class Solution {
    public:
        int count_water(vector<int>&height, int start ,int end)
        {
            int ret = 0;
            int target = min(height[start], height[end]);
            for (int i=start+1; i<end; ++i)
            {
                ret += target - height[i];
            }
            return ret;
        }
        int trap(vector<int>& height) {
            int size = height.size();
            if (size==0) return 0;
            int premax = height[0], preidx = 0;    // 利用premax省去了建单调栈， 空间复杂度降为常数
            int ans = 0;
            for (int i=1; i<size; ++i)
            {
                if (height[i]>=premax)
                {
                    ans += count_water(height, preidx, i);
                    premax = height[i];
                    preidx = i;
                }
            }
            int maxidx = preidx;
            premax = height[size-1], preidx = size-1;
            for (int i=size-1; i>=maxidx; --i)
            {
                if (height[i]>=premax)
                {
                    ans += count_water(height, i, preidx);
                    premax = height[i];
                    preidx = i;
                }
            }
            return ans;
        }
    };

[218. The Skyline Problem][]

天际线问题， 这种问题以前从来没见识过， 做一下算是长长见识了， 关键思路，

1.每次都是去当前横坐标里纵坐标最高的点作为转折点；

2.遇到建筑的右端点要先把高度删除再来判断最高点

3.相同横坐标有多个建筑， 要先把所有的纵坐标根据是起始点还是终结点在height数组里处理后再来判断最高点

高度数组建议用multiset, 判断左端点还是右端点可以用+height和-height来区分， 也可以维护一个endpoint数组

class Solution {
    public:
        vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
            multiset<int>heights;        // 存放高度
            vector<pair<int,int>>points;    // 存放当前遍历到的所有点
            vector<vector<int>>ans;        
            for (auto& build: buildings)
            {
                int start = build[0], end = build[1], height = build[2];
                points.push_back(make_pair(start, -height));    // 负数表示起始点， 正数表示终结点
                points.push_back(make_pair(end, height));
            }
            sort(points.begin(), points.end());
            int preheight = -1;
            for (int i=0; i<points.size(); ++i)
            {
                auto point = move(points[i]);
                int idx = point.first, yidx = point.second;
                if(yidx<0) heights.insert(-yidx);        // 起始点， 加入高度
                else heights.erase(heights.find(yidx));    // 终结点， 移除高度， 这里不能根据值erase， 否则会把所有的值全部删除
                if(i+1 < points.size() && points[i+1].first==idx) continue;    // 下一个点横坐标相同， 要一起处理
                int tempheight = heights.empty()? 0 : *(heights.rbegin());
                if (tempheight!=preheight)
                {
                    vector<int>temp = {idx, tempheight};
                    ans.push_back(temp);
                    preheight = tempheight;
                }
            }
            return ans;
        }
    };

[84. Largest Rectangle in Histogram][]

有点像粉刷问题， 其实这题利用单调栈也得好好想想什么样的情况能得到最大的面积， 直觉上来看一个柱子能得到的最大面积就是向左扫描和向右扫描直到出现小于自己高度的柱子， 用 高度\*宽度

单调栈实际上是解决了快速找到右边边界的问题， 同时由于其单调的特性， 左边的边界也能快速找到， 唯一要注意的一个点就是栈为空时存在把前面比较高的柱子忽略的情况，

一个用例\[5 ,4 ,1 ,2\]， 如果不注意的前面的5被出栈了的话， 4这根柱子能得到的面积只能算作4\*1， 而不是4\*2，从而得到错误的解，

比较巧妙的方法就是用哨兵， 前面放一个哨兵，高度要确保比所有的柱子低（也就是不会出栈）， 这样就能确保找到正确的左边界

右边放一个哨兵的好处就是可以确保原数组中所有的数据都已出栈，所有的高度都已经经过计算， 不会漏解；

代码如下

class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            stack<int>acending;
            heights.insert(heights.begin(), 0);    // 可以在原数组中插入1， 也可以在栈中放一个下标为-1的虚拟值
            heights.push_back(0);
            int size = heights.size();
            int ans = -1;
            int minele;
            for(int i=0; i<size; ++i)
            {
                if (acending.empty())
                {
                    acending.push(i);
                    ans = max(ans, heights[i]);
                }
                else
                {
                    if(heights[i] >= heights[acending.top()])
                    {
                        acending.push(i);
                    }
                    else
                    {
                        while(heights[acending.top()]>heights[i])
                        {
                            int idx = acending.top();
                            acending.pop();
                            int startidx = acending.top()+1;
                            int temp = heights[idx] * (i-startidx);
                            ans = max(ans, temp);
                            
                        }
                        acending.push(i);
                    }
                }
            }
            // 下面的代码由于哨兵的加入可以省略，可见哨兵的作用杠杠滴
            // while (!acending.empty())
            // {
            //     int idx = acending.top();
            //     acending.pop();
            //     if(acending.empty())
            //     {
            //         minele = heights[idx];
            //         break;
            //     }
            //     int temp = heights[idx] * (size-acending.top()-1);
            //     ans = max(ans, temp);
            // }
            // ans = max(ans, minele * size);
            return ans;
        }
    };

[179. Largest Number]: https://leetcode-cn.com/problems/largest-number/
[149. Max Points on a Line]: https://leetcode-cn.com/problems/max-points-on-a-line/
[406. Queue Reconstruction by Height]: https://leetcode-cn.com/problems/queue-reconstruction-by-height/
[42. Trapping Rain Water]: https://leetcode-cn.com/problems/trapping-rain-water/
[218. The Skyline Problem]: https://leetcode-cn.com/problems/the-skyline-problem/
[84. Largest Rectangle in Histogram]: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/