1.3000. 对角线最长的矩形的面积

 用pair解法：通过 pair 的比较特性，一次性完成了 "先比对角线（不开方），再比面积" 的逻辑。

pair<int, int> mx{};
 for (auto& d : dimensions) {
            int x = d[0], y = d[1];
            mx = max(mx, pair(x * x + y * y, x * y));
        }

2.1991. 找到数组的中间位置

先算总和，在遍历下标用前缀和判断是否符合规则。左求和*2+nums[i]=总和；

int total = accumulate(nums.begin(), nums.end(), 0);
 for (int i = 0; i < nums.size(); ++i) {
            if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }

3.35. 搜索插入位置

lower_bound()函数，二分查找加一个判断（1.在前面判断target是否大于数组最大值；2.在最后判断nums[left]<target?）

俩种循环方式while(left<right)和while(left<=right)->right=mid和right=mid-1;终止条件分别是left = right和left = right + 1；

 4.LCR 074. 合并区间

先用sort进行第一列升序列排序；建立一个二维数组，与所给数组比较首位大小进行合并；

//[[1,6],[2,5],[8,10],[15,18]]
sort(intervals.begin(),intervals.end());
if(intervals[i][0]<=res.back()[1]){
     vector<int> temp = res.back();
     res.pop_back();
     res.push_back({temp[0],max(temp[1],intervals[i][1])});
}

5.48. 旋转图像

如果是顺时针旋转90度，则可以先水平翻转然后在对角线翻转实现；这点可以用很多地方；对角线就是（270度+一次镜像）水平就是（-180+一次镜像）；

在此题中是不能用额外的辅助空间的，所以要找到规律进行交换完成旋转；

    for(int i=0;i<n/2;i++){
        for(int j=i;j<n-i-1;j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n-j-1][i];        
            matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
            matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
            matrix[j][n-i-1] = temp;
        }
    }

6.面试题 01.08. 零矩阵，若M × N矩阵中某个元素为0，则将其所在的行与列清零

①用俩个数组row(m)、col(n)记录需要变零的行和列，空间复杂O(m+n)；②先遍历第一行和第一列用俩个变量记录是否有零，然后用原二维数组的第一行和第一列标记是否有需要变零的行和列，空间复杂O(1)；bool col,row = false;并没有都初始化，正确的是bool col= false,row = false;

7.498. 对角线遍历

用一个flag变量标记遍历向上还是向下、用while循环到（m，n）结束；向上遍历时行--列++、向下遍历时行++列--；再用内while控制到边界结束、行边界在左边时i++否则j++，列边界同理；

    while(i!=m-1 || j!=n-1){//到（m,n）
        if(flag){
            while(i!=0 && j!=n-1){//到边界
                res.push_back(mat[i][j]);
                i--;j++;}
            res.push_back(mat[i][j]);
            j!=n-1?i++:j++;flag = false;
        }
        else{
            while(j!=0 && i!=m-1){
                res.push_back(mat[i][j]);
                i++;j--;}
            res.push_back(mat[i][j]);
            i!=m-1?j++:i++;flag = true;
        }
    }

8.14. 最长公共前缀

先遍历第一个字符串的长度，在遍历字符串数组的长度；用第一个和后面的字符对比、判越界；

for(int i=0;i<strs[0].size();i++){
   for(int j=1;j<strs.size();j++){
       if(i>strs[j].size()-1 || strs[0][i]!=strs[j][i]){
             return s;
   }
}
s+=strs[0][i];

9.5. 最长回文子串

中心扩散法；分为奇数和偶数俩种情况、遍历字符串，从每个字符开始左右检查是否符合；

动态规划；dp[i][j]表示下标从i到j是否是回文，dp[i][j]=(dp[i+1][j-1]&&s[i]==s[j]);j-i<3dp==ture；

while(left>=0 && right<s.size() && s[left]==s[right]){
    left--;right++;
}
if(right-left-1>max_len){
  max_len = right-left-1;
  res = s.substr(left+1,right-left-1);
}

10.151. 反转字符串中的单词

从后往前遍历，遇见非空格开始到是空格结束是一个整体，加入res+“ ”，把最后空格去掉；

if(s[i]!=' '){
    while(i>=0 && s[i]!=' '){
    temp += s[i];i--;
    }
    reverse(temp.begin(),temp.end());//可选择任意一段反转
    res += temp + " ";
}

11.28. 找出字符串中第一个匹配项的下标

用substr函数、判断是否第一个大于第二个字符串；

for(int i=0;i<s1.size();i++){
    if(s1.substr(i,s2.size())==s2)
        return i;   
    }
}

