算法的学习

2025-04-09

我的算法笔记

查找

 #include<iostream>
 using namespace std;
 int n,m;
 void erfen(int x,int arr[]){
     int q=-1;
     int p=n;
     while(q+1<p){
         int a=(q+p)/2;
         if(arr[a]<x){
             q=a;
         }else p=a;
     }if(arr[p]==x)cout<<p+1<<" ";
     else cout<<-1<<" ";
 } 
 int main(){
     cin>>n>>m;
     int arr[n+10];
     for(int i=0;i<n;i++){
         cin>>arr[i];
     }
     int a;
     while(m--){
         cin>>a;
         erfen(a,arr);
     }
     return 0;
 }

这就是一个普通的二分查找，其中的erfen()就是一个所谓的二分模版。而且思路其实看完题就可以想出来。我觉得没啥好讲的。

A-B数对

链接：P1102 A-B 数对 - 洛谷

 #include<iostream>
 using namespace std;
 #include<algorithm>
 long long n, m;
 int arr[10000000];
 int erfenl( int arr[],int x) {
     int q = 0;
     int p = n+1;
     while (q+1< p) {
         int a = (q + p) / 2;
         if (arr[a] < x) {
             q = a;
         }
         else p = a;
     }if (arr[p] == x)return q;
 
 }
 int erfenw(int arr[],int x) {
     int q = 0;
     int p = n+1;
     while (q+1< p) {
         int a = (q + p) / 2;
         if (arr[a] <= x) {
             q = a;
         }
         else p = a;
     }if (arr[q] == x)return q;
 }
 int main() {
     cin >> n >> m;
     for (int i = 1; i < n+1; i++) {
         cin >> arr[i];
     }
      long long s=0;
     sort(arr+1,arr+n+1);
     for(int i=1;i<n+1;i++){
         int a=erfenw(arr,m+arr[i]);
         int b=erfenl(arr,m+arr[i]);
 
         s+=a-b;
     
     }cout<<s;
     
     return 0;
 }

本体的意思是在数组中寻找两个数，使他们的差值等于一个定值，问有多少组这种对数。可以采用两个循环嵌套。因为题目上面说“不同位置的数字一样的数对算不同的数对”，这就说明了第一层循环必须是遍历，我们必须对每一个数字都要进行计算。但是在内层的嵌套之中，就可以采用二分的思想，毕竟二分就是适合在一个数组中找出一个确定的数字。这个确定的数字就是arr[i]+m,所以就是说要找到数组中有多少个这种数。找到第一个这个数字，找到最后一个这个数字，然后两者的下标相减就行。关于找到这两个数字，可以采用二分之中的第一个大于等于的下标和第一个小于等于的下标，就是控制if语句中的“<”和“<=”这两种情况。

砍树

