class Test(): def heap_sort(self, nums): i, l = 0, len(nums) self.nums = nums # 构造大顶堆，从非叶子节点开始倒序遍历，因此是l//2 -1 就是最后一个非叶子节点 for i in range(l//2-1, -1, -1): self.build_heap(i, l-1) print(nums) # 上面的循环完成了大顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆 for j in range(l-1, -1, -1): nums, nums[j] = nums[j], nums self.build_heap(0, j-1) return nums def build_heap(self, i, l): """构建大顶堆""" nums = self.nums left, right = 2*i+1, 2*i+2 ## 左右子节点的下标 large_index = i if left <= l and nums[i] < nums[left]: large_index = left if right <= l and nums[left] < nums[right]: large_index = right # 通过上面跟左右节点比较后，得出三个元素之间较大的下标，如果较大下表不是父节点的下标，说明交换后需要重新调整大顶堆 if large_index != i: nums[i], nums[large_index] = nums[large_index], nums[i] self.build_heap(large_index, l)
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
This problem is an easy-level at Leetcode. I probably did it more than five times, once and once again. Just like a muscle memory.
However, I found an interesting solution today, which literally changed my mind about Python…
Here is the code:
# 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 Solution: def isBalanced(self, root: TreeNode, h = 1) -> bool: if not root: return h l = self.isBalanced(root.left, h + 1) r = self.isBalanced(root.right, h + 1) return abs(l - r) <= 1 and max(l, r)
I am very confused at the last line, the max(l, r) part.
I thought that max(l, r) should be converted as a bool value even it returns a integer type value, because as the second component of the operation AND, max(l, r) should represent as a bool variable.
Following by my worst idea, I supposed that the function isBalanced would return either 1 (True) or 0 (False). However, I found a crazy truth after experiments, that Python executor actually return a integer value (the maximum value of l and r) if abs(l – r) <= 1 is matched.
So, it really makes sense. Gain new knowledge of Python 🙂
There are two methods to calculate the median of an interval [low, high].
- m = ( l + h ) / 2
- m = l + ( h – l ) / 2
l + h may have addition overflow, but h-l will not. Therefore, it is best to use the second method of calculation.
This week, I welcomed a new apartment-mate, who was a brilliant theoretical physicist/ Product Manager/ Programmer/etc. In one word, he is amazing!
After a cheerful chat with him, I got known that he has extremely abundant experience spans many fields. He was used to be a postgraduate student at UCAS majored in theoretical physics, and RA at sustech, and be PM at MeiTuan (A Chinese take-away services pioneer), and be visit student at MPI.
And, you can’t imagine that, he is a very good programmer at BtyeDance currently XD.
Back to our points, I’d grasp this opportunity to learn some very fundamental knowledge about Quantum Computing. Speaking of which, I really wanna figure out the Shor’s Algorithm.
The most important concept of the Shor’s Algorithm should be how to find the period, in which we can take advantages of Quantum Computing.
Fine, my mentor calls me back… I will do this article lately. STAY TUNED!
Recently my task is refactoring some code to a new engine, and my OKR is guaranteeing the identical results with the old one, the entire process is just like bug-oriented programming…
In general neural networks have a sort of loss like that:
However, The part of the denominator integral is intractable of finding an analytic solution solution in practice. Therefore, we are going to make a distribution approaching the original distribution. KL divergence can be used to indicate the difference between these two distributions.
Great appreciate GFW (National Firewall) lifted me out!!! XD
How highly productive I am…
I just recently completed this post on an online Latex editor, that has a really impressive AI inference formula system. It is pretty good except that I don’t know how to elegantly export content as SVG~
Recently, I found that my lovely website server got busted by Chinese National Firewall (aka. GFW), Maybe because of the ShadowSocks proxy running on this server. I tried to snapshot this server to other servers a couple of times, but the visit speed was really sick. I suppose it related with my domestic DNS binding.
Due to the epidemic outbreak, I am impressively working from home for almost three month. Although I still need to work, but you know at home, I can spend more time on my personal interestings, like machine learning, music and reading. (Hope my mentor will never find this article out)
Attached is a probably boring illustration about transformer architecture. Almost every BERT-ish paper would like to describe it with a bunch of paragraphs. Ironically, I have never carefully looked through this structure. So today I eventually decided to dive deeply into this structure in a precious weekend afternoon.