剑指offer-Day19

Posted on Edited on In ,

剑指offer 64——求1+2+…+n

不让用+-*/，和if，switch，while，for等等。

有+=可以用

  1. 可尝试try-exception代替if
  2. 声明一个arr[1+n][n]，arr的大小就是n*(n-1)
  3. 利用逻辑运算符的短路效应实现if，比如n&&func(n-1);，若n为0则会跳过func(n-1)，直接执行下一个语句
  4. 用位运算实现俄罗斯农民乘法（二进制乘法）

剑指offer 68.1——二叉搜索树的最近公共祖先

1.并查集

二叉搜索树的结构可以降低时间复杂度

2.假如p和q分别在当前节点的左右儿子中，则说明当前节点就是最近公共祖先，递归or迭代都可以实现

剑指offer 68.2——二叉树的最近公共祖先

  1. 并查集，但太慢了

  2. 下面代码的思路：假如在当前节点的左右子树都没找到p或q，则返回nullptr；当左右两个子树返回的都不是nullptr时，说明当前节点是最近公共祖先

image-20230405232813379