1. 给定前序遍历序列构造二叉搜索树 100%

  1. 由于是二叉搜索树，因此将前序遍历序列升序排序后就是中序遍历序列

  2. 相当于给定前序序列和中序序列构造二叉树

    1. /**
    2. * struct TreeNode {
    3. *    int val;
    4. *    struct TreeNode *left;
    5. *    struct TreeNode *right;
    6. *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    7. * };
    8. */
    9. class Solution {
    10. private:
    11.  unordered_map<int, int> inValIdxMap;
    13.  TreeNode* dfs(vector<int>&preSlice, int preStart, int preEnd, int inStart, int inEnd)
    14.  {
    15.      if(preStart > preEnd)
    16.          return nullptr;
    18.      int val = preSlice[preStart];
    19.      TreeNode* root = new TreeNode(val);
    20.      int rootIdxOfIn = inValIdxMap[val];
    21.      int leftLen = rootIdxOfIn - inStart;
    22.      root->left = dfs(preSlice, preStart + 1, preStart + leftLen, inStart, rootIdxOfIn - 1);
    23.      root->right = dfs(preSlice, preStart + leftLen + 1, preEnd, rootIdxOfIn + 1, inEnd);
    24.      return root;
    25.  }
    26. public:
    27.  /**
    28.   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    29.   *
    30.   *
    31.   * @param preSlice int整型vector 先序遍历结果数组
    32.   * @return TreeNode类
    33.   */
    34.  TreeNode* reConstructBST(vector<int>& preSlice) {
    35.      vector<int> inSlice = preSlice;
    36.      sort(inSlice.begin(), inSlice.end());
    37.      for(int i = 0; i < inSlice.size(); ++i)
    38.          inValIdxMap[inSlice[i]] = i;
    39.      return dfs(preSlice, 0, preSlice.size() - 1, 0, preSlice.size() - 1);
    40.  }
    41. };

2. 矩阵顺时针旋转90°后逆时针螺旋遍历 100%

其实就和[中等] 54. 螺旋矩阵基本一致，只是从左下角开始逆时针螺旋遍历（下边界、右边界、上边界、左边界）

  1. class Solution {
  2. public:
  3.     /**
  4.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  5.      *
  6.      *
  7.      * @param matrix int整型vector<vector<>>
  8.      * @return int整型vector
  9.      */
  10.     vector<int> antiSpiralOrder(vector<vector<int> >& matrix) {
  11.         if(matrix.size() == 0 || matrix[0].size() == 0)
  12.             return {};
  13.         int rows = matrix.size();
  14.         int cols = matrix[0].size();
  16.         int up = 0;
  17.         int down = rows - 1;
  18.         int left = 0;
  19.         int right = cols - 1;
  20.         vector<int> result;
  21.         while(result.size() < rows * cols)
  22.         {
  23.             if(down >= up)
  24.             {
  25.                 for(int i = left; i <= right; ++i)
  26.                     result.push_back(matrix[down][i]);
  27.                 --down;
  28.             }
  30.             if(right >= left)
  31.             {
  32.                 for(int i = down; i >= up; --i)
  33.                     result.push_back(matrix[i][right]);
  34.                 --right;
  35.             }
  37.             if(up <= down)
  38.             {
  39.                 for(int i = right; i >= left; --i)
  40.                     result.push_back(matrix[up][i]);
  41.                 ++up;
  42.             }
  44.             if(left <= right)
  45.             {
  46.                 for(int i = up; i <= down; ++i)
  47.                     result.push_back(matrix[i][left]);
  48.                 ++left;
  49.             }
  50.         }
  51.         return result;
  52.     }
  53. };

3. 求最大等比子序列长度 90.91%

求整数数组 nums 中最大等比子序列的长度。最长递增子序列可能是升序的，也可能是降序的。

卡在 90.91% 了，不知道错在哪

  1. 应该是下面第 23 行应该改为 list[i][div] = max(list[i][div], 1 + list[j][div]);
  1. 第 12、13 行，应该还要判断，当 len == 2 时，两个数之间能否整除，因为虽然题目没要求等比的比值是整数，但是例如两个数 2、3，如果等比，比值是 2/3 或 3/2，都不存在第三个数让它们是等比数列，这种情况下应该返回 1

  2. 看到有人说解法是：最长递增子序列 + 整除判断，所以比值必须是整数（升序等比子序列） or 1/整数（降序等比子序列）？ ```cpp class Solution { public: /**

    • 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    • @param nums int整型vector 整形数组

    • @return int整型 */ int longestGeometricSeqLength(vector& nums) { int len = nums.size(); if(len <= 2)

      1.  return len;

      vector> list(len); int result = 0; for(int i = 1; i < len; ++i) {

      1.  for(int j = 0; j < i; ++j)
      2.  {
      3.      if(nums[j] == 0)
      4.          continue;
      5.      double div = double(nums[i]) / double(nums[j]);
      6.      list[i][div] = 1 + list[j][div];
      7.      result = max(result, list[i][div]);
      8.  }

      } return result + 1;

// int result = 2; // for(int i = 0; i < len; ++i) // { // for(int j = i + 1; j < len; ++j) // { // double div = double(nums[j]) / double(nums[i]); // int pre = nums[j]; // int curlen = 2; // for(int k = j + 1; k < len; ++k) // { // if(double(nums[k]) / double(pre) == div) // { // ++curlen; // pre = nums[k]; // } // } // result = max(result, curlen); // } // } // return result; } }; ```