Java教程

每日刷题计划Day12-递归+树

本文主要是介绍每日刷题计划Day12-递归+树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题源:LeetCode

LeetCode月徽章每日一题

1414. 和为 K 的最少斐波那契数字数目

给你数字 k ,请你返回和为 k 的斐波那契数字的最少数目,其中,每个斐波那契数字都可以被使用多次。

斐波那契数字定义为:

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 , 其中 n > 2 。
数据保证对于给定的 k ,一定能找到可行解。

示例 1:
输入:k = 7
输出:2
解释:斐波那契数字为:1,1,2,3,5,8,13,……
对于 k = 7 ,我们可以得到 2 + 5 = 7 。

示例 2:
输入:k = 10
输出:2
解释:对于 k = 10 ,我们可以得到 2 + 8 = 10 。

示例 3:
输入:k = 19
输出:3
解释:对于 k = 19 ,我们可以得到 1 + 5 + 13 = 19 。

提示:
1 <= k <= 10^9

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        if (k == 0) return 0;
        if (k == 1) return 1;
        
        // 找不大于k的最大的fib,结果在a中
        int a = 1, b = 1;
        while (b <= k) {
            b = a + b;
            a = b - a;
        }
        return findMinFibonacciNumbers(k - a) + 1;
    }
};

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例1:在这里插入图片描述
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:
输入:l1 = [], l2 = []
输出:[]

示例 3:
输入:l1 = [], l2 = [0]
输出:[0]

提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

方法:递归
我们可以如下递归地定义两个链表里的 merge 操作(忽略边界情况,比如空链表等):

list1[0]+merge(list1[1:],list2) list1[0]<list2[0]
list2[0]+merge(list1,list2[1:]) otherwise

也就是说,两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

算法

我们直接将以上递归过程建模,同时需要考虑边界情况。

如果 l1 或者 l2 一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l1 和 l2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) {
            return list2;
        } else if (list2 == nullptr) {
            return list1;
        } else if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

复杂度分析

时间复杂度:给出一个递归算法,其时间复杂度 O(T) 通常是递归调用的数量(记作 R) 和计算的时间复杂度的乘积(表示为 O(s))的乘积:O(T)=R ∗ O(s)。O(n + m),其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空),函数 mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(n + m)。

空间复杂度:O(n + m),其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n + m 次,因此空间复杂度为 O(n + m)。

25. K 个一组翻转链表

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

进阶:

你可以设计一个只使用常数额外空间的算法来解决此问题吗?
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:
在这里插入图片描述输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例2:
在这里插入图片描述
输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

示例 3:
输入:head = [1,2,3,4,5], k = 1
输出:[1,2,3,4,5]

示例 4:
输入:head = [1], k = 1
输出:[1]

大致过程可以分解为
1、找到待翻转的k个节点(注意:若剩余数量小于 k 的话,则不需要反转,因此直接返回待翻转部分的头结点即可)。
2、对其进行翻转。并返回翻转后的头结点(注意:翻转为左闭又开区间,所以本轮操作的尾结点其实就是下一轮操作的头结点)。
3、对下一轮 k 个节点也进行翻转操作。
4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点,即将每一轮翻转的k的节点连接起来。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    //左闭右开区间
    ListNode* reverse(ListNode* head, ListNode* tail){
        ListNode* pre = NULL;
        ListNode* next = NULL;
        while(head != tail){
            next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* tail = head;
        for(int i = 0; i < k; i++){
            //剩余数量小于k的话,则不需要反转
            if(tail == NULL)  return head;
            tail = tail->next;
        }

        //反转前k个元素
        ListNode* newHead = reverse(head, tail);
        head->next = reverseKGroup(tail, k);

        return newHead;

    }
};

206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:
在这里插入图片描述
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例2:
输入:head = []
输出:[]

方法一:迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* curr = head;
        while(curr){
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

复杂度分析
时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。
空间复杂度:O(1)。

方法二:
@老汤
为什么可以使用递归?因为符合递归的三个条件:
1.大问题拆成两个子问题
2.子问题求解方式和大问题一样
3.存在最小子问题
在这里插入图片描述
在这里插入图片描述
发生在递归调用前面的是递的时候要做的事情,发生在递归调用后面的是归的时候要做的事情。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        //上面是递的部分
        ListNode* ans = reverseList(head->next);//调用递归函数
        //下面是归的部分
        head->next->next = head;
        head->next = NULL;
        return ans;
    }
};
这篇关于每日刷题计划Day12-递归+树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!