链接：[P1873 COCI 2011/2012 #5] EKO / 砍树 - 洛谷

 #include<iostream>
 #include<algorithm>
 using namespace std;
 long long n, m;
 int arr[10000000];
 int main() {
     cin >> n >> m;
     long long a = 0;
     for (long long i = 0; i < n; i++) {
         cin >> arr[i];
         a += arr[i];
     }
     sort(arr, arr + n);
     long long l = 0;
     long long r = arr[n-1];
     long long b = a - m;
    long long t = 0;
    int mid;
     while (l + 1 < r) {
          mid = (l + r) / 2;
          t = 0;
         for (int i = 0; i <n; i++) {
             if (arr[i] > mid) {
                 t += arr[i]-mid;
             }
         }
         if (t < m) {
             r = mid;
         }
         else l = mid;
     }
     cout << l;
 }

这个题要找到一个数字，使得大于这个数字的数字与这个数字的差的和要大于m，并且这个数字要尽可能大，其实我一开始并不知道应该怎么去写。但是我知道这个数字肯定是要在这个数组的最大值和0之间的。如果我把这之中的所有的数字遍历一遍，我一定可以找到这个数字，这是暴力解法。我们可以对其优化，关于在数组中找数字，其实可以采用二分的思路。我们把左边界定位0，右边界定位最大值。然后我们第一次定中间的数字为要找的数字，如果这个计算的和要小于m，就说明这个数字大了，答案应该是在左边，那我们把右边界定位这个数字。如果是大于m，我们尝试寻找有没有比跟这个数字更大，同时可以满足这个要求的数字，答案应该是在这个数字的右边，那我们把左边界定为这个数字。其实这就是二分的思想。那二分写就行。

木材加工

链接：P2440 木材加工 - 洛谷

 #include<iostream>
 #include<algorithm>
 #include<iomanip>
 using namespace std;
 long long n, k;
 long long arr[1000010];
 bool fc(long long x) {
     int s = 0;
     for (int i = 0; i < n; i++) {
         s += arr[i] / x;
     }
     return s >= k;
 }
 int main() {
     cin >> n >> k;
     for (int i = 0; i < n; i++) {
         cin >> arr[i];
     }
     sort(arr, arr + n);
     long long l = 0;
     long long r = 10e8;
     while (l + 1 < r) {
         long long mid = (l + r) / 2;
         if (fc(mid)) {
             l = mid;
         }
         else r = mid;
         
     }
     cout<<l;
     return 0;
 }

一开始的思路是打算先给数组排序，然后我找到数组第一个数，也就是最小的数字，然后对这个数字进行二分，找到答案，然后把数组进行遍历，把数组里面的每个数字除以答案，求和看是不是大于等于k。但是我忽略了一个问题，就是这个答案一定就在最小的数字里面吗？存在一种情况就是，如果答案比第一个数字大，但是后面仍是可以除成k。所以在二分的时候，边界的初始值就不能是以最小的数字来，而是以题目最大的数字来。

烦恼的高考志愿

链接：P1678 烦恼的高考志愿 - 洛谷

 #include<iostream>
 #include<algorithm>
 #include<iomanip>
 using namespace std;
 int a1[100100];
 int b1[100100];
 long long m, n;
 long long erfen(int x) {
     int l = -1;
     int r = m;
     if(x<=a1[0]){
         return a1[0]-x;
         }
     while (l + 1 < r) {
         int mid = (l + r) / 2;
         if (x<a1[mid]) {
            
             r = mid;
         }
         else l = mid;
         
     }return min(abs(x-a1[l]),abs(x-a1[r]));
 }
 int main() {
     cin >> m >> n;
     for (int i = 0; i < m; i++) {
         cin >> a1[i];
     }
     sort(a1, a1 + m);
     for (int j = 0; j < n; j++) {
         cin >> b1[j];
     }
     long long s = 0;
     for (int i = 0; i < n; i++) {
         s += erfen(b1[i]);
     }
     cout << s;
     return 0;
 }

其实这个本质上就是找到数组中最靠近x的数，这个方法也是二分的方法，二分中的if，边界是指向最后一个<的数字，即是最后一个小于x的数，另一个边界是第一个大于等于x的数字，那么最接近的数字可不就是左边界和右边界的最小数么。

一元三次方程求解

链接：[P1024 NOIP 2001 提高组] 一元三次方程求解 - 洛谷

 #include<iostream>
 #include<algorithm>
 #include<iomanip>
 using namespace std;
 double a, b, c, d;
 double fc(double x) {
     return a * x * x * x + b * x * x + c * x + d;
 }
 double erfen(double x) {
     double l = x;
     double r = x + 1;
     while (l + 0.001 < r) {
         double mid = (l + r) / 2;
         if (fc(mid)*fc(r) < 0) {
             l = mid;
         }
         else r = mid;
     }return r;
 }
 int main() {
     cin >> a >> b >> c >> d;
     int s = 0;
     for (double i = -100; i < 101; i++) {
         if (fc(i) == 0) {
             s++;
             cout << fixed << setprecision(2) << i << " ";
         }
         else if (fc(i) * fc(i + 1) < 0) {
             cout <<fixed<<setprecision(2) << erfen(i) << " ";
             s++;
         }
         
         if (s == 3)break;
     }return 0;
 }

因为题目说了三个根都在-100到100之间，其实我们可以在这个区间中遍历，遍历每一个数字，并以它和它+1作为区间，对它进行二分，找到答案就行，但是在if这里，因为要找根，两个边界的值的乘积肯定是小于0的，如果小于0的话，就表示根在范围之中，因为一开始两个边界肯定是一个大于0，一个小于0，所以我们只改变一边，就是左边，我们通过mid的值和r的值的乘积是否为0来判断，如果小于0，说明mid还是在答案的左边，还可以往右边靠近，如果是大于0，就说明mid和r都在答案的一侧，这时就要改变r往左走。

丢失的数字

链接：268. 丢失的数字 - 力扣（LeetCode）

 class Solution {
 public:
     int missingNumber(vector<int>& nums) {
 long s=0;
 int n=nums.size();
 long t=n*(n+1)/2;
 for(int i=0;i<n;i++){
     s+=nums[i];
 }return t-s;
     }
 };

解题思路：这个题其实很简单，因为题目说了是数值是从0到n，完全可以求出0-n的和减去数值的和，差值就是我要的答案。

搜索旋转排序数组

链接：33. 搜索旋转排序数组 - 力扣（LeetCode）

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

解题思路：这个题我们采取的是一次二分的方法，因为题目告诉了一开始是个升序序列，之后会中间随机选取一个数字，之前的数字（包括这个数字）跟后面的数字进行了交换。我们取得mid，其中很重要的一个点就是mid的一边一定是顺序的。if nums[0]<nums[mid]这就是在判断mid的左边是否是顺序的，如果是顺序的，然后再看target是否是在左边这个范围内，如果是的，右边界移动，如果不是左边界移动。如果左边界不是顺序的，那么就说明右边界是顺序的，在右边界内判断target在不在右边界内。二分得要在顺序数组内判断，所以先判断是不是顺序。然后在原来是靠arr[mid]<target来判断，target在哪边，但是这个有一半是非顺序的，不能就这样写，但是我们是有半边是顺序的，我们可以通过判断target是否在这个半边来确定，同时判断的条件也要改成nums[0] <= target && target < nums[mid]这种形式。

删除数组中重复的数字

链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

 class Solution {
 public:
     int removeDuplicates(vector<int>& nums) {
        int n=nums.size();
        if(n==0) return 0;
        int j=0;
        for(int i=0;i<n;i++){
         if(nums[j]!=nums[i]){
             nums[++j]=nums[i];
         }
        }return j+1;
     }
 };

解题思路：我认为这个题目没有说清楚，他隐含了一个条件是重复的数字都是相邻的，用双指针解法，首先j指向nums[0],i开始遍历，如果i下标的nums是跟j下标的数组不一样的话，j++的下标就是这个数字，但是这有一个问题，如果我的数组内重复的元素不是挨在一起的呢？

三数之和

链接：15. 三数之和 - 力扣（LeetCode）

 class Solution {
 public:
     vector<vector<int>> threeSum(vector<int>& nums) {
         int n = nums.size();
         sort(nums.begin(), nums.end());
         vector<vector<int>> ans;
         // 枚举 a
         for (int first = 0; first < n; ++first) {
             // 需要和上一次枚举的数不相同
             if (first > 0 && nums[first] == nums[first - 1]) {
                 continue;
             }
             // c 对应的指针初始指向数组的最右端
             int third = n - 1;
             int target = -nums[first];
             // 枚举 b
             for (int second = first + 1; second < n; ++second) {
                 // 需要和上一次枚举的数不相同
                 if (second > first + 1 && nums[second] == nums[second - 1]) {
                     continue;
                 }
                 // 需要保证 b 的指针在 c 的指针的左侧
                 while (second < third && nums[second] + nums[third] > target) {
                     --third;
                 }
                 // 如果指针重合，随着 b 后续的增加
                 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                 if (second == third) {
                     break;
                 }
                 if (nums[second] + nums[third] == target) {
                     ans.push_back({nums[first], nums[second], nums[third]});
                 }
             }
         }
         return ans;
     }
 };

解题思路：这一个题首先要把三数求和转化成二数求和。首先你要对数组进行排序，之后对数组进行遍历，因为是要求三数的和为0，那么可以转化成二数求和为-nums[i],在i之后的数字采用双指针的解法，一个指针j指向i+1，一个指向最后一个数字，然后两者开始靠拢，如果nums[j]+nums[k]大于目标，k--，如果小于目标，会退出while，同时for的j会自加。直到相加等于-nums[i];

最接近的三数之和

链接：16. 最接近的三数之和 - 力扣（LeetCode）

 class Solution {
 public:
     int threeSumClosest(vector<int>& nums, int target) {
         int n=nums.size();
         sort(nums.begin(),nums.end());
         int ans=nums[0]+nums[1]+nums[2];
         for(int i=0;i<n;i++){
             int k=n-1;
           int j=i+1;
                 while(j<k){
                     int a=nums[i]+nums[j]+nums[k];
                     if(abs(target-ans)>abs(target-a)){
                         ans=a;
                     }
                     if(a>target){
                         k--;
                     }else if(a==target){
                         return a;
                     }else if(a<target){
                         j++;
                     }
                 }
             
         }return ans;
     }
 };

解题思路：这一个题目跟上一个题类似，不过不同的点在于，这个题j是没有单独的给for循环自加的，而是通过判断和与目标的大小来决定是否自加。

四数之和

链接：18. 四数之和 - 力扣（LeetCode）

 class Solution {
 public:
     vector<vector<int>> fourSum(vector<int>& nums, int target) {
         vector<vector<int>> quadruplets;
         if (nums.size() < 4) {
             return quadruplets;
         }
         sort(nums.begin(), nums.end());
         int length = nums.size();
         for (int i = 0; i < length - 3; i++) {
             if (i > 0 && nums[i] == nums[i - 1]) {
                 continue;
             }
             if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                 break;
             }
             if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                 continue;
             }
             for (int j = i + 1; j < length - 2; j++) {
                 if (j > i + 1 && nums[j] == nums[j - 1]) {
                     continue;
                 }
                 if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                     break;
                 }
                 if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                     continue;
                 }
                 int left = j + 1, right = length - 1;
                 while (left < right) {
                     long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                     if (sum == target) {
                         quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});
                         while (left < right && nums[left] == nums[left + 1]) {
                             left++;
                         }
                         left++;
                         while (left < right && nums[right] == nums[right - 1]) {
                             right--;
                         }
                         right--;
                     } else if (sum < target) {
                         left++;
                     } else {
                         right--;
                     }
                 }
             }
         }
         return quadruplets;
     }
 };

