Skip to main content

1-数组-二分查找

二分查找类​

704. 二分查找​

我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

  • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid -1;
            else if (nums[mid] < target) left = mid + 1 ;
        }
        return -1;
    }
};

如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

有如下两点：

  • while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的

  • if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left = 0, right = nums.size();
            while (left <  right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] == target) return mid;
                else if (nums[mid] > target) right = mid;
                else if (nums[mid] < target) left = mid + 1;
            }
            return -1;
        }
    };

35. 搜索插入位置​

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0 , right = nums.size() -1;
        int mid = 0;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid -1;
            else if (nums[mid] < target) left = mid +1;
        }
        return left ;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置**​

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0 , right = nums.size() - 1;
        //查找满足条件的最小数字 left <= target
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        int l = left;
        //查找满足条件的最大数字 right >= target
        left = 0 , right = nums.size() - 1;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }
        if(l > right) return {-1,-1};
        return {l,right};
    }
};

//函数方法
upper_bound(nums.begin(),nums.end(),target);
lower_bound(nums.begin(),nums.end(),target);

69. x 的平方根 ​

class Solution {
public:
    int mySqrt(int x) {
        int left = 0 ,right = x;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if((long long) mid * mid == x) return mid;
            if((long long) mid * mid > x) right = mid - 1;
            else left = mid + 1;
        }
        return right;
    }
};

367. 有效的完全平方数​

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 0,right = num;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if((long long) mid * mid == num) return true;
            else if((long long) mid * mid < num) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};

33. 搜索旋转排序数组**​

注意这个else if判断

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            if(nums[left] == nums[mid]) left++;
            else if(nums[right] >= nums[mid])
            {
                if(target > nums[mid] && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
            else{
                if(target < nums[mid] && target >= nums[left]) right = mid - 1;
                else left = mid + 1;
            }
        }
        return -1;
    }
};

154. 寻找旋转排序数组中的最小值 II​

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = (left + right) / 2;
            if(nums[right] > nums[mid]) right = mid;
            else if(nums[right] < nums[mid])left = mid + 1;
            else right--;
        }
        return nums[right];
    }
};

540. 有序数组中的单一元素​

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            //cout << mid <<endl;
            if(mid > 0 && nums[mid] == nums[mid - 1])
            {
                //右边为偶数
                if((nums.size() - 1 - mid) % 2 == 0) right = mid;
                //左边为偶数
                else left = mid + 1;
            }
            else if(mid < nums.size() - 1 && nums[mid] == nums[mid + 1])
            {
                //左边为偶数
                if(mid  % 2 == 0) left = mid;
                //右边为偶数
                else right = mid -1; 
            }
            else return nums[mid];
        }
        return nums[mid];
    }
};

2300. 咒语和药水的成功对数​

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(),potions.end());
        vector<int> res;
        for(int x: spells)
        {
            if((long long) x * potions[0] > success )res.push_back(potions.size());
            else if((long long) x * potions.back() < success)res.push_back(0);
            else
            {
                int left = 0, right = potions.size() - 1;
                while(left <= right)
                {
                    int mid = (left + right) / 2;
                    if((long long) potions[mid] * x >= success) right = mid - 1;
                    else left = mid + 1;
                }

                res.push_back(potions.size() - left);
            }
        }
        return res;
    }
};

162. 寻找峰值*​

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        while(left < right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[mid + 1])  right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

剑指 Offer II 073. 狒狒吃香蕉​

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int right = 0;
        for(int x:piles) right = max(right,x);
        int left = 1;
        while(left <= right)
        {
            int speed = (left + right) / 2;
            int count = 0;
            for(int x:piles) count += (x / speed) + ((x % speed) > 0);
            if(count <= h) right = speed - 1;
            else  left = speed + 1;
        }
        return left;
    }
};

剑指 Offer 41. 数据流中的中位数​

class MedianFinder {
    vector<int> res;
public:
    /** initialize your data structure here. */
    MedianFinder() {
    }
    
    void addNum(int num) {
        auto x = lower_bound(res.begin(),res.end(),num);
        res.insert(x,num);
    }
    
    double findMedian() {
        if(res.size() % 2 == 1) return res[res.size() / 2];
        else return ((double)res[res.size() / 2] + res[res.size() / 2 - 1]) / 2;
    }
};

面试题 16.06. 最小差​

class Solution {
public:
    int smallestDifference(vector<int>& a, vector<int>& b) {
        sort(a.begin(),a.end());
        long res = INT_MAX;
        for(long x : b)
        {
            auto start = lower_bound(a.begin(),a.end(),x);
            if(start - a.begin() >= a.size()) res = min(res,abs(x - a.back()));
            else
            {
                res = min(res,abs(x - a[start - a.begin()]));
                if(start - a.begin() - 1 >= 0)
                    res = min(res,abs(x - a[start - a.begin() - 1]));
            }
            
        }
        return res;
    }
};

278. 第一个错误的版本​

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while(left < right)
        {
            int mid = ((long)left + right) / 2;
            cout << mid << " ";
            if(!isBadVersion(mid) && (mid == 0 || isBadVersion(mid - 1))) return mid;
            if(!isBadVersion(mid)) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

1095. 山脉数组中查找目标值*​

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        //首先找到山峰值
        int peek = 0 , left = 0 ,right = mountainArr.length() - 1;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            int mid_num = mountainArr.get(mid);
            int mid_num1;
            if(mid < mountainArr.length() - 1)mid_num1 = mountainArr.get(mid + 1);
            int mid_num2;
            if(mid > 0 )mid_num2 = mountainArr.get(mid - 1);
            if(mid > 0 && mid < mountainArr.length() - 1 &&
            mid_num > mid_num2 && mid_num > mid_num1)
            {
                peek = mid;
                break;
            }
            if(mid == 0 || mid_num > mid_num2) left = mid + 1;
            else right = mid - 1;
        }
        //山峰值
        //cout << peek <<endl;
        //峰值左侧 - 单调递增
        int rfind_left = -1 , rfind_right = -1;
        left = 0 ,right = peek;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            int mid_num = mountainArr.get(mid);
            if( mid_num == target)
            {
                rfind_left = mid;
                break;
            }
            else if(mid_num < target) left = mid + 1;
            else right = mid - 1;
        }
        //cout << rfind_left <<endl;

        //峰值左侧 - 单调递减
        left = peek ,right = mountainArr.length() - 1;;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            int mid_num = mountainArr.get(mid);
            if( mid_num == target)
            {
                rfind_right = mid;
                break;
            }
            else if(mid_num > target) left = mid + 1;
            else right = mid - 1;
        }
        //cout << rfind_right <<endl;
        if(rfind_right == -1) return rfind_left;
        else if(rfind_left == -1) return rfind_right;
        return min(rfind_left,rfind_right);
    }
};

