leetcode 600-700

太过爱你忘了你带给我的痛 2022-11-25 10:11 233阅读 0赞

### 文章目录 ###

*  重做题
 *  605. 种花问题
 *  645. 错误的集合
 *  646. 最长数对链（dp\\贪心）
 *  647. 回文子串
 *   *  回文字符串
 *  698. 划分为k个相等的子集(dfs)
 *  704. 二分查找
 *  712. 两个字符串的最小ASCII删除和
 *  713. 乘积小于K的子数组（dp）
 *  718. 最长重复子数组(dp\*\*\*\*\*\*\*\*\*\*\*)
 *   *  最长公共子串
 *  738. 单调递增的数字
 *  739. 每日温度（单调栈）
 *  743. 网络延迟时间
 *  746. 使用最小花费爬楼梯
 *  
 *  766. 托普利茨矩阵
 *  
 *  852. 山脉数组的峰顶索引
 *  860. 柠檬水找零
 *  870. 优势洗牌
 *  875. 爱吃香蕉的珂珂
 *  881. 救生艇
 *  901. 股票价格跨度
 *  
 *   *  建立自定义节点node放入map或者set
     *  八方向时合并写
 *  1094. 拼车
 *  1143. 最长公共子序列(dp\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*)

# 重做题 #

# 605. 种花问题 #

边界条件态麻烦这样做  
**在原序列左右两侧都先添个0**

class Solution {
        
    public:
        bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        
            int res = 0;
            if(flowerbed.empty())return false;
            if((int)flowerbed.size()==1)return !flowerbed[0] || !n;
            for(int i = 0; i< (int)flowerbed.size() ;i++)
            {
        
                if(i==0){
        if(flowerbed[i]==0 && flowerbed[i+1]==0){
        flowerbed[i]=1;res++;}}
                else if (i==(int)flowerbed.size()-1){
        if(flowerbed[i]==0 && flowerbed[i-1]==0){
        flowerbed[i]=1;res++;}}
                else {
        if(flowerbed[i]==0 && flowerbed[i-1]==0 && flowerbed[i+1]==0) {
        flowerbed[i]=1;res++;}}
            }
            return res>=n;
        }
    };

# 645. 错误的集合 #

一遍遍历的方法，但是还是超时了

class Solution {
        
    public:
        vector<int> findErrorNums(vector<int>& nums) {
                
            sort(nums.begin(),nums.end());
            vector<int> ref; int res1 = -1, res2 = -1;
            for(auto i:nums)
            {
        
                if(find(ref.begin(),ref.end(),i)!=ref.end())res1 = i;
                if(!ref.empty() && ref.back()<i-1)res2 = i-1;
                ref.push_back(i);
            }
            if(res2==-1)
            {
        
                if(nums[0]!=1)res2 = 1;
                else res2 = nums.size();
            }
            return {
        res1,res2};
            
        }
    };

使用哈希表的方法，注意一般不对哈希表进行遍历，因为迭代器不支持加减操作十分难用，只用其查找操作

class Solution {
        
    public:
        vector<int> findErrorNums(vector<int>& nums) {
        
            sort(nums.begin(),nums.end());
            unordered_map<int,int> mp;
            int res1 = -1,res2 = -1;
            for(auto i:nums)
            {
        
                mp[i]++;if(mp[i]==2)res1 = i;
            }
            for(int i=1;i<=nums.size();i++)
            {
        
                if(mp[i]==0){
        res2= i;break;}
            }
            return {
        res1,res2};
    
        }
    };

两次遍历，就是使用find，超时了，可以看到vec中的find复杂度还是很高的

class Solution {
        
    public:
        vector<int> findErrorNums(vector<int>& nums) {
        
            int res1 = 0,res2 = 0;
            for(int i =0;i<nums.size();i++)
            {
        
                if( find(nums.begin(),nums.begin()+i,nums[i])!=nums.begin()+i)
                {
        res1 = nums[i];break;}
            }
            for(int i =1;i<=nums.size();i++)
            {
        
                if(find(nums.begin(),nums.end(),i)==nums.end())
                {
        res2 = i;break;}
            }
            return {
        res1,res2};
    
        }
    };