解题思路：这个题的思路也跟上一个类似，但是他的注意要求很多，第一，最外层的i在遍历的时候，他是不能有重复的，如果上一个和这个重复，那么这个的循环就要跳过。如果存在nums[i]+nums[i+1]+nums[i+2]+nums[i+3]的和大于目标，因为这个已经是最小的和了，如果这个和都大于目标的话，那么就没有答案。如果nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1]这个都小于目标，以为这个和是最大值，这个都小的话，那么两个指针也就没有必要移动了，就可以跳过这个循环，进入下一个循环。后面的也是同理。 while (left < right && nums[left] == nums[left + 1]），因为存在有相同点数字，找到相同的数字的最后一个，这样while结束，我的指针就指向了相同数的最后一个，但是因为我已经在第一个数相同的数字那里已经记录了，所以现在相同的数字我也不要，指针再次变动一次，这样就是下一个不一样的数字了，哪怕我这个数字只有一个，那我可以跳过while循环，但是我还得把指针变动一次，指向下一个数字。后面同理。如果四数的和大于目标，右指针自减，否则就是左指针自加。

第一个缺失的正整数

链接：41. 缺失的第一个正数 - 力扣（LeetCode）

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

解题思路：这个题他有时间和空间的限制，不同的哈希表并不能满足这一情况，对此我们只能针对题目给的数组进行改动。我们只关心数组中大于0的数组。而我们所需要的答案肯定是在[0,n(n是数组长度)]之间的，我们把给的数组变成哈希表的类型。假设arr[0]=3,那么在正常的哈希表中，haxi[3]=1。相当于是把数组给排序了一遍，然后原来下标为0变成了下标为3。在这个题中，我们可以把数组中[0,n]的数字按照进行“排序”，arr[0]=3，我们并不需要真的把这个3放到第三位，我们可以像哈希表一样，把下标3给打上标记，这样一通打上标记之后，[0,n]之间第一个没有打上标记的就是我们所需要找到的答案，这个思路跟哈希表的思路一样。那么关于小于等于0的数字，我们把他们变成n+1，这样不会干扰我们。我们打算把数组先都变成正数，然后打上标记的方法是给数字变负。即是nums[num-1]=-abs(nums[num-1])，但是注意，因为我们是变化自身的数组，这样就存在我后面遍历到已经产生变动的数字，所以针对这个情况，好在一开始数字都是正数，变化只是加个负号而已，我们可以把这个数字先取绝对值，这样就获得了原来没有变化的数字，然后进行操作，这就是为什么一开始要num=abs(nums[i])

最长回文子串

链接：5. 最长回文子串 - 力扣（LeetCode）

 #include <iostream>
 #include <string>
 #include <vector>
 
 using namespace std;
 
 class Solution {
 public:
     string longestPalindrome(string s) {
         int n = s.size();
         if (n < 2) {
             return s;
         }
 
         int maxLen = 1;
         int begin = 0;
         // dp[i][j] 表示 s[i..j] 是否是回文串
         vector<vector<int>> dp(n, vector<int>(n));
         // 初始化：所有长度为 1 的子串都是回文串
         for (int i = 0; i < n; i++) {
             dp[i][i] = true;
         }
         // 递推开始
         // 先枚举子串长度
         for (int L = 2; L <= n; L++) {
             // 枚举左边界，左边界的上限设置可以宽松一些
             for (int i = 0; i < n; i++) {
                 // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                 int j = L + i - 1;
                 // 如果右边界越界，就可以退出当前循环
                 if (j >= n) {
                     break;
                 }
 
                 if (s[i] != s[j]) {
                     dp[i][j] = false;
                 } else {
                     if (j - i < 3) {
                         dp[i][j] = true;
                     } else {
                         dp[i][j] = dp[i + 1][j - 1];
                     }
                 }
 
                 // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                 if (dp[i][j] && j - i + 1 > maxLen) {
                     maxLen = j - i + 1;
                     begin = i;
                 }
             }
         }
         return s.substr(begin, maxLen);
     }
 };

解题思路：首先这个题目的核心思想是用动态规划来做，dpi表示s的第i个到第j个字符串是否为回文序列。首先我们知道单个字符肯定是回文的，所以dpi=1;我们遍历回文串的长度，从1到n，左边界i可以从0开始，右边界j就是左边界加上我们遍历的字符串的长度。我们还是判断s[i]和s[j]，如果相同的话，就要分情况讨论，普通情况下：这俩相等，那就要看dpi+1是否是字符串。如果一个字符串是回文串，那么我在首尾各加上一个相同的字符，那这个字符串依旧是回文的。我们把dpi=dpi+1理解成，如果字符串(首尾分别是i+1，j-1)是回文串，那么我前后各加上一个相同的字符，即是左边界-1，右边界+1，就变成了dpi,那么dpi是不是字符串就取决于我的dpi+1是不是回文了。另外一种情况就是当我的字符串只有3个，那么我就不可能i+1,j-1的，我们就直接判断这个是不是字符串即可。

回形链表

链接：141. 环形链表 - 力扣（LeetCode）

 /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
 class Solution {
 public:
     bool hasCycle(ListNode *head) {
        unordered_set<ListNode*>hash;
        while(head!=NULL){
         if(hash.count(head)){
             return true;
         }
         hash.insert(head);
         head=head->next;
        } 
        return false;
     }
 };

解题思路：这个题目不难，就是把每一个节点都丢到set里面，然后利用count()来确定是否出现过，主要还是要熟悉一下set的用法以及碰到链表题的写法。

多数元素

链接：169. 多数元素 - 力扣（LeetCode）

 class Solution {
 public:
     int majorityElement(vector<int>& nums) {
         unordered_map<int,int>hash;
         int a=0,b=0;
         for(int i:nums){
             hash[i]++;
             if(hash[i]>b){
                 b=hash[i];
                 a=i;
             }
         }
         return a;
     }
 };

解题思路：这一个题也不难，但是我想说的是map和普通数组的差异。这题一开始还是打算用arr[nums[i]]++,这样来记录的，但是发现了两个问题。第一个问题是：如果我的nums[i]是负数怎么办？数值的下标不能为负啊。其二，我都是先记录完之后再遍历一遍找答案，这就复杂了。针对第二个问题，其实我可以把他简化到记录的遍历之中，本身就是找最大值么，在记录的时候，我就是设置最大值为0，记录完一个比较一下最大值，更新一下。就是普通遍历数组找最大值的方法的方法塞到了记录的遍历里面。针对第一个问题，得要用map，其实我用数组的本质上就是利用下标和值的关系。而map就很好的符合这一要求。用法都差不多，而且还没有负数限制。

字母异位词分组

链接：49. 字母异位词分组 - 力扣（LeetCode）

 class Solution {
 public:
     vector<vector<string>> groupAnagrams(vector<string>& strs) {
         unordered_map<string,vector<string>>hash;
         for(string s:strs){
             string x=s;
             sort(x.begin(),x.end());
             hash[x].emplace_back(s);
         }
         vector<vector<string>>ans;
         for(auto it=hash.begin();it!=hash.end();it++){
             ans.emplace_back(it->second);
         }
         return ans;
     }
 };

解题思路：这个题的思路就是因为单词的字母顺序是不一样的，但是字母的种类是一样的，其实可以这样写。你先把单词的字母排序，排序完之后你就会发现顺序不一样的都会变成一样。这个时候你就可以用map来记录。map的key就是排序后的单词，它的value就是排序之前的单词。这样相当于就是把这些单词分类了。但是map的value是一个vector<string>。

回到首页

最长连续序列

链接：128. 最长连续序列 - 力扣（LeetCode）

 class Solution {
 public:
     int longestConsecutive(vector<int>& nums) {
         stack<int>arr;
         sort(nums.begin(),nums.end());
         int max=0,t=0;
         for(int i=0;i<nums.size();i++){
             if(arr.empty()){
                 arr.push(nums[i]);
                 t++;
             }else{
                 if(arr.top()==nums[i]-1){
                     t++;
                 }else if(arr.top()==nums[i]){
 
                 }else {
                     max=max>t?max:t;
                     t=1;
                 }
                 arr.push(nums[i]);
             }
         }
          max=max>t?max:t;
         return max;
     }
 };

解题思路：这个题首先可以想到先把nums给排序，然后看后面的数字是不是前面的数字加1，如果是的话，计数器t++，不是的话，记录当前的t是不是最大的max，然后t=0，但是有一点值得说明的是，我数组最后一个数字处理完，此时的t不一定就是0，t可能还是记录了最后一端连续的数字的，所以最后还有把t跟max比较一下。

重复的dna序列

链接：187. 重复的DNA序列 - 力扣（LeetCode）

 class Solution {
     const int L = 10;
 public:
     vector<string> findRepeatedDnaSequences(string s) {
         vector<string> ans;
         unordered_map<string, int> cnt;
         int n = s.length();
         for (int i = 0; i <= n - L; ++i) {
             string sub = s.substr(i, L);
             if (++cnt[sub] == 2) {
                 ans.push_back(sub);
             }
         }
         return ans;
     }
 };

