jicahoo/pythonalgr

learn algorithm using python

pythonalgr

Learn algorithm using python on leetcode.

94. Binary Tree In Order Traversal

今天, 在脑海里, 总结了一下三种二叉树遍历的迭代实现方式, 有一些感悟:

1. 先序的迭代实现是最简单的, 因为你只需要访问根节点一次, 访问之后, 就可以从栈中丢弃, 放入子树的节点, 就可以完成后续的工作.
2. 中序遍历的迭代实现, 核心操作, POP时,如果有右孩子, 把右孩子的最左一串入栈. 出栈的是, 这个节点的相对角色是个root节点. 所以 出栈时, 左子树已遍历完毕, 然后, root出栈, 再将右子树遍历. 次栈顶元素是刚POP出的元素的父节点, 关系反过来, POP出元素是次栈顶元素的左孩子, 逻辑以和上面的 'root出栈时, 它的左子树以遍历完毕'形成完备的逻辑和算法流程.
3. 注意栈中相邻节点的逻辑关系, 在中序遍历中, 相邻节点是左孩子和父节点的关系, 父节点更靠栈底, 或者是 父节点的左孩子的右子树的某些节点与父节点的关系. 有助于理解算法.
4. 迭代中, 仍有递归的**. 要以子树作为一个整体去构造算法和理解算法. 而不仅仅是, 左孩子, 右孩子。要理解为左子树, 右子树.
5. 后序遍历, 要走根节点两次, 复杂些. 父节点是从左节点到右节点的桥梁, 因为是后续, 所以要保存父节点, 走完左子树, 从父节点, 找到右子树啊, 再回到父节点.
6. 在中序遍历和后续遍历中, 最左串是算法的脉络或者二叉树的脉络.

136. Single Number

• Just use xor.
• xor operation has below mathematical property: 0 xor n = n; n xor n = 0; n xor m = m xor n. You can easily prove that below solution is correct.

return reduce(lambda x, y : x ^ y, numbers, 0);

144. Binary Tree Preorder Traveral. 二叉树先序遍历

• 算法复杂度是怎样的?

145. Binary Tree Postorder Traversal. 二叉树后序遍历

• 经过不懈努力, 写出了一个简洁版本. 如果你的代码看着有重复的地方, 重复的逻辑, 重复的循环, 总有奇奇怪怪的变量, 你总是可以去除它.
• 我写的解法的结构和94题的二叉树中序遍历是一模一样的. 其实是受了94题的解法的启发, while循环担任了两层循环职责. 一个是驱动整体逻辑, 一个是驱动不断地POP栈顶元素.
• 在遍历树的节点的时候, 你要不断地改变自己的参照系. 在不同的步骤中, 你可能会选择不同的节点作为所谓的当前的根节点, 以选中的根节点, 思考如何进行 下一步操作, 所以, 你要足够小心, 不要把这个参照系, 在不断的变换中, 弄混了.

146. LRU Cache

• Result: Beat 43%. Time: O(1), Space: O(n). Time spent: 4 hours.
• Not easy to operate the pointers in the doubly linked list correctly. Need to be very carefully.
• Many internal structure and variable for maintaining a O(1) LRU cache. Need to update them carefully.

155. Min Stack

• The simple and straightforward way may be the fast one.
• Use MaxHeap structure is not good choice, comparing the simple solution. The simpe solution beats 60%, the bad one beats only <10%.

227. Basic Calculator II

• Result: Beat 63%. Time: O(n), Space: O(n)
• Think about how do you calculate + - * /
• String basic paring method: regex, split, strip, then process tokens as list. Just string -> split -> list -> process linearly.
• We can handle them linearly, since it is simple string without '(' or negative number. How to handle more complex expression?
• More better way?

241. Different ways to add parentheses.

• TODO

338. Count Bits

• Result: Best score 95% Time:O(n) Space: O(n)
• Question Tag: DP, Bit Operation.
• The mechanism of binary digits: try to get the DP formula:
• number_of_bits(n) = number_of_bits(n/2) if n is even;
• number_of_bits(n) = number_of_bits(n/2) + 1 if n is odd.
• number_of_bits(0) = 0.
• Learned: the step in DP may not be n -> n + 1. In this question, the step in DP is n/2 -> n. Generally, f(n) = DP(m). 1 < m < n.

385. Mini Parser

• How to find the list's elements? You have to find the comma in the first level.
• How to determine the first level? Use stack (which is tracking the pair of "[" and "]") to determine if current comma is in the first level.

387. First unique character in a string.

• Score: 80%. Time: O(n) Space: O(n).
• Note: Not store useless info. Just store the index of char if there is no dup currently. If found dup, just set -1.

383. Ransom Note [TODO]

• Just follow the most natural way. Time complexity: m+n+n. Space complexity: 26*size( store "letter":[count_a,count_b] )
• Try to write code directly. Ran into several issues: alogrithm is not right (since not use pseudo code and prove its correct), not familiar with Pythons's list index operation.
• Try to avoid m*n time complexity.
• Now time complexity: nlogn+mlogm+m*n, it seems that I failed on my goal. Space complexity: if sorted is in-place, it should be O(1)
• TODO: Like a sub-set check of set with duplicate elements or common sub-string check problem; Another possible better way is to use Hash. From problem itself, we don't need sort. It's more about set operation.
• I learned to use assert of Python to run my test case.
• I didn't think out complete & useful test cases, just hurried up to submit my code.
• Two things I got: Think clear about the algorithm: pseudo code prove and complete test case. Maybe 80% is on it, 20% to write code. Try to stick to it.

421. Max XOR value in array.

• Current result beats 7% in python. More details, see the comments of code.

422. Find duplicates (twice) in array.

• Beats 72%. Time: O(n), Space: O(1).
• Solution: Leverage mod operation.
• What I learned: read question carefully, especially the key condition: 1 <= a[i] <= n and repeats twice

Java程序员问Python程序员

• Python程序执行入口是什么? Java中是main函数。
• Python的模块是什么时候，如何加载的？ Java中，是懒加载类的，运行时，用到了某个class, 就加载那个class
• Python的字符串长什么样子，是什么编码的？ Java的String是UTF-16的
• Java中的byte code 和 Python的pyc可以对应起来吗? pyc的作用是什么？
• Java有CLASSPath的概念， Python对应的概念是什么？ Python执行的实行是从何处查找依赖的包的？
• Java需要Getter/Setter, Python怎样弄?
• Java有静态成员, Python有吗？
• Java有不同的访问修饰符: private, protected, public. Python对应的东西是什么? Python是如何做到模块级别，类级别的封装的？