[leetcode] Next Permutation && Longest Valid Parentheses

• 今天我们主要分享两道题的做法—Next Permutation和 Longest Valid Parentheses
• Next Permutation
  • 题意：给定一个数组nums,修改这个数组里面数字的顺序，使得修改后的数组的数字排序刚好比修改前的数组顺序的字典序大一个。比如说比1,2,3字典序大一的就是1,3,2。如果不存在这样一个序列(整个数组按照从大到小排列)，则返回从小到大的序列。
  • 思路
    • 我们从后往前看整个数组，假设说最后一个数字刚好比倒数第二个数组大，那么只需要交换这两个数字就好。
    • 那么如果最后一个数字比倒数第二个数字大呢？也就是说n->n-1之间是升序的关系，那么我们交换之后，反而字典序变小了。
    • 所以，对于我们来说，我们就是要从后往前找到第一个i和i-1之间是降序的关系。那么此时的i-1就是我们要替换的位置。
    • 为什么我们要从后往前找呢？首先我们要找到字典序只大一的新序列。也就是说我们要找到所有比该字典序大的序列里面字典序最小的。如果我们从前往后遍历，找到一个j，如果j<i-1,则肯定存在更小的字典序组合使其大于原来的字典序。所以我们从后往前可以保证是最小的。
    • 那我们找到i-1了之后呢？用谁来和他替换呢？通过上一步我们知道0~i-1之间的是不能动的，所以我们就在i ~ n之间找到一个最小的大于第i-1的数，假设说这个位置是j。那么我们就交换i-1和j之间的数。
    • 此外，此时i ～ n之间是一个降序排列，我们增加来i-1所在位置的值后，i~n的序列应该就是最小的，所以应该是一个升序排列。所以我们再颠倒一下i～n之间的顺序就好。
    • 再此外，如果我们找不到这样的i呢？也就是所有的数字都是从0～n降序排列的，这时候字典序已经是最大的了，所以我们就返回最小的字典序就好，执行reverse操作。
  • 代码(C++, 8ms, 100%)

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int size = int(nums.size());
            int first_decrease = -1;
            for(int j=size-1;j>0;j--){
                if(nums[j] > nums[j - 1]){
                    first_decrease = j - 1;
                    break;
                }
            }
            if(first_decrease == -1){
                reverse(nums.begin(), nums.end());
            } else{
                int swap_index = -1;
                for(int j = first_decrease;j<size-1;j++){
                    if(nums[j + 1] <= nums[first_decrease]){
                        swap_index = j;
                        break;
                    }
                }
                if(swap_index == -1){
                    swap_index = size - 1;
                }
                swap(nums[first_decrease], nums[swap_index]);
                reverse(nums.begin() + first_decrease + 1, nums.end());
            }
        }
    };
               

