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;}
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;}
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;
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;}