1300. 转变数组后最接近目标值的数组和​

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(),arr.end());
        vector<int> part = arr;
        partial_sum(part.begin(),part.end(),part.begin());
        int left = 0 , right = target;
        int res = INT_MAX , pos = 0;

        while(left <= right)
        {
            int mid = (left + right) / 2;
            //查询数组中大于等于mid 的位置 m
            auto x = lower_bound(arr.begin(),arr.end(),mid);
            int m = x - arr.begin() ;
            int p;
            if(m == arr.size()) p = part.back();
            else p = part[m] - arr[m] +(arr.size() - m) * mid;

            //cout << mid << " " << m << " "<< p  << " "  <<endl;
            if(res > abs(target - p))
            {
                res = abs(target - p);
                pos = mid;
            }
            else if(res == abs(target - p)) pos = min(pos,mid);

            if((m == arr.size() && mid > arr.back()) || p > target) right = mid - 1;
            else left = mid + 1;
        }
        return pos;
    }
};

410. 分割数组的最大值***​

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        /*我先猜一个mid值，然后遍历数组划分，使每个子数组和都最接近mid（贪心地逼近mid）， 这样我得到的子数组数一定最少;
如果即使这样子数组数量仍旧多于m个，那么明显说明我mid猜小了，因此 lo = mid + 1;
而如果得到的子数组数量小于等于m个，那么我可能会想，mid是不是有可能更小？值得一试。因此 hi = mid;
由题意可知：子数组的最大值是有范围的，即在区间 [max(nums),sum(nums)] 之中。 令 h=sum(nums) l=max(nums)，mid=(l+h)/2，计算数组和最大值不大于mid对应的子数组个数 cnt(这个是关键！) 如果 cnt>m，说明划分的子数组多了，即我们找到的 mid 偏小，故 l=mid+1； 否则，说明划分的子数组少了，即 mid 偏大(或者正好就是目标值)，故 h=mid。*/
        long left = nums[0],right = 0;
        for(int x : nums)
        {
            left = max(left, (long)x);
            right += x;
        }
        while(left < right)
        {
            long mid = (left + right) / 2;
            int cnt = 1;
            long temp = 0;
            for(int x : nums)
            {
                temp += x;
                if(temp > mid) 
                {
                    cnt++;
                    temp = x;
                }
            }
            if(cnt > k) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

1011. 在 D 天内送达包裹的能力​

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        //left -> m天  right -> 一天
        long left = weights[0] , right = 0;
        for(int x : weights)
        {
            left = max(left,(long)x);
            right += x;
        }
        //求最小的天数逼近days天数的weights
        while(left < right)
        {
            long mid = (left + right) / 2;
            long temp = 0;
            int count = 1;
            for(int x : weights)
            {
                temp += x;
                if(temp > mid)
                {
                    count++;
                    temp = x;
                }
            }
            //说明用的天数多了，搬运的货物少了
            if(count > days) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

611. 有效三角形的个数​

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res = 0,index = 0;
        sort(nums.begin(),nums.end());
        while(index < nums.size()&&  nums[index] == 0) index++;
        if(nums.size() - index < 3) return 0;
        for(int i = index; i < nums.size();i++)
        {
            for(int j = i + 1;j < nums.size();j++)
            {
                int mas = nums[i] + nums[j];
                //不满足的开始位置
                int pos = lower_bound(nums.begin() + j , nums.end(),mas) - nums.begin();
                //cout << pos << " ";
                res += pos - j - 1;
            }
        }
        return res;
    }
};

475. 供暖器​

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(heaters.begin(),heaters.end());
        int left = 0 ,right = max(houses.back(),heaters.back());
        unordered_map<int,int> close;
        for(int i : houses)
        {
            //寻找最近的供暖
            int pre = lower_bound(heaters.begin(),heaters.end(),i) - heaters.begin();
            if(pre < heaters.size()) 
            {
                close[i] = heaters[pre];
                if(pre - 1 >= 0) close[i] = heaters[pre] - i < i - heaters[pre - 1] ? heaters[pre] : heaters[pre - 1];
            }
            else close[i] = heaters[pre - 1];
        }
        while(left < right)
        {
            int mid = (left + right) / 2;
            bool find = true;
            for(int i : houses)
            {
                if(i <= close[i] + mid  && close[i] - mid <= i) continue;
                else 
                {
                    find = false;
                    break;
                }
            }
            if(find) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

436. 寻找右区间​

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        unordered_map<int,int> umap;
        for(int i = 0; i < intervals.size();i++) umap[intervals[i][0]] = i;
        vector<int> temp(intervals.size());
        for(int i = 0; i < intervals.size();i++) temp[i] = intervals[i][0];
        sort(temp.begin(),temp.end());
        vector<int> res;
        for(auto x : intervals)
        {
            int pos = lower_bound(temp.begin(),temp.end(),x[1]) - temp.begin();
            if(pos == intervals.size()) res.push_back(-1);
            else res.push_back(umap[temp[pos]]);
        }
        return res;
    }
};

数组​

941. 有效的山脉数组​

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if(arr.size() < 3) return false;
        int cur = 1;
        while(cur < arr.size()&& arr[cur -1] < arr[cur]) cur++;
        if(cur == 1 || cur == arr.size()) return false;
        while(cur < arr.size()&& arr[cur -1] > arr[cur]) cur++;
        if(cur != arr.size()) return false;
        return true;
    }
};

189. 轮转数组​

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        reverse(nums.end() - k,nums.end());
        reverse(nums.begin(),nums.end() - k);
        reverse(nums.begin(),nums.end());
    }
};