• Longest Valid Parentheses
  • 题意：给你一个字符串s，s里面只包含了 '('和‘)‘。问你最长的能匹配的字符串的长度。比如说:"((())()(",前面的这个字符串最长能匹配的子字符串长度就为6=>"(())()"
  • 解法1：
    • 定义两个stack1(存储‘（‘)，stack2（存储1和2）。"("表示1，“()“表示为2。
    • 当pos=i遇到“)“的时候
      • 如果stack1还有尚未匹配的“(“，则stack2中最顶部的1将其变成2，再放入stack2中。
      • 如果stack1为空，则返回当前的res和i~n这个字符串的最大值。
    • 当pos=i遇到‘(‘的时候
      • stack1中加入’(’,stack2中加入1。
    • 最后，当pos遍历完成的时候，我们会得到stack2，他的形式如：1，2，2，1，1，2。则我们在其中找到最大的连续的2的和。就是我们的结果。我们利用两个stack是为了计算出现过多的’('而导致前面匹配的()和后面匹配的‘()‘分开计算。
    • 代码(C++, 16ms, )：

  int get_res_from_stack(stack<int> stack2){
          int res = 0;
          bool restart = false;
          int cur_res = 0;
          // print(stack2);
          while(not stack2.empty()){
              int cur = stack2.top();
              stack2.pop();
              if(cur == 1){
                  restart = true;
              }
              if(cur == 2){
                  if(restart){
                      cur_res = 2;
                      restart = false;
  
                  }else{
                      cur_res += 2;
                  }
                  res = max(res, cur_res);
              }
          }
          return res;
      }
  int longestValidParentheses_v2(string s) {
          // cout<<s<<endl;
          stack<char> stack1;
          stack<int> stack2;
          int res = 0;
          int cur_len = 0;
          for(int i=0;i<s.length();i++){
              if(s[i] == ')'){
                  if(stack1.empty()){
                      return max(max(res, get_res_from_stack(stack2)), longestValidParentheses(s.substr(i+1)));
                  }else{
                      cur_len += 2;
                      stack1.pop();
                      // cout<<stack2.top()<<endl;
                      stack<int> tmp;
                      while(stack2.top() != 1){
                          tmp.push(stack2.top());
                          stack2.pop();
                      }
                      stack2.pop();
                      stack2.push(2);
                      while(not tmp.empty()){
                          stack2.push(tmp.top());
                          tmp.pop();
                      }
                  }
              }else{
                  stack1.push('(');
                  stack2.push(1);
              }
          }
          res = max(res, get_res_from_stack(stack2));
          return res;
      }
             

  • 解法2：
    • 上述解法1的主要问题在于，从stack2中去1的时候要来回倒，增加了耗时。那么我们怎么优化呢？我参考了官方的solution中的stack方法，下面就介绍官方的stack方法。
    • 我们只用一个stack保存’('中的位置，当遇到‘)‘的时候，我们弹出stack中保存的位置，就可以计算长度。
    • 但是问题在于，我们如果区分"()(())"和“()(()“这两种情况，如果只用上一步的算法，我们对前者计算得到4(不能将2和4加起来)，后者计算得到2。
    • 如何解决呢？我们在初始化stack的时候，提前加入一个位置-1。表示的当前开始计算的前一个元素，那样我们计算长度的时候也不用加1。
    • 具体来说
      • 当我们遇到"(“的时候，我们将位置i加入stack中。
      • 当我们遇到")"的时候，我们首先将上一个元素弹出。如果弹出后队列为空，则直接将i加入stack，continue(这时候对应的是出现了多余的’)’,那我们就相当重新开始计算len)。如果队列不为空，则取出top元素，用i-top，得到长度。并与res比较取得最大的那个。
    • 代码(C++, 8ms)

  int longestValidParentheses_v1(string s){
          stack<int > stack1;
          stack1.push(-1);
          int res = 0;
          for(int i=0;i<s.length();i++){
              if(s[i] == '('){
                  stack1.push(i);
              }else{
                  stack1.pop();
                  if(stack1.empty()){
                      stack1.push(i);
                  }else{
                      int len = i - stack1.top();
                      res = max(res, len);
                  }
              }
          }
          return res;
      }
             

  • 解法3：动态规划
    • 我们定义一个数组dp，dp[i]表示以s[i]结尾的能匹配的字符串的最长长度。
    • 如果s[i] = ‘(’,根据定义可知，dp[i]=0。
    • 如果s[i] = ‘)’,
      • 如果s[i-1] = ‘(’, 则刚好可以组成“()“，所以dp[i] = dp[i-2] + 2
      • 如果s[i-1] = ‘)’, 则是‘))‘,的情况，
        • 那么此时如果s[i-1-dp[i-1]]=’(’,说明当前的‘)‘可以匹配到合适的‘(‘，那么dp[i] = dp[i] + 2 + dp[i-1-dp[i-1]-1]。
        • 否则，dp[i] = 0
    • 代码(C++, 8ms)

  int longestValidParentheses_v3(string s){
          // dp
          int* dp = new int[s.length()];
          memset(dp, 0, sizeof(int) * s.length());
          int res = 0;
          for(int i=1;i<s.length();i++){
              if(s[i] == ')' && s[i-1] == '('){
                  if(i>=2)
                      dp[i] = dp[i-2] + 2;
                  else
                      dp[i] = 2;
              }else{
                  if(s[i] == ')' && s[i-1] == ')'){
                      if(s[i-dp[i-1]-1] == '('){
                          dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2];
                      }
                  }
              }
              res = max(res, dp[i]);
              // cout<<"i="<<i<<", dp="<<dp[i]<<endl;
          }
          return res;
      }