# 646. 最长数对链（dp\\贪心） #

class Solution {
        
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
        
            //把重合的去掉
            if(pairs.empty())return 0;
            sort(pairs.begin(), pairs.end());
            int dp = pairs[0][1], res = 0;
            for(int i = 1 ; i< (int)pairs.size() ;i++)
            {
        
                if( pairs[i][0]<= dp)
                {
        
                    res++;
                    dp = min(dp, pairs[i][1]);
                }
                else
                {
        
                    dp = pairs[i][1];
                }
            }
            return (int)pairs.size()-res;
        }
    };

和套娃问题非常类似，唯一不一样的是需要下一个的第一个大于前一个的最后一个  
注意需要排序  
注意需要条件筛选  
注意dp表达式

class Solution {
        
    public:
        static bool myfunc(const vector<int> num1, const vector<int> num2)
        {
        
            if( num1[0]<num2[0] || (num1[0]==num2[0] && num1[1]>num2[1] ))
            {
        return true;}
            else
            {
        return false;}
        }
        int findLongestChain(vector<vector<int>>& pairs) {
        
            int len = pairs.size();
            sort(pairs.begin(),pairs.end(),myfunc);
            int res = 0;
            vector<int> dp(len,1);
            for(int i =0  ; i<len ;i++)
            {
        
                for(int j = 0 ;j<i ;j++)
                {
        
                    if(pairs[i][0]>pairs[j][1]){
        dp[i] = max(dp[i],dp[j]+1);}
                }
                res = max(res,dp[i]);
            }
            return res;
    
        }
    };

# 647. 回文子串 #

## 回文字符串 ##

**dp\[i\]\[j\]表示\[i, j\]范围内字符是否为回文串，i从后向前遍历，j从i位置向后遍历，如果s\[i\] == s\[j\]，那么i和j满足下面两个条件之一，则dp\[i\]\[j\] = true。  
如果i和j相邻或只隔着一个字符，则dp\[i\]\[j\] = true  
否则如果dp\[i + 1\]\[j - 1\] = true，则dp\[i\]\[j\] = true**  
回文字符串判断：使用二维的布尔矩阵  
若单个字符（即对角线处）一定为回文  
若相邻的相等（即对角线往右上一斜排）一定为回文  
若隔一个的相等，一定为回文  
上面满足的两个条件，相等且距离小于等于2  
当相等且里面的为回文，那么这两个也是回文，  
满足的两个条件：相等且里面两个为回文

class Solution {
        
    public:
        int countSubstrings(string s) {
        
            if (s.empty()) return 0;
            int size = s.size(), res = 0;
            vector<vector<bool>> dp(size, vector<bool>(size));
            for (int i = size - 1; i >= 0; --i) {
        
                for (int j = i; j < size; ++j) {
        
                    dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
                    if (dp[i][j]) ++res;            
                }            
            }
            return res;
        }
    };
    
    作者：guohaoding
    链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/647-hui-wen-zi-chuan-liang-chong-fang-fa-zhong-xin/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 698. 划分为k个相等的子集(dfs) #

class Solution {
        
    public:
        bool flag = false;
        void dfs(vector<int>& nums,int sum ,int target,vector<int>& record,int num,int k)
        {
        
            if(flag)return;
            if(sum==target){
        num++;sum=0;}
            if(num==k){
        flag=true;return;}
            for(int i = 0;i<nums.size();i++)
            {
        
                if(record[i]==0)
                {
        
                    record[i]=1;
                    sum += nums[i];
                    dfs(nums,sum,target,record,num,k);
                    sum -= nums[i];
                    record[i]=0;
                }
            }        
        }
        inline static bool cmp(int a,int b)
        {
        return b>a;}
        bool canPartitionKSubsets(vector<int>& nums, int k) {
        
            int sum = 0;
            for(auto n:nums)sum+=n;
            if(sum%k!=0)return false;
            sort(nums.begin(),nums.end(),cmp);
            int target = sum/k;
            if(nums.front()>target)return false;
            vector<int> record(nums.size(),0);
            dfs(nums,0,target,record,0,k);
            return flag;
        }
    };

