今日目标

  • 双指针法
  • 排列组合
  • 二叉树
  • 二维矩阵
  • 动态规划

双指针、三指针法

345. 反转字符串中的元音字母 - 力扣(LeetCode) (leetcode-cn.com)

思路简单,略。

class Solution {
public:
  bool isVowel(char c) {
    const char *const v = "aeiouAEIOU";
    for (int i = 0; i < 10; i++) {
      if (v[i] == c) {
        return true;
      }
    }
    return false;
  }
  string reverseVowels(string s) {
    int l = 0, r = s.size();
    while (l < r) {
      while (l < r && !isVowel(s[l])) {
        l++;
      }
      while (l < r && !isVowel(s[r])) {
        r--;
      }
      char tmp = s[l];
      s[l] = s[r];
      s[r] = tmp;
      l++;
      r--;
    }
    return s;
  }
};

11. 盛最多水的容器 - 力扣(LeetCode) (leetcode-cn.com)

思路就是 Area = min (leftHeight, rightHeight) * width,移动两边较短的板,记录过程中遇到过的最大面积。

209. 长度最小的子数组 - 力扣(LeetCode) (leetcode-cn.com)

300. 最长递增子序列 - 力扣(LeetCode) (leetcode-cn.com)

双指针滑动窗口法 l, r 指针。 若 r 右移,sum += v [r] 若 l 右移,sum -= v [r] 先让 r 右移,直到满足条件 然后让 l 左移,直到不满足条件 返回临界条件即可。

排列组合

排列组合常常用于暴力算法中,性能一般不太好(除非是可以公式化的题等)。

排列

排列的穷举:假设有列表 {1,2,3,4,5},则全排列相当于 1 x {2,3,4,5} + 2 x {1,3,4,5} + 3 x {1,2,4,5} + 4 x {1,2,3,5} + 5 x {1,2,3,4},可以用递归解决。

组合

组合的穷举

不同的二叉搜索树 - 不同的二叉搜索树 - 力扣(LeetCode) (leetcode-cn.com)

15. 三数之和 - 力扣(LeetCode) (leetcode-cn.com)

暴力穷举(超时):

class Solution {
public:
  vector<vector<int>> anySum(vector<int> &nums, int any, int expect) {
    if (nums.size() < any) {
      return {};
    }
    vector<vector<int>> ret;
    // 如 {0,0,1,2,3}, 1, 0
    // 则应该返回 {{0},{0}}
    if (any == 1) {
      for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == expect) {
          vector<int> ni;
          ni.push_back(nums[i]);
          ret.push_back(ni);
        }
      }
    }
    // 将 nums [i] 与剩下的右边的组合
    for (int i = 0; i < nums.size(); i++) {
      if (i - 1 >= 0 && nums[i] == nums[i - 1]) {
        continue;
      }
      vector<int> tmp = nums;
      tmp.erase(tmp.begin(), tmp.begin() + i + 1);

      // nums[0] +  anySum(nums-nums[0]) = expect
      vector<vector<int>> try_list = anySum(tmp, any - 1, expect - nums[i]);
      for (int j = 0; j < try_list.size(); j++) {
        try_list[j].push_back(nums[i]);
        ret.push_back(try_list[j]);
      }
    }
    sort(ret.begin(), ret.end());
    return ret;
  }
  void remove_duplicated(vector<vector<int>> &nums) {
    auto current = nums.begin();
    auto end = nums.end();
    while (current != end) {
      auto next = current + 1;
      if (next != end) {
        if (*current == *next) {
          nums.erase(current);
          end = nums.end();
          continue;
        }
      }
      current++;
    }
  }
  vector<vector<int>> threeSum(vector<int> &nums) {
    // 排序去重
    sort(nums.begin(), nums.end());
    print_vec(nums);
    auto ret = anySum(nums, 3, 0);
    remove_duplicated(ret);
    return ret;
  }
};

三数之和可以利用双指针 + 一个中间值。遍历有序数组,当两端之和等于中间的相反数时满足。同时跳过重复数,提高性能。

组合公式运用

高考数学典型题:62. 不同路径 - 力扣(LeetCode) (leetcode-cn.com)

class Solution {
public:
  int64_t combination(int64_t n, int64_t k) {
    int64_t numerator = 1;
    int64_t denominator = 1;
    for (int64_t i = 0; i < k; i++) {
      numerator *= n - i;
      denominator *= i + 1;
    }
    return numerator / denominator;
  }
//m 行 n 列,m > n
  // 需要走 m + n - 2 次,其中纵向最多 n - 1 次
  int64_t uniquePaths(int64_t m, int64_t n) {
    if (m < n)
      return uniquePaths(n, m);
    auto path = m + n - 2;
    auto turn = n - 1;
    return combination(path, turn);
  }
};

二叉树

后序遍历

145. 二叉树的后序遍历 - 力扣(LeetCode) (leetcode-cn.com)

后序就是 左右根 的顺序访问节点。

class Solution {
public:
  