724. 寻找数组的中心下标​

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int left = 0, right = accumulate(nums.begin(),nums.end(),0) , cur = 0;
        while(cur < nums.size())
        {
            right -= nums[cur];
            if(right == left) return cur;
            left += nums[cur];
            cur++;
        }
        return -1;
    }
};

922. 按奇偶排序数组 II​

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        //双指针
        for (int i = 0; i < nums.size(); ++i) {
            if (i % 2 != nums[i] % 2)
            {
                int r = nums.size() - 1;
                while (r >= 0 && i % 2 != nums[r] % 2) r--;
                swap(nums[i],nums[r]);
            }
        }
        return nums;
    }
};

1365. 有多少小于当前数字的数字​

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        unordered_map<int,int> umap;
        vector<int> res = nums;
        sort(res.begin(),res.end());
        for(int i = res.size() - 1; i >= 0;i--) umap[res[i]] = i;
        for(int i = 0;i < res.size() ;i++) res[i] = umap[nums[i]];
        return res;
    }
};

448. 找到所有数组中消失的数字​

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for(int i = 0; i < nums.size() ;i++)
        {
            if(nums[i] > 0 && nums[nums[i] - 1] > 0)
            {
                nums[nums[i] - 1] = -nums[nums[i] - 1];
            }
            if(nums[i] < 0 && nums[-nums[i] - 1] > 0)
            {
                nums[-nums[i] - 1] = -nums[-nums[i] - 1];
            }
        }
        vector<int> res;
        for(int i = 0; i < nums.size() ;i++) if(nums[i] > 0) res.push_back(i + 1);
        return res;
    }
};

769. 最多能完成排序的块​

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int res = 0 ,mx = 0;
        for(int i = 0; i < arr.size() ;i++)
        {
            mx = max(mx , arr[i]);
            if(mx == i)res++;
        }
        return res;
    }
};

149. 直线上最多的点数​

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        if(points.size() < 3) return points.size();
        int maxpoint = 1;
        for(int i = 0; i < points.size() ;i++)
        {
            for(int j = i + 1;j < points.size() ;j++)
            {
                int x1 = points[i][0] , y1 = points[i][1] , x2 = points[j][0],y2= points[j][1];
                int sum = 2;
                for(int k = j + 1; k < points.size();k++)
                {
                    int x3 = points[k][0] , y3 = points[k][1];
                    if((x1 - x2) * (y1 - y3)  == (x1 - x3) *(y1 - y2) ) sum++;
                    maxpoint = max(maxpoint,sum);
                }
            }
        }
        return maxpoint;
    }
};

80. 删除有序数组中的重复项 II​

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() < 3) return nums.size();
        int res = 2;
        for(int i = 2; i < nums.size();i++)
        {
            if(nums[i] != nums[res - 2]) nums[res++] = nums[i];
        }
        return res;
    }
};

274. H 指数​

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(),citations.end());
        int res = 0;
        for(int i = 1; i <= citations.size();i++)
        {
            auto start = lower_bound(citations.begin(),citations.end(),i);
            if(citations.end() - start >= i) res = i;
        }
        return res;
    }
};

//方法二 --- 前缀和
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int count[1001] = {0};
        int maxs = 0;
        for(int i = 0; i < citations.size(); i++)
        {
            count[citations[i]]++;
            maxs = max(citations[i],maxs);
        }
        for(int i = 999; i >= 0; i--) 
        {
            count[i] += count[i + 1];
            if(count[i] >= i) return i;
        }
        return 0;
    }
};

4. 寻找两个正序数组的中位数​

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(nums1.size()+nums2.size());
        int i = 0 ,j = 0;
        while(i < nums1.size() && j < nums2.size())
        {
            if(nums1[i] < nums2[j]) 
            {
                res[i + j] = nums1[i];
                i++;
            }
            else 
            {
                res[i + j] = nums2[j];
                j++;
            }
        };
        while(i < nums1.size()) res[i + j - 1] = nums1[i++];
        while(j < nums2.size()) res[i + j - 1] = nums2[j++];


        if(res.size() % 2 == 1) return res[res.size() / 2];
        return (double)(res[res.size() / 2 - 1] + res[res.size() / 2]) / 2;
    }
};

41. 缺失的第一个正数​

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i = 0; i < nums.size();i++)
        {
            if(nums[i] > 0 && nums[i] < nums.size() && nums[i] != nums[nums[i] - 1]) 
            {
                swap(nums[i],nums[nums[i] - 1]);
                i--;
            }
        }
        int cur  = 0;
        while(cur < nums.size())
        {
            if(nums[cur] != cur + 1) return cur + 1;
            cur++;
        }
        return nums.size() + 1;
    }
};

75. 颜色分类​

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        int cur = 0;
        while(cur <= right)
        {
            if(nums[cur] == 0 && left < cur) swap(nums[cur],nums[left++]);
            else if(nums[cur] == 2 && right > cur)swap(nums[cur],nums[right--]);
            else cur++;
        }
    }
};

581. 最短无序连续子数组​

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> res = nums;
        sort(res.begin(),res.end());
        int left = 1, right = 0;
        for(int i = 0;i < nums.size();i++)
        {
            if(nums[i] != res[i])
            {
                left = i;
                break;
            }
        }
        for(int i = nums.size() - 1;i >= 0;i--)
        {
            if(nums[i] != res[i])
            {
                right = i;
                break;
            }
        }
        return right - left + 1;
    }
};

剑指 Offer 03. 数组中重复的数字​

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        //原地哈希
        for(int i = 0; i < nums.size();i++)
        {
            if(i != nums[i]) 
            {
                if(nums[i] == nums[nums[i]]) return nums[i];
                swap(nums[i],nums[nums[i]]);
                i--;
            }
        }
        return 0;
    }
};

剑指 Offer 61. 扑克牌中的顺子​

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        //统计 0 的数量
        int  st = 0 ,gap = 0;
        while(nums[st] == 0) st++;
        for(int i = st + 1; i < nums.size();i++)
        {
            if(nums[i] == nums[i - 1]) return false;
            gap += nums[i] - nums[i - 1];
        }
        return gap <= 4;
    }
};