# 704. 二分查找 #

最关键的还是边界问题，因为这道题里只要相等的值，这样的话边界一旦不满足可以直接进行范围缩小，然后在整个循环的时候，要有等号

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

# 712. 两个字符串的最小ASCII删除和 #

求ascii直接将字符相加就行，本质上就是求公共最大子序列，但是要将dp关系式改一下，里面不再存个数，而是直接求这个字符串的ascii码之和

class Solution {
        
    public:
        int minimumDeleteSum(string s1, string s2) {
        
            //其实就是在求最大公共子序列
            int len1 = s1.size();
            int len2 = s2.size();
            vector<vector<int>> dp(len1+1,vector<int> (len2+1,0));
            for(int i = 1 ; i<len1+1; i++)
            {
        
                for(int j =1 ; j< len2+1 ;j++)
                {
        
                    if(s1[i-1]==s2[j-1]) dp[i][j] = dp[i-1][j-1] + int(s1[i-1]);
                    else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
            //dp[i][j]为最大的长度，但是现在需要知道是哪些字符串
            int sum1 = 0;
            for(int i = 0 ; i< len1;i++)
            {
        
                sum1 += int(s1[i]);
            }
            int sum2 = 0;
            for(int i = 0 ; i< len2 ; i++)
            {
        
                sum2 += int(s2[i]);
            }
            return sum1 +sum2 - 2*dp[len1][len2];
        }
    };

# 713. 乘积小于K的子数组（dp） #

是求公共子串中判断回文子串类似的问题，为了防止溢出要注意剪枝

class Solution {
        
    public:
        bool is(vector<int> temp,int k)
        {
        
            int sum = temp[0];
            int len = temp.size();
            for(int i = 1 ; i<len ;i++ )
            {
        
                sum = sum *temp[i];
            }
            if(sum<k) return true;
            else return false;
        }
    
        int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        
            //采用的是二维数组法，遍历半个，每次进行判断
            int res=0;
            int len = nums.size();
            vector<vector<int>> dp(len, vector<int>(len,0));
            for(int i = 0; i<len ;i++)
            {
        
                for(int j = i ; j<len ;j++)
                {
        
                    vector<int> temp(nums.begin()+i,nums.begin()+j+1);
                    if(is(temp,k)) res++;
                    else break;
                }
            }
            return res;
        }
    };

# 718. 最长重复子数组(dp\*\*\*\*\*\*\*\*\*\*\*) #

## 最长公共子串 ##

要特别注意题目里是否必须是连续的，如果可以不用连续（**最长公共子序列**）就用注释里的方法做，如果可以连续（**最长公共子串**）就用另一种dp方法做

class Solution {
        
    public:
        int findLength(vector<int>& A, vector<int>& B) {
        
            int lena = A.size();
            int lenb = B.size();
            vector<vector<int>> v(lena +1 , vector<int>(lenb+1,0));
            /*
            for(int i = 1 ; i< lena+1 ; i++)
            {
                for(int j = 1; j<lenb+1 ; j++)
                {
                    if(A[i-1]==B[j-1])v[i][j] = v[i-1][j-1] +1 ;
                    else v[i][j] = max(v[i-1][j],v[i][j-1]);
                }
            }
            return v[lena][lenb];
            */
            int max = 0;
            for(int i = 1 ; i< lena+1 ; i++)
            {
        
                for(int j = 1; j<lenb+1 ; j++)
                {
               
                    if(A[i-1] == B[j-1]) v[i][j] = v[i-1][j-1]+1;
                    else v[i][j]=0;
                    if(v[i][j]>max)max = v[i][j]; 
                }
            }
            return max;
        }
    };

# 738. 单调递增的数字 #

class Solution {
        
