Toll Free Bridge in iOS Development

Toll Free Bridge is the channel connecting the Cocoa and CoreFoundation.
TFB是连接Cocoa和CoreFoundation的一个设计。
For example, we can use an Objc object of NSString as CFString, or reversed.
我们可以在程序中把NSString当做CFString来用,也可以把CFString当做NSString来用。
The detail is described in the article below.
下面这篇文章很详细得介绍了它。
http://www.winddisk.com/2012/08/16/toll-free-bridging/

Solve Discuz Forum Error 114: Table ‘forum_thread’ is marked as crashed and autorepair failed

Just now, I reboot the server, and after that the Discuz forum encounter an error 114 :
Table ‘forum_thread’ is marked as crashed and last (automatic) repair failed

It’s easy to solve this situation, just:

1.open the phpmyadmin
2.select the database that contain the forum
3.select the table forum_thread
4.in the sql tab, run “REPAIR TABLE ‘forum_thread'”
5.done!



Reference
http://www.acogle.cn/show_news.asp?id=473

Remove Push Notifications from Notification Center in iOS Development

If the notification is local, it’s easy by
如果是本地通知,下面的代码就解决了。

[[UIApplication sharedApplication] cancelAllLocalNotifications];

But if the notifications come from the push notification, this does’t work.
但是如果是来自于推送的话,这不管用。
After search and try, only the third method in a blog works, although it’s weird.
搜了很久发现有一个办法可以解决,虽然这个办法非常怪异。

UIApplication* application = [UIApplication sharedApplication];
NSArray* scheduledNotifications = [NSArray arrayWithArray:application.scheduledLocalNotifications];
application.scheduledLocalNotifications = scheduledNotifications;

<br>
Reference
http://josh-asch.net/2012/02/29/ios-development-remove-old-notifications-from-notification-center/

Macbook Pro Retina 黑屏

昨天开始,用着用着MBPR就黑了,然后各种折腾,按电源键,开合屏幕。之后有时候点按之后5-6s,会一闪大概2s又黑了(还是慢慢黑的),或者一亮之后就稳定不黑了。

今天写着代码,写着写着又黑了,而且怎么折腾都不亮,或者一亮又黑。随时受不了。打电话给苹果售后,然后售后说了一个方法,
1.到完全关机状态(如果不确定的话,就按着电源5s以上)
2.接上电源(后面操作估计不能断电)
3.按着左边的shift+control+option,和电源四个键5s以上,然后同时松开。这步之后电脑应该没有任何反应,还是处于关机状态。
4.在点一下电源键之后,迅速按住左边option+command和”r”,”p”,四个键不放,然后电脑会开始“咣咣咣”的响,4声之后同时松开。

也不知道管不管用,反正现在是好的。
其实是在售后问我序列号的时候,我把笔记本合上,反过来告诉他序列号,然后翻过来打开屏幕的时候,就好了。之后的操作也不知道是不是管用的。

================== 2013-1-30 更新 ===================
后来证明了3点:
1·问题依然存在
2·把笔记本翻过来一下再翻回去,问题都能解决。
3·客服人员说的方法没有用。

================== 2014-02-28 更新 ==================
终于找打了原因,其实就是MBPR以为合上了盖子,它的传感器不是传统的机械开关,而是磁性的。
前两天偶然的机会,我直接把本本放在自动麻将桌上,而且上面的铺了一层麻将(带磁性),然后放上去就黑了,拿起来就亮了。
所以总的说来,这不是问题,不过apple的客服应该知道这种可能性。

LeetCode Problem: Maximum Depth of Binary Tree

Recursively count the depth of tree node. One node’s depth is the maximum depth of it’s children’s depth + 1 or 0 if node is NULL.
递归计算就可以了,如果是空节点,深度是0,否则这个节点的子树的最大深度是其子节点最大深度 + 1。



Maximum Depth of Binary Tree Sep 30 ’12
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.



Code, 64ms pass large set

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root == NULL) return 0;
        int leftdep = maxDepth(root->left);
        int rightdep = maxDepth(root->right);
        return 1 + std::max(leftdep,rightdep);
    }
};

LeetCode Problem: Valid Palindrome