LCR 011. 连续数组​

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size();i++) if(nums[i] == 0) nums[i] = -1;
        partial_sum(nums.begin(),nums.end(),nums.begin());
        unordered_map<int,int> umap;
        for(int i = 0; i < nums.size() ;i++)
        {
            if(umap.find(nums[i]) == umap.end()) umap[nums[i]] = i;
            else sum = max(i -  umap[nums[i]] , sum);
            if(nums[i] == 0) sum = max(sum,i + 1);
        }
        return sum;
    }
};

443. 压缩字符串​

class Solution {
public:
    int compress(vector<char>& chars) {
        int charsum = 1;
        string chs;
        chs.push_back(chars[0]);
        for(int i = 1; i < chars.size();i++)
        {
            if(chars[i] == chs.back()) charsum++;
            else
            {
                if(charsum != 1)chs += to_string(charsum);
                charsum = 1;
                chs.push_back(chars[i]);
            }
        }
        if(charsum > 1) chs += to_string(charsum);
        for(int i = 0 ;i < chs.size();i++)chars[i] = chs[i];
        chars.resize(chs.size());
        return chars.size();
    }
};

334. 递增的三元子序列​

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        long long MAX = 1e16;
        long long vec[3] = {MAX,MAX,MAX};
        for(int x : nums)
        {
            int i = 2;
            while(i >= 0 && x <= vec[i]) i--;
            vec[i + 1] = x;
            if(vec[0] != MAX && vec[1] != MAX && vec[2] != MAX ) return true;
        }
        return false;
    }
};

面试题 16.11. 跳水板​

class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if(k == 0) return {};
        vector<int> res;
        res.push_back(k * shorter);
        if(shorter == longer) return res;
        for(int i = 1 ; i <= k; i++)
        {
            res.push_back(k * shorter + (longer - shorter) * i);
        }
        return res;
    }
};

442. 数组中重复的数据​

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        unordered_set<int> res;
        int cur = 0;
        while(cur < nums.size())
        {
            if(nums[cur] - 1!= cur) 
            {
                if(nums[cur] == nums[nums[cur] - 1]) 
                {
                    res.insert(nums[cur]);
                    cur++;
                }
                else swap(nums[cur],nums[nums[cur] - 1]);
            }
            else cur++;
        }
        return vector<int>(res.begin(),res.end());
    }
};

1013. 将数组分成和相等的三个部分​

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int num = accumulate(arr.begin(),arr.end(),0);
        if(num % 3 != 0) return false;
        num /= 3;
        if(num == 0)
        {
            int cnt = 0;
            partial_sum(arr.begin(),arr.end(),arr.begin());
            for(int i = 0; i < arr.size();i++)
                cnt += arr[i] == 0;

            if(cnt >= 3) return true;
            return false;
        }
        int left = 0, right = arr.size() - 1;
        int l = 0, r = 0;
        while(left < right && l != num) l += arr[left++];
        while(left < right && r != num) r += arr[right--];
        return l == num && r == num;
    }
};

697. 数组的度​

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int,int> umap , start , end;
        for(int i = 0; i < nums.size();i++)
        {
            umap[nums[i]]++;
            end[nums[i]] = i;
        }
        for(int i = nums.size() - 1; i >= 0;i--) start[nums[i]] = i;
        int res = 0, max_len = 0;
        for(auto x: umap)
        {
            if(max_len < x.second)
            {
                max_len = x.second;
                res = end[x.first] - start[x.first] + 1;
            }
            else if(max_len == x.second) res = min(end[x.first] - start[x.first] + 1,res);
        }
        return res;
    }
};

747. 至少是其他数字两倍的最大数​

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

1497. 检查数组对是否可以被 k 整除​

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        unordered_map<int,int> umap;
        for(long x : arr) 
        {
            int p = (x % k + k) % k;
            umap[p]++;
        }
        for(auto x: umap)
        {
            if(x.second != umap[abs(k - x.first)] && x.first != 0 && x.first != k) return false;
        }
        return umap[0] % 2 == 0;
    }
};

849. 到最近的人的最大距离​

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int pre = -1;
        unordered_map<int,int> umap;
        for(int i = 0; i < seats.size();i++)
        {
            if(seats[i] == 1) pre = i;
            else if(pre != -1)umap[i] = i - pre;
        }
        pre = -1;
        int res = 0;
        for(int i = seats.size() - 1; i >= 0;i--)
        {
            if(seats[i] == 1) pre = i;
            else if(umap.count(i) && pre != -1)umap[i] = min(pre - i, umap[i]);
            else if(pre != -1)umap[i] = pre - i;

            if(seats[i] == 0) res = max(res , umap[i]);
        }
        return res;
    }
};

915. 分割数组​

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        /*

        代码的思路是：
        定义一个变量leftMax，表示左边部分的最大值，初始为nums[0]。
        定义一个变量leftPos，表示左边部分的最后一个位置，初始为0。
        定义一个变量curMax，表示当前遍历过的元素的最大值，初始为nums[0]。
        从第二个元素开始遍历数组，对于每个元素nums[i]：
        更新curMax为curMax和nums[i]中的较大值。
        如果nums[i]小于leftMax，说明当前元素不能放在右边部分，需要扩展左边部分，因此更新leftMax为curMax，更新leftPos为i。遍历结束后，返回leftPos + 1即可。*/
        int n = nums.size();
        int curMax = nums[0],leftMax = nums[0],leftPos = 0;
        for(int i = 1; i < nums.size() - 1;i++)
        {
            curMax = max(curMax , nums[i]);
            if(nums[i] < leftMax)
            {
                leftMax = curMax;
                leftPos = i;
            }
        }
        return leftPos + 1;
    }
};

324. 摆动排序 II​

class Solution {
public:
    //从中间往前遍历
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr = nums;
        sort(arr.begin(), arr.end());
        for(int i = 0, j = (n + 1) / 2 - 1,k = n - 1; i < n; i += 2, j--, k--)
        {
            nums[i] = arr[j];
            if(i + 1 < n) nums[i + 1] = arr[k];
        }
    }
};

矩阵​

240. 搜索二维矩阵 II​