  vector<int> postorderTraversal(TreeNode *root) {
    if (nullptr == root) {
      return {};
    }
    stack<int> sret;
    // 后序遍历: left right mid,
    // 输出顺序是 lrm,则如果用栈,入栈顺序是 mrl
    stack<TreeNode *> s;
    s.push(root);
    while (!s.empty()) {
      auto out = s.top();
      s.pop();
      sret.push(out->val);
      if (out->left)
        s.push(out->left);
      if (out->right)
        s.push(out->right);
    }
    vector<int> ret;
    while (!sret.empty()) {      
      auto out = sret.top();
      sret.pop();
      ret.push_back(out);
    }
    return ret;
  }
};

前序、中序遍历都可以用栈实现。层序遍历最好用队列实现。

有序链表转换二叉搜索树

数组转完全二叉树

TreeNode *create_tree(vector<int> v, int i = 0) {
  if (v[i] == -1) {
    return nullptr;
  }
  auto current = new TreeNode(v[i]);
  if (i < v.size()) {
    auto i_left = 2 * i + 1;
    auto i_right = 2 * i + 2;
    current->left = create_tree(v, i_left);
    current->right = create_tree(v, i_right);
    return current;
  }
  return current;
}

判断对称二叉树

101. 对称二叉树 - 力扣(LeetCode) (leetcode-cn.com)

关键思路:l.r == r.l && l.l == r.r

#include <binary_tree.h>
#include <debug.h>
class Solution {
public:
  /*
          1
         / \
        2   2
       / \ / \
      3  4 4  3
     /         \
    5           5

  */
  bool mirrorEq(TreeNode *l, TreeNode *r) {
    if (l == nullptr && r == nullptr) {
      return true;
    }
    // 其中一个为 null,则不等
    if (l == nullptr || r == nullptr) {
      return false;
    }
    if (l->val != r->val) {
      return false;
    }
    return mirrorEq(l->left, r->right) && mirrorEq(l->right, r->left);
  }
  bool isSymmetric(TreeNode *root) { return mirrorEq(root->left, root->right); }
};

int main(int argc, char const *argv[]) {
  Solution s;
  int null = -1;
  TreeNode *t =
      // create_tree({1, 2, 2, 3, 4, 4, 3, 5, -1, -1, -1, -1, -1, -1, 5});
      create_tree({1, 2, 2, null, 3, null, 3});
  print_tree(t);
  cout << s.isSymmetric(t) << endl;
  return 0;
}

路径总和

112. 路径总和 - 力扣(LeetCode) (leetcode-cn.com)

思路:遍历顺带计算带权路径长度。

二维矩阵

搜索二维矩阵

即在一个行列均升序的矩阵中快速定位一个值。此题相当于二叉搜索树。

image-20211111183804491

旋转四十五度,变成二分搜索,对每个节点,左小右大:

image-20211111190004084

参考代码:

#include <debug.h>

class Solution {
public:
  // return: hasErr
  bool movedown(vector<vector<int>> &m, int &x, int &y) {
    if (x + 1 == m.size()) {
      return true;
    }
    x++;
    return false;
  }
  // return hasErr
  bool moveleft(vector<vector<int>> &m, int &x, int &y) {
    if (y == 0) {
      return true;
    }
    y--;
    return false;
  }
  bool searchMatrix(vector<vector<int>> &m, int target) {
    if(m.size() == 0){
      return false;
    }
    // 需要注意轴向
    // +--> y
    // |
    // x
    // 以右上角为起始点
    int x = 0, y = m[0].size() - 1;
    bool err = false;
    // 如果 target 大于当前,则向下移动,小于则向左移动,等于则返回
    //true,越界则返回 false
    while (true) {
      if (target > m[x][y]) {
        err = movedown(m, x, y);
      } else if (target < m[x][y]) {
        err = moveleft(m, x, y);
      } else {
        return true;
      }
      if (err) {
        return false;
      }
    }
  }
};

int main(int argc, char const *argv[]) {
  Solution s;
  vector<vector<int>> m = {
      {1, 4, 7, 11, 15},    {2, 5, 8, 12, 19},    {3, 6, 9, 16, 22},
      {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30},
  };
  cout << s.searchMatrix(m, 5) << endl;

  m = {{-5}};
  cout << s.searchMatrix(m, -2) << endl;

  m = {{1, 4}, {2, 5}};
  cout << s.searchMatrix(m, 4) << endl;

  m = {{1, 3, 5, 7, 9},
       {2, 4, 6, 8, 10},
       {11, 13, 15, 17, 19},
       {12, 14, 16, 18, 20},
       {21, 22, 23, 24, 25}};
  cout << s.searchMatrix(m, 11) << endl;
  return 0;
}

搜索二维矩阵

动态规划

主要参考的是这篇著名文章:告别动态规划,连刷 40 道题,我总结了这些套路,看不懂你打我(万字长文) - 知乎 (zhihu.com)

跳跃游戏

55. 跳跃游戏 - 力扣(LeetCode) (leetcode-cn.com)

class Solution {
public:
  // 如果一个位置能够到达,那么这个位置左侧所有位置都能到达
  bool canJump(vector<int> &nums) {
    // 能跳的最远距离
    auto farthest = 0;
    // 目标位置
    auto end = nums.size() - 1;
    for (int i = 0; i <= farthest; i++) {
      auto cur_farthest = i + nums[i];
      farthest = max(cur_farthest, farthest);
      if (farthest >= end) {
        return true;
      }
    }
    return false;
  }
};

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。