解题思路:这个题本来是打算用set写的，但是发现set的特性不适合，就是set的容器里面是不允许重复的，一个键值只能出现0或者1次，如果用set就会出现问题，第一次出现判断是否出现，没有出现，然后加入set，第二次判断是否出现，出现过一次，然后就会加入到vector里面，但是第三次判断的时候就出问题了，第三次判断依旧是出现过一次，加入到vector里面，这样就导致vector里面放了2个相同的元素。所以针对这一情况，不能只是单纯的判断是否出现，而是要精确到判断只出现2次才行，这时就要用map了。

比特位计数

链接：338. 比特位计数 - 力扣（LeetCode）

 class Solution {
 public:
     vector<int> countBits(int n) {
         vector<int>dp(n+1,0);
 
         for(int i=1;i<=n;i++){
             if(i%2){
                 dp[i]=dp[i-1]+1;
             }else{
                 dp[i]=dp[i>>1];
             }
         }
         return dp;
     }
 };

解题思路：还是动态规划的思想，首先如果数字是奇数，那么二进制最后一位肯定是个1，那么我们计算这个二进制1的数量可以看成两个部分，前面一段和最后一个1，这俩相加就行，那么前面一段1的个数相当于就是这个数字-1的数字。举例：5是101，看成100+1，其中100就是4的二进制，总结可以写成5=4+1。这就是dp[n]=dp[n-1]+1。如果n是偶数，那么最后一位就是0，那么它的1的个数和它的二进制去到最后一个0的二进制没有区别，举例：8 1000，最后一位是0，那么和1000去除最后一位0，也就是100没有区别。100就是4，再次举例 10 1010 去除最后一位 101 5，1的个数是不变的。那么去除最后一位，就是[i>>1]的操作，i>>1表示i向右位移1位。

不同路径2

链接：63. 不同路径 II - 力扣（LeetCode）

 class Solution {
 public:
     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
          vector<vector<int>>dp(100,vector<int>(100));
         int m=obstacleGrid.size();
         int n=obstacleGrid[0].size();
         if(obstacleGrid[m-1][n-1]||obstacleGrid[0][0])
         return 0;
         dp[0][0]=1;
         for(int i=0;i<obstacleGrid.size();i++){
             for(int j=0;j<obstacleGrid[0].size();j++){
                 if(i==0||j==0){
                    if(i==0&&j>0){
                     if(obstacleGrid[i][j-1]==1){
                         dp[i][j]=0;
                     }else{
                         dp[i][j]=dp[i][j-1];
                     }
                    }
                    if(j==0&&i>0){
                     if(obstacleGrid[i-1][j]==1){
                         dp[i][j]=0;
                     }else{
                         dp[i][j]=dp[i-1][j];
                     }
                    } 
             }
             else{
                 if(obstacleGrid[i][j-1]==0){
                     dp[i][j]+=dp[i][j-1];
                 }else{
                 }
                 if(obstacleGrid[i-1][j]==0){
                     dp[i][j]+=dp[i-1][j];
                 }else{
 
                 }
             }
         }
     }return dp[m-1][n-1];
     }
 };

解题思路：其实这个题主要还是记住一个模版，就是走格子，问你有多少种走法。因为只能往下或者往右走，我们用dpm数组，代表从0到i有多少种走法。dpi=dpi-1+dpi，但是要注意i=0或者j=0的情况。

跳跃游戏2

链接：45. 跳跃游戏 II - 力扣（LeetCode）

 class Solution {
 public:
     int jump(vector<int>& nums) {
         int n=nums.size(); 
         vector<int>dp(n,0);
         for(int i=0;i<n;i++){
             int a=0;
             if(nums[i]<n-1-i){
                 a=nums[i];
             }else{
                 a=n-i-1;
             }
             for(int j=1;j<=a;j++){
                 if(dp[i+j]!=0){
                     if(dp[i+j]>dp[i]+1){
                         dp[i+j]=dp[i]+1;
                     }
             }else if(dp[i+j]==0){
                 dp[i+j]=dp[i]+1;
             }
         }
     }return dp[n-1];
     }
 };

解题思路：我们采用dp[i]表示从0到i用最少的次数到达。举例nums[2]=3,那么nums[3],nums[4],nums[5]都是nums[2]+1就可以到达。但是我们要注意一点，可能dp[2]+1比dp[3]要大，如果要大，那么意味着之前有数字到这里需要的次数比从nums[2]到达要更少，那么我们其实没有必要更新数字。同时还要注意，nums[i]往后跳的时候，可能跳的最大值会超过数组的长度。这时候就要判断，nums[i]往后跳的范围到底是nums[i]还是nums.size()-i-1。

交错字符串

