Welcome to LeaCoder's Blog!
持之以恒终有收获，自律自强方至成功-
LeetCode-235--二叉搜索树的最近公共祖先(Lowest-Common-Ancestor-of-a-Binary-Search-Tree
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。
Python3实现
递归
#@author:leacoder #@des: 递归, 二叉搜索树的最近公共祖先 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if p.val<root.val and q.val<root.val: #如果 p q 的值都是小于root的值 那么 需要在二叉搜索树 左子树中找 return self.lowestCommonAncestor(root.left,p,q) if p.val>root.val and q.val>root.val: #如果 p q 的值都是大于root的值 那么 需要在二叉搜索树 右子树中找 return self.lowestCommonAncestor(root.right,p,q) return root #其他情况 一个比root 大 一个比root小 那么 root必然为其公共祖先循环
#@author:leacoder #@des: 循环, 二叉搜索树的最近公共祖先 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': while root: if p.val<root.val and q.val<root.val: #如果 p q 的值都是小于root的值 那么公共祖先必在其左子树中 root = root.left elif p.val>root.val and q.val>root.val: #如果 p q 的值都是大于root的值 那么公共祖先必在其右子树中 root = root.right else: return root
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
-
LeetCode-206--反转链表(Reverse-Linked-List)
#反转一个单链表
LeetCode 206. 反转链表(Reverse Linked List)
示例:
输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL
C++实现
1、迭代实现 C++
反转链表(Reverse Linked List)C++迭代实现
/** * @author:leacoder * @des: 迭代实现 反转链表 */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* cur = head; //当前指针节点 ListNode* prev = NULL; //前指针节点 ListNode* temp = NULL; //临时节点 while(NULL!=cur){ temp = cur->next; //临时节点，暂存当前节点的下一节点(断开处的节点)，用于后移 cur->next = prev; //将当前节点指向它前面的节点 prev = cur; //前指针后移 cur = temp; //当前指针后移 } return prev; } };2、递归实现 C++
反转链表(Reverse Linked List)C++递归实现
/** * @author:leacoder * @des: 递归实现 反转链表 */ class Solution { public: ListNode* reverseList(ListNode* head) { //第一个条件是判断递归开始，传入的参数的合法性。第二个是递归的终止条件 if (NULL==head || NULL==head->next) return head; ListNode* result = reverseList(head->next); // 循环递归找到最后一个节点 (head->next为最后一节点） 那么 result指向最后节点 以【A B C D】为例 指向 D head->next->next = head;//以【A B C D】为例 最底部到达此处时 head 为 C ,head->next 为 D ，反转为 head->next->next 为 C (head) head->next = NULL; //以【A B C D】为例 断开 C D 之间连接 C 的 next 指向 NULL，即为 head->next = NULL 如果不断掉 C D成环 递归无法终止 return result; } };递归实现注意传入的参数的合法性以及递归的终止条件终止条件的判断，特别注意 最后
head->next = NULL置空不然链表成环
Java实现
Java实现逻辑上与C++无区别
1、迭代实现 Java
反转链表(Reverse Linked List) JAVA 迭代实现
2、递归实现 Java
反转链表(Reverse Linked List) JAVA 递归实现
Python3 实现
反转链表(Reverse Linked List) Py3 迭代实现
# @author:leacoder # @des: 迭代实现 反转链表 class Solution: def reverseList(self, head: ListNode) -> ListNode: cur = head prev = None while cur: cur.next,prev,cur = prev,cur,cur.next #多元赋值 return prev实现逻辑 与 C++、Java 无差别，但是采用了一种赋值机制即多元赋值 采用这种方式赋值时，等号两边的对象都是元组并且元组的小括号是可选的。通常形式为
x, y = 1,'a string' 等同于(x, y) = (1,'a string') 这种赋值类型最经常用到的环境是变量交换，形如 x, y = y, x 这种交换方式无需中间变量即可交换两个变量的值x = 123 y = 'a string' print(x,y) x, y = y, x print(x,y) 输出结果： 123 a string a string 123
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
-
LeetCode-141--环形链表(Linked-List-Cycle)
环形链表
环形链表(Linked List Cycle) 给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数
pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是-1，则在该链表中没有环。示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 </pre>
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
有两种解题思路：
1、存储记录，遍历链表与存储记录进行比较，如果不存在这将其记录下来，如果存在那么链表成环
2、快慢指针，两个指针循环遍历链表，慢指针每次循环移一步快指针每次循环移两步，如果链表遍历结束之前存在快慢指针指向同一节点则链表成环Python3 实现
1、存储记录 实现 Py3
环形链表(Linked List Cycle) Py3 存储记录 实现
# @author:leacoder # @des: 存储记录 环形链表 class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ save = set() #用于 存储 链表中每个节点地址 cur = head while cur is not None: #循环迭代链表 if cur in save: #是否有记录 return True #有返回True else: save.add(cur) #存储记录cur cur = cur.next #下移 return False2、快慢指针 实现 Py3
环形链表(Linked List Cycle) Py3 快慢指针 实现
# @author:leacoder # @des: 快慢指针 环形链表 class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ fast = slow = head while slow and fast and fast.next: slow = slow.next #慢指针 每次移一步 fast = fast.next.next #快指针 每次移二步 if slow == fast: return True return FalseJava实现
Java实现逻辑上与Python3无区别
1、存储记录 实现 Java
环形链表(Linked List Cycle) Java 存储记录 实现
2、快慢指针 实现 Java
环形链表(Linked List Cycle) Java 快慢指针 实现
C++实现
环形链表(Linked List Cycle) C++ 快慢指针 实现
扩展阅读：
Java HashSet api doc from oracle
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习