leetcode解题思路分析（二十三）155 - 167题

蔚落 2023-05-21 08:57 40阅读 0赞

1.  最小栈  
    实现一个栈，可以常数时间返回最小值

**很简单的一道题，没啥说的**

class MinStack { 
    public:
        /** initialize your data structure here. */
        MinStack() { }
        
        void push(int x) { 
            if(x < min) { 
                min = x;
            }
    
            minStack.push(make_pair(min, x));
        }
        
        void pop() { 
            minStack.pop();
            if (minStack.empty()) { 
                min = INT_MAX;
            } else { 
                min = minStack.top().first;
            }
        }
        
        int top() { 
            return minStack.top().second;
        }
        
        int getMin() { 
            return minStack.top().first;
        }
    
    private:
        int min = INT_MAX;
        stack<pair<int, int>> minStack;
    };

1.  相交链表

**本题的思路主要是用两个指针分别指向A/B首部，以同样速度向后滑动，滑到尾部后指向另一个链表再次滑动。如果二者相交且不为NULL则说明有交点，否则说明不相交。  
数学思路主要是：ptrA走了a独有的+公共部分+b独有的，而ptrB走了b独有的+公共部分+a独有的，速度相同路程相同必定相交。如果交点为NULL说明公共部分为0**

class Solution { 
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 
            ListNode *ptrA = headA, *ptrB = headB;
            while (ptrA != ptrB)
            { 
                ptrA = ptrA ? ptrA->next: headB;
                ptrB = ptrB ? ptrB->next: headA;
            }
            return ptrA;      
        }
    };

1.  寻找峰值  
    峰值元素是指其值大于左右相邻值的元素。  
    给定一个输入数组 nums，其中 nums\[i\] ≠ nums\[i+1\]，找到峰值元素并返回其索引。  
    数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

**采取二分查找，大的那一侧必存在峰值**

int findPeakElement(int* nums, int numsSize)
    { 
        int left = 0;
        int right = numsSize - 1;
        while(left < right)
        { 
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1])
            { 
                right = mid;
            }
            else
            { 
                left = mid + 1;
            }
        }
        return left;
    }

1.  最大间距  
    给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。  
    如果数组元素个数小于 2，则返回 0。

**（1）最简单的做法是调用stl自带的排序，然后遍历一遍获取最大值。**

class Solution 
    { 
    public:
        int maximumGap(vector<int>& nums)
         { 
            if (nums.size() < 2)
                return 0;
    
            sort(nums.begin(), nums.end());
            int max = 0;
            for (int i = 1; i < nums.size(); i++)
            { 
                int tmp = nums[i] - nums[i - 1];
                if (tmp > max)
                    max = tmp;
            }
            return max;
        }
    };

**（2）采用桶排序的方式求解**

class Solution { 
    public:
    class Bucket
    { 
    public:
        bool used = false;
        int minval = numeric_limits<int>::max();        // same as INT_MAX
        int maxval = numeric_limits<int>::min();        // same as INT_MIN
    };
    
    int maximumGap(vector<int>& nums)
    { 
        if (nums.empty() || nums.size() < 2)
            return 0;
    
        int mini = *min_element(nums.begin(), nums.end()),
            maxi = *max_element(nums.begin(), nums.end());
    
        int bucketSize = max(1, (maxi - mini) / ((int)nums.size() - 1));        // bucket size or capacity
        int bucketNum = (maxi - mini) / bucketSize + 1;                         // number of buckets
        vector<Bucket> buckets(bucketNum);
    
        for (auto&& num : nums) 
        { 
            int bucketIdx = (num - mini) / bucketSize;                          // locating correct bucket
            buckets[bucketIdx].used = true;
            buckets[bucketIdx].minval = min(num, buckets[bucketIdx].minval);
            buckets[bucketIdx].maxval = max(num, buckets[bucketIdx].maxval);
        }
    
        int prevBucketMax = mini, maxGap = 0;
        for (auto&& bucket : buckets) 
        { 
            if (!bucket.used)
                continue;
    
            maxGap = max(maxGap, bucket.minval - prevBucketMax);
            prevBucketMax = bucket.maxval;
        }
    
        return maxGap;
    }
    
    
    };

1.  比较版本号  
    比较两个版本号 version1 和 version2。  
    如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。

**采取两个队列读取比较即可**

class Solution { 
    public:
        int compareVersion(string version1, string version2) { 
            queue<int> v1, v2;
    
            //提取数字
            __getQueue(v1, version1);
            __getQueue(v2, version2);       
    
            //补齐
            if (v1.size() < v2.size())
            { 
                while (v1.size() != v2.size())
                    v1.push(0);
            }
            else if (v1.size() > v2.size())
            { 
                while (v1.size() != v2.size())
                    v2.push(0);
            }
    
            //逐个取出，判断大小
            while (!v1.empty())
            { 
                if (v1.front() > v2.front())return 1;
                else if (v1.front() < v2.front()) return-1;
                v1.pop(); v2.pop();
            }
            return 0;
        }
    
    private:
        void __getQueue(queue<int> &q, string s)
        { 
            string tmp;
    
            for (auto c : s)
            { 
                if (c != '.')
                    tmp += c;
                else
                { 
                    q.push(stoi(tmp));
                    tmp.clear();
                }
            }
            if (tmp != "") 
                q.push(stoi(tmp));
    
            return;
        }
    };

1.  分数到小数

class Solution { 
    public:
        //小数部分如果余数出现两次就表示该小数是循环小数了
        string fractionToDecimal(int numerator, int denominator) { 
            if(denominator==0) return "";//边界条件，分母为0
            if(numerator==0) return "0";//边界条件，分子为0
            string result;
            
            //转换为longlong防止溢出
            long long num = static_cast<long long>(numerator);
            long long denom = static_cast<long long>(denominator);
            
            //处理正负号，一正一负取负号
            if((num>0)^(denom>0))result.push_back('-');
            
            //分子分母全部转换为正数
            num=llabs(num);denom=llabs(denom);
            
            //处理整数部分
            result.append(to_string(num/denom));
            
            //处理小数部分
            num%=denom;                         //获得余数
            if(num==0)return result;             //余数为0，表示整除了，直接返回结果
            result.push_back('.');              //余数不为0，添加小数点
            int index=result.size()-1;          //获得小数点的下标
            unordered_map<int,int> record;      //map用来记录出现重复数的下标，然后将'('插入到重复数前面就好了
            while(num&&record.count(num)==0){    //小数部分：余数不为0且余数还没有出现重复数字
                record[num]=++index;
                num*=10;                        //余数扩大10倍，然后求商，和草稿本上运算方法是一样的
                result+=to_string(num/denom);
                num%=denom;
            }
            if(record.count(num)==1){            //出现循环余数，我们直接在重复数字前面添加'(',字符串末尾添加')'
                result.insert(record[num],"(");
                result.push_back(')');
            }
            return result;
        }
    };

1.  两数之和2  
    给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。  
    函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。  
    **本题采用暴力搜索可解，但是时间复杂度高。采用哈希表也可以，但是空间复杂度高。最优解法为采取双指针滑动。因为题意说明了是排序数组而且必有唯一解，因此这是最佳解法**

class Solution { 
    public:
        vector<int> twoSum(vector<int>& numbers, int target) { 
            int low = 0, high = numbers.size() - 1;
            while (low < high) { 
                int sum = numbers[low] + numbers[high];
                if (sum == target)
                    return { low + 1, high + 1};
                else if (sum < target)
                    ++low;
                else
                    --high;
            }
            return { -1, -1};
        }
    };