leetcode 刷题2

二分查找的绝妙运用：?看到有序数列，算法复杂度

0033. 搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        // 如果中间元素小于最右边的元素，说明右半边是有序的
        if (nums[mid] < nums[right]) {
            // 如果目标值位于有序的右半边范围内
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;  // 在右半边继续搜索
            } else {
                right = mid - 1;  // 在左半边继续搜索
            }
        }
        // 如果中间元素大于最右边的元素，说明左半边是有序的
        else {
            // 如果目标值位于有序的左半边范围内
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;  // 在左半边继续搜索
            } else {
                left = mid + 1;  // 在右半边继续搜索
            }
        }
    }

    return -1;  // 如果没有找到目标值，返回 -1

    }
};

162. 寻找峰值? 二分法套模板

思路：这道题，最最最重要的是条件，条件，条件，两边都是负无穷，数组当中可能有很多波峰，也可能只有一个，如果尝试画图，就跟股票信息一样，没有规律，如果根据中点値判断我们的二分方向该往何处取， 这道题还有只是返回一个波峰。你这样想，中点所在地方，可能是某座山的山峰，山的下坡处，山的上坡处，如果是山峰，最后会二分终止也会找到，关键是我们的二分方向，并不知道山峰在我们左边还是右边，送你两个字你就明白了，爬山（没错，就是带你去爬山），如果你往下坡方向走，也许可能遇到新的山峰，但是也许是一个一直下降的坡，最后到边界。但是如果你往上坡方向走，就算最后一直上的边界，由于最边界是负无穷，所以就一定能找到山峰，总的一句话，往递增的方向上，二分，一定能找到，往递减的方向只是可能找到，也许没有。

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

这个方法注意一下边界的处理

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

        return left;
    }
};

4. 寻找两个正序数组的中位数?(超级难)

中位数：奇数：中间那个数，偶数，中间两个数的平均值。

方法一.不考虑复杂度，直接莽，合并数组。找到中位数。

方法二：数组存放的数其实没什么用，不需要将两个数组真的合并，我们只需要找到中位数在哪里就可以了

class Solution { //不需要将两个数组真的合并，我们只需要找到中位数在哪里就可以了
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int i = 0, j = 0, num = 0; // i--》nums1的指针
        int len = m + n;
        int pre = -1;
        int p = -1;                               //存值
        for (num = 0; num <= len / 2; num++) { // 0 1 2 3 4 5
            pre = p;
            if (i < m && (j >=n || nums1[i] < nums2[j])) {
                p = nums1[i++];
            } // nums1没到头或者nums2到头或者＜
            else
                p = nums2[j++];
        }
        if (len % 2) //奇数个
            return p;
        else
            return (p + pre) / 2.0;
    }
};

精华：1.利用pre来存放上一个数，利用p来存放当前的数据。2.移动的条件判断。

for (num = 0; num <= len / 2; num++) { // 0 1 2 3 4 5
            pre = p;
            if (i < m && (j >=n || nums1[i] < nums2[j])) {
                p = nums1[i++];
            } // nums1没到头或者nums2到头或者＜
            else
                p = nums2[j++];
        }

?方法三：题目是求中位数，其实就是求第?k?小数的一种特殊情况，而求第?k?小数有一种算法。

我们一次遍历就相当于去掉不可能是中位数的一个值，也就是一个一个排除。由于数列是有序的，其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数，我们可以每次循环排除掉 k/2 个数。而这k/2个数是较小数数列的前k/2个。

