剑指offer-Day19
剑指offer 64——求1+2+…+n
不让用+-*/,和if,switch,while,for等等。
有+=可以用
- 可尝试try-exception代替if
- 声明一个arr[1+n][n],arr的大小就是n*(n-1)
- 利用逻辑运算符的短路效应实现if,比如
n&&func(n-1);
,若n为0则会跳过func(n-1),直接执行下一个语句 - 用位运算实现俄罗斯农民乘法(二进制乘法)
剑指offer 68.1——二叉搜索树的最近公共祖先
1.并查集
二叉搜索树的结构可以降低时间复杂度
2.假如p和q分别在当前节点的左右儿子中,则说明当前节点就是最近公共祖先,递归or迭代都可以实现
剑指offer 68.2——二叉树的最近公共祖先
并查集,但太慢了
下面代码的思路:假如在当前节点的左右子树都没找到p或q,则返回nullptr;当左右两个子树返回的都不是nullptr时,说明当前节点是最近公共祖先