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

⭐️个人主页：摸鱼の文酱博客主页‍♂️
博客领域：java编程基础,mysql
写作风格：干货,干货,还是tmd的干货
精选专栏：【Java】【mysql】 【算法刷题笔记】
博主的码云gitee，平常博主写的程序代码都在里面。
支持博主：点赞、收藏⭐、留言
作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

思路:根据前几个数字的阶乘我们可以知道 当 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;
}

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

对于没有约束的二叉树而言，可以很简单地想到使用下面这个递归的解法：
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;

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

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