class Solution {
public:
    int findmid(vector<int>& nums1, vector<int>& nums2, int l1, int r1, int l2,
                int r2, int k) {
        if (r1 <= l1) // nums1为空
            return nums2[l2 + k - 1];
        if (r2 <= l2) // nums2为空
            return nums1[l1 + k - 1];
        int mid1 = (l1 + r1) / 2, mid2 = (l2 + r2) / 2; //分别的中位数
        int d = mid1 - l1 + 1 + mid2 - l2 + 1;          
        if (d > k) {
            if (nums1[mid1] < nums2[mid2])
                return findmid(nums1, nums2, l1, r1, l2, mid2, k);
            else
                return findmid(nums1, nums2, l1, mid1, l2, r2, k);
        } else {
            if (nums1[mid1] < nums2[mid2])
                return findmid(nums1, nums2, mid1 + 1, r1, l2, r2,
                               k - (mid1 - l1 + 1));
            else
                return findmid(nums1, nums2, l1, r1, mid2 + 1, r2,
                               k - (mid2 - l2 + 1));
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        if ((n + m) % 2)
            return (findmid(nums1, nums2, 0, n, 0, m, 1 + (n + m) / 2));
        else
            return (findmid(nums1, nums2, 0, n, 0, m, (n + m) / 2) +
                    findmid(nums1, nums2, 0, n, 0, m, 1 + (n + m) / 2)) /
                   2.0;
    }
};

?240. 搜索二维矩阵 II

关键信息：（注意矩阵不是正矩阵）

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

?大体思路：

1,暴力法，两层for循环。复杂度O（mn）

2.删 类似前面做的旋转矩阵。 但要从右上角或者左下角开始删。

class Solution {//删，从右上角开始删。
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n=matrix.size();//行数
        int m=matrix[0].size();//列数
        int row=0;int col=m-1;
        while(col>=0&&row<=n-1){//终止条件到达左下角 【n-1,0】
            if(matrix[row][col]>target)
                col--;//col 确定下来了
            else if(matrix[row][col]<target)
                row++;
            else return true;//等于
        }
        return false;
    }
};

3.二分法一下子去掉k/4个元素：

1.找到中间元素：9；2.9>tatget;去掉右下角。3.分别递归其他三个部分。

class Solution {
public:
    //在[rangeX1~rangeX2][rangeY1~rangeY2]范围内搜索
    bool searchA(vector<vector<int>>& matrix, int target,int rangeX1,int rangeX2,int rangeY1,int rangeY2){
        //递归中止
        if(rangeX1>rangeX2||rangeY1>rangeY2){
            return false;
        }
        //计算中心位置（c_x,c_y）
        int c_x=(rangeX1+rangeX2)/2;
        int c_y=(rangeY1+rangeY2)/2;
        //递归，三部分的结果分别为p1,p2,p3
        bool p1,p2,p3;
        if(matrix[c_x][c_y]==target){
            return true;
        }else if(matrix[c_x][c_y]<target){
            p1=searchA(matrix,target,rangeX1,c_x,c_y+1,rangeY2);//右上
            p2=searchA(matrix,target,c_x+1,rangeX2,c_y+1,rangeY2);//右下
            p3=searchA(matrix,target,c_x+1,rangeX2,rangeY1,c_y);//左下
        }else{
            p1=searchA(matrix,target,rangeX1,c_x-1,c_y,rangeY2);//右上
            p2=searchA(matrix,target,rangeX1,c_x-1,rangeY1,c_y-1);//左上
            p3=searchA(matrix,target,c_x,rangeX2,rangeY1,c_y-1);//左下
        }
        return p1||p2||p3;//一真为真，只要一个存在就返回ture
    }
 
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0||matrix[0].size()==0){return false;}
        int n=matrix.size(),m=matrix[0].size();
        return searchA(matrix,target,0,n-1,0,m-1);
    }
};

4.二分法迭代器：这个主要强调一下迭代器的用法

1）auto遍历迭代器

vector<int> ans;
for(auto it=ans.begin();it!=ans.end();it++)
{
    cout<<*it<<endl;
}
为什么begin()要指向开头第一个元素，而end()要指向末尾最后一个元素的下一个呢？

因为：方便判断，左闭合范围

begin()==end()：意味着容器里没有元素

begin()+1==end()：意味着容器里只有一个元素

begin()+1<end()：意味着容器里不止一个元素 

2）lower_bound()--》二分查找