这道题有一个简单的技巧：我们可以从右上角开始查找，若当前值大于待搜索值，我们向左 移动一位；若当前值小于待搜索值，我们向下移动一位。如果最终移动到左下角时仍不等于待搜 索值，则说明待搜索值不存在于矩阵中。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int raw = 0 , col = matrix[0].size() - 1;
        while (raw < matrix.size() && col >= 0)
        {
            if (matrix[raw][col] == target) return true;
            else if(matrix[raw][col] < target) raw++;
            else col--;
        }
        return false;
    }
};

59. 螺旋矩阵 II​

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n , vector<int>(n,0));
        int count = 2;
        res[0][0] = 1;
        int row = 0, col = 0;
        while(count <= n * n)
        {
            while(col < n - 1 && res[row][col + 1] == 0) res[row][++col] = count++;
            while(row < n - 1 && res[row + 1][col] == 0) res[++row][col] = count++;
            while(col > 0 && res[row][col - 1] == 0) res[row][--col] = count++;
            while(row > 0 && res[row - 1][col] == 0) res[--row][col] = count++;
        }
        return res;
    }
};

54. 螺旋矩阵​

//54. 螺旋矩阵（与上一题思路相似，生成矩阵判断是否走过）
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {

        int i = 0 , j = 0 ,count = 1;
        int size = matrix.size() * matrix[0].size();
        vector<vector<bool>> sym(matrix.size(),vector<bool>(matrix[0].size(), false));
        vector<int> res;
        res.push_back(matrix[0][0]);
        sym[0][0] = true;
        while (count < size)
        {
            while (j < matrix[0].size() -1 && !sym[i][j+1])
            {
                res.push_back(matrix[i][++j]);
                sym[i][j]=true;
                count++;
            }
            while (i < matrix.size() -1 && !sym[i+1][j])
            {
                res.push_back(matrix[++i][j]);
                sym[i][j]=true;
                count++;
            }
            while (j > 0 && !sym[i][j-1])
            {
                res.push_back(matrix[i][--j]);
                sym[i][j]=true;
                count++;
            }
            while (i>0 && !sym[i-1][j])
            {
                res.push_back(matrix[--i][j]);
                sym[i][j]=true;
                count++;
            }
        }

        return res;
    }
};

48. 旋转图像​

class Solution {
public:+-
    void rotate(vector<vector<int>>& matrix) {
        //先上下，后对称
        for( int i = 0 ; i < matrix.size() / 2;i++)
            swap(matrix[i],matrix[matrix.size() - i - 1]);
        for(int i = 0; i < matrix.size(); i++)
            for(int j = i + 1; j < matrix[0].size(); j++)
                swap(matrix[i][j],matrix[j][i]);
    }
};

566. 重塑矩阵​

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        if (r * c != mat.size() * mat[0].size()) return mat;
        vector<vector<int>> res(r,vector<int>(c));
        int col = 0 , raw = 0 , count = 0;
        for (int i = 0; i < mat.size(); ++i) {
            for (int j = 0; j < mat[0].size(); ++j) {
                count = i * mat[0].size() + j;
                raw = count / c;
                col = count % c;
                res[raw][col] = mat[i][j];
            }
        }
        return res;
    }
};

73. 矩阵置零​

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> col , row;
        for(int i = 0; i < matrix.size();i++)
        {
            for(int j = 0; j < matrix[0].size();j++)
            {
                if(matrix[i][j] == 0) 
                {
                    col.insert(i);
                    row.insert(j);
                }
            }
        }
        for(int i : col)
        {
            for(int j = 0; j < matrix[0].size();j++)
            {
                matrix[i][j] = 0;
            }
        }
        for(int i : row)
        {
            for(int j = 0; j < matrix.size();j++)
            {
                matrix[j][i] = 0;
            }
        }
    }
};

289. 生命游戏​

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        // 活 - 死 -- -1
        // 死 - 活 --  2
        function<int(int,int)> findpre = [&](int i , int j)->int{
            if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) return 0;
            return board[i][j];
        };

        function<void (int ,int)> isde = [&](int i ,int j)
        {
            //统计活细胞数量
            int count = 0;
            count += abs(findpre(i , j - 1)) == 1;
            count += abs(findpre(i + 1, j - 1)) == 1;
            count += abs(findpre(i - 1, j - 1)) == 1;
            count += abs(findpre(i - 1, j)) == 1;
            count += abs(findpre(i - 1, j + 1)) == 1;
            count += abs(findpre(i, j + 1)) == 1;
            count += abs(findpre(i + 1, j + 1)) == 1;
            count += abs(findpre(i + 1, j)) == 1;
            
            if((abs(findpre(i , j)) == 1 ) && (count < 2 || count > 3))
            {
                board[i][j] = -1;
            }
            else if(abs(findpre(i , j)) != 1 && count == 3)
            {
                board[i][j] = 2;
            }
        };

        for(int i = 0; i < board.size();i++)
        {
            for(int j = 0; j < board[0].size();j++)
            {
                isde(i,j);
            }
        }

        for(int i = 0; i < board.size();i++)
        {
            for(int j = 0; j < board[0].size();j++)
            {
                if(board[i][j] == -1)board[i][j] = 0;
                if(board[i][j] == 2) board[i][j] = 1;
            }
        }
    }
};

118. 杨辉三角​

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        for(int i = 0 ; i < numRows;i++)
        {
            vector<int> tmp(i + 1, 1);
            for(int j = 1 ; j < i; j++)
            {
                tmp[j] = res[i - 1][j] + res[i - 1][j - 1];
            }
            res.push_back(tmp);
        }
        return res;
    }
};