To solving this problem, using two pointer to track the characters in the string. i, from the beginning of string; j, from the back of the string.
这个问题简单,只需要收尾两个指针相向而行,比较是否相等就可以了,过程中跳过不是字母也不是数字的字符。算法如下:

while i < j do {
  1.if s[i] is not alphanumeric, moving i forward and continue
  2.if s[j] is not alphanumeric, moving j backward and condinue
  3.if s[i] != s[j] (ignoring the cases) return false.
  4.moving i forward and j backward by one step
}
return true;



Valid Palindrome Jan 13
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.



Code, 60ms pass large set

class Solution {
    inline bool isAlpha(char c) {
        if(c >= 'a' && c <= 'z') return true;
        if(c >= 'A' && c <= 'Z') return true;
        if(c >= '0' && c <= '9') return true;
        return false;
    }
    inline char lower(char c) {
        if(c >= 'A' && c <= 'Z')
            return ('a' + (c-'A'));
        return c;
    }
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = 0, j = s.size() - 1;
        while(i < j) {
            if(!isAlpha(s[i])) {
                ++i;
                continue;
            }
            if(!isAlpha(s[j])) {
                --j;
                continue;
            }
            if(lower(s[i++]) != lower(s[j--])) {
                return false;
            }
        }
        return true;
    }
};



Code rewrite at 2013-2-4

class Solution {
    bool isValidChar(char c) {
        if (c >= '0' && c <= '9')
            return true;
        if (c >= 'a' && c <= 'z')
            return true;
        if (c >= 'A' && c <= 'Z') {
            return true;
        }
        return false;
    }
    char lower(char c) {
        if (c >= 'A' && c <= 'Z') {
            return 'a' + c - 'A';
        }
    }
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s.size() <= 1) return true;
        int si=0,ei=s.size()-1;
        while(si < ei) {
            while(si < ei && !isValidChar(s[si]))
                ++si;
            while(si < ei && !isValidChar(s[ei]))
                --ei;
            if(lower(s[si]) != lower(s[ei])) {
                return false;
            }
            ++si;--ei;
        }
        return true;
    }
};



Code rewrite at 2013-03-03

class Solution {
    bool isValid(char c) {
        if (c >= '0' && c <= '9')
            return true;
        if (c >= 'a' && c <= 'z')
            return true;
        if (c >= 'A' && c <= 'Z') {
            return true;
        }
        return false;
    }
    char lower(char c) {
        if (c >= 'A' && c <= 'Z') {
            return 'a' + c - 'A';
        }
    }
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s.size() <= 1) return true;
        int si=0,ei=s.size()-1;
        while(si < ei) {
            if(!isValid(s[si])) {
                ++si;
                continue;
            }
            if(!isValid(s[ei])) {
                --ei;
                continue;
            }
            if(lower(s[si++]) != lower(s[ei--])) {
                return false;
            }
        }
        return true;
    }
};

LeetCode Problem: Pascal’s Triangle II

Follow the algorithm in LeetCode Problem: Pascal’s Triangle, we can simple return the required row from the result.
从上一个题的算法LeetCode Problem: Pascal’s Triangle,可以得到一个简单的方法就是,在上一题的基础上,最后返回需要的行即可。

But, we can optimize this to use constant extra space, even better than the required O(k) extra space in the problem description below.
题目要求最好能用O(k)的额外空间,但是我们可以做的更好,甚至只用常数的额外空间就好了。

 [1,3,3,1],
 [1,4,6,4,1]

Take the above two rows as example, we can see that, the element in the last row is only relative to the element above it and the one before the element above it. So we can generate the last row from the previous row in backward order in place.Thus, we do not need the extra spaces.
拿上面这两行为例,每一个元素其实只与它上面一个和左上那一个元素相关。也就是说,如果要生成元素的下标是i的话,它只和i和i-1相关。所以我们可以用从后往前的顺序原地生成后一行。这样就不用任何辅助空间了。



Pascal’s Triangle II Oct 29 ’12
Given an index k, return the kth row of the Pascal’s triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?



Code, 16ms pass large test set