C++ STL标准库中还提供有 lower_bound()、upper_bound()、equal_range() 以及 binary_search() 这 4 个查找函数，它们的底层实现采用的都是二分查找的方式。

C++ 函数 std::map::lower_bound() 返回一个迭代器，它指向不小于键 k 的第一个元素。


lower_bound() 函数定义在<algorithm>头文件中，其语法格式有 2 种，分别为：
//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

//实例：

#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i,int j) { return i>j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i>j;//增加 
    }
};
int main() {
    int a[5] = {0,1,2,5,4};
    //从 a 数组中找到第一个不小于 3 的元素
    int *p = lower_bound(a, a + 5, 3);//返回的是值 --》a[3]=5 
    cout << "*p = " << *p << endl;//*p =5 

    vector<int> myvector{ 4,8,3,1,2 };
    //根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素的值//mycomp2 i>j增序-->找到第一个不是增序的元素值 
    vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(),3,mycomp2());// *iter = 3
    cout << "*iter = " << *iter;
    return 0;
}

本题代码：?

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n=matrix.size();int m=matrix[0].size();
        for(auto &row:matrix){//行遍历
            auto it=lower_bound(row.begin(),row.end(),target);//每行内部遍历
            if(it!=row.end()&&*it==target)
                return true;
        }
        return false;
    }
};

69. x 的平方根?

方法一：遍历?

注意：int*int会发生溢出 所以i的变量类型是long long

Leetcode：runtime error: signed integer overflow: 46341 * 46341 cannot be represent in type “int“

class Solution {
public:
    int mySqrt(int x) {
        long long i=0;
        if(x==1||x==0) return x;
        for( i=0;i<=x/2;i++){
           if(i*i>=x)
            break;
        }
        return i*i==x?i:i-1;
    }
};

方法二：二分查找?

• 时间复杂度：O(logx)，即为二分查找需要的次数。

上面那个方法到k/2，那我们再进一步：

重点： eg。8--》2 所以<= 的时候ans=mid；

else if (mid * mid <= x) {
      ans = mid;L = mid + 1;}

class Solution { //二分查找
public:
    int mySqrt(int x) {
        int ans;
        int L = 0;
        int R = x;
        while (L <= R) {
            long long  mid = (R - L) / 2 + L;
            if (mid * mid > x) {
                R = mid - 1;
            }

            else if (mid * mid <= x) {
                ans = mid;
                L = mid + 1;
            }
        }
        return ans;
    }
};

283. 移动零

思考：本来打算直接pop（值==0），但是忘记了，pop_back()只能删除末尾元素?

方法一：记录0元素个数；

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int num = 0; //目前0元素的个数

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                num++;
            } else
                nums[i - num] = nums[i];
        }
        int t=n-num;
        while (t<n)
            nums[t++] = 0;
    }
};

方法二：只保存非0元素。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n=nums.size();
        int num=0;//目前非0元素的个数
        
        for(int i=0;i<n;i++){
            if(nums[i]!=0){
               nums[num++]=nums[i];
            }
        }
        while(num<nums.size())
            nums[num++]=0;
             
    }
};

?方法三：双指针(其实就是方法二)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int right = 0; //快慢指针
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

?415. 字符串相加

方法一：模拟竖式

class Solution { //模拟竖式
public:
    string addStrings(string num1, string num2) {
        int tmp = -1;     //用来存放当前两数的和
        int carry = 0;    //用来存放当前的进位
        string ans = ""; //设置为字符串巧妙加减
        int n = max(num1.size(), num2.size());
        int i = num1.size()-1;
        int j= num2.size()-1;
        
        while (i >= 0 || j >= 0) {
            int n1 = i >= 0 ? num1[i] - '0' : 0;
            int n2 = j >= 0 ? num2[j] - '0' : 0;
            tmp = n1 + n2 + carry;
            carry = tmp / 10;
            ans = to_string(tmp % 10) + ans;
            i--;
            j--;
        }
        return carry ? "1" + ans : ans;
    }
};

