赣南脐橙网络营销策划书_为企业做贡献的句子_seo网站快排_友情链接方面

题目1：汉诺塔

面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）

解题思路：

递归的函数头dfs(A,B,C,n)：ABC是三个柱子，n表示盘子个数，函数表示的含义是：A上的n个盘子，借助B转移到C上

函数体：1.把A上的n-1个盘子,借助C转移到B，2.A上的最后一个盘子移动到C，3.把B上的n-1个盘子借助A移动到C

递归出口：只有一个盘子的时候，直接把盘子转移到C上

class Solution {public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {dfs(A, B, C, A.size());}public void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int n) {if (n == 1) {// 把A中的一个元素删除,转移到CC.add(A.remove(A.size() - 1));return;}// 1.把A上的n-1个盘子,借助C转移到Bdfs(A, C, B, n - 1);// 2.A上的最后一个盘子移动到CC.add(A.remove(A.size() - 1));// 3.把B上的n-1个盘子借助A移动到Cdfs(B, A, C, n - 1);}
}

题目2：合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

思路：

函数头设计：给你两个链表，返回两个链表合并后的链表

函数体：比较两个链表头结点的大小，让值较小的那个链表，头结点之后的部分与另一个链表进行合并

递归出口：如果链表1为空，返回链表2；如果链表2为空，返回链表1

代码实现：

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) {return list2;}if (list2 == null) {return list1;}// 1.比大小if (list1.val < list2.val) {list1.next = mergeTwoLists(list1.next, list2);return list1;} else {list2.next = mergeTwoLists(list2.next, list1);return list2;}}
}

题目3：反转链表

206. 反转链表 - 力扣（LeetCode）

思路：

先反转head后面的结点，反转后调整结构

函数头：给你一个链表，返回链表反转之后的链表

函数体：先反转头结点后面的链表，然后头结点和得到的链表进行连接，调整链表的结构

递归出口：如果链表为空，或者只有一个结点，直接返回head

class Solution {public ListNode reverseList(ListNode head) {// 边界情况if (head == null || head.next == null) {return head;}// 1.先反转后面的结点ListNode newHead = reverseList(head.next);// 2.调整结构head.next.next = head;head.next = null;return newHead;}
}

题目4：两两交换链表中的结点

24. 两两交换链表中的节点 - 力扣（LeetCode）

思路：

函数头：给你一个链表，两两交换相邻的两个结点，返回交换后的链表

函数体：先不交换前面两个结点，先交换除了前面两个结点的后面的链表，得到后面交换好的链表后，交换前两个结点，然后连接链表

递归出口：结点为空，或者只有一个结点，不交换

代码实现：

class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}ListNode ret = swapPairs(head.next.next);ListNode nextNode = head.next;head.next = ret;nextNode.next = head;head = nextNode;return head;}
}

题目5：Pow(x,n)

50. Pow(x, n) - 力扣（LeetCode）

快速幂算法：快速求出x的n次幂

原理：

函数头：给你x和n，返回x的n次幂

函数体：先求出x的二分之n次幂，求得的结果ret，返回ret*ret，如果n是奇数，需要

递归出口：当n==0时，返回1

代码实现：

注意细节：当n小于0，返回的是 1/ x的-n次幂，为了防止溢出，需要把n转换为long类型

class Solution {public double myPow(double x, int n) {if (n < 0) {return 1.0 / pow(x, -(long)n);}return pow(x, (long) n);}public double pow(double x, long n) {if (n == 0) {return 1.0;}double ret = pow(x, n / 2);if (n % 2 == 1) {return ret * ret * x;}return ret * ret;}
}