链接：97. 交错字符串 - 力扣（LeetCode）

 bool isInterleave(string s1, string s2, string s3) {
 int m = s1.size();
     int n = s2.size();
     vector<vector<bool>>dp(m + 1, vector<bool>(n + 1, false));
     if(m+n!=s3.size())return false; //这里判断s1的长度加上s2的长度是否可以等于s3的长度，如果不可以的话，就返回false
     dp[0][0] = true;//这里的0表示空字符串,因为判断s1和s2的第一个字符时，需要dp[1-1]即dp[0]，为了方便采用ture,更重要的是出现是s1=",s2="",s3=""，这一特殊情况。
 
     for (int i = 1; i < m + 1; i++) {
         if (s1[i - 1] == s3[i - 1]) {//注意这边i-1是因为i是第i个字符，要变化到数组的下标需要减一
             if (dp[i - 1][0]) {//如果前i-1个字符都可以配对，那么前i个可以配对
                 dp[i][0] = 1;
             }
         }
     }//单独判断是s1的第i个字符能否与s3的第i个字符相等。
     for (int i = 1; i < n + 1; i++) {
         if (s2[i - 1] == s3[i - 1]) {
             if (dp[0][i - 1]) {
                 dp[0][i] = 1;
             }
         }
     }
    
     
     for (int i = 1; i < m+1; i++) {
         for (int j = 1; j < n+1; j++) {
             if (s2[j-1] == s3[i + j - 1]) {//这里举个例子，现在遍历到S1的第2个，s2的第3个,此时出现s2的第三个与s3的第五个相等，但是因为这里的i,j都是代表第多少个，变到数组下标都要减一。
                 if (dp[i][j - 1]) {//接上面的例子，此时我应该判断s1的前2个和s2的前两个能否与s3的前4个配对，对应的是dp[i][j-1]；
                     dp[i][j] = 1;
                 }
             }
             if (s1[i-1] == s3[i + j - 1]) {
                 if (dp[i - 1][j]) {
                     dp[i][j] = 1;
                 }
             }
         }
     }
     return dp[m][n];

解题思路：采用动态规划的写法，dpi表示s1的前i个字符和s2的前j个字符组合，可以配对上s3的前i+j个字符。其中，假设现在遍历到dpi，如果s2的x等于s3相对应的字符的话，判断dpi是否是true，如果可以的话，既然s的前i+x-1个字符可以配对，同时s2的x也能配对，这样dpi=true;但是这里有一个点，就是dp的0并不是表示s1的第一个字符，而是表示空字符串。

最长有效括号

链接：32. 最长有效括号 - 力扣（LeetCode）

 class Solution {
 public:
     int longestValidParentheses(string s) {
         int size = s.length();
         vector<int> dp(size, 0);
 
         int maxVal = 0;
         for(int i = 1; i < size; i++) {
             if (s[i] == ')') {
                 if (s[i - 1] == '(') {
                     dp[i] = 2;
                     if (i - 2 >= 0) {
                         dp[i] = dp[i] + dp[i - 2];
                     }
                 } else if (dp[i - 1] > 0) {
                     if ((i - dp[i - 1] - 1) >= 0 && s[i - dp[i - 1] - 1] == '(') {
                         dp[i] = dp[i - 1] + 2;
                         if ((i - dp[i - 1] - 2) >= 0) {
                             dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                         }
                     }
                 }
             }
             maxVal = max(maxVal, dp[i]);
         }
         return maxVal;
     }
 };

解题思路：链接跳转我觉得人思路讲的比我好得多。一开始打算是照着最长回文来写，发现不行，最后打算用最大子串数组和来写，也不行。看了一下这个题解，他的关键在于对于情况的分析，他列出了两种情况，一种是“（）（）"这种，还有一种是“（（（）））”这种。

excel表列名称

链接：168. Excel 表列名称 - 力扣（LeetCode）

 class Solution {
 public:
     string convertToTitle(int columnNumber) {
         string ans;
         int a=columnNumber;
         int b=0;
         while(a){
             a--;
               ans+=a%26+'A';     
             a=a/26;
         }
         reverse(ans.begin(),ans.end());
         return ans;
     }
 };

解题思路：这个题很有意思，看似是26进制转化，但是实际上不是的，我们那普通的5进制转换吧，当x=5时，变成10，那么每一位数字的范围就是[0,4],但是这个题他的范围是[1,26]，并不是[0,25]。如果我们单纯的取模26，那么会出现[0,25]，那就会出问题，假设我是26，那么会出现aa，同时后面x/26也就是==1，会出现额外的一轮。所以不能单纯的/26,取模会出现[0,25],但是题目却是[1,26]映射[a,z]。我借用一段话“在正常的基数转换中，例如从十进制转换到二进制或十六进制，我们通常不需要减一。这是因为这些系统的基数（2或16）都有一个表示0的符号。例如，在二进制中，我们有0和1两个符号；在十六进制中，我们有0到9和A到F共16个符号。

然而，在这个问题中，我们的基数是26，但是我们只有'A'到'Z'共26个符号，并且没有符号可以表示0。所以，我们需要将输入的数减一，以便将0到25映射到'A'到'Z'。

总的来说，是否需要减一取决于我们的基数系统是否有一个表示0的符号。如果有，我们通常不需要减一；如果没有，我们可能需要减一。”

pow(x,n)

链接：50. Pow(x, n) - 力扣（LeetCode）

 class Solution {
 public:
     double myPow(double x, int N) {
         double ans = 1;
         long long n = N;
         if (n < 0) { // x^-n = (1/x)^n
             n = -n;
             x = 1 / x;
         }
         while (n) { // 从低到高枚举 n 的每个比特位
             if (n & 1) { // 这个比特位是 1
                 ans *= x; // 把 x 乘到 ans 中
             }
             x *= x; // x 自身平方
             n >>= 1; // 继续枚举下一个比特位
         }
         return ans;
     }
 };

解题思路：快速幂这一道题得要用快速幂的写法，上面有详细题解，我们以13举例子，n^{13可以计算成n*n}4n^{8。而我们乘法的操作就是用if来完成的，很巧妙的发现13的二进制中1101,位数为1的正好表示2}0,2^2,23,也就是1,4,8。所以我们可以通过二进制表达式来计算。如果这个比特位是1，那么ans就要乘上二进制这一位代表的数。计算完之后，我们二进制要往前一位去判断是否为一，这里可以采用右位移的办法。当然我们还等知道这一位所代表的是什么数字。假设第二位是n^{4，按照二进制规则，第三位是n}8，就是xx而已。回到首页

排列序列

链接：60. 排列序列 - 力扣（LeetCode）

     vector<int>num;
         int factorial=1;
         for(int i=1;i<=n;i++){
             num.push_back(i);
             factorial=factorial*i;
         }
         k--;
         vector<int>res;
         int t=n;
         while(num.size()!=0){
             factorial=factorial/t;
             int x=k/(factorial);
             res.push_back(num[x]);
             k=k%factorial;
             t--;
             num.erase(num.begin()+x);
         }
           string result = "";
     for (int val : res) {
         result += to_string(val);
     }
 
     return result;

解题思路：其实这个题目挺像找规律的。。。链接看这个图自己写的，至于原理为什么是这个，其实我也没有反应过来。尝试讲讲吧。首先最简单的办法就是把所有排序都列出来，这就是暴力的思想。从中我们发现一点，那就是第一排到第（n-1）！排都是1，第（n-1）！+1排到第2（n-1）！都是2，以此类推。我们只知道需要多少排，其实我们可以知道我们要的排在哪一段之中。我们举个例子，假设n=3，那么前2排的首字符就是1。3,4排就是2。5,6排就是3。k=4,我们要计算第四排，他是在首字符为2的段落里面。我们可以把k-1，这样通过（4-1）/2=1,我们就可以知道他是在第1+1=2段里面。总的来说，我们可以把第一个位为1的那几排看成一段，第一位为2的那几段看成一段，以此类推。因为可以肯定第一段的长度就是（n-1）！，所以我们知道k是在第几段了。接着我们使用num数组，[1,2……n]，这就是表示，当（k-1）/(n-1)!=x;num[x]就是我们要的第一位数字。接下来，我们针对第二段来看。我们需要知道在第二段里面，我们要的排数是在第二段的相对位置。所以有k=k%（n-1）！；此时我们又可以按照之前的思路进行循环计算。但是重要的一点，因为一个数字只会出现一次，第一位的数字已经出现了，所以在num上面就要删除这个数字。

存在重复元素3

链接：220. 存在重复元素 III - 力扣（LeetCode）

 class Solution {
 public:
     bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
         set<long>hash;
         for(int i=0;i<nums.size();i++){
             auto it=hash.lower_bound(nums[i]-valueDiff);
             if(it!=hash.end()&&*it<=nums[i]+valueDiff){
                 return true;
             }
             hash.insert(nums[i]);
             if(hash.size()>indexDiff){
                 hash.erase(hash.find(nums[i-indexDiff]));
             }
         }
         return false;
     }
 };

解题思路：我们采用滑动数组的思想来写。可以看成一个长度为indexdiff的数组，然后找到这个数组中与第一个数字满足条件的数字。我们遍历数组nums，如果hash数组中存在一个数字，这个数字比nums[i]-valuediff要大，同时比nums[i]+valuediff要小，那么就是满足题意的。这就可以return true了。如果没有的话，我们就把这个数字放入hash数组中，又因为hash数组的长度为indexdiff,所以如果长度超过indexdiff,我们要去除数组中第一个数字，而第一个数字就是nums[i-indexdiff],而因为hash数组内的顺序和nums的顺序是一样的。hash数组中的第一个数字，就是nums数组中i下标减去indexdiff。假设indexdiff=3，现在hash数组中有i=3的数字，i=4的数字，i=5的数字。我添加新的i=6的数字，那要去除第一个i=3的数字，6-3=3。总的来说，其实用暴力的话，就是第一层nums遍历，第二次遍历nums[i]-nums[i+indexdiff]。这种方法就是针对第二层循环，比o(index)稍微快一点。

加油站

链接：134. 加油站 - 力扣（LeetCode）

 class Solution {
 public:
     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
         int a=0,b=0;
         int start=0;
         for(int i=0;i<cost.size();i++){
             a+=gas[i]-cost[i];
             b+=gas[i]-cost[i];
             if(b<0){
                 start=i+1;
                 b=0;
             }
         }
         return a<0?-1:start;
     }
 };

解题思路：链接跳转首先这个题一定要明确一点，总油量>总油耗一定有解。而start就是找那个解到底在哪里。暴力的思路就是把每一个点都当成起点，然后遍历一点数组。但是其实是没有必要的。从i到i+1，核心就是剩余油量+gas[i]-cost[i],当这个结果大于等于0，那么我就可以开到i+1，我们来看gas[i]-cost[i]<0的情况，我们假设前三站这个数值都是负数，x1+x2+x3=-a，这时我把这个三个站看成一个整体，那就我想从1到3，只要1的剩余油量>a就行，那么就意味着，我从4一直到最后的的剩余油量比a大就行。就是只用遍历一次就可以了。至于从哪开始，我只需要保证当前的油量不是负数就行了。一直到最后一站，只要不是负数，同时总油量大于总油耗就行。

