> 文档中心 > leecode递归基础练习(172,1342,222,LCP44)

leecode递归基础练习(172,1342,222,LCP44)


📜个人简介

⭐️个人主页:摸鱼の文酱博客主页🙋‍♂️
🍑博客领域:java编程基础,mysql
🍅写作风格:干货,干货,还是tmd的干货
🌸精选专栏:【Java】【mysql】 【算法刷题笔记】
🎯博主的码云gitee,平常博主写的程序代码都在里面。
🚀支持博主:点赞👍、收藏⭐、留言💬
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!

172.阶乘后的零

思路:根据前几个数字的阶乘我们可以知道 当 n<5 时,都不会出现末尾的 0 ;
思考原因可知: 末尾为零的情况就是10(100,1000~~)的倍数,也就是说要在一个数的阶乘的数字中找 10
(或者10的因子–2 * 5);又因为 2 的倍数比 5 的倍数要多得多,所以能有几个 10 ,就取决于有几个 5;
那么这个问题就可以转换成求 n 可以除几个 5;

java代码:

private static int trailingZeroes(int num) { //递归 if(num<5){     return 0; }else {     return num/5+trailingZeroes(num/5); }    }
    private static int trailingZeroes(int num) { //非递归int zeroCount = 0; long currentMultiple = 5;while (num > 0) {     num /= 5;     zeroCount += num; } return zeroCount;    }

c语言代码:

//递归int trailingZeroes(int n){    if(n<5){ return 0;    }    return n/5+trailingZeroes(n/5);}//非递归int trailingZeroes(int n) {    int result = 0;    while (n >= 5) { n = n / 5; result += n;    }    return result;}

leecode递归基础练习(172,1342,222,LCP44)

1342.将数字变成 0 的操作次数

将 \textit{num}num 与 11 进行位运算来判断 \textit{num}num 的奇偶性。

记录操作次数时:

如果 num 是奇数,我们需要加上一次减 1 的操作。

如果num>1,我们需要加上一次除以 2 的操作。

然后使num 的值变成num/2。重复以上操作直到 num=0 时结束操作。

java代码:

//递归    public int numberOfSteps(int num) { if(num == 0){     return 0; } if(num % 2 == 0){     return 1 + numberOfSteps(num/2); }else{     return 1 + numberOfSteps(num-1); }    }    //非递归    public static int numberOfSteps(int num) { int ret = 0; while (num > 0) {     ret += (num > 1 ? 1 : 0) + (num & 0x01);     num >>= 1; } return ret;    }

c语言代码:

//递归 int numberOfSteps(int num){    if(num==0){ return 0;    }    if(num % 2 == 0){ return 1 + numberOfSteps(num/2);    }else{ return 1 + numberOfSteps(num-1);    }}//非递归 int numberOfSteps2(int num) {    int ret = 0;    while (num) { ret += (num > 1 ? 1 : 0) + (num & 0x01); num >>= 1;    }    return ret;}

leecode递归基础练习(172,1342,222,LCP44)

222. 完全二叉树的节点个数

对于没有约束的二叉树而言,可以很简单地想到使用下面这个递归的解法:
java代码:

 public int countNodes(TreeNode root) { if(root != null){ return 1 + countNodes(root.right) + countNodes(root.left);    }    return 0;    }

c语言代码:

int countNodes(struct TreeNode* root){     if(root != NULL){ return 1 + countNodes(root->right) + countNodes(root->left);    }    return 0;

leecode递归基础练习(172,1342,222,LCP44)

LCP 44. 开幕式焰火

创建HashSet,利用其去重的特性,遍历搜索二叉树的节点,节点不为空的情况下,将该节点的值存入HashSet,最后返回HashSet.size;
java代码:

HashSet<Integer> hashSet = new HashSet<>();    public int numColor(TreeNode root) { dfs(root); return hashSet.size();    }    public void dfs(TreeNode root){ if(root==null)return; if(!hashSet.contains(root.val))hashSet.add(root.val); dfs(root.left); dfs(root.right);    }

先创建一个哈希表,用memset将所有的值置为0;
遍历树的节点,如果节点不为NULL,就将哈希表的一个数改为1;
然后遍历左子树,遍历右子树;
最后检查哈希表中修改了几个1,返回;
c语言代码:

int Hash[1024];void transfer(struct TreeNode* root) {    if(root) { Hash[root->val] = 1; // (1) transfer(root->left);// (2) transfer(root->right);      // (3)    }}int numColor(struct TreeNode* root){    int i, sum = 0;    memset(Hash, 0, sizeof(Hash));    transfer(root);    for(i = 1; i <= 1000; ++i) { if(Hash[i]) ++sum;    }    return sum;}

在这里插入图片描述