LeetCode 笔记一

LeetCode 笔记一

• • 1.最长连续序列
  • 2.验证二叉搜索树
  • 3.柱状图中最大的矩形
  • 4.单词搜索
  • 5.最小覆盖字串
  • 6.跳跃游戏

前言：主要是记录一些算法题的解题思路与技巧，纯当笔记用。

图片与部分代码来源：leetcode
图片与部分代码来源：leetcode
图片与部分代码来源：leetcode

1.最长连续序列

力扣链接：最长连续序列

暴力的解法当然是分别以数组中每一个数作为第一个数，找到连续的最长序列，取其中的最大值。

然而这种解法有很多重复计算。

举个例子：有序列 0，2，8，3，9，4，5 。

显然最长连续序列是 2，3，4，5 。

但在暴力解法的过程以 2 为第一个数的最长序列为 2，3，4，5；以 3 为第一个数的最长序列为 3，4，5；以 4 为第一个数的最长序列为 4，5；以 5 为第一个数的最长序列为 5。

仔细观察会发现 以 3，4，5开头的遍历是没有必要的，因为如果某个数字在数组中存在比它小 1 的数，那么比它小 1 的数字能构成的最长连续序列至少比它大 1 。

它不可能构成最长连续序列，所以这种数字可以直接跳过，避免没必要的遍历。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for (const int& num : nums) {
            num_set.insert(num);
        }

        int max_=0;
        for(auto& tmp:nums){

            if(!num_set.count(tmp-1)){

                int sum=1;
                while(num_set.count(tmp+1)){

                    ++sum;
                    ++tmp;
                }

                max_=max(max_,sum);
            }
        }   

        return max_; 
    }
};

2.验证二叉搜索树

力扣链接：验证二叉搜索树

一棵正常的二叉搜索树，其中序遍历得到的序列是严格有序的，利用这个性质可以判断一个树是否是二叉搜索树。

class Solution {
public:
    
    long front=LONG_MIN;

    bool isValidBST(TreeNode* root) {
       
         if(!root)  return true;

         bool left=isValidBST(root->left);   //当左子树不满足时，整颗树就不满足了，可以直接返回，不用遍历右子树
         if(!left)  return false; 

         if(front>=root->val)  return false;  //当右子树不满足时，整颗树就不满足了，可以直接返回，不用遍历左子树
         front=root->val;

         bool right=isValidBST(root->right);
         if(!right)  return false;

         return true;
    };
};

3.柱状图中最大的矩形

力扣链接：柱状图中最大的矩形

算是很经典的单调栈的应用了。

暴力思路，固定柱状体矩形高，在当前高下扩展长度，直至找到第一个比当前矩形矮的矩形，停止扩展。

利用单调栈优化，使时间复杂度从O(n ²) 降为 O(n) 。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        
        int n = heights.size();
        vector<int> left(n), right(n, n);
        
        stack<int> sta;
        for (int i = 0; i < n; ++i) {
            
            while (!sta.empty() && heights[sta.top()] >= heights[i]) {
                
                right[sta.top()] = i;
                sta.pop();
            }

            left[i] = (sta.empty() ? -1 : sta.top());
            sta.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i)  ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        
        return ans;
    }
};

4.单词搜索

力扣链接：力扣链接

class Solution {
public:
    bool dfs(vector<vector<char>>& board,vector<vector<int>>& mask,string& word,int line,int row,int place){

         if(word.size()==place)  return true;

         if(line>=board.size() || line<0 || row<0 || row>=board[0].size() || board[line][row]!=word[place])  return false;    //把不合法的边界值放到下层去判断，减少了这层的很多的判断性代码

         if(!mask[line][row]){

             mask[line][row]=1;

             if(dfs(board,mask,word,line+1,row,place+1) || dfs(board,mask,word,line-1,row,place+1) || dfs(board,mask,word,line,row+1,place+1) || dfs(board,mask,word,line,row-1,place+1))  return true;    //在这四个回溯函数中，只要有一个返回 true 就证明二维数组中存在我们要查找的单词，可以直接返回，不用再判断下去，利用了 || 运算符的逻辑中断。



             mask[line][row]=0;
         }

         return false;
    }

    bool exist(vector<vector<char>>& board, string word) {

         int n=board.size(),m=board[0].size();
         vector<vector<int>> mask(n,vector<int>(m,0));
         for(int i=0;i<n;++i){    //从二维数组的每一个元素开始
             for(int j=0;j<m;++j){
                 if(dfs(board,mask,word,i,j,0))  return true;
             }
         }

         return false;
    }
};

记录这题的主要原因是这回溯代码写的太好了。

精简高效。

5.最小覆盖字串

力扣链接：最小覆盖字串

思路是维护一个滑动窗口，直至滑动窗口中包含所有需要的字符。

此时收缩左窗口等到一个最小覆盖子串。

变量 S ，找到 S 中最小的覆盖子串，返回。

看下面的代码，用了一个小技巧，使时间复杂度为 O(n) 。

class Solution {
public:

    string minWindow(string s, string t) {
            
           int n=t.size();
           vector<int> need(128,0);    //用数组作为哈希表索引
           for(auto& ch:t)  ++need[ch];   //记录字符串 t 中字符及数量

           int right=0,left=0,count=n,min_=0,size=INT_MAX;
           while(right<s.size()){

               if(need[s[right]]>0)  --count;   //用于计数，当其为0时表示滑动窗口中包含所有需要的字符
               --need[s[right]];   //使进入滑动窗口的字符在哈希表中计数减一，这样就能分辨出普通字符与 t 中字符及数量

               if(!count){

                   while(left<right && need[s[left]]<0)  ++need[s[left++]];    //收缩左窗口
                       
                   if(size>right-left+1){

                      size=right-left+1;
                      min_=left;
                   }  
              
                   ++count;
                   ++need[s[left]];
                   ++left;
               }

               ++right;
           }

           return size==INT_MAX?"":s.substr(min_,size);
    }
};

6.跳跃游戏

力扣链接：跳跃游戏

可以维护一个最远能到达的变量，遍历所有元素，如果在当前元素能到达的最远距离比这个变量之前的值大，就把新的值赋给变量。

class Solution {
public:
    bool canJump(vector<int>& nums) {

         int max_=0;     //存储最远能到达的值
         for(int i=0;i<nums.size();++i){

             max_=max(max_,nums[i]+i);    //当前元素能使得能到达的距离变长
             if(max_==i && i!=nums.size()-1)  return false;   //说明已经走不动了
         }

         return true;
    }
};