    public:
        int monotoneIncreasingDigits(int N) {
        
            for(int i =N; i>=0 ;i--)
            {
        
                string s = to_string(i);
                int len = s.size();
                bool b = true;
                for(int i = 1; i<len ;i++)
                {
        
                    if(s[i]<s[i-1]){
        b = false;break;}
                }
                if(b)return i;
            }
            return 0;
        }
    };

# 739. 每日温度（单调栈） #

class Solution {
        
    public:
        vector<int> dailyTemperatures(vector<int>& T) {
        
            //第一种是暴力解法容易想到
            //第二种单调栈
            vector<int> st;
            vector<int> res(T.size(),0);
            for(int i = 0; i< T.size();i++)
            {
        
                while(!st.empty() && T[i]>T[st.back()])
                {
        
                    res[st.back()]=i-st.back();
                    st.pop_back();
                }
                st.push_back(i);
            }
            return res;
        }
    };

# 743. 网络延迟时间 #

class Solution {
        
    public:
        int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        
            vector<vector<int> > adj(N + 1, vector<int>(N + 1, INT_MAX));/邻接矩阵
            vector<int> dist(N + 1, INT_MAX);
            vector<bool> visited(N + 1, false);//是否访问过
            dist[K] = 0;
            visited[K] = true;//初始点访问
            for (auto& e : times) {
        
                adj[e[0]][e[1]] = e[2];//放入邻接矩阵中
                if (e[0] == K) {
        
                    dist[e[1]] = e[2];
                }
            }
            for (int i = 1; i < N; ++i) {
        
                int min_dist = INT_MAX;
                int min_ind = -1;
                for (int j = 1; j <= N; ++j) {
        
                	找到未访问过的里面的最小值，
                    if (!visited[j] && dist[j] < min_dist) {
        
                        min_dist = dist[j];//找到最小值
                        min_ind = j;
                    }
                }
                if (min_dist == INT_MAX)
                    return -1;
                visited[min_ind] = true;
                for (int j = 1; j <= N; ++j) {
        
                    if (!visited[j] && adj[min_ind][j] != INT_MAX && 
                            min_dist + adj[min_ind][j] < dist[j])
                        dist[j] = min_dist + adj[min_ind][j];
                }
            }
            int max_dist = -1;
            for (int i = 1; i <= N; ++i)
                if (max_dist < dist[i])
                    max_dist = dist[i];
            return (max_dist == INT_MAX) ? -1 : max_dist;
        }
    };
    
    作者：da-li-wang
    链接：https://leetcode-cn.com/problems/network-delay-time/solution/c-dijkstra-by-da-li-wang/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 746. 使用最小花费爬楼梯 #

动态规划：找到关系式，然后进行遍历构造dp数组

class Solution {
        
    public:
    
    
        int minCostClimbingStairs(vector<int>& cost) {
        
            //理论上可以用递归每次都选择走一步或者走两步，但是树会很庞大
            //所谓dp，通常要求出一个表达式，这个表达式一般是用之前的量的函数构成，最后同循环遍历或者递归实现
            int len = cost.size();
            vector<int> dp = cost;
            cost.push_back(0);
            dp.push_back(0);
            for(int i = 2 ; i< len+1 ; i++)
            {
        
                dp[i] = cost[i] + min(dp[i-1],dp[i-2]);
    
            }
            return dp[len];
    
    
        }
    };

#  #

class Solution {
        
    public:
        vector<int> partitionLabels(string S) {
        
            int xu1=0;
            int xu0=0;
            vector<int> res;
            for(int i=0;i<S.size();i++){
        
                int tmp=S.find_last_of(S[i]);
                if(tmp>xu1) xu1=tmp;
                if(i==xu1) {
        
                    res.push_back(xu1-xu0);
                    xu0=xu1;
                }
            }
            res[0]++;
            return res;
        }
    };
    
    作者：kalase
    链接：https://leetcode-cn.com/problems/partition-labels/solution/shan-yong-findsui-ran-you-dian-man-by-kalase/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 766. 托普利茨矩阵 #