注意：这三句将字符串运用的极其巧妙。（这里注意看注释）

 string ans = ""; //设置为字符串巧妙加减
//"";注意这里不用“ ”
 ans = to_string(tmp % 10) + ans;
//to_string  C++里面字符串转换
//注意顺序
 return carry ? "1" + ans : ans;//进位前面＋1；

方法二：逻辑一样，不知道复杂度为何差那么大?

这个复杂度很小。

class Solution {
public:
    string addStrings(string num1, string num2) {
        //竖式模拟
        int index1 = num1.length() - 1, index2 = num2.length() - 1;
        string& c = index2 < index1 ? num1 : num2;//c为长的字符串的复制，其实就是要个长度有用
        int index3 = index2 < index1 ? index1 : index2;//index3为c的长度
        int x = 0, y =0, CY = 0;//CY为进位
        while(index3 >= 0){
            if(index1 >= 0){
                x = num1[index1] - '0';//变为int
            }
            if(index2 >= 0){
                y = num2[index2] - '0';
            }
            c[index3] = (x + y + CY) % 10 + '0';//变为char
            CY = (x + y + CY) / 10;
            x = 0, y = 0;
            index3--, index2--, index1--;
        }
        return CY == 0 ? c : "1" + c;
    }
};

进入进入滑动窗口！?终于拜拜二分！

3. 无重复字符的最长子串?(这道题之前做过了)

? //思想：遍历s中的元素，如果不在滑动窗口中重复，就加入窗口（此时，窗口长度会增大）。如果重复，就从窗口中删除元素（此时窗口长度减少，开始位置后移）。

class Solution { //滑动窗口
    //大题思想：遍历s中的元素，如果不在滑动窗口中重复，就加入窗口（此时，窗口长度会增大）。如果重复，就从窗口中删除元素（此时窗口长度减少，开始位置后移）。
public:
    int lengthOfLongestSubstring(string s) {
        int ans, maxl = 0; // ans临时变量，maxl最大值;
        if (s.size() == 0)
            return 0;
        //创建无序字符集合，保存滑动窗口
        unordered_set<char> huadong;
        int start = 0;
        for (int i = 0; i < s.size(); i++) {
            while (huadong.find(s[i]) !=
                   huadong.end()) { //当前字符s[i]在集合 huadong中已经存在

                huadong.erase(s[start]);

                start++;
            }
            maxl = max(maxl, i - start + 1);
            huadong.insert(s[i]);
        }
        return maxl;
    }
};

一些小技巧?

(huadong.find(s[i]) !=huadong.end())//类似python in

?0076. 最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) {
        // 用一个无序映射（unordered_map）来记录需要的字符及其出现次数
        unordered_map<char, int> need;
        
        // 需要的字符总数
        int need_cnt = t.size();
        
        // 最小窗口子串的起始位置和长度
        int min_begin = 0, min_len = 0;
        
        // 遍历字符串t，记录每个字符及其出现次数
        for (const char& c : t) {
            need[c]++;
        }
        
        // 使用滑动窗口思想来查找最小窗口子串
        for (int left = 0, right = 0; right < s.size(); ++right) {
            
            // 当前字符在need中出现的次数大于0时，说明是需要的字符
            if (need[s[right]] > 0) {
                // need_cnt减少1，表示找到了一个匹配字符
                need_cnt--;
            }
            
            // need中该字符的出现次数减少1，表示已经使用了一个字符
            need[s[right]]--;
            
            // 当需要的字符都找到时，满足条件
            if (need_cnt == 0) {
                // 缩小窗口范围，尽量找到更小的窗口
                while (need[s[left]] < 0) {
                    // need中该字符的出现次数加1，表示窗口向右缩小，该字符变成需要的字符
                    need[s[left]]++;
                    left++;                    
                }
                
                // 计算当前窗口的长度
                int len = right - left + 1;
                
                // 更新最小窗口子串的起始位置和长度
                if (min_len == 0 || len < min_len) {
                    min_begin = left;
                    min_len = len;
                }
                
                // 窗口的左边界右移，破坏满足条件的窗口，继续寻找下一个满足条件的窗口
                need[s[left]]++;
                need_cnt++;
                left++;
            }
        }
        
        // 返回最小窗口子串
        return s.substr(min_begin, min_len);
    }
};