994. 腐烂的橘子​

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        vector<vector<int>> pre = grid;
        int cnt = -1;
        bool flag = true;
        while(flag)
        {
            flag = false;
            for(int i = 0; i < grid.size(); i++)
            {
                for(int j = 0; j < grid[0].size();j++)
                {
                    if(pre[i][j] == 2)
                    {
                        if(i > 0 && grid[i - 1][j] == 1) 
                        {
                            flag = true;
                            grid[i - 1][j] = 2;
                        }
                        if(j > 0 && grid[i][j - 1] == 1) 
                        {
                            flag = true;
                            grid[i][j - 1] = 2;
                        }
                        if(i < grid.size() - 1 && grid[i + 1][j] == 1) 
                        {
                            flag = true;
                            grid[i + 1][j] = 2;
                        }
                        if(j < grid[0].size() - 1 && grid[i][j + 1] == 1) 
                        {
                            flag = true;
                            grid[i][j + 1] = 2;
                        }

                    }
                }
            }
            
            pre = grid;
            cnt++;
        }

        for(int i = 0; i < grid.size(); i++)
            for(int j = 0; j < grid[0].size();j++)
                if(grid[i][j] == 1) return -1;

        return cnt;
    }
};

2352. 相等行列对​

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        vector<vector<int>> grid2 = grid;
        int res = 0;
        for(int i = 0; i < grid2.size();i++)
            for(int j = i + 1; j < grid2[0].size();j++)
                swap(grid2[i][j],grid2[j][i]);
        for(int i = 0; i < grid.size();i++)
            for(int j = 0; j < grid2.size();j++)
                if(grid[i] == grid2[j]) res++;
        return res;
    }
};

498. 对角线遍历***​

解析：https://leetcode.cn/problems/diagonal-traverse/solutions/1497406/by-lin-shen-shi-jian-lu-k-laf5/

同一条对角线ij之和相等。

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        vector<int> res;
        if (mat.empty() || mat[0].empty()) return res;
        int n = mat.size(), m = mat[0].size();
        for (int i = 0; i < n + m - 1; i ++ ) 
        {
            if (i % 2 == 0)  //偶数对角线
            {
                //终点纵坐标为 m - 1 ，横坐标 i - (m - 1)
                for (int x = min(i, n - 1); x >= max(0, i - m + 1); x -- )//从下往上遍历
                    res.push_back(mat[x][i - x]);
            } else           //奇数对角线
            {      
                for (int x = max(0,  i - m + 1); x <= min(i, n - 1); x ++ )//从上往下遍历
                    res.push_back(mat[x][i - x]);
            }
        }
        return res;
    }
};

840. 矩阵中的幻方​

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        if(grid.size() < 3 || grid[0].size() < 3) return 0;
        function<bool(int , int)> func = [&](int i, int j){
            if(i + 2>= grid.size() || j + 2 >= grid[0].size()) return false;
            unordered_set<int> uset;
            for(int m = 0; m < 3; m++)
            {
                for(int n = 0; n < 3 ; n++){
                    if(grid[i + m][n + j] > 9 || grid[i + m][n + j] < 1) return false;
                    uset.insert(grid[i + m][n + j]);
                }
            }
            if(uset.size() < 9) return false;
            int p = grid[i][j] + grid[i + 1][j + 1] +grid[i + 2][j + 2];
            if(p != grid[i][j + 2] + grid[i + 1][j + 1] + grid[i + 2][j]) return false;
            for(int k = 0; k < 3; k++)
            {
                int t = grid[i + k][j] + grid[i + k][j + 1] + grid[i + k][j + 2];
                int m = grid[i][j + k] + grid[i + 1][j + k] + grid[i + 2][j + k];
                if(t != p || m != p) return false;
            }
            return true;
        };
        int cnt = 0;
        for(int i = 0; i < grid.size();i++)
        {
            for(int j = 0; j < grid[0].size();j++)
            {
                cnt += func(i,j);
            }
        }
        return cnt;
    }
};

807. 保持城市天际线​

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        //寻找每一行，每一列的最大值并记录
        vector<int> rowMax(grid.size());
        vector<int> colMax(grid.size());
        for(int i = 0; i < grid.size();i++)
        {
            for(int j = 0; j < grid.size();j++)
            {
                rowMax[i] = max(rowMax[i],grid[i][j]);
                colMax[i] = max(colMax[i],grid[j][i]);
            }
        }
        int cnt = 0;
        for(int i = 0; i < grid.size();i++)
        {
            for(int j = 0; j < grid.size();j++)
            {
                cnt += min(rowMax[i],colMax[j]) - grid[i][j];
            }
        }
        return cnt;
    }
};

1358. 包含所有三种字符的子字符串数目​

class Solution {
public:
    int numberOfSubstrings(string s) {
        //我们可以对于每个下标i作为右端点，寻找左边最近满足要求的下标j，那么从0到j的所有下标都满足要求，以下标i作为右端点答案就是j+1。
        int n = s.size(), ans = 0, p[3] = { -1, -1, -1 };
        for(int i = 0; i < n; i ++ ) p[s[i] - 'a'] = i, ans += min({p[0], p[1], p[2]}) + 1;
        return ans;
    }
};

字符串​

541. 反转字符串 II​

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0 ; i < s.size() ;i += k *2 )
        {
            if(i + k <= s.size()) reverse(s.begin() + i,s.begin() + i + k);
            else reverse(s.begin() + i,s.end());
        }
        return s;
    }
};

剑指 Offer 05. 替换空格​

class Solution {
public:
    string replaceSpace(string s) {
        string res;
        for(char x:s)
        {
            if(x == ' ') 
            {
                res.push_back('%');
                res.push_back('2');
                res.push_back('0');
            }
            else res.push_back(x);
        }
        return res;
    }
};

151. 反转字符串中的单词​

class Solution {
public:
    string reverseWords(string s) {

        /*
         *
         * 1.移除字符串多余空格
         * 2.翻转单词
         * 3.翻转字符串
         */

        //1.移除字符串多余空格 双指针
                int slow =0, fast=0;
        s.push_back(' ');
        while (s[fast] == ' ')fast++;
        while (fast < s.size()-1)
        {
            if (s[fast] == ' ' && s[fast+1] == ' ') fast++;
            else s[slow++] = s[fast++];

        }
        s.resize(slow);

        //2.翻转单词
        int last = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (i == s.size() - 1) std::reverse(s.begin()+last, s.end());
            else if(s[i] == ' ')
            {
                std::reverse(s.begin()+last, s.begin()+i);
                last = i+1;
            }
        }

        //3.翻转字符串
        std::reverse(s.begin(), s.end());
        return s;
    }
};

459. 重复的子字符串​

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string ss = s.substr(1) + s;
        ss.pop_back();
        int fid = ss.find(s);
        return fid != -1;
    }
};