class Solution {
        
    public:
        bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        
            int l1 = matrix.size();
            int l2 = matrix[0].size();
            for(int i=1 ;i<l1 ;i++)
            {
        
                for(int j =1 ;j<l2 ;j++)
                {
        
                    if(matrix[i][j]!=matrix[i-1][j-1])return false;
                }
            }
            return true;
        }
    };

#  #

一开始是这样做的，但是发现始终不对，因为每次对pair的second修改不成功，于是去vs试了一下

class Solution {
        
    public:
        static inline bool func(const pair<char,int>& p, const pair<char,int>& q)
        {
        
            return p.second>q.second;
        }
    
        string reorganizeString(string S) {
        
            unordered_map<char,int> mp;
            for(auto i:S)mp[i]++;
            vector<pair<char,int>> vt;
            vt.assign(mp.begin(),mp.end());
            sort(vt.begin(),vt.end());
            string res;
            while((int)res.size()<(int)S.size())
            {
        
                for(auto v:vt)
                {
        
                    if(v.second>=1)
                    {
        
                        res = res + v.first;
                        v.second -= 1;
                    }
                }
            }
            int len = res.size();
            //return (res[len-1]!=res[len-2])?res:"";
            return res;
        }
    };

下面两种对pair值修改的结果竟然是不同的，说明对pair的修改必须建立在整体索引之上，像auto v:vt这样取出再修改是不行的

vector<pair<int, int>> v = {
        pair<int,int>(1,2)};
    	pair<int,int> vt = v[0];
    	//vt.second--;
    	v[0].second--;
    	cout << v[0].second << endl;

# 852. 山脉数组的峰顶索引 #

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

# 860. 柠檬水找零 #

class Solution {
        
    public:
        bool lemonadeChange(vector<int>& bills) {
        
            unordered_map<int,int> mp;
            for(auto bill:bills)
            {
        
                if(bill==5)mp[5]++;
                else if(bill==10)
                {
        
                    if(mp[5]>=1){
        mp[5]--;mp[10]++;}
                    else return false;
                }
                else
                {
        
                    if(mp[10]>=1 && mp[5]>=1){
        mp[10]--;mp[5]--;}
                    else if(mp[5]>=3){
        mp[5] -=3;}
                    else return false;
                }
            }
            return true;
        }
    };

# 870. 优势洗牌 #

对vector很灵活的用法

class Solution {
        
    public:
        vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        
            sort(A.begin(), A.end());
            vector<int> ans;
            for (int i = 0; i < B.size(); i++) {
        
                auto iter = upper_bound(A.begin(), A.end(), B[i]);
                if (iter != A.end()) {
        
                    ans.push_back(*iter);
                    A.erase(iter);
                } else {
        
                    ans.push_back(A[0]);
                    A.erase(A.begin());
                }
            }
            return ans;
        }
    };
    
    作者：nimodawoha
    链接：https://leetcode-cn.com/problems/advantage-shuffle/solution/er-fen-cha-zhao-pai-xu-by-nimodawoha/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 875. 爱吃香蕉的珂珂 #

思路应该是找到最大的一组，然后一个一个试，但是为了更快速的，采用二分法来试，在二分法的边界问题上十分讲究，稍有不慎就会出错

class Solution {
        
    public:
        bool eat(int speed, vector<int>& piles, int H)
        {
        
            int sum = 0;
            for(auto pile:piles)
            {
        
                sum +=(pile+speed-1)/speed;
            }
            return sum>H;
        }
        int minEatingSpeed(vector<int>& piles, int H) {
        
            int len = piles.size();
            int m=0;
            for(auto pile:piles)
            {
        
                m =max(m,pile);
            }
            int left =1;
            int right = m;
            while(left<right)
            {
        
                int mid=(left+right)/2;
    
                if(eat(mid,piles,H))
                {
        
                    left =mid +1;
                }
                else
                {
        
                    right =mid;
                }
            }
            return left;
            
    
        }
    };

