LeetCode专题训练：数组和字符串

传送门

之前忙着开学，有相当一段时间没有做题了，实在是罪过…

数组

t1寻找数组的中心索引

找到数组中的一个位置，这个位置之前的所有元素和等于这个位置之后的所有元素和。如果没有就返回-1。

感觉思路有点滑动窗口的味道。维护两个变量lsum与rsum，分别表示当前位置左边的元素和与右边的元素和，然后根据题意O(n)遍历判断就行了。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int rsum = 0, lsum = 0;
        const int n = nums.size();
        if(n == 0) return -1;

        for(auto& el: nums) rsum += el;

        rsum -= nums[0];
        if(rsum == 0) return 0;
        
        for(int i = 1; i < n; i++)
        {
            lsum += nums[i-1];
            rsum -= nums[i];
            if(rsum == lsum) return i;
        }

        return -1;
    }
};

需要注意一些细节问题。

t2搜索插入位置

给出一个有序数组与一个数，找到这个数的位置，如果找不到就找到它该插入的位置。

用一个set来判断存在，再用一次遍历找到插入(或这个数)的位置。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        set<int> ss(nums.begin(), nums.end());
        const int n = nums.size();
        
        if(!ss.count(target))
        {
            if(target < nums[0]) return 0;
            else if(target > nums[n-1]) return n;

            for(int i = 0; i < n - 1; i++)
            {
                if(nums[i] < target && nums[i+1] > target) return i+1;
            }
        }
        else
        {
            for(int i = 0; i < n; i++) if(nums[i] == target) return i;
        }

        return -1;

    }
};

t3合并区间

给出一个区间的集合，合并所有重叠的区间。

重叠显然指的是区间a的上界小于等于区间b的下界。

对interval数组以第一列元素为关键字升序排序，这样能确保如果当前的interval[i][0]都大于答案中最后一个区间的上界，那么剩下所有没遍历到的区间也满足这个关系。

那么现在就有两种情况：①当前遍历到的interval[i][0]大于答案中最后一个区间的上界，那么后面所有的区间都大于它，则当前区间与之前的区间不存在重叠关系，直接压入答案数组；②在情况①之外，说明当前区间与之前的区间存在交叉，那么只需要更新区间上界就可以了。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        const int n = intervals.size();
        vector<vector<int>> ans;
        if(!n) return {};

        sort(intervals.begin(), intervals.end());
        for(int i = 0; i < n; i++)
        {
            int l = intervals[i][0];
            int r = intervals[i][1];

            if(!ans.size() || ans.back()[1] < l)
                ans.push_back({l, r});
            else
                ans.back()[1] = max(ans.back()[1], r);
        }

        return ans;
    }
};