12.561. 数组拆分 ，俩俩组队，得到最大的min（a,b）

排序，偶数下标相加；

13.1. 两数之和

哈希表最优，时间复杂度O(n);如果想用双指针，则要用一个pair数组(nums[i],i)n,然后把n以first排序，比较n的first，返回n的second、时间复杂度为O(nlogn);

14.209. 长度最小的子数组

双指针，如果sum大于target那么左指针移动到不大于为止，否则sum一直加右指针；

这个题和连续个1思想都对，但是写的很冗余，需改进；如果在一个循环中，有俩个是互补的条件那么就不需要写俩个循环了，写一个循环，另一个写外面就可以了；

for(int i=0;i<nums.size();i++){
   if(nums[i]==1)
      temp++;
   else 
      temp=0;
   res = max(res,temp);
}
while(fast<nums.size()){
   sum+=nums[fast];
   while(sum>=target){//进入这个循环代表，符合题干要求
      res = min(res,fast-slow+1);
      sum-=nums[slow];
      slow++;
   }
   fast++;
}

15.118. 杨辉三角\119. 杨辉三角 II

vector<vector<int>> res={{1}}这样初始化列的大小就是一，如果用resize那么就不用push了，直接可以用下标表示数组，否则没有初始化不能直接用下标要建一个vector<int>；

在算组合数C（n，m）的时候，防止溢出采用边乘边除的方法；

int C(int n,int k){ 
    k = min(k,n-k);
    int res = 1;
    for(int i=1;i<=k;i++){
        res=res*(n-k+i)/i;
    }
    return res;
}

16.153. 寻找旋转排序数组中的最小值，寻找旋转排序数组中的最小值 II

用二分查找，但是要和right去比；我是和nums[0]相比虽然也能做对但会有缺陷；如果元素不是独一无二的，那么就要先去除尾部和头部相等的部分；

 while (low < high) {
      int mid = low + (high - low) / 2;
      if (nums[mid] < nums[high]) {
          high = mid;
       }
      else {
          low = mid + 1;
      }
 }

17.26. 删除有序数组中的重复项

用完unique之后要记得-nums.begin(),得到去重后有效数组后的第一位索引5；重复元素每次都移到末尾，如果只用unique那么会得到*it等于0 1 2 3 4 2 2 3 3 4的中的2;

vector<int> nums = {0,0,1,1,1,2,2,3,3,4};
int index = unique(nums.begin(),nums.end())-nums.begin();
auto it = unique(nums.begin(),nums.end());//*it==2

18.136. 只出现一次的数字

有a^a = 0；0^a = a所以有 a^b^a = a^a^b = b；索引把所以值异或；cout<<(a^b)<<endl;

19.7. 整数反转

while(x){
   sum=sum*10+x%10;
   x/=10;
}

20.50. Pow(x, n)

利用二进制和反复平方的思想，时间复杂度为O（logn）;

while(n){
   if(n&1) res*=x;
   x*=x;
   nn=nn>>1;
}

21.367. 有效的完全平方数

用二分法然后比较mid和double（num/mid）的大小；

22.287. 寻找重复数

可以使用二分法解决该问题。对于这个题目，我们可以利用鸽笼原理，设定一个中间值 mid，统计数组中小于等于 mid 的数的个数，如果这个数的个数超过了 mid，说明重复的数在 [1, mid] 的范围内，否则重复的数在 [mid + 1, n] 的范围内。时间复杂度是O（nlogn）；