# 881. 救生艇 #

思路还有点难想，但是首位双指针法很有道理

class Solution {
        
    public:
        int numRescueBoats(vector<int>& people, int limit) {
        
            int res = 0;
            sort(people.begin(),people.end());
            int i = 0, j=(int)people.size()-1;
            while(i<j)
            {
        
                if(people[i]+people[j]<=limit)
                {
        
                    res++;i++;j--;
                }
                else
                {
        
                    res++;j--;
                }
            }
            if(i==j)res++;
            return res;
        }
    };

# 901. 股票价格跨度 #

在折叠的时候会丢失信息，专门用一个数组储存这个丢失的个数信息

class StockSpanner {
        
    public:
        StockSpanner() {
        }
        
        int next(int price) {
        
            int ans=1;
            while(!pri.empty()&&pri.top()<=price){
        
                ans+=cache.top();
                cache.pop();
                pri.pop();
            }
            pri.push(price);
            cache.push(ans);
            return ans;
        }
    private:
        stack<int> cache;
        stack<int> pri;
    };
    
    /**
     * Your StockSpanner object will be instantiated and called as such:
     * StockSpanner* obj = new StockSpanner();
     * int param_1 = obj->next(price);
     */
    
    作者：dai-52
    链接：https://leetcode-cn.com/problems/online-stock-span/solution/gu-piao-jia-ge-kua-du-czhu-shi-fu-can-kao-ti-jie-b/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#  #

肯定是使用bfs，但是遇到一个问题，就是set和map一样，不能保存vector和pair类型，所以怎么储存是一个问题  
1.错误的做法

class Solution {
        
    public:
        int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        
            //最短路径bfs
            int num = 0;
            int len1 = grid.size();
            int len2 = grid[0].size();
            queue<vector<int>> qt;
            unordered_set<int> st;
            qt.push({
        0,0});st.insert(make_pair(0,0));
            while(!qt.empty())
            {
        
                int len = qt.size();
                for(int i = 0;i<len;i++)
                {
        
                    auto temp = qt.front();qt.pop();
                    if(st.find(temp)==st.end())
                    {
        
                        int x = temp[0],y = temp[1];
                        if(x==len1-1 && y=len2-1)return num;
                        if(x-1>=0&&grid[x-1][y]==0)qt.push({
        x-1,y});
                        if(y-1>=0&&grid[x][y-1]==0)qt.push({
        x,y-1});
                        if(x+1<len1&&grid[x+1][y]==0)qt.push({
        x+1,y});
                        if(y+1<len2&&grid[x][y+1]==0)qt.push({
        x,y+1});
                        st.insert({
        x,y});
                    }
    
                }
                num++;
            }
            return -1;
        }
    };

2.利用矩阵进行储存，访问过的就置为2之后不再访问

class Solution {
        
    public:
        vector<vector<int>>dir={
        {
        0,1},{
        0,-1},{
        1,0},{
        -1,0},{
        1,1},{
        1,-1},{
        -1,1},{
        -1,-1}};
        int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        
            if(grid[0][0]==1)return -1;
            int n=grid.size();
            queue<pair<int,int>>q;
            q.push(make_pair(0,0));
            int length=1;
            grid[0][0]=2;   //将访问过的点标记为2
            while(!q.empty()){
        
                int l=q.size();      //遍历当前队列所有的元素
                for(int i=0;i<l;i++){
        
                    int x=q.front().first;
                    int y=q.front().second;
                    q.pop();
                    if(x==n-1&&y==n-1)return length;
                    for(int j=0;j<8;j++){
            
                        int x1=x+dir[j][0];
                        int y1=y+dir[j][1];
                        if(x1<0||y1<0||x1>=n||y1>=n||grid[x1][y1])continue;  //越界或者不满足访问条件跳过
                        grid[x1][y1]=2;
                        q.push(make_pair(x1,y1));
                    }
                }
                length++;
            }
            return -1;
    
        }
    };
    
    作者：mei-you-ni-de-liu-yue-tian
    链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix/solution/cbiao-zhun-de-bfs-by-mei-you-ni-de-liu-yue-tian/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

