链表转换为二叉排序树、反应式编程 RxSwift 和 RxCocoa 、区块链 hyperledger 环境搭建、环境架构、John 易筋 ARTS 打卡 Week 20

用户头像
John(易筋)
关注
发布于: 2020 年 10 月 04 日

1. Algorithm: 每周至少做一个 LeetCode 的算法题

笔者的文章:



算法:把排好序的链表转换为二叉排序树Convert Sorted List to Binary Search Tree

题目

109. Convert Sorted List to Binary Search Tree



Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.



For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.



Example 1:



Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]



Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:



Input: head = []
Output: []



Example 3:



Input: head = [0]
Output: [0]



Example 4:



Input: head = [1,3]
Output: [3,1]



Constraints:

  • The number of nodes in head is in the range [0, 2 * 10^4].

  • -10^5 <= Node.val <= 10^5



解法一:转为数组后,根据数组序号二分组装成二叉排序树

思路:

因为树有左右分叉,用递归解法。

  1. 把链表的值,组装成数组;

  2. 根据数组的索引,递归调用组装成二叉排序树



# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ConvertSortedListToBinarySearchTree:
# Convert the given linked list to an arry
def mapListToValues(self, head: ListNode):
vals = []
while head:
vals.append(head.val)
head = head.next
return vals
def sortedListToBST(self, head: ListNode) -> TreeNode:
# check edge
if head == None :
return None
if head.next == None:
return TreeNode(head.val)
# Form an array out of the given linked list and then
# use the array to form the BST
values = self.mapListToValues(head)
# l and r represent the start and end of the given array
def convertListToBST(l, r):
# Invalid case
if l > r:
return None
# Middle element forms the root.
mid = (l + r) // 2
node = TreeNode(values[mid])
# Baes case for when there is only one element left in the array
if l == r:
return node
# Recursively fom BST on the two halves
node.left = convertListToBST(l, mid - 1)
node.right = convertListToBST(mid + 1, r)
return node
return convertListToBST(0, len(values) - 1)
````
# 解法二:找链表中的中间节点,组装成二叉排序树
组装树的方法是用递归,如果能持续找到中间节点,就可以持续组装树的middle, middle.left, middle.right.
找中间节点的方法,用快慢两个指针,慢指针每次走一步,快指针每次走两步;这样子就可以找出中间节点。
```py
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ConvertSortedListToBinarySearchTree:
def findMiddle(self, head: ListNode):
# The pointer used to disconnect the left half from the mid node.
preNode = None
slowNode = head
fastNode = head
# Iterate until fastNode doesn't reach the end of the linked list.
while fastNode and fastNode.next:
preNode = slowNode
slowNode = slowNode.next
fastNode = fastNode.next.next
# Handling the case when slowNode was equal to head
if preNode:
preNode.next = None
return slowNode
def sortedListToBST2(self, head: ListNode):
# If the head doesn't exist, then the linked list is empty
if not head:
return None
# Find the middle element for the list
mid = self.findMiddle(head)
# the mid becones the root of the BST.
node = TreeNode(mid.val)
# Base case when there is just one element in the linked list
if head == mid:
return node
# Recursively form balanced BSTs using the left and right halves of the original list.
node.left = self.sortedListToBST2(head)
node.right = self.sortedListToBST2(mid.next)
return node



参考

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/solution/



2. Review: 阅读并点评至少一篇英文技术文章

笔者写的文章:



响应式编程或反应式编程 RxSwift和RxCocoa 从入门到精通 Reactive programming



学习并翻译下面的文章,主要是学习RxSwift和RxCocoa 响应式编程。

https://www.raywenderlich.com/1228891-getting-started-with-rxswift-and-rxcocoa



3. Tips: 学习至少一个技术技巧

笔者的文章:



如何在Mac OS X中设置文件权限chmod



Mac上的每个文件和文件夹都具有一组可配置的权限。权限控制三种访问类型:读取,写入和执行。您可以混合使用任何类型,以授予七个访问级别,如下所示。



读取,写入和执行权限重叠以创建七个八进制权限表示法。



在下一部分中,您将学习如何使用“信息”窗口来修改权限。但是要真正利用权限,您需要学习基于Unix的符号和八进制权限符号,这些符号隐藏在Mac OS X图形用户界面下。下表列出了所有可用的权限。

终端应用程序允许您使用八进制表示法来设置所有者,组和其他所有人的权限。要创建“只写”投递箱文件夹,可以将目录权限设置为622,以赋予所有者读和写权限,而组和其他所有人都只写权限。三组符号如下所示。



一般用到的修改为管理员最高权限为:

# 管理员最高权限,
$ chmod 755 *



4. Share: 分享一篇有观点和思考的技术文章

笔者写的博客链接



Mac OS 区块链hyperledger环境搭建、环境架构介绍、环境如何用、部署 Chaincode、智能合约的调用



主要讲述如何在Mac OS中搭建Hyperledger的环境,以及架构说明









发布于: 2020 年 10 月 04 日 阅读数: 21
用户头像

John(易筋)

关注

问渠那得清如许?为有源头活水来 2018.07.17 加入

工作10+年,架构师,曾经阿里巴巴资深无线开发,汇丰银行架构师/专家。开发过日活过亿的淘宝Taobao App,擅长架构、算法、数据结构、设计模式、iOS、Java Spring Boot。易筋为阿里巴巴花名。

评论

发布
暂无评论
链表转换为二叉排序树、反应式编程 RxSwift和RxCocoa 、区块链hyperledger环境搭建、环境架构、John 易筋 ARTS 打卡 Week 20