925.长按键入​

 class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        if(name.size() > typed.size()) return false;
        int l1 = 0 , l2 = 0;
        while(l1 < name.size())
        {
            //计算cur数量
            int l1_count = 0;
            char cur1 = name[l1];
            while(l1 < name.size() && cur1 == name[l1]) 
            {
                l1_count++;
                l1++;
            }
            if(l2 >= typed.size()) return false;
            int l2_count = 0;
            char cur2 = typed[l2];
            while(l2 < typed.size() && cur2 == typed[l2]) 
            {
                l2_count++;
                l2++;
            }
            if(cur1 != cur2 || l1_count > l2_count)return false;
        }

        return l2 == typed.size();
    }
};

680. 验证回文串 II​

class Solution {
public:
    bool validPalindrome(string s) {
        int left = 0 ,right = s.size() - 1;
        int count = 0;
        //left 匹配
        while (left < right)
        {
            if (s[left] == s[right])
            {
                left++;
                right--;
            } else
            {
                left++;
                count++;
            }
        }
        //right 匹配
        if (count <= 1) return true;

        left = 0 ,right = s.size() - 1;
        count = 0;
        //left 匹配
        while (left < right)
        {
            if (s[left] == s[right])
            {
                left++;
                right--;
            } else
            {
                right--;
                count++;
            }
        }
        return count <= 1;
    }
};

696. 计数二进制子串*​

class Solution {
public:
    int countBinarySubstrings(string s) {
        int count = 0 ,pre = 0 , cur = 1;
        for(int i = 1; i < s.size();i++)
        {
            if(s[i] == s[i - 1]) cur++;
            else
            {
                pre = cur;
                cur = 1;
            }
            if(pre >= cur) count++;
        }
        return count;
    }
};

409. 最长回文串​

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int> umap;
        for(char x:s) umap[x]++;
        bool ch = false;
        int count = 0;
        for(auto x:umap)
        {
            if(!ch && x.second % 2 == 1) 
            {
                count += x.second;
                ch = true;
            }
            else if(ch && x.second % 2 == 1) count += x.second - 1;
            else count += x.second;
        }
        return count;
    }
};

7. 整数反转​

class Solution {
public:
    int reverse(int x) {
        bool fu = x < 0;
        unsigned int res = 0;
        x = abs(x);
        if(to_string(x).size() >= 10 && x % 10 > 2) return 0;
        while(x)
        {
            res *= 10;
            res += x % 10;
            x /= 10;
        }
        res = fu ? -res:res;

        if(!fu && res > 2147483647) return 0;
        if(fu && -res > 2147483648) return 0;
        return res;
    }
};

227. 基本计算器 II​

class Solution {
public:
    int calculate(string s) {
        vector<int> nums;
        vector<char> ops;
        ops.push_back('+');
        int cur = 0;
        while(cur < s.size())
        {
            //加减号直接入栈
            if(s[cur] == '+' || s[cur] == '-') ops.push_back(s[cur++]);
            //乘除号
            else if(s[cur] == '*' || s[cur] == '/')
            {
                char op = s[cur++];
                while(s[cur] == ' ') cur++;
                string nu;
                while(s[cur] >= '0' && s[cur] <= '9') nu.push_back(s[cur++]);
                int num1 = nums.back();
                nums.pop_back();
                if(op == '*')nums.push_back(num1 * stoi(nu));
                if(op == '/')nums.push_back(num1 / stoi(nu));
            }
            else if(s[cur] >= '0' && s[cur] <= '9')
            {
                string nu(1,s[cur++]);
                while(cur < s.size() && s[cur] >= '0' && s[cur] <= '9') nu.push_back(s[cur++]);
                nums.push_back(stoi(nu));
            }
            else cur++;
        }
        int res = 0;
        for(int i = 0;i < nums.size() ;i++)
        {
            //cout << ops[i] << nums[i] <<endl;
            nums[i] = ops[i] == '+'? nums[i] : -nums[i];
            res += nums[i];
        }
        return res;
    }
};

224. 基本计算器​

class Solution {
public:
    int calculate(string s) {
        vector<int> nums;
        vector<char> chs;
        int cur = 0;
        while(cur < s.size())
        {
            //是符号，则要找到其后面的数字
            if(s[cur] == '+' || s[cur] == '-' || s[cur] == '(') chs.push_back(s[cur++]);

            else if(s[cur] == ')')
            {
                int res = 0;
                while(chs.size() && chs.back() != '(')
                {
                    res += nums.back();
                    nums.pop_back();
                    chs.pop_back();
                }
                chs.pop_back();

                if(chs.size() == 0 || chs.back() == '(') chs.push_back('+');
                if(chs.back() == '-') nums.push_back(-res);
                else nums.push_back(res);
                cur++;
            }
            else if(s[cur] >= '0' && s[cur] <= '9')
            {
                if(chs.size() == 0 || chs.back() == '(') chs.push_back('+');
                string nu(1,s[cur++]);
                while(cur < s.size() && s[cur] >= '0' && s[cur] <= '9') nu.push_back(s[cur++]);
                if(chs.back() == '+') nums.push_back(stoi(nu));
                if(chs.back() == '-') nums.push_back(-stoi(nu));
            }
            else cur++;
        }
        int res = 0;
        for(int x : nums) res += x;
        return res;
    }
};

14. 最长公共前缀​

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        for(int i = 0; i < strs[0].size();i++)
        {
            char s = strs[0][i];
            for(int j = 1; j < strs.size();j++)
            {
                if(strs[j].size() <= i || strs[j][i] != s) return res;
            }
            res.push_back(s);
        }
        return res;
    }
};

290. 单词规律​

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        stringstream ss(s);
        string item;
        unordered_map<char,string> umap1;
        unordered_map<string,char> umap2;
        int i = 0;
        while(getline(ss, item, ' '))
        {
            if(i >= pattern.size()) return false;
            if(umap2.find(item) != umap2.end() && (umap1[pattern[i]] != item || umap2[item] != pattern[i])) return false;
            umap1[pattern[i]] = item;
            umap2[item] = pattern[i];
            i++;
        }
        if(i != pattern.size() || umap1.size() != umap2.size()) return false;
        return true;
    }
};