## 建立自定义节点node放入map或者set ##

## 八方向时合并写 ##

3.利用新的节点，这种方法是最泛化实用性最强的要多学习

struct Node{
        
        int x;
        int y;
    };
    int dpx[8] = {
        0,0,-1,-1,-1,1,1,1};
    int dpy[8] = {
        -1,1,-1,0,1,-1,0,1};
    class Solution {
        
    public:
        int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        
            if(grid[0][0] == 1){
        
                return -1;
            }
            int N = grid.size();
            queue<Node> q;
            vector<vector<int>> visit = grid;
            Node node = {
        0,0};
            q.push(node);
            int minPath = 0;
            while(!q.empty()){
        
                int len = q.size();
                minPath++;
                for(int i = 0;i < len;i++){
        
                    Node temp = q.front();
                    q.pop();
                    if(visit[temp.x][temp.y]){
        
                        continue;
                    }
                    if(temp.x == N - 1 && temp.y == N-1){
        
                        return minPath;
                    }
                    visit[temp.x][temp.y] = 1;
                    for(int i = 0;i<8;i++){
        
                        int tempx = temp.x + dpx[i];
                        int tempy = temp.y + dpy[i];
                        if(tempx < 0 || tempx >= N || tempy < 0 || tempy >= N){
        
                            continue;
                        }
                        Node nodeTemp = {
        tempx,tempy};
                        q.push(nodeTemp);
                    }
                }
            }
    
            return -1;
            
        }
    };
    
    作者：jasonnk
    链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix/solution/er-jin-zhi-ju-zhen-zhong-de-zui-duan-lu-jing-by-ja/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 1094. 拼车 #

事先建好容器，很好的方法

class Solution {
        
    public:
        bool carPooling(vector<vector<int>>& trips, int capacity) {
        
            vector<int> vt(1000,0);
            for(auto trip:trips)
            {
        
                for(int i = trip[1] ;i< trip[2]; i++)
                {
        
                    vt[i] += trip[0];
                }
            }
            for(auto i:vt)
            {
        
                if(i>capacity)return false;
            }
            return true;
        }
    };

# 1143. 最长公共子序列(dp\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*) #

用dp\[i\]\[j\]表示text1的i号位与text2的j号位之前的LCS长度  
根据text1\[i\]与text2\[j\]是否相同分为以下两种情况：  
1.若text1\[i\] == text2\[j\]，则dp\[i\]\[j\] = dp\[i-1\]\[j-1\] + 1;  
2.若text1\[i\] != text2\[j\]，则dp\[i\]\[j\] = max(dp\[i-1\]\[j\], dp\[i\]\[j-1\])。

作者：zed-65536  
链接：https://leetcode-cn.com/problems/longest-common-subsequence/solution/zui-chang-gong-gong-zi-xu-lie-by-zed-65536/  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
        
    public:
        int longestCommonSubsequence(string text1, string text2) {
        
            int len1 = text1.size();
            int len2 = text2.size();
            vector<vector<int>> v(len1+1, vector<int>(len2+1,0));
            for(int i = 1 ; i <len1+1 ;i++)
            {
        
                for(int j = 1 ; j< len2+1 ; j++)
                {
        
                    if(text1[i-1]==text2[j-1]) v[i][j] = v[i-1][j-1]+1;
                    else v[i][j] = max(v[i-1][j], v[i][j-1]);
                }
            }
            return v[len1][len2];
        }
    };