?718. 最长重复子数组

第一反应：KMP？ 结果想多了

思路：滑动窗口算法，求解两个数组的最长公共子数组的长度。看图：https://assets.leetcode-cn.com/solution-static/718/718_fig1.gif

class Solution {//滑动窗口
public:
    int maxL(vector<int>& A, vector<int>& B,int ai,int bi,int len){
        int ret=0,k=0;//k当前对齐时，重复的个数
        for(int i=0;i<len;i++){
            if(A[ai+i]==B[bi+i])
                k++;//重复加加
            else k=0;//不重复就0;ret保存最大K值
            ret=max(ret,k);  
        }return ret;
    }
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int i=0;
        int ret=0;
        int n=nums1.size();int m=nums2.size();
        for(int i=0;i<n;i++){//nums1对齐
            int len=min(m,n-i);//每次比较数组时都比较长度比较短的
            int maxlen=maxL(nums1,nums2,i,0,len);
            ret=max(ret,maxlen);
        }
        for(int i=0;i<m;i++){
            int len=min(n,m-i);
            int maxlen=maxL(nums1,nums2,0,i,len);
            ret=max(ret,maxlen);
        }
        return ret;
    }
};

• maxL?函数是用来计算两个数组指定位置开始的子数组的最长公共长度。函数参数解释如下：

  • A?和?B：两个输入数组。
  • ai?和?bi：起始位置的索引。
  • len：子数组的长度。
    函数通过比较?A?和?B?数组在相同位置上的元素，来统计重复的个数?k。如果当前位置的元素相同，则?k?值加 1；如果不相同，则将?k?重置为 0。每次更新?k?的同时，记录最大的?k?值为?ret。函数返回最大的?ret?值。

• findLength?函数是主函数，用于计算两个数组的最长公共子数组的长度。函数参数解释如下：

  • nums1?和?nums2：两个输入数组。
    函数首先定义了两个变量?ret?和?maxlen，分别用于保存最大公共子数组的长度和当前计算得到的最长公共子数组的长度。
    然后，通过嵌套的循环遍历?nums1?和?nums2?的不同起始位置，分别调用?maxL?函数求解当前位置开始的最长公共子数组的长度，并更新?maxlen?和?ret。
    最后返回?ret，即两个数组的最长公共子数组的长度

83. 删除排序链表中的重复元素（so easy）题目条件保证链表已经按升序?排列

利用数据结构里面链表的删除代码就可以。

注意一下，链表的定义，看开头。

返回方法return head;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {//链表：链表已经按升序 排列
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        ListNode*p=head->next; ListNode* pre=head;
        while(p){
            if(p->val==pre->val){//相等就断链
                pre->next=p->next;
                p=pre->next;
            }
            
            else{//指针后移
                pre=p;
                p=p->next;
            } 
            
        }
            return head;
    }
};

82. 删除排序链表中的重复元素 II（升级版）

思路：跳过那些相同的结点。创 头节点的方法值得学习。返回的时候，因为申请了 ans头结点，所以应该返回ans->next;

class Solution { //链表：链表已经按升序 排列
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head)
            return head;
        //因为head也可能被删除，所以创建头结点
        ListNode* ans = new ListNode(105, head); // val=105;next=head;
        //-100 <= Node.val <= 100,保证不会重复
        ListNode* p = head;
        ListNode* pre = ans;
        while (p&&p->next) {
            if (p->val == p->next->val) { //相等
                ListNode* tmp = p->next->next;
                while (tmp && tmp->val == p->val)
                    tmp = tmp->next;
                pre->next = tmp;
                p = tmp;
            }

            else { //指针后移
                pre = p;
                p = p->next;
            }
        }
        return ans->next;
    }
};