去除重复字母

链接：316. 去除重复字母 - 力扣（LeetCode）

 class Solution {
 public:
     string removeDuplicateLetters(string s) {
       
         // 记录每个字符最后出现的位置
         std::unordered_map<char, int> last_occurrence;
         for (int i = 0; i < s.size(); ++i) {
             last_occurrence[s[i]] = i;
         }
 
         // 栈用于构建最终结果
         std::stack<char> str;
         // 用于标记字符是否已经在栈中
         std::vector<bool> see(256, false);  // 足够大以覆盖ASCII字符集
 
         for (int i = 0; i < s.size(); ++i) {
             char c = s[i];  // 获取当前字符
             if (!see[c]) {  // 如果当前字符不在栈中
                 // 如果栈顶字符大于当前字符，并且栈顶字符在后面还会出现
                 while (!str.empty() && str.top() > c && i < last_occurrence[str.top()]) {
                     see[str.top()] = false;  // 标记栈顶字符为未见
                     str.pop();  // 移除栈顶字符
                 }
                 see[c] = true;  // 标记当前字符为已见
                 str.push(c);  // 将当前字符压入栈
             }
         }
 
         // 构建最终结果字符串
         std::string ans = "";
         while (!str.empty()) {
             ans = str.top() + ans;  // 注意这里是在前面插入，保持正确的顺序
             str.pop();
         }
 
         return ans;
     }
 };

解题思路:这个题的思路是栈写，我们遍历s，如果s[i]要比栈顶的字符要小，同时如果后面还会出现这个字符，那么就可以把栈顶的字符去掉，然后一直循环，直到栈顶是比s[i]更小的字符。但是有两个点，第一，s[i]这个字符肯定是不能在栈里面有相同的字符，所以，我们要有一个记录数组，如果这个字符放进栈了，对s[i]这个字符打上标记，遍历到下一个一样的字符就可以直接跳过了。第二，要看s后面有没有相同的字符，其实可以用另外一个数组，标记每一个字符最后出现的位置。如果遍历到当前的位置，这个位置要大于我要找的字符所对应的最后位置，那就是意味着后面不会出现这个一模一样的字符了，这时就不能去掉这个字符。反之可以，但是值得注意的是，在去除顶的时候，因为你是从栈里面去除的，所以意味着这个字符是打上进去栈的标记的，这时你得清空这个标记。

递增的三元子序列

链接：334. 递增的三元子序列 - 力扣（LeetCode）

 class Solution {
 public:
     bool increasingTriplet(vector<int>& nums) {
         if(nums.size()<3)return false;
         int small=INT_MAX,mid=INT_MAX;
         for(int num:nums){
             if(num<=small){
                 small=num;
             }else if(num<=mid){
                 mid=num;
             }else if(num>mid){
                 return true;
             }
 
         }
         return false;
     }
 };

解题思路：对数组进行遍历，然后找到遍历过的部分中的最小的两个数字，如果存在之后遍历的数字比第二小的数字大，那么就可以找到了，但是这里存在一个点：假设数组为3 5 1 6，遍历到前两个，small=3，mid=5，之后变成了small=1，mid=5，之后最后的6大于mid，但是我们发现三者的顺序是不对的，但是为什么就可以说是找到呢？其实核心点在于，这个数字比mid大，它隐含的一点就是:在mid之前一定有个比mid小的数字，此时组成子序列的最小值不是small现在指向的数字，而是之前的那一个。我们假设一下，如果mid前面没有比他小的，这有可能出现吗？是不可能的，因为我们是先判断是不是small，如果数字比small大，才会开始判断是不是mid，一定是先出small，如果之后的数字比small大，才会进入mid，否则直接就small改写了。还有一种情况 1 1 1 1 1，针对这种情况，因为有=，所以也可以处理。

摆动序列

链接：376. 摆动序列 - 力扣（LeetCode）

 class Solution {
 public:
     int wiggleMaxLength(vector<int>& nums) {
       if(nums.size()<2)return nums.size();
       int t=0;
       int d=2;
       
       for(int i=1;i<nums.size();i++){
         if(nums[i]-nums[i-1]>0){
            if(d==0){
             t++;
            
            }if(d==2)t++; 
            d=1;
         }else if(nums[i]-nums[i-1]<0){
             if(d==1){
                 t++;
                 
             }if(d==2)t++;
             d=0;
         }
       }
       return t+1;
     }
 };

解题思路：这题可以用一个更简单的思路，你就看两个数字之间的差值，如果是大于0，那他就是上升的，小于0就是下降的，计算从上升变成下降和从下降变成上升的次数就好，这样就可以避免差值等于0的情况

整数替换

链接;397. 整数替换 - 力扣（LeetCode）

 class Solution {
 public:
     int integerReplacement(int n) {
        long t=0;
        if(n==2147483647)t--;
         while(n!=1){
             if(n%2==0){
                 n=n/2;
           
             }else{
                 if(n!=3&&(n>>1)&1==1&&n!=2147483647)n++;
                 else n--;
             }      t++;
         }
         return t;
     }
 };

解题思路：还是用到位运算，这里需要探究n++和n--的区别，我们从位运算的角度来看，n是奇数，那么二进制最后一位一定是1，最后三位是101，n++就是110，n--就是100，发现n--的情况可以连续除2次，但是n++除2此之外还要n++或n--一次，所以这种情况得要n--，但是要是111呢，n++，就是1000，n--是110，n++就可以直接连除，但是n--就不是的。所以说要尽量多变成偶数，如果是奇数的话还是要变成偶数，就会多一步。

删除链表的倒数第N个结点

链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

 class Solution {
 public:
     ListNode* removeNthFromEnd(ListNode* head, int n) {
         if (head == nullptr) {
             return head;
         }       
         ListNode* first = head;
         ListNode* second = head;
         int s = 1;
         while (first->next != nullptr) {
             first = first->next;
             s++;
             if (s > n+1) {
                 second = second->next;
             }
         }
         if(n==1&&s==1){
            
             return nullptr;
         }else if(n==s){
             second=second->next;
             return second;
         }
         ListNode* third=second->next;
         second->next=third->next;
         third->next=nullptr;
         return head;
     }
 };

解题思路：这一个题形问题，我们先用两个指针，一个先走n步，然后两个指针同时走，当第一个指针走到链表的末尾时，第二个指针指向的节点就是倒数第n个节点，然后我们删除即可。

验证回文串2

链接：680. 验证回文串 II - 力扣（LeetCode）

 class Solution {
 public:
 bool checkstring(string s,int m,int n){
     while(m<n){
         
             if(s[m]!=s[n]){
                 return false;
             }
             m++;
             n--;
         
     }
     return true;
 }
     bool validPalindrome(string s) {
     int s1=0,s2=s.size()-1;
     int a = 0;
     bool f = true;
     while (s1 <= s2) {
         if (s[s1] == s[s2]) {
             s1++;
             s2--;
         }
         else {
             return checkstring(s,s1,s2-1)||checkstring(s,s1+1,s2);
             }
             
         }return true;
     }
     
     
 };

解题思路：这一个题的核心在于，要删除一个字符，所以当我们第一次遇到两边不相等的时候，我们就要对字符进行删除。来看删除后的字符串是不是回文串。这个操作只需要进行一次。不需要后面再次对字符串进行删除操作了。对于字符串的删除操作，要么左指针移动，要么右指针移动。两种情况只要有一个返回true就行。所以要再写一个函数，用来判断字符串是否是回文串。

二叉树的前中后序遍历

在有了dfs的基础思想之后，其实前中后序有点像dfs，所以还是用递归来写，

 class Solution {
 public:
     void inorder(TreeNode* root, vector<int>& ans) {
         if (root == nullptr)
             return;
         inorder(root->left, ans);
         ans.push_back(root->val);
         inorder(root->right, ans);
     }
     vector<int> inorderTraversal(TreeNode* root) {
         vector<int> ans;
         inorder(root, ans);
         return ans;
     }
 };