class Solution {
public:
    vector getRow(int rowIndex) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector ret;
        if(rowIndex < 0) return ret;
        for(int ir = 0; ir <= rowIndex; ++ir) {
            //put an 1 at the end of this row
            ret.push_back(1);
            //handle the rest of elements backward
            for(int ic = ir - 1; ic > 0; --ic) {
                ret[ic] = ret[ic] + ret[ic - 1];
            }
        }
        return ret;
    }
};

LeetCode Problem: Pascal’s Triangle

The problem is simple, each element in the triangle is the sum of two numbers above it.
这个题目简单,三角形中每一个元素的值是其上面两个值的和。

So, just build the rows one by one according the row above it. And the first row is {1}.
根据当前行的上面一层数字,就可以逐行生成整个三角形了。初值是第一行:{1}



Pascal’s Triangle Oct 28 ’12
Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]



Code, 12ms pass large test set

class Solution {
public:
    vector > generate(int numRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector >ret;
        if(numRows == 0) return ret;
        //first row
        ret.push_back(vector(1,1));
        //rest rows;
        for(int nr = 2; nr <= numRows; ++nr) {
            vector thisrow(nr,1);
            vector &lastrow = ret[nr-2];
            for(int ic = 1; ic < nr - 1; ++ic) {
                thisrow[ic] = lastrow[ic-1] + lastrow[ic];
            }
            ret.push_back(thisrow);
        }
        return ret;
    }
};

当遇到了“文件目录损坏且无法读取”的时候怎么办?

今天备份文件的时候,把移动硬盘从路由器拔下来,插到台式机上,直接弹出一个对话框:
“是否需要格式化硬盘”
下面两个选项,“格式化”和“取消”,默认的还是“格式化”。
还好今天早上不是很清醒,手速较慢,没有直接回车。
(这里要鄙视一下MS,你也不尝试一下修复磁盘,你就格式化,要是上面有重要数据你让用户怎么办啊)



然后在“计算机”里面,能看到移动硬盘加载在I盘符下,但是双击会提示“文件目录损坏且无法读取”。
这个时候不要捉急,能解决的。
按下win+r,输入“cmd”,回车;
在弹出的命令行窗口中,输入“chkdsk i: /F”,然后回车。(其中i是我这次的盘符,请根据你的移动硬盘盘符进行修改)
然后就等等吧,反正我的移动硬盘在chkdsk运行完了之后就能正常访问了,里面文件什么的都好好的。



在此也提醒一下,产生这个问题的主要原因是因为没有“安全弹出”,就直接拔掉硬盘;或者是突然断电之类的情况。

Red-Balck Tree

红黑树
是一颗比较平衡的二叉搜索树,算法复杂,但是保证了各种操作最差情况下是O(logn)

定义
除了普通二叉搜索树的要求以外,还有几个其它的要求:
1·根节点是黑色的
2·不能有两个相邻的红色节点,(父子不同红色)
3·叶节点是黑色的(这里定义的叶节点是指空节点,不包含数字)
4·根节点到所有叶节点的各条路径上的黑色节点数目是相等的
5·所有节点,非红即黑

性质
最长和最短的根节点到叶节点的路径长度只差不超过2倍。
所有操作都可以在O(logn)时间内完成。

查找操作
查找操作和普通二叉搜索树是一样的

插入操作
按照普通二叉搜索树的方法,将要插入的节点插入到二叉树里面,所有的节点在插入的时候都涂成红色,然后分情况进行处理
1·如果插入的节点没有父节点(即刚插入的节点是根节点),直接涂成黑色就搞定。

void insert_case1(node n) {
     if (n->parent == NULL)
         n->color = BLACK;
     else
         insert_case2(n);
 }

2·设插入的节点的父节点为F,如果F是黑色的,就什么也不用做。

void insert_case2(node n) {
     if (n->parent->color == BLACK)
         return; /* 树仍旧有效 */
     else
         insert_case3(n);
 }

3·否则的话,F是红色,那么F不是根节点,所以F必然有父节点,设父节点的父节点是G(必然是黑色)。设父节点的兄弟节点是U。如果U存在并且F和U都是红色的,那么就将FU涂成黑色,G涂成红色。然后把G当做新加入的节点从第1步开始依次查看。

 void insert_case3(node n) {
     if (uncle(n) != NULL && uncle(n)->color == RED) {
         n->parent->color = BLACK;
         uncle(n)->color = BLACK;
         grandparent(n)->color = RED;
         insert_case1(grandparent(n));
     }
     else
         insert_case4(n);
 }

