当前位置：首页 > news >正文

快速幂+公共父节点

news 来源：原创 2025/8/26 10:51:30

``# 快速幂
求：23的10000次幂，那么就是求23的5000次幂，因为23^50*2350=23^100;所以可以遍历log(n)次

int res=1;
int tmp=23;
for(int i=1;i<=logn;++i)
{tmp*=tmp;
}

显然，我们无法通过logn计算次数；
比如是非偶数的怎么计算呢？
我们可以考虑一下：100二进制位=（1100100）=2²⁺²5+2^6=4+32+64=100
所以我们可以得到

int res=1;
int tmp=23;
int n=100
while(n>0)
{while(n&1)res*=tmp;tmp*=tmp;n>>1;
}

应用：找好数字

题目描述

一个数字字符串是好数字当它满足（下标从 0 开始偶数下标处的数字为偶数且奇数下标处的数字为质数（2，3，5 或 7）。
比方说，“2582” 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 “3245” 不是好数字，因为3在偶数下标处但不是偶数。
给你一个整数n，请你返回长度为n且为好数字的数字字符串总数。由于答案可能会很大，请你将它对1e9+7 取余后返回 。
一个数字字符串是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

示例 1：
输入：n = 1
输出：5
解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。
示例 2：
输入：n = 4
输出：400

理论分析

代码

long long fastPow(long long a,long long b,long long mod){int res=1;a=a%mod;while(b>0){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}int countGoodNumbers(long long n) {const long long mod=1e9+7;long long evePosition=(n+1)/2;long long oddPosition=n/2;long long res=(fastPow(5,evePosition,mod)*fastPow(4,oddPosition,mod))%mod;return (int)res;}

二叉树的父节点

“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)

分析

思路1

找父节点，那就是找前序遍历的节点
比如：找5的父节点：3；找4的父节点：3，5,2三个父节点
找公共父节点：就是二者前序遍历中的5，我们可以通过map<TreeNode,int>mp
然后逆序遍历map就可以得到最近的父节点

缺点：需要mp来维护，但是这个不是二叉搜索树，如果要查找6，一个查找8，我们需要记录全部的过程，并且是没有规律的，遍历的后面处理的很复杂，尤其是树的深度很深的时候

思路2

上面算是迭代的过程，递归+迭代，递归遍历，然后迭代找父节点
我们如何用迭代来结算呢？
转换思考方向：我们递归遍历，查看该节点是不是父节点就好了

必须输入的是root，节点p，节点q
是否是父节点：
1. 情况1：root节点p或者root节点q，root为最近父节点
2. 情况2：root->left==节点p，root->right=q，root为最近父节点
3. 情况3：root的左右子树中存在p，q；这个就是递归开始的条件了
  1. 情况3.1：p，q全在左子树
  2. 情况3.2：p，q全在右子树
  3. 情况3.3：p，q分别在左右子树中

代码1

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{if(root==nullptr)return nullptr; //递归结束的标志，找到叶子节点了if(root==p||root==q)return root; //p，q就是跟节点了，所以可以直接找到TreeNode* left=tranverse(root->left, p, q);TreeNode* right=tranverse(root->right, p, q);//情况2+情况3.3，从递归角度来看，p，q是分别在左右子树还是分别为左右子节点是没有区别的if(left!=nullptr&&right!=nullptr){return root;}return left==nullptr？left:right;
}

优化代码1

我们可以看到，如果在左子树找到了p，q我们还是需要遍历右子树的？有没有什么方法是找到了就不需要遍历的，我们可以通过一个状态码state来记录

 bool state=false;TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(state){return nullptr;}if (root == nullptr) {return nullptr;}// 前序位置if (root== p || root == q) {// 如果遇到目标值，直接返回return root;}TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);// 后序位置，已经知道左右子树是否存在目标值if (left != nullptr && right != nullptr) {// 当前节点是 LCA 节点state=true;return root;}return left != nullptr ? left : right;}

优化2

上面state虽然减少了进入递归，即通过提前返回nullptr来的方式减少进入左右子树，
我们可以通过遍历左子树，如果左子树返回不为空，直接不进入右子树即可

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr || root == p || root == q) {return root;}TreeNode* left = lowestCommonAncestor(root->left, p, q);if (left && left != p && left != q) {return left; // 如果 left 已经是 LCA，直接返回，不再递归右子树}TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left && right) {return root;}return left ? left : right;
}

stor(root->right, p, q);

    if (left && right) {return root;}return left ? left : right;

}

第一种优化的缺点

应用：找好数字

题目描述

理论分析

代码

二叉树的父节点

分析

思路1

思路2

代码1

优化代码1

优化2

相关文章：