其实看的很清楚了，中序就是先递归左边，然后输出自身，再递归右边。前序和后序也是这样，只是很简单的稍微改了一下顺序而已。

合并两个有序数组

链接：88. 合并两个有序数组 - 力扣（LeetCode）

 class Solution {
 public:
     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
         if(n==0){
             return ;
         }else if(m==0){
             for(int i=0;i<n;i++){
                 nums1[i]=nums2[i];
             }
             return;
         }
         int a=m-1,b=n-1;
         for(int i=nums1.size()-1;i>=0;i--){
              if(b>=0&&a<0){
                  nums1[i]=nums2[b];
                 b--;
             }
             if(a>=0){
             if(nums1[a]>=nums2[b]){
                 nums1[i]=nums1[a];
                 a--;
             }else {
                 nums1[i]=nums2[b];
                 b--;
             }
             }
             if(b<0){
                 break;
             }
            
 
         }
        
     }
 };

思路：这个题其实还是不简单的，一开始是想到用双指针，如果不要求非要拼接在nums1的话，我可以单开一个新的数组，一个指针在nums1，一个指针在nums2，然后比较谁小，然后把小的数字放入新开的数组，同时小的那个指针往后移动，就这样两根指针往后便利，直到最后两根指针遍历完。但是问题在于要求在nums1上面改动。。。如果还是按照原来的思想，问题是我在nums1上插入了新的数据，那么就会覆盖原来的数据，毕竟这不是链表。想了很久，因为原来的思想是从小到大，那么我换一个方向，我从大到小来弄，会不会好一点，因为nums1最后的那些都是0，所以在插入的时候是不用去考虑覆盖原来的数据的。就这样就避免了这个问题。同时在不断往前插入的过程中，一定会涉及到处理nums1原来的数据的，两种情况，第一是我要覆盖掉这个数字，但是我要覆盖掉这个数字，也就意味着这个数字已经被插入到nums1的后面了，所以是覆盖是没有问题的。第二种情况是我不需要去覆盖这个数字，但是出现这个情况也就意味着我的nums2的所有数字刚刚好直接接在nums1的数字后面就行。这是核心的思想，但是需要注意几个特殊的点，第一，nums1.size()0或者nums2.size()0，这是一种特殊的情况。第二，nums2在nums1的前面，这种情况在执行的时候，我的nums1的指针已经到头了，所以在下一个循环判断nums1[a]就会数组越界，所以必须在前面写上一个判定说a>=0。但是此时我的nums2还有数字没有加入到nums1里面，所以需要针对当nums1的指针到头并且nums2的指针没有到头的情况，这时候我还是需要把nums2的数字往nums1里面加。同时上述的情况必须要在判断a>=0的前面。因为如果在后面的话，那就很有可以a>=0的判定执行一遍，然后后面判断b>=0&&a<0的判定也执行一遍，这样就会执行两遍，答案就会不对。

移出元素

链接：27. 移除元素 - 力扣（LeetCode）

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

思路：其实这个题目最简单好使的是用nums.erase(i)来弄，auto i=nums.begin(),然后判断*i==val就行。但是我们主要是讲算法，我们换一个思想来弄。看到题目给的例子，可以看到都是把要需要移出的数字放在了数组的最后，所以我们就可以想到遍历数组，当数字是需要移出的，我们把它往后移。这个时候我可以在数组的末尾建立一个指针，如果这个指针指向的数字不是我要移出的，那完全可以跟我前面那个要移出的指针进行交换。如果后面的那个指针指向的是我要移出的，那么我就一直往前移动，直到找到第一个不等于val的数字，并进行交换就行。那么这个过程的截止要求就是：我们后面的指针已经碰到了前面的指针，那其实已经遍历完成了，就可以break了。注意特殊情况，这个数组都是val，那么我后面的指针就会不断的往前移动，直到超出数组边界。这个时候就是应该要返回0。要计算数组内有多少个不等于val的数字，你可以再次遍历一边。同时你要是一次遍历，你就在遍历的时候去判断，如果不等于就自加，除此之外，你每一次前后交换的时候，都是把后面的一个不等于的弄到前面来了，但是这会前面就不会去自加，这时我就新写一个自加。

删除数组中有序的重复项

链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）]

、

思路：这个题思路比较简单，首先第一个数字肯定不用管，我们从第二个开始看，因为题目最后的答案一定都是每一位都是不同的数字，我们设计一个指针指向第一个数字，随着这个指针的不断的偏移，意味着前面的数组都是只有互不相同的。我们不断的循环这个数组，当循环到的数字跟指针所指向的数字不同，那也就意味着这个数字是不在我的答案里面的，我需要将这个数字加入到我的答案，所以我将前面的指针赋值成这个数字，然后指针往后偏移，这样就实现了我答案数组的增加。

轮转数组

链接：189. 轮转数组 - 力扣（LeetCode）

 class Solution {
 public:
     void rotate(vector<int>& nums, int k) {
         if(nums.size()==1){
             return ;
         }
         vector<int>arr;
         k=k%nums.size();
         for(int i=nums.size()-k;i<nums.size();i++){
             arr.push_back(nums[i]);
         }
         for(int i=nums.size()-1-k;i>=0;i--){
             nums[i+k]=nums[i];
         }
         for(int i=0;i<k;i++){
             nums[i]=arr[i];
         }
         return ;
     }
 };

思路：这题的想法是用一个数组记录要从数组尾转移到数组头的数字，之后把前面的往后移动，最后把记录的数组的数字填到原来数组的前面，过还是过了，但是在题解上看到一种牛逼的，数组翻转，先全部翻转，然后k个之前为一组，翻转一次，k个之后为一组，在翻转一次，这样不就需要额外的数组去记录，牛逼。

买卖股票的最佳时机

链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）

 class Solution {
 public:
     int maxProfit(vector<int>& prices) {
         int n=prices[0];
         int s=0;
         for(int i=1;i<prices.size();i++){
             if(prices[i]<=n){
                 n=prices[i];
             }
             else{
                 if(prices[i]-n>s){
                     s=prices[i]-n;
                 }
             }
         }return s;
     }
 };

思路：一开始想着说n2遍历，结果超时了，然后就一直想不出来了，看了一眼评论区，“前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}”看得我是醍醐灌顶，然后照着弄就过了。但是我想说的点是，其实之前我认为的动态规划，并不是真这个意义上的动态规划，我只是看着我写的代码很像就误以为了，只能是是形似而不是神似。总结一下，我觉得动态规划的核心在于你将之前的情况的答案和加上这一次的情况的答案进行比较，所得出的答案，然后在下一次还是同样的，这可能就是状态转移方程的核心意义所在。

买卖股票的最佳时机2

链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

 class Solution {
 public:
     int maxProfit(vector<int>& prices) {
         vector<vector<int>>dp(prices.size(),vector<int>(2,0));
         dp[0][1]=prices[0]*-1;
         if(prices.size()==1){
             return 0;
         }
         for(int i=1;i<prices.size();i++){
             dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
             dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
         }
         return dp[prices.size()-1][0];
     }
 };

思路：用到的经典的递归的思想，定义dp二位数字，其中i表示天数，j取0,1。0表示手上没有股票，1表示手上有股票。然后 dpi=max(dpi-1,dpi-1+prices[i]); dpi=max(dpi-1,dpi-1-prices[i]);今天手上有股票，可能是昨天手上有股票或者昨天没有股票今天买的股票。同理可得今天没有股票的情况。

跳跃游戏

链接：55. 跳跃游戏 - 力扣（LeetCode）

 class Solution {
 public:
     bool canJump(vector<int>& nums) {
         int s=0;
         for(int i=0;i<nums.size();i++){
             if(i<s){
                 if(nums[i]+i>s){
                     s=nums[i]+i;
                 }
             }else if(s==i){
                 s=nums[i]+i;
             }
             else{
                 return false;
             }
         }
         return true;
     }
 };