76. 最小覆盖子串​

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> t_map;
        unordered_map<char,int> s_map;
        int sum = 0,res = INT_MAX,start = 0;
        for(char x:t) t_map[x]++;
        int left = 0 , cnt = t_map.size();
        for(int i = 0; i < s.size();i++)
        {
            if(t_map[s[i]] > 0)
            {
                s_map[s[i]]++;
                if(s_map[s[i]] == t_map[s[i]] ) sum++;
            }
            while(sum == cnt)
            {
                if(res > i - left + 1)
                {
                    res = i - left + 1;
                    start = left;
                }

                if(s_map[s[left]] > 0)
                {
                    if(s_map[s[left]] == t_map[s[left]] ) sum--;
                    s_map[s[left]]--;
                }
                left++;
            }
        }
        return res==INT_MAX ? "":s.substr(start,res);
    }
};

剑指 Offer 67. 把字符串转换成整数​

class Solution {
public:
    int strToInt(string str) {
        int st = 0;
        while (str[st] == ' ')st++;
        bool isfu = (str[st] == '-');
        if(str[st] == '-' || str[st] == '+') st++;
        int bndry = INT_MAX / 10;
        //int lenth = isfu ? str.size()- 1 - st++  :str.size() - st;
        //cout <<lenth << endl;
        int  res = 0;
        while (st < str.size())
        {
            if(str[st] < '0' || str[st] > '9') break;
            if (res > bndry || res == bndry && str[st] > '7') return isfu? INT_MIN : INT_MAX;
            res = 10 * res  + (str[st++] - '0');
        }
        return isfu ? -res:res;
    }
};

面试题 01.05. 一次编辑​

class Solution {
public:
    bool oneEditAway(string first, string second) {
        if((abs((int)first.size() - (int)second.size())) >= 2) return false;
        else if(first.size() == second.size())
        {
            int count = 0;
            for(int i = 0; i < first.size();i++)
            {
                if(first[i] != second[i]) count++;
            }
            return count <= 1;
        }
        else{
            int left = 0, right = 0 ,count = 0;
            while(left < first.size() && right < second.size())
            {
                if(first[left] != second[right]) 
                {
                    first.size() > second.size() ? left++ : right++;
                    count++;
                    //cout << first[left] << "  " << first[right] << endl;
                }
                else{
                    left++;
                    right++;
                }
            }
            return count <= 1;
        }
    }
};

面试题 01.09. 字符串轮转​

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if(s1.size() != s2.size()) return false;
        string news = s2 + s2;
        return news.find(s1) != -1;
    }
};

165. 比较版本号​

class Solution {
public:
    int compareVersion(string version1, string version2) {
        vector<int> v1;
        vector<int> v2;
        stringstream ss(version1);
        stringstream ss2(version2);
        string tmp;
        while(getline(ss,tmp,'.')) v1.push_back(stoi(tmp));
        while(getline(ss2,tmp,'.')) v2.push_back(stoi(tmp));

        while(v1.size() < v2.size()) v1.push_back(0);
        while(v1.size() > v2.size()) v2.push_back(0);
        for(int i = 0; i < v1.size();i++)
        {
            if(v1[i] < v2[i]) return -1;
            if(v1[i] > v2[i]) return 1;
        }
        return 0;
    }
};

43. 字符串相乘​

class Solution {
    string addStrings(string num1, string num2) {
        string res;
        //对齐
        if (num1.size() > num2.size()) num2 = string(num1.size() - num2.size(),'0')+num2;
        if (num1.size() < num2.size()) num1 = string(num2.size() - num1.size(),'0')+num1;
        int n = num2.size() , fd = 0;
        while (n--)
        {

            res = string(1,((num1[n] + num2[n]  - 2 * '0' + fd) % 10)+'0') + res;
            if (num1[n] + num2[n]  - 2 * '0' + fd >= 10)  fd = 1;
            else fd = 0;
        }
        if(fd) res = "1"+ res;
        return res;
    }
    string mulStrings_one(string num1, char num2)
    {
        string res;
        int add = 0;
        for(int i = num1.size() - 1; i >= 0; i--)
        {
            int t = (num2 - '0') * (num1[i] - '0') + add;
            add = t / 10;
            char newC = t % 10 + '0';
            res.push_back(newC);
        }
        if(add) res.push_back(add + '0');
        reverse(res.begin(),res.end());
        return res;
    }
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") return "0";
        string res;
        int k = 0;
        for(int i = num2.size() - 1; i >= 0; i--)
        {
            string p = mulStrings_one(num1,num2[i]);
            p = p + string(k,'0');
            res = addStrings(p,res);
            k++;
        }

        return res;
    }
};

830. 较大分组的位置​

class Solution {
public:
    vector<vector<int>> largeGroupPositions(string s) {
        vector<vector<int>> res;
        s.push_back(' ');
        int cur = 1,pre = 0;
        for(int i = 1; i < s.size();i++)
        {
            if(s[i] == s[i - 1])cur++;
            else
            {
                if(cur >= 3) res.push_back({pre,i - 1});
                pre = i;
                cur = 1;
            }
        }

        return res;
    }
};

792. 匹配子序列的单词数**​

// 执行用时：100 ms, 在所有 C++ 提交中击败了 97.72% 的用户
// 内存消耗：31.8 MB, 在所有 C++ 提交中击败了 94.19% 的用户
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        int cnt = 0;
        for (string &word : words) {
            int cur = -1;
            bool ok = true;
            for (char &c : word) {
                // 查找 cur 之后是否出现了 c
                cur = s.find(c, cur + 1);
                if (cur == string::npos) {
                    ok = false; 
                    break;
                }
            }
            if (ok) cnt++;
        }
        return cnt;
    }
};

187. 重复的DNA序列​

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        if(s.size() < 10) return {};
        vector<string> res;
        unordered_map<string,int> count;
        for(int i = 0; i <= s.size() - 10 ; i++)
        {
            string sub = s.substr(i, 10);
            count[sub]++;
        }
        for(auto x : count) if(x.second > 1) res.push_back(x.first);
        return res;
    }
};