(45两步都假设F是G的左子结点,如果F是G的右子结点,那么下面的操作都反向)
4·否则,要么U不存在,要么U是黑色。如果新节点N是F的左子节点,转5;否则对F做一次左旋转,并且交换新节点N和F的角色,进行第5步处理
(这一步有点诡异,怎么会出现黑色的U呢?因为在加入N之前,G(黑)-F(红)-Leaf(黑) = 2黑,G(黑)-U(黑)-…-Leaf(黑) >=3 黑,不可能啊。后来想明白了,这种情况只可能是由于第3步中交换颜色之后导致的情况。)

void insert_case4(node n) {
     if (n == n->parent->right && n->parent == grandparent(n)->left) {
         rotate_left(n->parent);
         n = n->left;
     } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
         rotate_right(n->parent);
         n = n->right;
     }
     insert_case5(n);
 }

5·这种情况下,N是F的左子结点,且NF都是红色,G是黑色,U是黑色。此时对G做一次右旋转,且交换G和U的颜色,搞定。

 void insert_case5(node n) {
     n->parent->color = BLACK;
     grandparent(n)->color = RED;
     if (n == n->parent->left && n->parent == grandparent(n)->left) {
         rotate_right(grandparent(n));
     } else {
         /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
         rotate_left(grandparent(n));
     }
 }

删除操作
(未完待续…)



Reference
http://blog.csdn.net/longerzone/article/details/7817533
http://zh.wikipedia.org/wiki/红黑树

Algorithm Problem: Find Out the Minimum Number that Great or Equal to a Given Number In BST

Given a BST and a Number k, find out the minimum number p that p >= k.
给定一个BST的根,以及一个数k,返回在BST中的不小于k的最小的节点。

The method is descriped below, in the code.
具体方法在代码中注释得很清楚了.

The recursive and non-recursive code is included.
下面的代码中包含了递归和非递归两种.


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};
TreeNode *findKRecursive(TreeNode *root, int k) {
    if (NULL == root) {
        //there is no node that match the requisite.
        //在这颗空子树中是找不到目标的
        return NULL;
    }
    if (root->val == k) {
        //the node equal to k is find
        //找到了正好等于k的节点,这就是全局要找的节点。
        return root;
    } else if (root->val < k) {
        //root is less than k, so the result node is in it's right sub-tree, if there is.
        //如果根节点的值小于k,那么唯一的满足条件的节点只能去右子树中查找,如果右子树中没有,那整棵树也没有。
        return findKRecursive(root->right, k);
    } else {
        //root is > k, so the target node may be in it's left sub-tree, or is the current node.
        //如果根节点的值>k,那么值更小的满足要求的节点可能出现在左子树中
        TreeNode *knode = findKRecursive(root->left, k);
        if (knode) {
            //if a node is found in left sub-tree, then knode->value must <= cur->value, so return it
            //如果左子树中确实找到了一个节点满足要求,那么他的值一定不大于当前节点的值
            return knode;
        } else {
            //or there is no node which value is >= k, then , root is the best choice for the result.
            //否则左子树中没有>=k的节点,那最小的满足>=k要求的节点就是root了。
            return root;
        }
    }
}

TreeNode *findK(TreeNode *root, int k) {
    TreeNode *lastFound = NULL;//record the last node found which value is >= k
    TreeNode *cur = root;//current node to search for.
    while (cur) {
        if (cur->val == k) {
            //the node equal to k is find
            //找到了正好等于k的节点,这就是全局要找的节点。
            return cur;
        } else if (cur->val > k) {
            //root is > k, so the result may be in it's left sub-tree, or cur is the best result
            //如果根节点的值>k,那么值更小的满足要求的节点可能出现在左子树中,如果左子树没有的话,这就是最好的选择
            lastFound = cur;
            cur = cur->left;
        } else {
            //root is less than k, so the result node is in it's right sub-tree, if there is.
            //如果根节点的值小于k,那么唯一的满足条件的节点只能去右子树中查找,如果右子树中没有,那整棵树也没有。
            cur = cur->right;
        }
    }
    return lastFound;
}