on June 5, 2015
Read most popular leetcode blogs:
Tuesday, June 9, 2015
Leetcode: Interleave string
on June 5 - 6 , 2015
In my preference order, read those websites, and then, figure out ways to improve my understanding the problem.
Leetcode: scramble string
Here is the coding blog about the algorithm with a few solutions.
非常喜欢这道题目, 希望从中体会到开发高难度的项目的挑战性; 纸上谈兵, 学习, 训练; 把C# 代码写一写. 一直在想递归算法的时间复杂度, 是N的六次方.
C# practice is here.
July 9, 2015 ( 2nd round study )
Totally forget what the problem is about. And by mistake I guessed that scramble strings is all permutations of string (n!), actually it is O(3^n).
Read the blog, the link is here.
plan to add the recursive solution plus memorization using C#.
Leetcode: Divide Two Integers
June 4, 2015
this website provided a very clear explanation using math formula. Great explanation:
C# code:
/*
* first time using uint in C# - June 4, 2015
* The sbyte data type is an 8-bit signed integer.
The byte data type is an 8-bit unsigned integer.
The short data type is a 16-bit signed integer.
The ushort is a 16-bit unsigned integer.
The int data type is a 32-bit signed integer.
The uint is a 32-bit unsigned integer.
The long data type is a 64-bit signed integer.
The ulong is a 64-bit unsigned integer.
The char data type is a Unicode character (16 bits).
The float data type is a single-precision floating point.
The double data type is a double-precision floating point.
The bool data type is a Boolean (true or false).
The decimal data type is a decimal type with 28 significant digits (typically used for financial purposes).
* first time using uint in C# - June 4, 2015
* The sbyte data type is an 8-bit signed integer.
The byte data type is an 8-bit unsigned integer.
The short data type is a 16-bit signed integer.
The ushort is a 16-bit unsigned integer.
The int data type is a 32-bit signed integer.
The uint is a 32-bit unsigned integer.
The long data type is a 64-bit signed integer.
The ulong is a 64-bit unsigned integer.
The char data type is a Unicode character (16 bits).
The float data type is a single-precision floating point.
The double data type is a double-precision floating point.
The bool data type is a Boolean (true or false).
The decimal data type is a decimal type with 28 significant digits (typically used for financial purposes).
*/
static int divide3( int dividend, int divisor) {
int result = 0;
bool sign = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
static int divide3( int dividend, int divisor) {
int result = 0;
bool sign = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
uint a = (uint)(dividend >= 0 ? dividend : -dividend);
uint b = (uint)(divisor >= 0 ? divisor : -divisor);
uint b = (uint)(divisor >= 0 ? divisor : -divisor);
/*
* Try to figure out what we are doing in loops:
*
*/
while (a >= b) {
int multi = 1;
uint bb = b;
* Try to figure out what we are doing in loops:
*
*/
while (a >= b) {
int multi = 1;
uint bb = b;
while (a >= bb) {
a -= bb;
result += multi;
if (bb < int.MaxValue >> 1)
{
bb += bb;
multi += multi;
}
}
}
a -= bb;
result += multi;
if (bb < int.MaxValue >> 1)
{
bb += bb;
multi += multi;
}
}
}
if (sign) return -result;
else return result;
}
else return result;
}
Algorithm study
May 31, 2015
Spent two hours to read the webpage:
watch the video:
Start to practice coding and share it on github, first thing to write is about binary tree:
Binary tree maximum distance, diameter of binary tree
May 29, 2015
Diameter of binary tree: The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.
Read two websites:
copy Java code solution from the website:
http://blog.csdn.net/fightforyourdream/article/details/16843303
- /**
- * 求二叉树中节点的最大距离 即二叉树中相距最远的两个节点之间的距离。 (distance / diameter)
- * 递归解法：
- * （1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0
- * （2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离，
- * 要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离，
- * 同时记录左子树和右子树节点中到根节点的最大距离。
- *
- * http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html
- *
- * 计算一个二叉树的最大距离有两个情况:
- 情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
- 情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
- 只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离
- */
- public static Result getMaxDistanceRec(TreeNode root){
- if(root == null){
- Result empty = new Result(0, -1); // 目的是让调用方 +1 后，把当前的不存在的 (NULL) 子树当成最大深度为 0
- return empty;
- }
- // 计算出左右子树分别最大距离
- Result lmd = getMaxDistanceRec(root.left);
- Result rmd = getMaxDistanceRec(root.right);
- Result res = new Result();
- res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) + 1; // 当前最大深度
- // 取情况A和情况B中较大值
- res.maxDistance = Math.max( lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance) );
- return res;
- }
- private static class Result{
- int maxDistance;
- int maxDepth;
- public Result() {
- }
- public Result(int maxDistance, int maxDepth) {
- this.maxDistance = maxDistance;
- this.maxDepth = maxDepth;
- }
- }
binary tree algorithms
学习算法, 我还是很幼稚; 从紧张, 到慌乱, 体会很多. 最大体会是时间是宝贵的资源, 每天没有机会写代码, 就可以多读一些代码. 三四个月前, 有时, 一道题目折腾一天, 一个周末只有二天. 现在, 情况改善, 可以集中把十几道题目一起阅读, 思考. 有时间, 再把C#的代码写出来, 开通Github, 把代码放上去.
我喜欢几个博客:
链表
二分查找，你真的掌握了吗？
Binary tree algorithms
May 28, 2015
To expand my knowledge, challenge my understand of binary tree, read through over 1000 lines Java code, and then, memorize all the algorithms. 非常幸运, 可以阅读这上千行的代码, 理解, 并记忆这些二插树的算法. 花几个小时, 读一读; 思考思考, 对不常写算法的我, 是一个崭新的开始.
最喜欢, 也是第一次阅读, 理解的算法:
- 递归转换BST为双向链表(DLL)
- 分层遍历二叉树（递归）
- 后序遍历迭代解法
- 求二叉树的深度（高度） 迭代解法： O(n) ( 基本思想同LevelOrderTraversal，还是用一个Queue )
- 将二叉查找树变为有序的双向链表 迭代解法 ( 类似inorder traversal的做法 )
Leetcode: Post order binary tree traversal iteratively
May 28, 2015
Problem statement:
Given a binary tree,
return the postorder traversal of its nodes’ values.
For example: Given
binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you
do it iteratively?
May 27, 2015
这道题看了题解, 才知道问题解决很有难度; 我还没有想过, 估计想也想不清楚; 现在还是第一次接触这题目, 所以, 先阅读, 花半个小时.
认真看看EMC软件工程师的代码, 学习做事的认真的态度.
有机会, 我用C#把代码写一遍, 提高自己的编程能力.
求平方根:
LeetCode
/ LintCode 答案查询
July 7 2015
Share C# code:
Morris inorder traversal - binary tree
May 26, 2015
Problem Statement:
Print inorder traversal of the tree without
using extra space (Morris Traversal)
Study two websites:
Implement the code using C#, and use the same
example in the above website.
Here is the short description to understand
the algorithm:
Concept
Involved:
Morris traversal is an implementation of
in-order traversal that uses threading:
1.
Create links to the
in-order successor
2.
Print the data using
these links
3.
Revert the changes to
restore original tree.
Here is the C# code:
read the blog (July 9, 2015):
Leetcode: Binary tree preorder traversal
Note: Recursive solution is trivial, could you do it iteratively?
May 26, 2015 - Read the website:
Read the leetcode solution in C++ first:
class Solution {
public:
vector preorderTraversal(TreeNode *root) {
vector result;
const TreeNode *p;
stack s;
p = root;
if (p != nullptr) s.push(p);
while (!s.empty()) {
p = s.top();
s.pop();
result.push_back(p->val);
if (p->right != nullptr) s.push(p->right);
if (p->left != nullptr) s.push(p->left);
}
return result;
}
};
class Solution {
public:
vector preorderTraversal(TreeNode *root) {
vector result;
const TreeNode *p;
stack s;
p = root;
if (p != nullptr) s.push(p);
while (!s.empty()) {
p = s.top();
s.pop();
result.push_back(p->val);
if (p->right != nullptr) s.push(p->right);
if (p->left != nullptr) s.push(p->left);
}
return result;
}
};
Here is the C# code:
Morris preorder:
original paper (read it if I need to challenge my understanding)
The explanation in the following blog is more clear compared to Leetcode solution.
Here is the pseudo code:
preorder(node) if node == null then return visit(node) preorder(node.left) preorder(node.right)
这道题有意思, 考虑到自己很少用栈, 应该好好练习写代码.
iterativePreorder(node)
parentStack = empty stack
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
visit(node)
if (node.right ≠ null) parentStack.push(node.right)
node = node.left
else
node = parentStack.pop()
Leetcode video time
May 24, 2015
Spent time to watch the video about stack. Very good video. on May 24, 2015
There is a lecture to explain the question to find last k number maximum number.
Look up Catalan combination problem.
Leetcode解题经历
最近二周上班工作太忙, 下班打网球; 前一阵下班做题, 比较有挫折感, 体重上升; 上楼梯吃力. 所以, 上周尝试下班不看代码, 早睡早起. 周六重新开始, 学习写代码.
看几个录像, 由于网速问题, 看了几个. 但是, 觉得非常有帮助.
May 23, 2015
特别喜欢这个讲座, Leetcode question 3 也是与字符串相关的.
Recently, I was too busy at work, and go to play tennis after work; I did not have chance to review Leetcode questions, felt frustrated, and my body weight goes up; difficult to climb stairs from first floor to 3rd floor. So, back to normal, go to bed early and then get up early. Now, it is the time to start to work on, and learn more things about coding.
My favorite video is to talk about string manipulation. 看看自己用中文认真学习算法, 会不会提高自己的自信心. 下面是笔记:
总结: 单词翻转, in-place O(1) space, 原地
本身O(1)空间
递归, 堆栈空间可以不计算
原地相关的问题:
字符川循环左移, 右移动
快排partition相关
滑动窗口
能达到O(n)时间的复杂度
O(1)的空间复杂度
规则相关
匹配(暴力): KMP比较少见
Manacher - 要求比较高的笔试
Leetcode: strstr function
problem statement:
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
May 17, 11:30pm
特别喜欢字符串操作题目.
Leetcode 4: Median of two sorted arrays
Problem statement: There are two sorted arrays A and B
of size m and n respectively. Find the median of the two sorted arrays. The
overall run time complexity should be O(log(m+n)).
May 17, 2015
这道题我想了好几个小时, 读了题解, 没有读明白．直到我读了Leetcode的题解, 总算读懂了题目的分析．让我感叹计算机科学的奇妙．有大学学数学分析的感觉．
下面是题解分析:
这是一道非常经典的题。这题更通用的形式是，给定两个已经排序好的数组，找到两者所有元
素中第k 大的元素。
1. O(m + n) 的解法比较直观，直接merge 两个数组，然后求第k 大的元素。
2. O(k)时间，O(1) 空间; 但是，当k 很接近m + n 的时候，这个方法还是O(m + n) 的。
不过我们仅仅需要第k 大的元素，是不需要“排序”这么复杂的操作的。可以用一个计数器，
记录当前已经找到第m 大的元素了。同时我们使用两个指针pA 和pB，分别指向A 和B 数组的第
一个元素，使用类似于merge sort 的原理，如果数组A 当前元素小，那么pA++，同时m++；如果
数组B 当前元素小，那么pB++，同时m++。最终当m 等于k 的时候，就得到了我们的答案，O(k)
时间，O(1) 空间。但是，当k 很接近m + n 的时候，这个方法还是O(m + n) 的。
3. 更好的方案
有没有更好的方案呢？我们可以考虑从k 入手。如果我们每次都能够删除一个一定在第k 大元
素之前的元素，那么我们需要进行k 次。但是如果每次我们都删除一半呢？由于A 和B 都是有序
的，我们应该充分利用这里面的信息，类似于二分查找，也是充分利用了“有序”。
假设A 和B 的元素个数都大于k/2，我们将A 的第k/2 个元素（即A[k/2-1]）和B 的第k/2
个元素（即B[k/2-1]）进行比较，有以下三种情况（为了简化这里先假设k 为偶数，所得到的结
论对于k 是奇数也是成立的）：
• A[k/2-1] == B[k/2-1]
• A[k/2-1] > B[k/2-1]
• A[k/2-1] < B[k/2-1]
如果A[k/2-1] < B[k/2-1]，意味着A[0] 到A[k/2-1] 的肯定在A [B] 的top k 元素的范围 内，换句话说，A[k/2-1 不可能大于A [ B 的第k 大元素。留给读者证明。 因此，我们可以放心的删除A 数组的这k/2 个元素。同理，当A[k/2-1] > B[k/2-1] 时，可以删除B 数组的k/2 个元素。
当A[k/2-1] == B[k/2-1] 时，说明找到了第k 大的元素，直接返回A[k/2-1] 或B[k/2-1] 即可。
因此，我们可以写一个递归函数。那么函数什么时候应该终止呢？
当A 或B 是空时，直接返回B[k-1] 或A[k-1]；
• 当k=1 是，返回min(A[0], B[0])；
• 当A[k/2-1] == B[k/2-1] 时，返回A[k/2-1] 或B[k/2-1]
－－
Read some blogs:
Practice code sharing: C# code:
2017 January 5,
Rewrite C# program for each time complexity:
O(m+n)
O(k)
O(log(m + n)
Post 3 code review on stackexchange.com code review.
Subscribe to:
Posts (Atom)