思路：定义一个变量记录可以调到的最大的位置，然后当遍历的位置小于这个最大位置时，如果可以跳到更大的位置，你就可以更新这个变量。但是当你遍历到最大的位置时，你就必须更新当前的变量，不能进行比较。如果超过了最大的位置，就是false；

跳跃游戏2

链接：https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview

 class Solution {
 public:
     int jump(vector<int>& nums) {
         vector<int>dp(nums.size(), 9999);
     dp[0] = 0;
     if(nums.size()==1)return 0;
     bool f=true;
     for (int i = 0; i < nums.size(); i++) {
         for (int j = 1; j <=nums[i]; j++) {
            if (i + j >= nums.size()-1) {
               return dp[i]+1;
            
          
             }
           
             if (dp[i + j] > dp[i] + 1) {
                 dp[i + j] = dp[i] + 1;
             }
             }
         
         
     }return dp[nums.size()-1];
 }
 };

思路：o（n）的方法没有看懂，就说我自己想的吧，往后遍历，假如调到这个位置是需要3步，那么从这个位置往后能跳到的位置都还4步，同时还需要判断一下这个四步是不是调到这个位置的最少次数，如果是就赋值上去，然后就是这样一直到最后。

H指数

链接：274. H 指数 - 力扣（LeetCode）

 class Solution {
 public:
     int hIndex(vector<int>& citations) {
         sort(citations.begin(),citations.end());
         reverse(citations.begin(),citations.end());
         int s=0;
         for(int i=0;i<citations.size();i++){
             if(citations[i]>=i+1){
                 s=i+1;
             }
         }
         return s;
     }
 };

思路：一开始是想二分，但是后来发现其实并不需要，首先需要排序，之后就是翻转，让数组从大到小排列。其实就是找从1-数组size里面找一个数字x，数组里面有x个数字比这个x大。相当于把这个数组遍历一遍，如果nums[0]>1;相当于数组里面至少有一个数字比1大，nums[1]>2，相当于数组里面至少有两个数字比2大，以此类推，直到找到最大的数字。

加油站

链接：134. 加油站 - 力扣（LeetCode）

 class Solution {
 public:
     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
         int a=0,b=0,ans=0;
         for(int i=0;i<cost.size();i++){
             a+=gas[i]-cost[i];
             b+=gas[i]-cost[i];
             if(b<0){
                 b=0;
                 ans=1+i;
             }
         }
         return a<0?-1:ans;
     }
 };

思路：其实这个题目之前写过，但是现在写还是不会。。。之前还写了题解的。重新来写一遍吧。首先我们可以知道，所有的gas相加减去cost，最后的值是小于0，那么就肯定跑不完，返回-1，所以a的作用就是这个。再看b，首先的两层遍历就是，从gas[i]-cost[i]>0的来看，这个可能是起点，然后往后遍历，如果我的油量一直都是大于0，那么就是我要的。相当于双层遍历。但是需要优化。核心在于因为我的b是从0开始的，如果b是小于0，那没事了，如果b大于0，那我们就可以记录一下，往后b小于0了，那就说明从记录的点到现在这一个大范围内，都是油量小于0的，那这一个大范围就不用再次去遍历了。直接往后看就行了。

罗马数字转整数

链接：13. 罗马数字转整数 - 力扣（LeetCode）

 class Solution {
 public:
     int romanToInt(string s) {
         int  ans=0;
         int i=0;
         unordered_map<char,int>mymap{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
         while(i<s.size()){
           switch(s[i]){
             case 'I':if(s[i+1]=='V'){
                 ans+=4;
                 i+=2;
             }else if(s[i+1]=='X'){
                 ans+=9;
                 i+=2;
             }else{
                 ans+=1;
                 i++;
             }break;
 
             case 'X':if(s[i+1]=='L'){
                 ans+=40;
                 i+=2;
             }else if(s[i+1]=='C'){
                 ans+=90;
                 i+=2;
             }else{
                 ans+=10;
                 i++;
             }break;
 
             case 'C':if(s[i+1]=='D'){
                 ans+=400;
                 i+=2;
             }else if(s[i+1]=='M'){
                 ans+=900;
                 i+=2;
             }else{
                 ans+=100;
                 i++;
             }break;
 
             case 'V':
             ans+=5;
             i++;
             break;
 
             case 'L':
             ans+=50;
             i++;
             break;
 
             case 'D':
             ans+=500;
             i++;
             break;
 
             case 'M':
             ans+=1000;
             i++;
             break;
           }
         }return ans;
 
     }
 };

思路：这一题的思路很简单，就是模拟。罗马数字每一个数字都表示一个数字，转化之后相加就行。唯独需要注意的一点就是：I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。面对这三个时候，需要关注一下它们后面一位的数字是否满足上述的要求，如果满足就按要求来，否则就按照原来的思路来就行。

整数转罗马数字

题目链接：12. 整数转罗马数字 - 力扣（LeetCode）

 class Solution {
 public:
     string intToRoman(int num) {
         string ans="";
         vector<string>arr;
         int s=0;
         int i=1;
         while(num!=0){
             s=num%int(pow(10,i));
             i++;
             num-=s;
             if(s==4){
                 arr.push_back("IV");
             }else if(s==9){
                 arr.push_back("IX");
             }else if(s==40){
                 arr.push_back("XL");
             }else if(s==90){
                 arr.push_back("XC");
             }else if(s==400){
                 arr.push_back("CD");
             }else if(s==900){
                 arr.push_back("CM");
             }else {
                 string s1="";
                 char a='I';
                 if(s>=5&&s<10){
                     s1+="V";
                     s-=5;
                 }else if(s>=10&&s<50){
                     a='X';
                    
                     s=s/10;
                 }else if(s>=50&&s<100){
                     a='X';
                     s1+='L';
                     s-=50;
                     s=s/10;
                 }else if(s>=100&&s<500){
                     a='C';
                     s=s/100;
                 }else if(s>=500&&s<1000){
                     a='C';
                     s1+='D';
                     s-=500;
                     s=s/100;
                 }else if(s>=1000){
                     a='M';
                     s=s/1000;
                 }
                 for(int i=0;i<s;i++){
                     s1+=a;
                 }
                 arr.push_back(s1);             
             }
 
         }
         for(int i=arr.size()-1;i>=0;i--){
             ans+=arr[i];
         }
         return ans;
     }
 };

思路：我的思路是首先把数字进行分割，假设有一个数字1234，我分割为1000,200，30,4这四个数字。其次看每一位数字的第一位，如果是4或9，就要特殊处理。之后看剩下的数字，确定基数，就是确定在字符串右边多次添加的字符，假如是3，那就是I，假如是30，那就是X，确定基数之后，只需要判断s的首位是几，那么就是相当于要加几个。其次，如果是大于5，那么就需要在前面加上5所代表的数字，例如V，L之类的。

jarycaling's blog

算法的学习

我的算法笔记

查找

A-B数对

砍树

木材加工

烦恼的高考志愿

一元三次方程求解

丢失的数字

搜索旋转排序数组

删除数组中重复的数字

三数之和

最接近的三数之和

四数之和

第一个缺失的正整数

最长回文子串

回形链表

多数元素

字母异位词分组

最长连续序列

重复的dna序列

比特位计数

不同路径2

跳跃游戏2

交错字符串

最长有效括号

excel表列名称

pow(x,n)

排列序列

存在重复元素3

加油站

去除重复字母

递增的三元子序列

摆动序列

整数替换

删除链表的倒数第N个结点

验证回文串2

二叉树的前中后序遍历

合并两个有序数组

移出元素

删除数组中有序的重复项

轮转数组

买卖股票的最佳时机

买卖股票的最佳时机2

跳跃游戏

跳跃游戏2

H指数

加油站

罗马数字转整数

整数转罗马数字